什麼是一些實施尾呼叫消除的好方法？

我已經寫了一個C/C++的非混合的小Scheme解釋器，但我還沒有實現proper tail calls。什麼是一些實施尾呼叫消除的好方法？

我知道經典的Cheney on the MTA algorithm，但是還有其他很好的實現方法嗎？我知道我可以將Scheme堆棧放在堆上，但這仍然不是正確的消除，因爲標準說應該支持無限數量的活動尾部調用。

我也擺弄了longjmps，但到目前爲止，我認爲它只會適用於非共同遞歸尾調用。

主要的基於C的方案如何實現適當的尾遞歸？

2011-05-14 csl

我看到一個非常類似的問題已被問：http://stackoverflow.com/questions/5986058/how-does-one-implement-a-stackless-interpreted-language – csl 2011-05-14 16:25:29

我發現Peter Norvig的原始JScheme實現了這個很好地與一個簡單的蹦牀。在http://norvig.com/jscheme/Scheme.java滾動到eval（） – csl 2012-09-19 08:19:40

比編寫編譯器和虛擬機更簡單，就是註冊並詮釋你的解釋器。既然你有一個解釋器，而不是一個編譯器（我認爲），你只需要一些簡單的轉換來獲得對tail調用的適當支持。

你必須首先用continuation-passing風格寫所有的東西，這在C/C++中可能很奇怪。丹·弗裏德曼的ParentheC教程步驟您通過改造一個高層次的，遞歸程序成一種形式，是機器翻譯爲C.

最後，你會基本上是實現一個簡單的VM那裏，而不是使用常規功能要求做的eval，applyProc等，通過設置全局變量傳遞參數，然後做一個goto下一個參數（或使用頂級循環和程序計數器）...

return applyProc(rator, rand)

變得

reg_rator = rator 
reg_rand = rand 
reg_pc = applyProc 
return

也就是說，所有通常互相調用的函數都被簡化爲一個僞彙編，其中它們只是不再發生的代碼塊。一個頂級環路控制程序：

for(;;) { 
    switch(reg_pc) { 
    case EVAL: 
     eval(); 
     break; 
    case APPLY_PROC: 
     applyProc(); 
     break; 
    ... 
    } 
}

編輯：我通過我的個人愛好Scheme解釋，用JavaScript編寫的同一進程中去。我利用了很多匿名程序，但它可能有助於作爲具體的參考。看看FoxScheme's commit history從2011-03-13開始（30707a0432563ce1632a）向上穿過2011-03-15（5dd3b521dac582507086）。

編輯^ 2：非尾遞歸仍然會消耗內存，即使它不在堆棧中。

來源

2011-05-15 01:50:36 erjiang

（編輯^ 2）我糾正了標準說的問題，謝謝。 – csl 2011-05-15 12:15:51

不知道你有什麼，我會說這樣做最簡單的（也是最有啓發性的）方法是實現從Dybvig的方案編譯器和VM「三種模式以推行方案」。
我在Javascript這裏做了（Dybvig的PDF副本是有太多）：https://github.com/z5h/zb-lisp

檢查的src/compiler.js：compileCons，以及「操作碼」的執行情況的src/vm.js

來源

2011-05-14 20:44:40 z5h

我沒有使用底層虛擬機，至少現在還沒有。我有eprogn，eval和evlis。但是它使用C棧，所以它在遞歸循環上爆炸了。但感謝您的建議！ – csl 2011-05-16 07:27:29

如果您對口譯員的實施技巧很感興趣，那麼是沒有辦法克里斯蒂安奎因內克的書籍「LiSP - Lisp in Small Pieces」。它用完整代碼非常全面地解釋了實施Scheme系統的所有方面。這是一本很棒的書。

http://www.amazon.com/exec/obidos/ASIN/0521562473/qid=945541473/sr=1-2/002-2995245-1849825

但是不要忘記檢查出ReadScheme.org的文件。

的部分

編譯技術/實現技術和優化 http://library.readscheme.org/page8.html

對尾調用優化的不少論文。

其中您可以找到Dybvig的論文（一個經典）的鏈接，這是寫得很好。它以一種非常明確的方式解釋和激勵了一切。

來源

2011-05-15 10:59:43 soegaard

對於LiSP的推薦，但是可以直接面向任何從Queinnec站點下載並下載代碼的人：幾章很大程度上依賴於Meroonet，這是本書最後描述的類CLOS對象系統。在發現有人打包了Meroon，一個與Gambit一起使用的相關對象系統之前，我努力了好幾天才把它用於現代計劃中。你可以很容易地使用Meroon代替Meroonet來運行代碼，並且它在Gambit中沒有任何大驚小怪。 YMMV，natch。 http://www.math.purdue.edu/~lucier/software/Meroon/ – spacemanaki 2011-05-15 19:25:35

感謝您的閱讀建議。我有Queinnec的書，我已經看過他的第一章eval和evlis解決方案。猜猜他也會在後面的章節中使用CPS，這似乎是這樣做的事實上的方式。 – csl 2011-05-16 07:26:25

什麼是一些實施尾呼叫消除的好方法？

回答

相關問題