scheme中letrec的語義要如何轉化以及實現？
在做一個基於棧式虛擬機的scheme解釋器，目前已經把了let，let* 轉化成了相應的lambda形式，這一過程是在編譯時完成的，都翻譯成了虛擬機指令，現在在做letrec的時候遇到了困難。
比如這樣的形式：
(letrec ( (x y)
(z 3)
(y z) )
(+ x y z))
letrec中有三個需要綁定的變數
我只搜到了單個變數形式的轉換方式：
(letrec ((fact (lambda (x)
(if (= x 1)
x
(* x (fact (- x 1)))))))
(fact 5))
是
((lambda (fact x)
(fact x fact))
(lambda (x fact)
(if (= x 1)
x
(* x (fact (- x 1) fact))))
5)
第一段中存在多個綁定的letrec該如何轉化成等價的lambda語句？
如果不能等價轉換的話，編譯成等價的語義有什麼好的方法？
告訴你一個比較愚蠢但是最簡單的辦法，假設有如下代碼（不用lisp了用F#那樣子的才好看
let rec
x i = 1 + y i
y i = 1 + z i
z i = 1 + x i
那怎麼辦呢？很簡單，你直接把x，y，z在那幾個函數裡面不斷的展開，直到展開到自己為止，譬如說函數x裡面展開到x就不繼續展開了，然後就變成
let rect
x i = 1 + 1 + x i
y i = 1 + 1 + y i
z i = 1 + 1 + z i
這樣每一個函數都變成了只遞歸自己的，然後就上Y-combinator吧，啊哈哈哈哈哈。
不過展開的順序比較講究。這裡的例子還是比較簡單的。但是如果y的寫法是這樣的：
let rec
y i = (y i) * (1 + z i)
怎麼辦，每次y展開後都會出現y，這樣x和z的展開就無窮下去了。沒關係，只要你先把y展開好了，然後y自己就先Y-combinator了，這樣你就得到了一個完美的y函數，然後在x和z裡面直接使用就行了。
但是像這種明顯早已自我遞歸的還好點，如果y是這樣的：
let rec
y i = (x i) * (1 + z i)
那又怎麼辦呢？現在先來看看完整的聲明：
let rec
x i = 1 + y i
y i = (x i) * (1 + z i)
z i = 1 + x i
現在你先畫出依賴關係圖：
這是一個有向圖，有向圖通常就涉及排序。函數的依賴關係如果是偏序結構那自然是極好的。如果是完全地互相遞歸的函數，那麼依賴關係畫出來的整個有向圖都是全聯通的，一點都不偏序，這個性質不好。這個時候我們的目標就是，通過每次合併儘可能數量少的節點，把整個圖慢慢迭代處理成具有偏序依賴關係的圖（對於這個例子，最後只會剩下一個節點，因為他本身就是全聯通的）。
那怎麼合併呢？我們要找到最小全聯通子圖。只有一個節點的子圖就不管了，因為我們的目標就是把所有的全連通子圖都合併成一個一個的節點。這個時候我們有x，y，z，我們看x和y，是全聯通的。x和z不是（因為x無法到達z，在這裡我們不考慮y，因為考慮了的話就要把y包含進來，他就更大了，我們要找的是最小的）。y和z也不是。那現在大於一個節點的最小全連通子圖就是{x, y}，把它拿出來，搞成lambda，然後就可以刪去替換成一個大節點xy了。現在剩下xy和z兩個節點，自然是偏序的，因為是z依賴於xy（後面有解釋）。爽。
如何把依賴圖處理成具有偏序依賴關係的圖，就是排序的過程。至於如何排序，已經有很多經典演算法了，我就不說了。當然我說的可能不嚴謹，因為還是通俗易懂比較重要。只要你開始實現了，你自然會踏遍所有的坑，那細節也就都明白了。
上面的結論也就是說，最終我們通過排序，發現x和y要先同時做，做完才能做z。那麼我們看來看只拿出x和y會有什麼結果：
let rec
x i = 1 + y i
y i = (x i) * (1 + 1 + x i)
是不是發現又回到第一個簡單的問題了！先把x和y搞定，然後把大節點xy到z的邊刪去（因為代碼裡面已經沒有z了），最後z就好說了，利用x和y的結論，直接就做出來了。直觀來講，為什麼要先做x和y，因為不把x和y先搞好，我們會發現展開z是永遠也展開不完的（完的意思就是，z展開到裡面只包含z和其他已知或已處理的函數，然後停下來）。展開z會遇到x，x展開會遇到y，y展開會遇到x，永遠也沒辦法展開到只有x為止，永遠也停不下來。但是x和y就不一樣，x到y到z到x停下來了，y到z到x到y，停下來了。我們的排序就是為了保證，總是把能停下來的節點先處理。
最後要強調一下，為什麼要排序，因為如果你不排序直接無腦展開的話，演算法很容易不停機。這個排序的過程也是證明演算法一定會停機的過程。編譯器當然要能停機，所以你當然要排序。
http://www.cs.indiana.edu/~dyb/papers/fixing-letrec.pdfhttp://www.cs.indiana.edu/~dyb/pubs/letrec-reloaded.pdf
不對啊，你 letrec eval 第一個 binding (x y) 的時候，y 不是還沒定義嗎？letrec 只是建一個新的 environment 指向 lexical parent，然後每個 binding 都用這個 env 來 eval，結果再放進這個 env 里然後處理下一個 binding。比 let* 的 env 套 env 只是多了支持 recursion 的特性而已。
letrec 用同一個 env 來 eval bindings 並儲存 bindings 的好處就是，bindings 里定義的 lambda 的 env 就是這個 env，所以能遞歸調用自己。而 let 的 bindings 里定義的 lambda，用的是 let 的 parent env 來 eval，所以 env 對應的是 let 的 parent env，在那裡邊自然找不到自己，所以不能遞歸。let* 類似。
話說你要真把這些轉成「lambda形式」，不太理解啊。不帶 environment 的話，難道自己加 Y Combinator 然後化成 normal form？那不帶 normal form 的 lambda 怎麼辦？
如果不想做成單獨的 special-form，而是做成宏的話就是 @楊雙成 的那個答案，不過要實現幾個 destructive functions。
——————————這是用 R5RS 跑的結果：
用expand展開之後，你會發現簡單得不費一點腦筋。
===========================================
因爲letrec本身是一個宏，要想知道它幹了些什麼，宏展開後一看便知
(letrec ((odd? (lambda (n)
(if (= n 0)
#f
(even? (- n 1)))))
(even? (lambda (n)
(if (= n 0)
#t
(odd? (- n 1))))))
(odd? 3))
MIT Scheme 宏展開之後變成
(let ((odd? "void) (even? "void))
(let ((odd?.1 (lambda (n)
(if (= n 0)
#f
(even? (- n 1)))))
(even?.1 (lambda (n)
(if (= n 0)
#t
(odd? (- n 1))))))
(set! odd? odd?.1)
(set! even? even?.1)
(let ()
(odd? 3))))
可見letrec被很簡單的轉換成let。
============================
真的是一點都不費腦筋。
letrec 不是 展開成嵌套的lambda么
推薦閱讀：