抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2600000, indirect: -)
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.