SICP Section 2.1 : Thoughts

Alhamdulillah, I wrapped up this section a few days ago. Thirteen 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 concepts of cons, car, and cdr for manipulating pairs, which can, in turn, 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. This is another step in separating data abstraction from implementation.

4. Church Numbers – a new numbering system?

The Church encoding system represents 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 the value zero but was shocked to realize it was a procedure. Alhamdulillaah, I finally understood 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 with only functions and no inherent support for numbers, how do you add or represent numbers? Surprisingly, this is easy – you can model numbers by counting the 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 allows you to do addition and subtraction. While learning about lambda calculus was good, 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, suppose x / x is not equal to one (which can happen in interval arithmetic). In that case, 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…