通过异常查找描述尾递归优化的参考资料

Question

我用python和sapid lisp本身实现了一个小的lisp解释器(sapid lisp at google code)。也许它的主要特点是通过异常实现尾部和相互递归优化。实现细节在这里https://sites.google.com/site/sapidlisp/recursion-optimization。

相对于标准技术的优势在于，应用于递归解释器以获得尾递归优化的更改有限。劣势可能是时机问题。

我发现在python装饰器( http://code.activestate.com/recipes/474088/ )中使用了类似的技术。现在，为了把这项技术放在它的上下文中，我正在寻找描述lisp或其他解释型语言的这种技术的参考资料。有什么消息吗？

Answer 1

请看Eli的回答。但是为了添加更多的上下文，贝克的Cheney on the M.T.A.技术是一个众所周知的技巧，用于实现适当的尾递归，它使用C堆栈作为延续帧和其他对象的托儿所(就像在分代GC中一样)。这种技术不是像大多数尾递归实现那样保持堆栈较小(大多数尾递归实现都是这样)，而是允许堆栈增长一段时间，然后每隔一段时间通过大跳跃(longjmp、execption等)清除堆栈。在清除堆栈之前，将所有的活动内容复制到堆中。

只要您能够并愿意跟踪堆栈并将对象从堆栈复制到堆上，就可以很好地工作。Eli引用的论文(来自通用堆栈检查的续集)是关于将技巧适应于“托管”平台，在这些平台中，您不能直接检查堆栈。

Answer 2

请参阅Pettyjohn等人的Continuations from Generalized Stack Inspection和Joe Marshall的相关addendum。

(“解释”，无论这是什么意思，如今与主题无关。)