程序化非尾递归消除

我正在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

程序化非尾递归消除

回答

相关问题