javascript - 程序化无尾递归消除

我正在用JavaScript制作玩具Lisp解释器。 JS没有尾递归消除(TRE)，因此我在JS(伪代码)中使用while循环实现了TRE:

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

但是，不是尾递归的函数会用完JS堆栈(因为JS代码在eval_operands上重复出现太多):

(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

我该如何处理非尾递归函数？有什么选择？什么是好的资源？我已经阅读了一些有关蹦床，堆栈外部化和连续传递样式的信息，但是我所能找到的就是如何以这些样式编写代码，而不是如何使用那些技巧来编写解释器。

最佳答案

如果您能够在其他地方保存调用帧信息，则始终可以将调用转换为跳转。这就是“堆栈外部化”的含义。

对于您的解释器，您的调用框架数据需要保留非尾调用的延续(它本身可能还包含其他引用，例如它需要访问的任何变量)。每个 Activity 的非尾部调用将需要一个调用帧。

当然，所有这些都是将堆栈空间换成堆空间。最后，您实际上并不会以这种方式节省任何内存。 :-)

关于javascript - 程序化无尾递归消除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14633919/