※ 引述《SansWord (是妳)》之铭言：
: 来这里问问有没有更general 的 "letrec 如何可能" 的学理原则
Hmm... 我是觉得可以找 ccshan 建议的课本来看看。
我不知道 letrec 实际上是怎么做的，不过如果是谈原则，
我会用 fixed-point combinator 来解释 letrec. 这样不用
用到 set-cdr 或其他副作用。只要语言本身有提供 lambda
abstraction 就可以做出 letrec 的效果。
以你写到的 fact 为例子。在一个已经允许你用递回定义的
语言中你可以这样定 fact:
(define (fact n)
(if (= n 1)
1
(* n (fact (- n 1)))))
e.g. (fact 6) = 720.
（这边的 define 就是 letrec）但如果不准递回定义呢？
我们先定一个函数叫做 factF, 把递回的地方抽出来：
(define (factF g)
(lambda (n)
(if (= n 1)
1
(* n (g (- n 1))))))
factF 是一个产生函数的函数。给一个函数 g, (fact g)
又是一个整数到整数的函数。它只做了 fact 的“
第一层”。本来应该递回的地方则呼叫 f.
我们希望 g 的位置又是 (factF g). 也就是说我们得把
factF 喂给自己:
(factF (factF (factF ..... ))) 6 = 720.
这个“喂给自己”的动作可以用 Y combinator 来作。
Lambda calculus 中 Y combinator 是定义成:
Y F = (\x . F (x x)) (\x . F (x x))
这样一看实在是不知道在做什么。但如果我们把它展开:
Y F
= (\x . F (x x)) (\x . F (x x))
= F ((\x . F (x x)) (\x . F (x x)))
= F (F ((\x . F (x x)) (\x . F (x x))))
= F (F (F ((\x . F (x x)) (\x . F (x x))))
= ...
就看到 F 一个个跑出来了。 :)
在 Scheme 中原则上也是可以这么做，但 Scheme 是
strict 的语言，如果 Y 那样写会停不下来。所以得
多加一些 lambda 把那些 (x x) 的计算延迟掉:
(define (Y F)
((lambda (x)
(F (lambda (a) ((x x) a))))
(lambda (x)
(F (lambda (a) ((x x) a))))))
然后我们就可以定义
(define factY (Y factF))
某个意义上 Y 就是实作出了 letrec. 剩下来的就是
怎么用一些 macro 把它包起来... 这就要问真正会
Scheme 的人了..
Google 一下 Y combinator 会找到很多解说。例如
http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
: 更麻烦的问题～那mutual recursion呢？又要怎实作？
: 会不会有晦暗的角落出错我却没注意到？
Mutual recursion 其实也是一样的. 单独的递回定义是定义
一个东西，mutual recursion 是一次定义一组。
（下次有空试试看... ）