SICP Exercise 4.6: Implementing let in the evaluator as a derived expression based on lambda

Question

I'm attempting to write a function that transforms a let expression of the form:

(let ((var1 exp1) ... (varn expn))
  body)

Into an (equivalent) lambda expression of the form:

((lambda (var1 ... varn) body) exp1 ... expn)

Most of the solutions to this problem that I've found appear to be wrong, could someone confirm this is the case?

Take, for example this solution from SICP answers wiki

 ;; let expression 
 (define (let-vars expr) (map car (cadr expr))) 
 (define (let-inits expr) (map cadr (cadr expr))) 
 (define (let-body expr) (cddr expr)) 

 (define (let->combination expr) 
   (cons (make-lambda (let-vars expr) (let-body expr)) 
         (let-inits expr))) 

I believe let->combination will return a list of this form:

((lambda (var1 ... varn) body) (exp1 ... expn))

But, what I think it should return is a list of this form:

((lambda (var1 ... varn) body) exp1 ... expn)

Somehow, shouldn't a call to the apply function be used in let->combination? How should let->combination be modified to include apply?

Answer 1

I believe let-combination will return a list of this form:

((lambda (var1 ... varn) body) (exp1 ... expn))

But, what I think it should return is a list of this form:

((lambda (var1 ... varn)    body)  exp1 ... expn)

There's good news and bad news. The bad news is that your belief is incorrect. The good news is that your thought is correct. That is, you do want the result ((lambda …) …), and that's what this code produces.

This Scheme code doesn't require any special interpreter or anything, so you can test this out without any real problem. Let's look at the definitions again:

 (define (let-vars expr) (map car (cadr expr))) 
 (define (let-inits expr) (map cadr (cadr expr))) 
 (define (let-body expr) (cddr expr)) 

 (define (let->combination expr) 
   (cons (make-lambda (let-vars expr) (let-body expr)) 
         (let-inits expr))) 

So what would happen in (let->combination '(let ((x 34)) (list x))), for instance? You"ll be evaluating:

(cons (make-lambda (let-vars expr) (let-body expr)) 
      (let-inits expr))

What do these parts create? (make-lambda …) creates the lambda expression that you'd expect:

(lambda (x) (list x))

and (let-inits …) returns:

(34)

Now the question is, what is (cons '(lambda (x) (list x)) '(34))`? You can test that out easily enough; it's:

((lambda (x) (list x)) 34)

This may be a result of some confusion about how cons works. A list is simply either: the empty list, '(), or a pair produced by cons whose car is an element of the list, and whose cdr is the rest of the list. Thus:

               (cons 1 '())  ;=> (1)
               (cons 1 '(2)) ;=> (1 2)
(cons '(lambda (x) x) '(34)) ;=> ((lambda (x) x) 34)

I believe let-combination will return a list of this form:

((lambda (var1 ... varn) body) (exp1 ... expn))

… Somehow, shouldn't a call to the apply function be used in let-combination? How should let-combination be modified to include apply?

As we've seen, the code actually produces the result that you desired. If it actually produced something like ((lambda (var1 ... varn) body) (exp1 ... expn)), then you would probably want to use apply. The simplest way would be to produce

(apply (lambda (var1 ... varn) body) (list exp1 ... expn))

Note that we've added apply, as well as a call to list. This would require changing the definition of let->combination. One possibility would be:

(define (let->combination expr) 
   (cons 'apply
         (cons (make-lambda (let-vars expr) (let-body expr)) 
               (cons (cons 'list (let-inits expr))
                     '()))))

Another (simpler) option is:

(define (let->combination expr) 
   (list 'apply
         (make-lambda (let-vars expr) (let-body expr)) 
         (cons 'list (let-inits expr))))