Tail-Recursive Stack Disciplines for an Interpreter
Tail-Recursive Stack Disciplines for an Interpreter
复制标题
解释器的尾递归堆栈规则
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
R. Kelsey
中科院分区：
文献类型：
--
作者：
R. Kelsey
许多语言，包括方案、ML和Haskell，都要求它们的实现支持任意深度的尾递归调用。这一要求意味着传统的堆栈规则不能用于这些语言。本文研究了在基于堆栈的中介器中实现正确的尾递归的几种不同方法，包括在堆中传递参数、将参数复制到尾递归调用以及对堆栈进行垃圾回收。基准计时和其他运行时统计信息用于比较不同的方法。结果表明，使用堆栈是一个好主意，而且解释器的开销在很大程度上掩盖了各种堆栈规则在性能上的差异。1如果递归表示的无界迭代计算可以在常量空间中执行，则程序设计语言实现是真正尾递归的。方案Rees 86]、ML Milner 88]和Haskell Hudak 90]等语言的实现必须是尾递归的。这些语言还要求某些词汇环境有不同的程度。也就是说，传递给过程的参数可能需要保留到该过程返回后很长一段时间。同样，在方案中，延续也可能具有独立的范围。延续是在过程调用中保存的所有信息，用于在过程返回后重新启动过程的调用方。在方案中，过程调用可能会多次返回，因此可能需要保存延续以供以后使用。
Many languages, including Scheme, ML, and Haskell, require that their implementations support tail-recursive calls to arbitrary depth. This requirement means that a traditional stack discipline cannot be used for these languages. This paper examines several diierent methods of implementing proper tail recursion in a stack-based interpeter, including passing arguments in a heap, copying arguments to tail-recursive calls, and garbage collecting the stack. Benchmark timings and other run-time statistics are used to compare the diierent methods. The results show that using a stack is a good idea, and that the overhead of the interpreter largely overshadows the diierences in performance of the various stack disciplines. 1 The Problem A programming language implementation is properly tail recursive if unbounded iterative computations that are expressed recursively can be executed in constant space. Implementations of languages such as Scheme Rees 86], ML Milner 88], and Haskell Hudak 90] are required to be tail recursive. These languages also require that some lexical environments have in-deenite extent. That is, arguments passed to a procedure may need to be preserved until long after the procedure has returned. Similarly, in Scheme, continuations also may have indeenite extent. A continuation is all of the information that is saved across a procedure call and used to restart the procedure's caller once the procedure returns. In Scheme procedure invoca-tions may return more than once, so continuations may need to be saved for later use.