Back to School

I’ve recently been watching the Structure and Interpretation of Computer Programs video lectures. These are a boon to the programming community. I wish my school had just used these videos rather than attempting to teach Lisp themselves.

They go through the material at quite a speed. By the end of the first session you have everything essential to program in Scheme (a dialect of Lisp.) I have experimented with Lisp on previous occasions but this is the first time I have tried out Scheme. My first impressions are that it fixes a little of Lisp’s nasty bits. (I still take issue with abbreviations and Greek names like CONS CAR CDR LAMBDA.)

They also provide a refreshing view of computer science. “It’s not a science and … has little to do with computers.” Instead they describe the subject as a way to think about thinking and describe it in a language. English (or any other natural language) is not up to the job.

The syntax of Lisp is bracket heavy, but that is just the textual representation of language. If you read it aloud, you don’t read the brackets. One example I found enlightening is what they call “Alonzo’s hack.” Alonzo Church introduced lambda calculus which is the foundation of Lisp languages. The hack is to provide structured data purely through procedures. For example to define the structure of a pair of things:

(DEFINE (PAIR A B) (DEFINE (F G) (G A B)) F)
#<unspecified>
(DEFINE P (PAIR 5 6))
#<unspecified>

You can read this as “define pair of A and B as a function F which takes another function G and applies it to A and B.” (In the version of the Scheme interpreter I used, every definition returned “unspecified” rather than something more descriptive.) Then, “define P as a PAIR of 5 and 6. From this P is therefore a function that takes another function G, and applies it to 5 and 6.

To use this pair structure in a program, you’d need to get at its parts. To do that you can define:

(DEFINE (FIRST A B) A)
#<unspecified>
(DEFINE (SECOND A B) B)
#<unspecified>

Read that as “define first of A and B as A” and “define second of A and B as B.” That seems logical. Note that the A and B here are local. I could equally have used X and Y.

Now, because we defined our pair as a function which takes a function G, we can pass these functions as that parameter. The A and B inside the functions “first” and “second” will then be bound from left to right to the values in any pair. That is, 5 and 6 in our example P:

(P FIRST)
5
(P SECOND)
6

Of course, once you have a pair you can build lists, queues, trees, etc. It’s a nice example of power from such a simple syntax. The trick is in the ability of Lisp to bind the data to the parameters within the returned function. This is known as closure.

They characterise programming as like magic. The previous example being a good example of that. And they introduce the idea of “wishful thinking” which I understand as programming by intention.

Abstraction is described as a way to avoid making decisions. A student asks if that idea conflicts with the traditional view that when writing programs you should design everything first. One of the lecturers suggests that the only people who advocate designing everything first are those that haven’t developed large programs and that while computer science is sometimes like magic it’s also sometimes like religion.