7

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

如何处理非尾递归函数？有什么选择？什么是好的资源？我读过一些关于蹦床、堆栈外部化和延续传递风格的文章，但我能找到的只是如何以这些风格编写代码，而不是如何使用这些技术来编写解释器。

4

1 回答 1

4

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

对于您的解释器，您的调用帧数据需要保存非尾调用的延续（它本身可能保存进一步的引用，例如它需要访问的任何变量）。每个活动的非尾调用都需要一个调用帧。

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

于 2013-02-01T02:52:05.500 回答