Structure and Interpretation of Computer Programs by Harold Abelson

Structure and Interpretation of Computer Programs by Abelson and Sussman is a classic computer science book available online for free. The book took me over a year to finish as I read it sporadically. I did many of the exercises in the first three chapters, but sadly gave up as I approached chapter four because if I continued at the current pace it would have taken me over five years to finish the book. I would say I plan on completing the exercises some day, but in reality I doubt I’ll find the time. However, certainly try to tackle the problems as it’s the best way to grok the material.

The fist chapter is about building abstractions with procedures. The material is suitable for beginners as it explains the reasons behind using scheme and the basics of the all powerful repl. I prefer Common Lisp over scheme, but this book mostly focuses on fundamental concepts pertaining to all programming languages.

After the basics, the book explains normal order evaluation vs applicative order evaluation. Normal order evaluation applies the function before evaluating the arguments, i.e. substitutes the unevaluated arguments into the function body and then evaluates. Applicative order evaluation, which Scheme and Common Lisp use, evaluates all the arguments first and then applies the function. The chapter gives examples that illustrate the differences.

After covering abstractions, the chapter goes into recursion and iteration. The recommended style of programming between Common Lisp and Scheme differ here, as Schemers tend to favor recursion while Common Lispers tend to favor iteration. Schemers seem to love recursion so much that the Scheme standard requires tail call optimization. However, most mainstream CL implementations do offer that optimization as well.

Finally chapter one covers first class functions, an extraordinarily useful feature that programmers use routinely when working in modern languages that support them. Put simply, first class functions allow operators to have functions for their operands. That means you can pass functions in as arguments to other functions! Very useful in many situations.

Chapter one serves as a quick review for experienced programmers and gives a taste of whats yet to come. After reading the chapter, it should be clear that programming in a high level language such as lisp offers tremendous advantages over other languages.

The second chapter of SICP continues explaining how to program abstractions, but this time with data instead of procedures. It illustrates this with a simple example of rational numbers. Procedures are given to extract the numerator and denominator of the rational number, as well as a constructor procedure and basic math operators.

The actual numerator and denominator (the data) are kept in a cons cell, or a pair. The cons cell is a basic data type of lisp languages. It’s both simple and powerful, as you can use cons cells to build list and tree abstractions. In fact, the rest of the chapter uses cons cells for the foundation of all the abstractions. Note that Common Lisp, the lisp that I use and am most familiar with, has other data types including hash tables and vectors.

The chapter then goes on to show the box and pointer representation of cons cells and provides some sequence procedures. It explains trees and also works through mapping procedures. From my limited experience, it seems Scheme favors mapping over any of the for-while-loop mechanisms found in Java or C like languages. Common Lisp seems to be neutral in this regard. It has a powerful looping macro along with its mapping functions.

These ideas take only a short while to become acquainted with, but are powerful programming tools. The exercises and examples in the chapter illustrate this nicely. They are applicable to large amounts of problems that mainstream languages have difficulty in expressing today.

Next the chapter touches on symbolic data. Using the quote operator, one can prevent the quoted form from being evaluated. If you ever heard the saying “code is data, data is code”, this is what the section talks about.

The chapter ends with generic operators, which allow programmers to abstract their underlying representation even more.

Overall this chapter was a great refresher for me. It’s wealth of examples and exercises really drive home the points of data abstraction, and serves as a great learning tool for the foundation of computer science.

The first two chapters cover so many useful programming techniques that people often overlook one missing element that pervades in almost all other programming books: variable assignment!

Having local state gives rise to many useful programming structures, such as queues, tables, and the ability to model the real world using objects. One of the drawbacks of having variable assignment is that programs no longer are purely functional. A functional style eliminates the possibility of calling the same function with the same arguments and receiving a different result. This usually leads to less error prone and less spaghetti like programs. But having variable assignment has numerous advantages and a multi-paradigm language like Lisp can cater to each programmers particular taste.

The chapter covers how to model real world objects. This is analogous to classes in Common Lisp and other programming languages. The Scheme way of implementing classes outlined in this chapter shows how easily one can create their own object oriented system in Lisp, but Common Lispers always turn to their powerful, built-in CLOS instead of rolling their own.

Let’s take a look at an example comparing the two approaches by modeling a simple bank account program. First the Scheme way:

<pre>(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds”))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m ‘withdraw) withdraw)
((eq? m ‘deposit) deposit)
(else (error “Unknown request – MAKE-ACCOUNT”
m))))
dispatch)</pre>

Accounts have one local variable, the balance, and two methods: withdraw and deposit. It is used like this:

<pre>(define acc (make-account 100))
((acc ‘withdraw) 50) ;; => 50</pre>

Now let’s look at the Common Lisp way using CLOS:

<pre>(defclass account ()
((balance :initarg :balance :accessor account-balance)))

(defmethod withdraw ((account account) amount)
(if (>= (account-balance account) amount)
(decf (account-balance account) amount)
“Insufficient Funds”))

(defmethod deposit ((account account) amount)
(incf (account-balance account) amount))</pre>

In CLOS, classes only have local variables (called slots). CLOS uses Generic Functions to define actions upon objects. Classes can inherit slots from other classes, and generic functions can operate on any Lisp object, not just user defined classes. These simple concepts give the programmer tremendous flexibility in regards to modeling their objects. Generic functions also have before, after and around methods. For example, the withdraw function could be written as this:

<pre>(defmethod withdraw ((account account) amount)
(decf (account-balance account) amount))

(defmethod withdraw :around ((account account) amount)
(if (>= (account-balance account) amount)
(call-next-method)
“Insufficient Funds”))</pre>

I urge the interested reader to do more research on CLOS, as in my opinion no mainstream object oriented system matches its power.

As a fun exercise, you can of course translate Scheme’s “class” definitions into Common Lisp:

<pre>(defun make-account (balance)
(labels ((withdraw (amount)
(if (>= balance amount)
(setf balance (- balance amount))
“Insufficient funds”))
(deposit (amount)
(setf balance (+ balance amount)))
(dispatch (m)
(cond ((eq m ‘withdraw) #’withdraw)
((eq m ‘deposit) #’deposit)
(t (error “Unknown request – MAKE-ACCOUNT”)))))
#’dispatch))

(setf acc (make-account 100))
(funcall (funcall acc ‘withdraw) 20) ; => 80</pre>

Clearly Common Lisp’s multiple namespaces hurts the elegance of this approach: the two calls to funcall seem too verbose. But since Common Lisp is a Lisp, let’s reduce this verbosity by modifying the make-account function slightly and defining a macro:

<pre>(defun make-account (balance)
(labels ((withdraw (amount)
(if (>= balance amount)
(setf balance (- balance amount))
“Insufficient funds”))
(deposit (amount)
(setf balance (+ balance amount)))
;; Changes start here
(dispatch (m &rest args)
(case m
(withdraw (apply #’withdraw args))
(deposit (apply #’deposit args))
(t (error “Unknown request – MAKE-ACCOUNT”)))))
#’dispatch))

(defmacro define-account (name balance)
`(setf (symbol-function ‘,name) (make-account ,balance)))

(define-account acc2 200)
(acc2 ‘withdraw 30) ; => 170</pre>

This version has one less set of parenthesis then the original Scheme version!

The last two chapters deal with less often used programming practices: building interpreters and compilers. These areas really show off the power of Lisp languages. One can easily build domain specific languages to offer elegant solutions to complex problems. If one studies and understands these last two chapters, then they truly “get” Lisp.