The Elements of Programming

To construct complex programs, a programming language provides elements at different levels:

  • Primitive expressions: the smallest entities the language deals with.
  • Means of combination: ways to combine those primitive elements into compound ones.
  • Means of abstraction: ways to name those combinations so they can be used as units. This is abstraction, the central theme of the book.

Evaluation Order

Combinations follow definite evaluation rules. In Scheme, for example:

(+ 1 2)

Here + is the operator, while 1 and 2 are its operands. Evaluation applies the procedure represented by the former to the latter.

With a slightly more complex combination, we can see that evaluation can proceed in different orders. Suppose we define a procedure, sum-of-squares, and call it:

(define (square x) (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(sum-of-squares (+ 5 1) (* 5 2))

There are two ways this can expand. The first evaluates all the operands before applying the procedure:

(sum-of-squares (+ 5 1) (* 5 2))

(sum-of-squares 6 10)

(+ (square 6) (square 10))

(+ 36 100)

136

The second expands the operator first, continuing until there is nothing left to expand, and only then reduces the result:

(sum-of-squares (+ 5 1) (* 5 2))

(+ (square (+ 5 1))
   (square (* 5 2)))

(+ (* (+ 5 1) (+ 5 1))
   (* (* 5 2) (* 5 2)))

(+ (* 6 6)
   (* 10 10))

(+ 36 100)

136

The former is called applicative order (eager evaluation), and the latter normal order (lazy evaluation). Most popular languages today use applicative order, including C, Java, and Python. Haskell is the best-known representative of normal-order languages. Scheme, the language used in SICP, also uses applicative order.

The advantage of applicative order is easy to see: actual computation is performed as early as possible, so programs generally use less memory and run more efficiently. Its disadvantage is naturally that it cannot do certain things that normal order can. An interesting question is whether we can define our own function to implement if.

For example, suppose we pass in the condition, expression A, and expression B as arguments:

(define (my-if predicate exp-a exp-b) ... )

With applicative-order evaluation, this implementation is impossible. All the arguments would be evaluated before the function runs, including the expression belonging to the branch that should not be taken.

Scheme’s if operator must therefore depart from ordinary evaluation rules. Such elements are called special forms. Clearly, the define used above must also be a special form.

Recursive Procedures and Recursive Processes

I am not sure whether my Chinese translations of these terms are quite right; the book calls them recursive procedure and recursive process. The former is what we usually mean by recursion: a procedure refers to itself in its own definition. A recursive process, by contrast, describes a computation that continues making recursive calls while deferring a growing amount of work.

Take factorial as an example:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

The computation forms an arc. Each successive return contains deferred operations that must wait until the recursive calls have finished. Memory is needed at every level of the call. This is a recursive process.

Alternatively, we can put intermediate results into the function’s arguments so that those operations are no longer deferred:

(define (factorial n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
	product
	(fact-iter (* counter product)
		   (+ counter 1)
		   max-count)))
  (fact-iter 1 1 n))

(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

Here, factorial actually generates an iterative process, no different in its progression from a for loop in another language. The most notable difference from the earlier recursive process is that the expression returned by the recursive call has the function itself as its operator, while the computation is an operand. In an applicative-order language, that computation is naturally performed first. This style of recursion is called tail recursion.

Higher-Order Procedures and Lambda

In Scheme, we can pass not only ordinary variables but also functions as arguments, and return functions as results. These are higher-order procedures. Beyond Lisp, many other languages with functional-programming features support this, including JavaScript, Python, and Swift, while languages such as C and Java do not.

When using higher-order procedures, it becomes clear that giving every procedure a name is unnecessary. This is where lambda comes in. Lambda expressions originate in λ-calculus, a system of rules for variable binding and substitution that provides abstract function definition and application within a formal system. Scheme’s use of lambda is almost identical:

; variable
x

; abstraction
(lambda (x) (+ x 1))

; application
((lambda (x) (+ x 1)) 1)
=> 2

Of course, we can also bind the function to a name:

(define add-1 (lambda (x) (+ x 1)))

(add-1 1)
=> 2

That definition is exactly equivalent to this special use of define, which can be regarded as Scheme syntactic sugar:

(define (add-1 x) (+ x 1))

Likewise, let is syntactic sugar around lambda, making it convenient to define variables with a clear scope. The following expressions are equivalent:

(let ((x 1)
      (y 2))
  (+ x y))

((lambda (x y)
   (+ x y))
 1 2)

Summary

This part of Chapter 1 introduces the basic building blocks of computation and their evaluation rules. Through recursive procedures, these very simple rules can be combined into complex, powerful programs. The key is to build successive layers of abstraction on top of basic functionality. Lambda expressions are a particularly flexible way to construct those abstractions, especially as arguments to, or results of, higher-order procedures.