※ 引述《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 是一次定義一組。
（下次有空試試看... ）