Representing control in the presence of first-class continuations
Representing control in the presence of first-class continuations
复制标题
代表存在一流延续的控制
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Carl Bruggeman
中科院分区：
文献类型：
--
作者：
Robert Hieb;R. Dybvig;Carl Bruggeman
Scheme和Smalltalk等将延续作为一级数据对象提供的语言对高效实现提出了挑战。在堆中分配活动记录已被证明不能令人满意，因为增加了帧链接成本、增加了垃圾收集开销和减少了引用的局部性。但是，简单地在堆栈上分配活动记录并在创建延续时复制它们会导致无限的复制开销。本文描述了一种基于堆栈分配的新方法，该方法在创建延续时不需要复制堆栈，并且允许我们为恢复延续时复制的数量设置一个小的上限。这种新方法比简单的堆栈分配方法要快，而且不会出现与无界复制相关的问题。对于持续密集型的程序，我们的方法在最坏的情况下比堆分配方法慢一个常数因子，而对于典型的程序，它要快得多。另外一个重要的好处是，可以优雅而高效地处理堆栈溢出的恢复。
Languages such as Scheme and Smalltalk that provide continuations as first-class data objects present a challenge to efficient implementation. Allocating activation records in a heap has proven unsatisfactory because of increased frame linkage costs, increased garbage collection overhead, and decreased locality of reference. However, simply allocating activation records on a stack and copying them when a continuation is created results in unbounded copying overhead. This paper describes a new approach based on stack allocation that does not require the stack to be copied when a continuation is created and that allows us to place a small upper bound on the amount copied when a continuation is reinstated. This new approach is faster than the naive stack allocation approach, and it does not suffer from the problems associated with unbounded copying. For continuation-intensive programs, our approach is at worst a constant factor slower than the heap allocation approach, and for typical programs, it is significantly faster. An important additional benefit is that recovery from stack overflow is handled gracefully and efficiently.