Re: [問題] letrec 為何可以成立？ (In scheme, ma …

看板PLT (程式語言與理論)作者noctem (noctem)時間14年前 (2010/06/02 10:22)推噓4(4推 0噓 6→)

留言10則, 2人參與討論串2/6 (看更多)

※ 引述《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