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

Comments

Have something to write? Comment on this article.

Chris January 17, 2010

I just realized that I’ve implemented my caar, cadr, etc. macros backwards. (caar '(1 2 3)) in my C code would give you 2 rather than some random value. ARGH!

kbob January 17, 2010

Ah. Now it becomes clear why you implemented environments as parallel lists. When I first read the environment implementation, I wondered why you hadn’t used alists.

What that your idea or did you copy SICP?

Peter Michaux January 17, 2010

kbob,

I used parallel lists because that is how SICP implements environments. I wondered why they did it that way for a while too.

Chris January 17, 2010

Using a COMPOUND_PROC object the way you did really does make managing your environments easier. I’ve been trying to figure out how you kept from growing the environment list indefinitely in tail calls for the last half hour or so. That’s a nice trick!

pmarin January 17, 2010

Hi Peter.

I put my implementation In Tcl in Github: http://github.com/pmarin/Muddy-Scheme

the wiki page: http://wiki.tcl.tk/25512

I am still fighting with lambdas.

Now your scheme is compliant with The Little Schemer

Peter Michaux January 17, 2010

pmarin,

Thanks for posting a link to your code. It is great to see different implementations.

I wouldn’t say we are quite up to The Little Schemer yet as the examples in that book at least use cond with else, and and or. It won’t be long. :-)

Nick Fitzgerald February 24, 2010

I let this project sit on the backburners for a while after I got stuck on a nasty bug in my variable look ups.

I’m proud to say that I am finally done with lambda! I feel so good right now.

Stupidest bug ever.

Basically, Ada won’t let you change the value of arguments passed to functions (you can only do that with procedures, the split between functions are mathematical and pure and procedures can mutate is good in theory, but sucks when in practice when actually coding) so I had to make a copy called This_Env. Forgot to update one call to First_Frame, and it cost me hours and hours of debugging. Really too long, I'm embarassed.

Its all water under the bridge now though, I’m ecstatic to have lambda working, it feels great!

Peter Michaux February 25, 2010

Nick,

Way to stick with it!

I’ve been following the commits of various people’s github repositories. It’s great to see that people are continuing on and adding interesting features to their interpreters.

Charles Lloyd March 21, 2010

I notice in your iterative factorial example you have a define within a define. Is this legal? In the R6RS (page 6) they describe definitions as “top level definitions”:

Definitions are not expressions, and cannot appear in all places where an expression can occur. Moreover, a definition has no value.

However they don’t make it clear where they cannot appear other than the top level. I have not been able to find a clear, unambiguous statement on the use of define, especially within the frame of a local scope.

As a side note: I would like to cache some information on the Symbols to speed up lookup of Symbol values. However, if its possible to conditionally modify the local environment via define, then such cached information would be useless. If you take away this problem, you can start to consider several ways to improve Symbol lookup times.

Peter Michaux April 5, 2010

Charles,

You can have defines inside a lambda or define for a lambda as long as they are the first things in the procedure. SICP has many such examples. See R5RS section 7.1.3

<body> → <definition>* <sequence>

I’m sure that R6RS is the same for this issue as Scheme has been this way for a long time.

Have something to write? Comment on this article.