A Return To The Primitives.

When quarantine in the SF Bay Area first began in the spring, I had decided to use my free time to read through the classic Computer Science book, The Structure and Interpretation of Computer Programs (S.I.C.P) by Harold Abelson and Gerald Sussman. I also watched a handful of recorded video lectures by the authors freely available from M.I.T. The videos are ancient by internet standards (1985), but well worth the time to those interested by the history and evolution of Computer Science.

The language they use is Scheme, a dialect of Lisp. Scheme is a very interesting language. There’s almost no learning curve to the language, as there are only a handful of operations needed before powerful abstractions can be created. The hardest part of learning scheme (IMO) is context-switching between infix and prefix operators (writing (+ 4 5) instead of (4 + 5)). In fact, after using scheme for a bit, it becomes obvious that the operators are just themselves functions, and the operands are the parameters. In this sense, it’s more natural to write operations using the prefix method.

Scheme is a closure, meaning all functions are treated as “first class” and can be used as data for other functions. Essentially, Scheme is used to show that hierarchical abstractions can be created only using the primitive Lisp data type, known as a list, along with a handful of primitive operations.

The book as well as the video lectures fundamentally changed how I view the craft of programming. This blog post is only a preview of some of the big ideas from the material, and I highly suggest picking up a copy of the book for more exhaustive information.

The Fundamentals Of A Programming Language

Through the examples in S.I.C.P, it’s shown that all programming languages share the following three properties:

1. Primitive Types: What are the fundamental data types we can work with? Programming languages have Integers, boolean characters, floating points, etc.

2. Means of Combination: How do we operate on the primitive types? We need a way to combine primitive types. Programming languages have support for the arithmetic operations (addition, multiplication, modulus, etc.). Combinations can become infinitely complex subexpressions

    i.e. (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6)) These combinations of subexpressions follow specific rules for evaluation., where we start with the innermost expression and work outward. Later in the book it is shown that these expressions are evaluated in order of how they appear in a tree-like structure.

3. Means of abstractions: How do we abstract the operations we want into larger operations? This is where the idea of the function come into play.

All Programs Are Input To Another Program

One of the main points Abelson and Sussman attempt to convey early in the course is that all programs we write are essentially data as input to other programs at a lower level of abstraction. In essence, all programming can be thought of as creating increasing levels of abstraction. This is what we do whenever we need to create a domain-specific language.

In chapter 2 of S.I.C.P, we see some examples of domain-specific languages. a pictorial language, and a symbolic differentiator being developed. As a math nerd, the symbolic differentiation was the most intriguing. I wouldn’t be able to do justice to the insights conveyed by the example, so I’ll skip the details, but essentially the example shows how we can solve algebraic problems by representing the equations as lists.

The Evaluation Of Programs

In chapter 4 of S.I.C.P, the authors outline how programs are interpreted by other programs. A meta-circular evaluator is created in Scheme to interpret Scheme. Questions such as how does the interpreter store values as variables? How is the precedence of operations determined? How are abstractions handled? are all answered through the example.

Essentially, we end up with a model with two parts (which shouldn’t be a surprise to anyone who’s studied the intricacies of interpretation).

1. Evaluator: Evaluate the expression being passed into the interpreter. Evaluate any subexpressions and apply the value of the operator of the subexpression to the values of the operand subexpressions.

2. Applicator: Takes as input a procedure and a list of arguments to apply to the procedure. The applicator determines if we are applying primitive types, or applying another procedure. In the second case, the procedure is passed to the Evaluator. 

This elegant dance between the two operations continues until the program or procedure is completely evaluated and applied. Img1 is taken directly from S.I.C.P, and illistrates the simplicity of the interaction.

Closing Thoughts

Do I think Scheme will or should be used for writing production software? No, of course not. However, the ideas in Scheme/Lisp are so influential to Computer Science, that industry-recognized languages such as Clojure were created in its spirit.

I think whether you primarily use a strictly typed language such as Java, or a dynamically typed language such as Python, you can realize the power of building abstractions. Knowing that all programs will eventually be interpreted by another language will keep any programmer humble and in reverence for the geniuses who came before them.

Img1. The elegant dance between Eval and Apply