我在
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
我如何处理非尾递归函数？有什么选择？什么是好资源？我已经阅读了一些关于trampolining,stack externalizing和continuation-passing风格的内容,但我能找到的是如何用这些样式编写代码,而不是如何使用这些技术来编写解释器.
