Exercise 4.20 · 习题

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 ((⟨var₁⟩ ⟨exp₁⟩) … (⟨varₙ⟩ ⟨expₙ⟩))
⟨body⟩)

are a variation on let in which the expressions
⟨

e
x

p
k

⟩ that provide the initial values for the
variables ⟨

v
a

r
k

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

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!.

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.

练习 4.20：由于内部定义在外观上是顺序的，实际上却是同时的，有些人倾向于完全避免使用它们，而改用特殊形式 letrec。Letrec 的外观与 let 相似，因此它所绑定的变量同时绑定、互为作用域也就不足为奇了。上面的示例过程 f 可以不使用内部定义，而以完全相同的含义写成：

(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 表达式的形式为

(letrec ((⟨var₁⟩ ⟨exp₁⟩) … (⟨varₙ⟩ ⟨expₙ⟩))
⟨body⟩)

它是 let 的一种变体，其中为变量 ⟨varₖ⟩ 提供初始值的表达式 ⟨expₖ⟩ 在包含所有 letrec 绑定的环境中求值。这使得绑定中可以有递归，例如上面示例中 even? 和 odd? 的互递归，或用以下方式对 10 的阶乘求值：

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

将 letrec 实现为派生表达式，方法是将 letrec 表达式变换为如正文或练习 4.18 所示的 let 表达式。即，letrec 的变量应先用 let 创建，然后用 set! 赋值。

Louis Reasoner 对所有这些关于内部定义的讨论感到困惑。在他看来，如果你不想在过程内部使用 define，完全可以用 let。请通过画环境图来说明他的推理有何漏洞：画出在对 (f 5) 求值过程中，对 ⟨rest of body of f⟩ 求值时生效的环境（f 按本练习中的定义，使用 letrec）；再画出同一求值过程的环境图，但将 f 定义中的 letrec 换成 let。