Scheme from Scratch - Bootstrap v0.13 - Lambda the Ultimate
Published January 17, 2010 inScheme
I know you’ve been waiting with bated breathe. Well you can breath easy. We havefinally arrived to Scheme’s famously belovedlambda 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. Themap 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 totalok> (count 3)3> (count 5)8We know everyone’s favorite example of tail recursion is a linear iterativefactorial 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)24For those that know how the Y-operator works—not me—now is the time to get your kicks with anotherfactorial 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)120Given 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 typeCOMPOUND_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.
Theprocedure? predicate returns#t for either primitive or compound procedures.
A seconddefine 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 Ceval function like the Schemeif form. Because SICP implements Scheme in Scheme, they can have the procedure application outsideeval as the implementation language has tail calls.
Both types of procedures are shown by the Cwrite function as#<procedure>.
Bonus points to anyone who makes it possible to type the real Greek λ character into their interpreter as a synonym forlambda.
It surprised me today realizing thatPrimus hadn’t made it into the source code earlier but it seems quite appropriate they appear today along withlambda.
There is av0.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.
I just realized that I’ve implemented mycaar,cadr, etc. macros backwards.(caar '(1 2 3)) in my C code would give you2 rather than some random value. ARGH!
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?
kbob,
I used parallel lists because that is how SICP implements environments. I wondered why they did it that way for a while too.
Using aCOMPOUND_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!
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 withThe Little Schemer
pmarin,
Thanks for posting a link to your code. It is great to see different implementations.
I wouldn’t say we are quite up toThe Little Schemer yet as the examples in that book at least usecond withelse,and andor. It won’t be long. :-)
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.
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 calledThis_Env. Forgot to update one call toFirst_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!
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.
I notice in your iterative factorial example you have adefine within adefine. 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 viadefine, 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.
Charles,
You can havedefines inside alambda ordefine for alambda as long as they are the first things in theprocedure. 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 thisway for a long time.
Have something to write?Comment on this article.