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

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

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.