SICP

SICP Section 3.3 – 3.5 : Found a bug in memq

Posted on by AbdulFattaah Popoola

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
Advertisements

SICP Sections 2.3 & 2.4: Thoughts and Ideas

Posted on by AbdulFattaah Popoola

1. Top-Down Design

Most of the problems in the SICP book are solved in a top-down way with lower level details deferred until needed. The focus on high level details makes for expressive flexible code since implementation is based on well-defined interfaces and not implementations. Consequently, swapping and improving interfaces is a cinch – the dependency on high level interfaces shields consumers from tight coupling to details.

Picture a calculus system for integer operations (e.g. differentiation); as expected, these higher order functions need support for addition/subtraction/division operators. A top-down design will implicitly assume the add/subtract operators will work appropriately and focus on the higher level operators first. These low-level details can even be mocked and the system unit tested to prove logic accuracy.

The benefit of such a delayed implementation comes when the system needs to be extended to support complex numbers – the higher level operations are still the same, only the low level add/subtract operators need to be changed. Once done, the entire system should work as before.

Design is subjective and this is one approach; there might be better ways for other scenarios but again this can be tried and leveraged.

2. Generics: Data-directed vs Message-Passing Styles

Generics are useful for maintaining and extending existing systems.

The data-directed style maintains a huge table of known procedures and looks up desired operations based on keys. Extending such systems involves adding the new function signatures to the table; this allows the entire system to start using the newly added functions (sounds like the adapter pattern).

The downsides include the extra overhead of a procedures’ table, the need for consumers to know about available operations and the enforcement of contracts in the system. However, benefits such as flexibility, encapsulation and ease of accretion of new features can’t be ignored.

Message passing involves sending messages to objects to trigger the right operations. Sounds familiar? Yes, it does sound like OOP and is one of its major tenets. An object keeps a list of possible operations and invokes the right method based on the message it receives (think of invoking an instance method in an OOP language as sending a ‘message’ to the object e.g. a.b() ).

Languages like Python and JavaScript allow for a clearer example of the message passing metaphor since they allow creating hashtables of functions. With such a hashtable, you can invoke a function by sending a ‘message’ to such functions e.g. a[“b”]().

The question thus comes to mind, how do programming languages handle their primitive operations at a lower level? Do they do message passing? Keep tables?

3. Context

The importance of context and how they affect semantics in all languages (both human and programming).

Using the example from the book; three is equal to one plus two however ‘three’ is not equal to “one plus two”. The context determines what is meant and humans have long used this to create various literary forms such as puns, sarcasm etc.

The same applies to programming, context does determine if your program will run perfectly or if it will have subtle but difficult to find errors. One obvious example is the JavaScript that = this pattern.

4. Huffman Encoding

Some computer science and maths eh, the Huffman encoding scheme allows you to use much less space provided the conditions are met.

5. Understanding the problem deeply before writing any code

Coding should be simple. Unfortunately, a shallow understanding the problem being solved makes it a difficult task.

Spending a good chunk of time to really understand the programming task at hand has great benefits, it leads to well-thought out designs, simple models (simple is difficult!) and less bugs. It also reduces the chances of providing the wrong solution. It makes for a more fulfilling experience too – what beats the thrill of having zero compile errors on the first attempt?

If you liked this post then do check out a couple more exciting discoveries from my SICP journey:

1. SICP Section 2.2: New ideas and thoughts about programming
2. SICP Section 2.1 : Thoughts
3. SICP Section 1.3 : Thoughts and Concepts

SICP Section 2.2: New ideas and thoughts about programming

Posted on by AbdulFattaah Popoola

Here are 5 points to think about, hopefully they’ll trigger an ‘aha’ moment.

1. Leveraging the ‘Closure’ concept in programming

I am not talking about the ‘closure’ concept from programming (the one that involves free variables). This refers to the ‘closure‘ concept from mathematics and the power it brings to programming languages.

Mathematically, a set is closed under an operation if carrying out that operation on elements of the set will always give a result that is also in the set. For example, addition of positive integers is closed under the set of positive integers (subtraction is not: 1 – 3 = -2; which is not positive). Thus you can infinitely add positive numbers without worrying about ending up with non-positive numbers.

Lets take this to programming: closed operations allow chaining because the result will be always be a valid value for further operations. Does this strike a bell? Think fluent programming, think jQuery chains. This simple concept allows very complex actions by leveraging simple data and procedures.

2. Simple it might seem, difficult it might be

I initially thought Ex 2.18 would be dead easy; it was simple: reverse a scheme list. I realized my folly after spending the better part of an hour battling the task. Unlike pointer-based lists in C-like languages, the Scheme list is a chain of pairs, each pair points to another pair and so on. This negated walking down the list and reversing pointer directions.

Recursion was tricky since getting the second half of a list pair (i.e. cdr list) brought the entire sublist instead of just the element! The reversal task involved the following restrictions:

  • No variables allowed
  • Only the top element of a sublist can be retrieved while walking down the list
  • The procedure should recursively construct a new list simultaneously
  • Retrieval of elements at arbitrary positions is difficult; although possible, the absence of variables makes this useless.

My first approach worked but created a wrong data structure; Alhamdulillaah I eventually got the right solution. An elegant solution I found online solved the reversal problem simply – reversing a list is equivalent to appending the first element of the list to the reversal of the remaining elements.

3. Languages influence thinking and problem modelling

Languages play a big role in the way we think and write code, most of us see programming tasks through an ‘imperative’ pair of glasses. Alhamdulillah the SICP book is giving me a new pair of glasses. Don’t we all need a new pair of glasses every now and then?

Imagine a simple task: calculate the sum of the squares of the odd numbers in an array. The snippets below show both the imperative and functional styles of solving the problem.

function isOdd(num) {
    return (num %2 ) === 1;
}

function square(num) {
    return num * num;
}

//imperative style
function sumOddSq(arr) {
  var sumOddSq = 0;
  for(var i=0, l=arr.length; i < l; i++) {
      if(isOdd(arr[i])) {
          sumOddSq += square(arr[i]);
      }
  }
  return sumOddSq;
}

//functional style
function sumOddSq2(arr) {
  return arr.filter(isOdd)
            .map(square)
            .reduce(function (val, acc) {
                return val + acc;
            }, 0);
}

sumOddSq([1,2,3]);   //10
sumOddSq2([1,2,3]);  //10

The imperative approach involves walking through the array, checking for odd numbers, squaring those odd numbers and updating the sum as you go along. Using a functional programming approach, the task involves filtering the sequence for odd numbers, mapping the filtered numbers to their squares and then reducing these squares to a sum.

Functional programming relies heavily on the map, reduce and filter concepts and most problems can be solved based on these building blocks. For tasks involving non-list-like structures, converters can be used to create sequences and also generate structures from list results.

Did you notice? sumOddSq2 chains array operations; the map, reduce and filter operations can be said to be ‘closed’ over the set of arrays. Thus the result of any of these operations is always an array and can be reused immediately.

4. Software engineering is still engineering

Even though software engineers manipulate bits and not ‘real’ hardware; general engineering concepts still apply. There are a couple of interesting similarities; for example in electronics engineering, the diode can be viewed as an if statement while filters can be viewed as ‘filter‘ logic. The electronics engineer uses a filter, the software engineer uses a filter function. Both combine them to build even more complex abstractions.

Another example is the computer system and the various dependent layers; a simplified complexity order is shown below:

Transistors -> Logic gates  -> Circuits -> Processors -> Computers -> Distributed Systems

The same applies to software engineering, an application can be seen as:

Values -> Methods -> Classes -> Models -> Subsystems -> Modules -> Applications

We all start from something simple and progressively add complexity, each layer being shielded from the layer below it. A computer engineer can swap processors without breaking a computer; so should a software engineer be able to swap out layers in his code without bringing down the application.

5. Recursion

The 8 queens problem is one that a lot of people are familiar with and as you guessed, there was an exercise on that. The solution was quite simple – recursively build the board starting out with one queen. As the board grows, filter out positions that have queens attacking each other, finally return the list of all positions that have safe queens.

The functional-programming styled solution involved enumerating all positions, creating a safe? function to determine a valid board, passing this function to the filter and then outputting the results. It is great to see how functions can be composed and how the basic functional programming support for map, reduce and filter enable even higher levels of complexity.

I must admit I struggled a lot with this problem as it was difficult to understand and debug – walking up the call stack did expose some of its intricacies but it’s amazing how simple and how yet powerful the results of combining these simple concepts.

Conclusion

And that’s about it. Next is section 2.3 with about 20 questions; I skipped about 2 or 3 questions in 2.2 since I didn’t really feel they were worth solving. I hope I can get 2.3 done by mid January insha Allaah and create another post then!

Related Posts

Here are a couple more of my SICP-themed posts

1. SICP Section 2.1 : Thoughts

2. 5 things I have gained from SICP: Section 1.2

3. SICP Section 1.3 : Thoughts and Concepts

SICP Section 2.1 : Thoughts

Posted on by AbdulFattaah Popoola

Alhamdulillaah I wrapped up this section a few days ago – 13 of the solutions are here (if you are curious enough); the other three need proofs and I wasn’t in the ‘mood’ for too much interval arithmetic. So what did I learn?

1. More Scheme

This chapter introduced the concept of cons, car and cdr  for manipulating pairs which in turn can be used to create just about any data structure.

  • cons – means construct, allows you to build a pair from two arguments
  • car – contents of address part of register, returns the first element of a cons pair
  • cdr – contents of decrement part of register, returns the second element of a cons pair
  • cadr – contents of address part of contents of decrement part of register; this is equal to (car (cdr value)); you can do things like caadr too – every extra a represents a car while a d represents cdr. Thus (caadr x) is equal to (car (car (cdr x)))

2. Abstraction

Abstractions provide elegant ways of solving problems. They allow the programmer to think at a ‘higher’ level without worrying too much about implementation details. This leads to a cleaner design and more flexible code.

Lets take the ‘xor’ logic operator as an example; assuming you need to add negative integer support to a positive-integer only multiplication system, there are two ways to do this:

  • Evaluate every possible combination, have four if/else blocks and then assign the right sign afterwards
  • Leverage the xor operation.

Here is the xor table:

x y x xor y
+ + +
+ – –
– + –
– – +

This matches the four scenarios for multiplying two numbers. Thus, you can create a wrapper around the existing system for multiplication and then use the xor operator to find the sign of the output. Worth a thought isn’t it?

3. Architecture

There was a brief mention of the onion layer style of architecture which allows you to build software in layers – its main advantage is the ability to swap out any layer without ‘breaking’ the system.

Each level relies on the layer below it through a well-defined interface; you can swap layers as you think fit, you just have to follow the interface specifications. Another step in separating between data abstraction and implementation.

4. Church Numbers – a new numbering system?

The Church encoding system is a way of representing numbers and their operators in lambda calculus. The book introduces the Church zero and add-1 procedures first, I thought the zero procedure would evaluate to the value zero but was shocked to realize it was a procedure. Alhamdulillaah I finally got to understand it after reading Bill’s excellent post.

The main thing to know is this: It is possible to represent numbers even without using numbers!

Assuming a theoretical language that has only functions and no inherent support for numbers whatsoever; how do you add or represent numbers? Surprisingly this is easy to do – you could model numbers by counting the number of times you apply a function. This is what the Church numbers do – they apply input functions for a number of times that corresponds to the expected integer value.

The zero procedure takes in a procedure (which itself accepts another procedure) and calls it ‘zero’ times (never called); similarly, the one procedure evaluates its input once (that’s one right?). Generalizing these allow you to do addition and subtraction. While it was good to learn about lambda calculus however I wonder how real number arithmetic would be represented…

5. The woes of Interval Arithmetic

There were a couple of exercises on interval arithmetic; what struck me about this was the way small changes in calculation could lead to huge differences in results. Two algebraically equivalent formulas could lead to varying results due to overlooked ‘assumptions’.

For example, if for some reason x / x is not equal to one (can happen in interval arithmetic); then every operation that includes this division (implicitly or explicitly) can deviate from accurate results. The more the ‘precision-losing’ operations carried out, the more significant the deviation.

And that’s about it again. Section 2.2 has about 36 exercises and I hope to complete it by December insha Allaah. And yes, insha Allaah I’ll write about my thoughts again…

SICP Section 1.3 : Thoughts and Concepts

Posted on by AbdulFattaah Popoola

This section exposed me to the full power and beauty of functional programming. The expressiveness of using functions as values is awesome. For example, a sum of cubes function can use a sum function which itself relies on a reduce function. Think of higher order differentiation in mathematics and you do get the idea.

An interesting concept involves using lambda function as operators, if the value of an expression is a function, then it can be used as an operator! This pattern allows using functions the same way numbers and strings are used. A derived usage can be found in JavaScript, which allows invoking function expressions using the function invocation operator ().

A lot of programmers are familiar with callbacks (which pass functions into functions). However callbacks might mask the full untapped potential of functional programming. A callback can be passed a function as a value – it doesn’t necessarily have to be a number / string all the time. The other issue with callbacks is that they do not return values and thus limit function composition.

There are no limits to using functions as values (provided there is language support). Alhamdulillaah I got my eye-opening experience after solving exercise 1.45. The main points are

  • The repeated procedure accepts a procedure and returns a new procedure.
  • Repeated’s return value (a procedure) also accepts a procedure as input (a lambda) and returns another new procedure.
  • The final return value is then passed into the fixed-point procedure which does return a non-procedure value (although it can also be written to return a procedure).

The subtle trick was to realize that functions could be substituted with values and used in just about every way a value could be (provided you handle it right).

The amazing expressive power and flexibility comes at a cost though – first-class procedures are difficult to support in languages and this explains why few languages provide this. The main challenge is finding a way to safely store and retrieve the procedure’s free variables when it is not currently executing.

A free variable is defined on c2.com as any value that meets the following conditions:

  • It is not defined in the body of a function
  • It is not passed in as an input parameter
  • It is not available in scope at the point of usage

Alhamdulillaah I completed the chapter in two weeks (I initially though it would take four). Chapter 2 is next with about 92 exercises, about 14 weeks insha Allaah? We’ll see!

5 things I have gained from SICP: Section 1.2

Posted on by AbdulFattaah Popoola

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

Posted on by AbdulFattaah Popoola

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;
}

a and b 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…