SICP 全笔记

Exercise 4.20. Because internal definitions look sequential but are actually simultaneous, some people prefer to avoid them entirely, and use the special form letrec instead. Letrec looks like let, so it is not surprising that the variables it binds are bound simultaneously and have the same scope as each other. The sample procedure f above can be written without internal definitions, but with exactly the same meaning, as

(define (f x)
  (letrec ((even?
            (lambda (n)
              (if (= n 0)
                  true
                  (odd? (- n 1)))))
           (odd?
            (lambda (n)
              (if (= n 0)
                  false
                  (even? (- n 1))))))
    <rest of body of f>))

Letrec expressions, which have the form

(letrec ((<var1> <exp1>) ... (<varn> <expn>))
  <body>)

are a variation on let in which the expressions <expk> that provide the initial values for the variables <vark> are evaluated in an environment that includes all the letrec bindings. This permits recursion in the bindings, such as the mutual recursion of even? and odd? in the example above, or the evaluation of 10 factorial with

(letrec ((fact
          (lambda (n)
            (if (= n 1)
                1
                (* n (fact (- n 1)))))))
  (fact 10))

a. Implement letrec as a derived expression, by transforming a letrec expression into a let expression as shown in the text above or in exercise 4.18. That is, the letrec variables should be created with a let and then be assigned their values with set!.

b. Louis Reasoner is confused by all this fuss about internal definitions. The way he sees it, if you don’t like to use define inside a procedure, you can just use let. Illustrate what is loose about his reasoning by drawing an environment diagram that shows the environment in which the <rest of body of f> is evaluated during evaluation of the expression (f 5), with f defined as in this exercise. Draw an environment diagram for the same evaluation, but with let in place of letrec in the definition of f.

letrec 的实现

与 练习 4.16 一样，letrec 也是转化为 let 与 set! 的语句。我们可以借用里面的一些过程来实现 letrec。

(load "6-let.scm")


(define (install-eval-letrec)
  (install-eval-let) ;; install let support!  
  (define (make-lambda parameter body)
    ((get 'constructor lambda-tag) parameter body))

  (define (make-let vars vals body)
    ((get 'constructor 'let) vars vals body))

  (define (make-assignments vars vals)
    (map (lambda (var val)
           (list assignment-tag var val))
         vars vals))

  (define (letrec-binding exp)
    (car exp))

  (define (letrec-body exp)
    (cdr exp))

  (define (letrec->let exp)
    (let* ((bindings (letrec-binding exp))
           (vars (map (lambda (x) (car x)) bindings))
           (vals (map (lambda (x) (cadr x)) bindings))
           (body (letrec-body exp)))
      (make-let vars
                (map (lambda (x) ''*unassigned*) vars)
                (append (make-assignments vars vals) body))))

  (define (eval-letrec exp env)
    (eval (letrec->let exp) env))

  (put 'eval 'letrec eval-letrec)
)

环境图

当把 letrec 转化为 let 与 set! 的语句的时候，环境图如下。可以看到 even? 和 odd? 是在同一个环境中，所以可以实现相互引用。

+----------------------------------+
| f: ...                           |
|                                  |
+----------------------------------+
                         ^
                         |
                         |
                    +----+-----+
                    | x: 5     | (f 5)
                    +----------+
                         ^
                         |
                         |
              +----------+----------+
              |even?: '*unassigned* |
              |odd? : '*unassigned* |
              +---------------------+
               ((set! even? ...)
                (set! odd?  ...)
                <rest of body of f>)

但如果只使用 let 来定义，即

(define (f x)
  (let ((even?
         (lambda (n)
           (if (= n 0)
               true
               (odd? (- n 1)))))
        (odd?
         (lambda (n)
           (if (= n 0)
               false
               (even? (- n 1))))))
    <rest of body of f>))

环境图为

+----------------------------------+
| f: ...                           |
|                                  |
+----------------------------------+
                         ^
                         |
                         |   (f 5)
                    +----+-----+
                    | x: 5     | <--------------------------------------+<-----------+
                    +----------+                                        |            |
                         ^                                              |            |
                         |                                              |            |
                         |                                              |            |
              +----------+--------------------------------------------- | ---+       |
              |                                                       +-+-+  |       |
              |even?: (procedure (n) (if (= n 0) true (odd? (- n 1))) |env|) |       |
              |                                                       +---+  |       |
              |                                                        +---+ |       |
              |odd? : (procedure (n) (if (= n 0) true (even? (- n 1))) |env|)|       |
              |                                                        +-+-+ |       |
              +--------------------------------------------------------- | --+       |
                <rest of body of f>                                      +-----------+

这里的差别在于，在运行 f 的时候，f 的确可以“看到” even? 和 odd?，但 even? 和 odd? 分别有自己的 environment（都指向之前的一个 frame），所以 even? 并不会去自己的 frame 中寻找 odd? 而是去自己保存好的 frame 的位置去寻找 odd?。

将 let 转为 lambda 则可以更明显地看这个问题：

((lambda (even? odd?)
  <rest of body of f>)
 (lambda (if (= n 0) true (odd? (- n 1))))
 (lambda (if (= n 0) true (even? (- n 1)))))

可以看出在绑定 even? 与 odd? 之前，当做参数的两个 lambda 中的 odd? 和 even? 都是没有绑定的。