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

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.109.20.217