SICP

Exercise 4.8. ‘‘Named let’’ is a variant of let that has the form

(let <var> <bindings> <body>)

The <bindings> and <body> are just as in ordinary let, except that <var> is bound within <body> to a procedure whose body is <body> and whose parameters are the variables in the <bindings>. Thus, one can repeatedly execute the <body> by invoking the procedure named <var>. For example, the iterative Fibonacci procedure (section 1.2.2) can be rewritten using named let as follows:

(define (fib n)
  (let fib-iter ((a 1)
                 (b 0)
                 (count n))
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))

Modify let->combination of exercise 4.6 to also support named let.

named-let 也只需要借助于当前已经有的 let 表达式来完成定义。题目中的一个 named-let 的定义

(define (fib n)
  (let fib-iter ((a 1)
                 (b 0)
                 (count n))
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))

转化为 let 的表达式应该为

(let ((fib-iter 1))
  (begin
    (set! fib-iter (lambda (a b count)
                     (if (= count 0)
                         b
                         (fib-iter (+ a b) a (- count 1)))))
    (fib-iter 1 0 n)))

我们先使用 let 表达式使 fib-iter 这个名称对于之后的内容可见–至于它的初始内容，就无关紧要了。在接下来要做的事情中，就是把这个名称与其要绑定的过程绑定，在绑定之后，过程中如果使用了这个名称来进行递归也没有问题了，因为当运行到这个递归语句的时候，我们的名称已经绑定到了相应过程上了。

这是一种让过程有递归能力的普遍方法：

让名称可见；
将名称绑定到相应过程上。

我们将对 eval-let 的 package 进行修改。主要修改 let->combination 过程，如果传递进去的不是 named-let，那么之前的操作不变。如果是 named-let，那么 let->combination 将会把 named-let 转化为 let，然后再转化为 lambda 表达式。

我们的 let->combination 如下：

  (define (let->combination exp)
    (if (named-let? exp)
        (let->combination (cdr (named-let->let exp)))
        (cons (make-lambda (let-vars (let-bindings exp))
                           (let-body exp))
              (let-vals (let-bindings exp)))))

let->combination 中使用到了 named-let->let 的过程，如下：

  (define (named-let->let exp)
    (let ((var (car exp))
          (bindings (cadr exp))
          (body (cddr exp)))

      (let ((procedure (make-lambda (let-vars bindings)
                                    body)))
        (make-let (list var)
                  (list 1) ; arbitrary value!
                  ((get 'constructor sequence-tag)
                   (list (list 'set! var procedure)
                         (cons var (let-vals bindings))))))))

最后是我们的测试用例

; test the transformation

(let ((test-env (setup-environment)))
  (begin
    (install-eval-named-let)
    (assert= (eval '(let ((x 1) (y 1))
                      (+ x y)) test-env)
             2)
    (assert= (eval '(let ((x 1))
                      (let ((x 2))
                        (+ x 2))) test-env)
             4)
    (assert= (eval '(let ((x 1))
                      (let ((x 2))
                        (set! x 3))
                      x) test-env)
             1)
    (eval '(define (fib n)
             (let fib-iter ((a 1)
                            (b 0)
                            (count n))
               (if (= count 0)
                   b
                   (fib-iter (+ a b) a (+ count -1))))) test-env)
    (assert= (eval '(fib 10) test-env) 55)))

SICP 全笔记