Binding with lambda

20 March 2011 Berlin

As part of my Lisp learnings, I’ve been enjoying MIT’s freely-provided SICP videos. In the Lecture on Assignment, State, and Side-effects, a student asks about the differences between let, set! and define. Prof. Sussman explains that these forms are really just syntactic sugar for lambdas binding variables.

I thought this statement was interesting, so I used DrRacket to experiment.

First, I translated the let form to a lambda, by calling (lambda (x y) (+ x y)) with 1 and 2, binding them in the created context:

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

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

These have pretty much the same meaning, but the order of information in the let version makes for easier reading.

Then I tried translating let*, which allows the expression in each variable binding to have access to those bound before it. I thought nested lambdas could achieve this:

(let* ((x 1)
       (y (+ x 1))) 
  (+ y 1)) ; 3

((lambda (x) 
   ((lambda (y) (+ y 1))
    (+ x 1)))
 1) ; 3

Then I considered how define binds variables in the containing lambda scope:

((lambda () (define x 1) x)) ; 1

;Is a bit like
((lambda (x) x) 1) ; 1

But not exactly, because recursion doesn’t work in let form. These expressions both give an error, because the f isn’t visible in the position of the recursive application:

(let ((f (lambda (n) 
        (if (>= n 10) n (f (+ n 1)))))) 
     (f 1))
; (expand: unbound identifier in module in: f)

((lambda (f) (f 1))  
    (lambda (n) 
        (if (>= n 10) n (f (+ n 1)))))
; (expand: unbound identifier in module in: f)

To get around this problem Racket provides letrec, which is like let, but creates empty placeholders for ids before defining them:

(letrec ((f (lambda (n) 
           (if (>= n 10) n (f (+ n 1))))))
  (f 1)) ; 10

I’m guessing when translated to lambda, it means something like:

((lambda (f)
   (set! f (lambda (n) 
             (if (>= n 10) n (f (+ n 1)))))
   (f 1))
 void) ; 10

I expect Racket’s interpreter wouldn’t make such naive expansions, but it was a nice exercise for understanding the principle. It is nice to find out that the powerful scoping rules in Lisp have such elegant underpinnings.