程序化非尾遞歸消除

我正在JavaScript中製作一個玩具Lisp解釋器。 JS無尾遞歸消除（TRE），所以我實施TRE使用while循環JS（僞）：程序化非尾遞歸消除

function eval (exp, env) 
    while true 
    if exp is self evaluating 
     return exp 
    else if ... 
     ... 
    else if exp is a function call 
     procedure = eval(car(exp), env) 
     arguments = eval_operands(cdr(exp), env) 
     exp = procedure.body 
     env = extend_env(procedure.env, env) 
     continue # tail call

所以我很高興，像下面的一個尾遞歸函數沒有用完棧：

(define + 
    (lambda (n m) 
    (cond ((zero? n) m) 
      (else (+ (sub1 n) (add1 m)))))) 

(+ 10000 1) ;=> 10001

但是，功能是不是尾遞歸，（上eval_operands，因爲JS代碼再次出現太多）用完JS棧：

(define + 
    (lambda (n m) 
    (cond ((zero? n) m) 
      (else (add1 (+ (sub1 n) m))))) ; not proper tail-recursive 

(+ 10000 1) ;=> JS: Maximum call stack size exceeded

我如何處理非泰l遞歸函數？有什麼選擇？什麼是好資源？我已經讀了一些關於蹦牀，堆棧外化和延續傳遞風格的內容，但我能找到的是如何編寫這些風格的代碼，而不是如何使用這些技術來編寫解釋器。

來源

2013-01-31 Halst

由於您正在實施解釋器，所以性能不應該成爲您的問題，因此您可以先執行CPS轉換（然後所有的呼叫都將是尾部呼叫）。解釋CPS代碼很簡單，只需使用鏈接列表傳遞延續。 –

請務必閱讀FUNARG問題。 :) –

您可以總是如果您能夠在其他地方保存呼叫幀信息，則會將呼叫轉爲跳轉。這就是「堆棧外部化」所指的。

對於您的解釋器，您的呼叫幀數據需要保持非尾呼叫的延續（它本身可以保存更多的引用，例如它需要訪問的任何變量）。您將需要每個活動的非尾呼叫一個呼叫幀。

所有這些當然都是堆空間的交易堆棧空間。最後，你不會以這種方式保存任何內存。 :-)

來源

2013-02-01 02:52:05

你可以寫一些僞代碼（例如以我的eval僞代碼爲基礎）？ – Halst

程序化非尾遞歸消除

回答

相關問題