sicp-ex-4.7



<< Previous exercise (4.6) | Index | Next exercise (4.8) >>


meteorgan

  
  
  
 ;; 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))) 

3pmtea

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

Compared with 3pmtea's answer, the let expression generated in my solution is more elegant, but the implementation is worse.

  (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))))  

test:

 > (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) 


inchmeal

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)))) 

Simpler:

  
 (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)))   


dzy

 (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)))) 
  

master

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.

I'm confused by this comment. Is there an example of how the evaluator could fail on the first version of the expression?

Unraveling the definition of apply as given so far in the book, we're going to

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

where

  • (procedure-body procedure) is '((let ((y (+ x 1))) (+ x y))),
  • (procedure-parameters procedure) is '(x),
  • and arguments is '(1)
  • (and (procedure-environment procedure) is the environment where the original let* expression was evaluated). Since the procedure body has a single expression, eval-sequence reduces to eval. In other words, we're going to evaluate the inner let expression in an environment extended by the definition that x = 1, which is exactly what we should be doing.

So I don't think it makes a difference whether we immediately translate the let* expression to nested lambdas, or translate it to nested lets and let the interpreter of let finish the job. Am I missing something?