SICP Section 3.3 – 3.5 : Found a bug in memq


1. Is memq broken?

memq is an in-built list search function; it finds the first occurrence of a key in a list and returns a new list starting from that key.


(memq 3 (list 1 2 3 4))
//; '(3 4)

(memq 5 (list 1 2 3 4))
//; #f

Now that you know what memq does, lets look at some weird behaviour

(define x (list 1 2))
(define a (list 3 4))

//; append x to the list
(set! a (append a x))
(memq x a)
//; #f -> x is not in a

Building on that foundation leads to the following conundrum

(define x '(1 2 3))

//; Create a cycle: last element of x is itself
(set-cdr! x x)

//; is x in x?
(memq x x)

//; never-ending loop

memq tests whether the key exists in the list and if it does, then it returns the list starting from the first occurrence of the key. But what is the first occurrence in a cyclic list? Could this be the bug?

2. Algorithms, algorithms

  • Horner’s algorithm

This is useful for calculating polynomial values at discrete points; for example, given a polynomial function, f(x) = 7x³ + 4x² + 4; what is f(3)? A potential application (and possible interview question too) is to convert string values into numbers – 1234 is the value of x³ + 2x² + 3x + 4 when x is 10.


//assuming polynomial is represented from lowest power to highest

//i.e. 1234 -> [4, 3, 2, 1]

function horner (poly, base) {
    if(base === 0) {
        return 0;
    }

    var val = 0;
    var polyLen = poly.length;
    for(var i = 0; i < polyLen; i++ ) {
        val += poly[i] * Math.pow(base, i);
    }
    return val;
}

horner([4,3,2,1], 10);
//1234

  • Fast exponentiation

Because going twice as fast is more fun than going fast.


function exponent (base, power) {
    var val = 1;
    while(power > 0) {
        val = val * base;
        power = power - 1;
    }
    return val;
}

Now, lets look at fast exponentiation.

function fastExponent(base, power) {
    if(power === 1) {
        return base;
    }

    //handle odd powers
    if((power % 2) === 1) {
       return base * fastExponent(base, (power - 1));
    }

    var part = fastExponent(base, (power / 2));
    return part * part; //square of part also works
}

fastExponent(10,3)
//1000

Fast exponentiation grows logarithmically Ο(log N) while the normal one is Ο(N). This same concept can be reapplied to similar scenarios.

3. Streams

Functional programming offers many advantages but one potential downside is performance and needless calculation. For example, while imperative programming offers quick exit constructs (e.g. break, continue); functional programming constructs like filter, map and reduce have no such corollary – the entire list has to be processed even if only the first few items are needed.

Streams offer an elegant solution to this issue by performing only just-in-time computations. Data is lazily evaluated and this makes it possible to easily (and beautifully) represent infinite lists. Inshaaha Allaah I should explain this concept in an upcoming post. It’s very beautiful and elegant and powerful.

Related Posts on my SICP adventures

  1. SICP Review: Sections 3.1 & 3.2
  2. SICP Section 2.5

5 things I have gained from SICP: Section 1.2


Alhamdulillaah I finally completed section 1.2 of the SICP classic. I was amazed I took almost 150 days to complete 61 pages. I definitely need to sit up! Reading the text was not challenging, the bottleneck was ‘forcing’ getting myself to finish the exercises.

I was going to start on section 1.3 but I felt it would be better to reflect on the knowledge gained first.

1. A deeper understanding of procedures and their processes

Not all procedures are created equal – seemingly recursive procedure can be iterative in execution. Moreover, there is nearly always a way to make a recursive procedure execute in an iterative manner. This can lead to speed gains and also help you handle HUGE data.

Programming is deeper than I thought…

2. Mathematics

My Mathematical forays are usually related to Computer Science or Machine learning however I got to dabble into new fields. First was the Ackermann function; a fascinating recursive function which grows with mind-boggling speed – you have to think hard to grasp this. Next came primality testing and probabilistic approaches to prime number verification.

The Fermat test is good enough however it is fooled by the Carmichael numbers. To be sure, use the Miller-Rabin test.

I do not know how much of these will be useful in real-life but yeah… it is good to know.

3. Algorithms – exponentiation

The rapid exponentiation algorithm was an eye-opener – do stuff twice as fast :). Once you implement the ‘speed-up’ and ‘slow-down’ functions and handle all cases properly, you can take down exponentiation from a O(n) operation to a O(log n) operation. Combining this with a ‘tweaked’ recursive-but-iterative-in-execution procedure leads to ‘tales’ of joy…

It was also interesting to see how minor changes to code could wipe out performance gains made from clever algorithms. Exercise 1.26  showed how easy it was to lose the O(log n) gains from exponentiation by doing irrelevant work. A subtle ‘refactoring’ might have huge implications…

5. Perseverance

I initially find most exercises daunting and struggle to understand the task. I force myself to think about the problem for at most 15 minutes; if I still do not get it, then I allow myself to look at available solutions.

Alhamdulillaah I usually figure out the solution during the time window and then look up existing solutions to see other problem-solving approaches. I have also looked up solutions when I got stuck too – I was seeking ‘inspiration‘ :). It’s great to know we can solve most problems if we only persevere insha Allaah.

And that’s about it! Section 1.3 has about 18 exercises; since I typically solve an exercise in about 2 – 3 days (I have a 25 minute daily study schedule), I hope to be done with this section in about 4 – 6 weeks insha Allaah. Watch out for a new update then insha Allaah.

Here are my solutions on Github.

Here are a couple of my more academic-themed musings

1. Research is hard!

2. Wrangling with HUGE data

3. MOOC Review: Machine Learning

Reading the SICP BOOK


I have been longing to read the Structure and Interpretation of Computer Programs (SICP) for a long time – a lot of great programmers tout it as one of the ‘books‘ to read. In May I completed JS Allonge (a somewhat challenging read but got to understand the Y-combinator Alhamdulillaah) and I felt it was a good time to learn more about the SICP book; afterall how many 30-year old computing books still remain relevant?

The general consensus is that SICP is a classic every programmer should read and that it’ll make you a better programmer by changing the way you think. Reading such glowing appraisals awakened my interest (who doesn’t want to become a rockstar programmer?) and I decided to do it. However, there is a catch – reading the book is not enough, you have to do all the exercises! So I resolved to do all the exercises and read for at least 25 minutes daily (1 pomodoro).

The exercises appear deceptively simple until you try to solve them! Then you realize they are just as deceptively difficult!! For example, an exercise asks you to find the two largest numbers out of  a set of three – I bet a lot of people can write this in their sleep. However since the book expects programs to be written in Scheme; and Scheme variables haven’t been discussed yet, you have to make do without variables – now try that!

The good thing though is that the exercises are designed to fit the current context and buttress learning. Mathematical concepts and computer science principles are expertly interwoven into surprisingly simple explanations and real-life scenarios. Scheme is a nice language too – provided you can get past the scourge of parentheses.

Solving the exercises has been another eye-opener; I typically have to force myself to persevere. Alhamdulillaah I have been able to solve questions I typically would think were beyond me (I am probably too lazy). If I can’t solve a question in 25 minutes, I look for a solution online (see resources below); at times, I just want to compare my approach to others.

Here are some programming-perception changing concepts I picked up in the past few months:

1. Scope

A scope is just a group of expressions in which a binding has a name; it really does not have to be a function or class.

2. Free and bound variables

Free variables are those not defined in a procedure while bound variables are defined in it. Imagine the procedure below

function variable(){
   var a =1;
   var b = 2;
   return a + b;
}

and are bound variables however isn’t; it’s a free variable. Now try to think of what will happen if the ‘+’ operator can be bound to another value (quite possible in some languages). The original procedure works properly because the free variables are what they are expected to be; if they are changed, then you end in no mans land. Powerful right?

3. Recursive/Iterative processes and procedures:

Most recursive procedures can be re-written to spawn iterative processes. While this involves a couple of tricks, the performance and memory gains might require such fixes. Also not every recursive procedure spawns recursive processes, some actually are iterative in execution (see tail recursion).

Resources

If you are interested in reading the SICP books; here are a couple of helpful resources

1. My SICP exercise solutions

2. Unofficial ebook version

3. Solutions to SICP Exercises

4. Bill the Lizard; he undertook the SICP journey before me

5. Eli Bendersky, he also undertook the SICP journey some time ago

6. List of solutions

Quotes from the SICP book

Programming is like chess; you might know the rules but not know the strategy, tactics and methods

The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity…

To become experts, we must learn to visualize the processes generated by various types of procedures. Only after we have developed such a skill can we learn to reliably construct programs that exhibit the desired behavior.

Conclusion

Finally, believe! You can do it,  just persevere when it gets tough…