Study for Optimization of Continuations

虽然Scheme编程语言中的一流延续功能强大，但创建和调用延续的成本非常高。为了避免这个问题，我们提出了轻量级的延拓，称为无限期一次性延拓（或简称IOC）。IOC最多只能被调用一次，但可以在任何时候被调用。如果我们确定在程序执行过程中最多只调用一次continuation，那么通过将生成continuation的函数“call/cc”替换为生成IOC的函数“call/ioc”，程序的性能将显著提高。一般来说，然而，它是很难确定是否一个延续被调用最多once.In这项研究中，我们提出了一个算法来自动检测这些延续，可以被替换为IOCs，通过分析整个程序使用一种抽象的解释。基于此算法，我们开发了一个系统，检测那些“call/cc”的调用，可以被替换为“call/ioc”的调用。然后，我们分析了几个实用的方案在该系统上。该算法不能检测所有的可替换延续，因为该算法只使用从程序静态获得的信息。然而，我们的实验表明，在实际的Scheme程序中的大多数可替换的延续可以检测到该算法。

While first-class continuations as in the Scheme programming language are powerful, the cost of creating and calling continuations is very high. In order to avoid this problem, we have proposed light-weight continuations called indefinite one-time continuations (or IOCs for short). An IOC can be called at most once but can be called at any time.If we are sure that a continuation is called at most once during the execution of a program, then by replacing the function "call/cc" which generates a continuation with "call/ioc" which generates an IOC, the performance of the program will be significantly increased. In general, however, it is difficult to determine whether a continuation is called at most once.In this research, we proposed an algorithm to automatically detect those continuations that can be replaced by IOCs, by analyzing an entire program using a kind of abstract interpretation. Based on this algorithm, we developed a system which detects those "call/cc" calls that can be replaced by "call/ioc" calls. We then analyzed several practical Scheme programs on this system. This algorithm cannot detect all replaceable continuations since the algorithm uses only the information which is statically obtained from a program. However, our experiments showed that most replaceable continuations in practical Scheme programs can be detected by this algorithm.