javascript - 程序化非尾递归消除

Question

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

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

Answer 1

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

对于您的解释器，您的调用帧数据需要保存非尾调用的延续(它本身可能保存更多引用，例如它需要访问的任何变量)。每个事件的非尾调用都需要一个调用帧。

当然，所有这一切都是用堆栈空间换取堆空间。最后，您并没有真正以这种方式保存任何内存。 :-)