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

[noctem (noctem)]

※ 引述《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
推 SansWord:謝謝！ 我來試試看～
→ SansWord:這個方法是不是很像 Functional Programming with
→ SansWord:Overloading and Higher-Order Polymorphism
→ SansWord:ch 5.1 提到的functor?    (上面那篇by Mark P. Jones)
→ SansWord:裡面提到了如何抽象化 fold 之類的函數
→ SansWord:使用到了一個cata phi 機制～
推 godfat:對不起，推文請勿超過三行，超過麻煩用回文的方式，謝謝
推 SansWord:抱歉我不知道這個規則～所以我直接回這篇嗎?
→ godfat:板規有寫，沒關係以後記得就好
推 SansWord:好的～謝謝板主