Scheme from Scratch - Bootstrap v0.13 - Lambda the Ultimate

I know you’ve been waiting with bated breathe. Well you can breath easy. We have finally arrived to Scheme’s famously beloved lambda form and resulting compound procedures with lexically scoped variables and proper tail calls.

I wouldn’t be surprised if this step is the biggest draw for some people implementing their own Scheme. I was certainly happy when they first worked for me. From exactly 10:52pm PDT on August 12, 2009 until at least a week later you wouldn’t have been able to wipe the smile off my face. :-D

Let’s start with a few examples of what you can do after you implement compound procedures. This really is an important step for the functionality of our implementation. Turing complete, so to speak.

In other languages, higher order procedures have been all the rage in recent years. The map procedure is a nice example:

> (define (map proc items)
    (if (null? items)
        '()
        (cons (proc (car items))
              (map proc (cdr items)))))
ok
> (define (double x)
    (* 2 x))
ok
> (map double '(0 1 2 3))
(0 2 4 6)

Lexically scoped variables, and hence encapsulated state, were one of Scheme’s major contributions to programming languages:

> (define count
    ((lambda (total)
       (lambda (increment)
         (set! total (+ total increment))
         total))
     0)) ; initial total
ok
> (count 3)
3
> (count 5)
8

We know everyone’s favorite example of tail recursion is a linear iterative factorial implementation:

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

For those that know how the Y-operator works—not me—now is the time to get your kicks with another factorial procedure:

> (define Y
    (lambda (f)
      ((lambda (x) (f (lambda (y) ((x x) y))))
       (lambda (x) (f (lambda (y) ((x x) y)))))))
ok
> (define factorial
    (Y (lambda (fact) 
         (lambda (n) 
           (if (= n 0)
               1
               (* n (fact (- n 1))))))))
ok
> (factorial 5)
120

Given that we implemented environments so that frames can be chained, the implementation of Scheme’s compound procedures is not very difficult surprisingly. When I implemented this in C, I had SICP open and at times it almost felt like mindless copying.

Once place I choose to deviate from SICP’s implementation was by making compound procedures a disjoint data type COMPOUND_PROC. That is something that cannot be done very nicely in vanilla Scheme but is a breeze in C. SICP uses a list to represent the parameters, body and environment of the procedure.

The procedure? predicate returns #t for either primitive or compound procedures.

A second define form has been allowed to define compound procedures: (define (identity x) x). I think the implementation is interesting and worth examining in detail. What happens is the list for the define form is converted to a list for a lambda form. This is a manipulation of the abstract syntax tree and in the realm of macros. You’ve likely heard that in Lisp “code is data” and here it is in action. That generated list representing a lambda form is then evaluated and assigned to the given procedure name.

One place I had to stop and scrunch my eyebrows was for tail calls. In the end, it was just a matter of moving the procedure application inside the C eval function like the Scheme if form. Because SICP implements Scheme in Scheme, they can have the procedure application outside eval as the implementation language has tail calls.

Both types of procedures are shown by the C write function as #<procedure>.

Bonus points to anyone who makes it possible to type the real Greek λ character into their interpreter as a synonym for lambda.

It surprised me today realizing that Primus hadn’t made it into the source code earlier but it seems quite appropriate they appear today along with lambda.

There is a v0.13 branch on github for this version.

Previous article: Primitive Procedures Part 2
Next article: Begin