sicp-ex-4.7

  
  
  
 ;; let* expression 
 (define (let*? expr) (tagged-list? expr 'let*)) 
 (define (let*-body expr) (caddr expr)) 
 (define (let*-inits expr) (cadr expr)) 
 (define (let*->nested-lets expr) 
         (let ((inits (let*-inits expr)) 
                   (body (let*-body expr))) 
                 (define (make-lets exprs) 
                         (if (null? exprs) 
                                 body 
                                 (list 'let (list (car exprs)) (make-lets (cdr exprs))))) 
                 (make-lets inits))) 

The body of let* is a sequence of expressions, so I think it should be accessed with cddr. It can be transformed to a single expression with sequence->exp which is defined in the book.

  
 (define (let-args exp) (cadr exp)) 
 (define (let-body exp) (cddr exp)) 
 (define (make-let args body) (cons 'let (cons args body))) 
  
 (define (let*->nested-lets exp) 
   (define (reduce-let* args body) 
     (if (null? args) 
         (sequence->exp body) 
         (make-let (list (car args)) 
                   (list (reduce-let* (cdr args) body))))) 
   (reduce-let* (let-args exp) (let-body exp))) 
  

test:

> (let*->nested-lets '(let* ((x 1) (y 2)) x y))
'(let ((x 1)) (let ((y 2)) (begin x y)))
> (let*->nested-lets '(let* () 1))
1

  (define (let*->nested-lets exp env)  
          (define (make-let var-pairs body-exps)   
              (cons 'let (cons var-pairs body-exps)))  
          (define (nested-lets var-pairs body-exps)  
              (if (null? var-pairs) body-exps  
                  (make-let (list (car var-pairs))   
                            (if (null? (cdr var-pairs)) 
                                (nested-lets (cdr var-pairs) body-exps) 
                                (list (nested-lets (cdr var-pairs) body-exps))))))  
          (if (null? (cadr exp)) (cons 'begin (cddr exp)) 
              (nested-lets (cadr exp) (cddr exp))))  

 > (let*->nested-lets '(let* ((x 1) (y 2)) x y) 233) 
 (let ([x 1]) (let ([y 2]) x y)) 
 > (let*->nested-lets '(let* () x y) 233) 
 (begin x y) 

Another solution using fold:

  
 ;; var-defs and body should be list 
 (define (make-let var-defs body) 
   (cons 'let (cons var-defs body))) 
 (define (let*? exp) (tagged-list? exp 'let*)) 
 (define (let*->let exp) 
   (car 
    (fold-right (lambda(new rem) 
                  (list (make-let (list new) rem))) 
                (let-body exp) 
                (let-vardefs exp)))) 

  
 (define (let*->nested-lets exp)                                                                                                                                               
   (define (wrap def exp)                                                                                                                                                     
     (list 'let (list def) exp))                                                                                                                                         
   (let ((bindings (cadr exp))                                                                                                                                         
         (body (caddr exp)))                                                                                                                                                 
     (fold-right wrap body bindings)))   

 (define (let*? exp) (tagged-list? exp 'let*)) 
 (define (let*->nested-lets exp) 
         (expand-let*-clauses (cadr exp) (cddr exp))) 
 (define (expand-let*-clauses lets body) 
         (if (null? lets) 
                         (sequence->exp body) 
                         (list 'let (list (car lets)) (expand-let*-clauses (cdr lets) body)))) 
  

Here's my attempt at answering the question posed by the authors in the second part of the question. The answer becomes a little clearer if we use let->combination to expand the expression produced by let*->nested-lets:

 (let->combination (let*->nested-lets '(let* ((x 1) (y (+ x 1))) (+ x y)))) 
  
 ;; '(call (lambda (x) (let ((y (+ x 1))) (+ x y))) 1) 

The problem is that let->combination doesn't recursively expand the nested lets.

Although not the only way to implement it in our evaluator, the most straightforward way is as follows:

 (define (eval exp env) 
 ;; ... 
         ((application? exp) 
          (apply (eval (operator exp) env) 
                 (list-of-values (operands exp) env))) 
 ;; ... 
         ((lambda? exp) (make-procedure (lambda-parameters exp) 
                                        (lambda-body exp) 
                                        env)) 
 ;; ... 
         ((let? exp) (eval (let->combination exp) env)) 
 ;; ... 
 ) 

So, when we ask eval to evaluate '(call (lambda (x) (let ((y (+ x 1))) (+ x y))) 1), it will recognize it as a procedure application and try to apply (lambda (x) (let ((y (+ x 1))) (+ x y))) to 1). Will this work? That depends on the implementation of apply. It uses eval-sequence to apply compound procedures to arguments, so if apply succeeds in fully simplifying this expression then the expression will be evaluated correctly. However, it would make more sense to rewrite let->combination so that it can handle nested lets instead of relying on the caller knowing that it needs to be expanded again.

 (define (let->combination exp) 
   (define (rec this-exp) 
     (let ((next-exp (caddr this-exp))) 
     (if (let? next-exp) 
         (make-lambda (let-vars this-exp) 
                      (list (make-application (rec next-exp) (let-exps next-exp)))) 
         (make-lambda (let-vars this-exp) 
                      (let-body this-exp))))) 
   (make-application (rec exp) (let-exps exp))) 

This procedure produces expressions of the form:

 (let->combination (let*->nested-lets '(let* ((x 1) (y (+ x 1))) (+ x y)))) 
  
 ;; '(call (lambda (x) (call (lambda (y) (+ x y)) (+ x 1))) 1) 

Should be no problem for our evaluator.

 (eval-sequence (procedure-body procedure) 
     (extend-environment (procedure-parameters procedure) 
                         arguments 
                         (procedure-environment procedure)))