Loading...
Please wait, while we are loading the content...
Similar Documents
Managing continuations for proper tail recursion
| Content Provider | ACM Digital Library |
|---|---|
| Author | Yasugi, Masahiro Umatani, Seiji Komiya, Tsuneyasu Hiraishi, Tasuku |
| Abstract | Implementations of Scheme are required to be properly tailrecursive and to support an unbounded number of active tail calls. Clinger proposed a formal definition of proper tail recursion based on space efficiency. This definition encompasses systematic tail call optimization, where every tail call is converted to a jump (with an optional trampoline), as well as Baker's implementation of Scheme in the C language with CPS (continuation-passing style) conversion. Baker's implementation is space-efficient, since no new continuation is created on a CPS-converted tail call and garbage is collected even on C's execution stack. In our work, we discovered that an abstract machine that runs CPS-converted programs cannot be considered properly tailrecursive according to Clinger's definition if continuation closures are simply created with the lexical environments for all variables. Furthermore, an abstract machine that employs neither explicit environments nor continuations is also improperly tail-recursive. This paper discusses the above issue and also proposes new techniques to implement a properly tail-recursive Scheme interpreter in an extended C language by following space-efficiency based definitions of proper tail recursion. In our approach, a program is not converted into CPS. The primary concept is to avoid stack overflow by creating a space-efficient first-class continuation represented as a list containing only the "Frame" objects necessary for the rest of the computation and immediately invoking the continuation. We use a language mechanism called "L-closures" to access the contents of the execution stack as values of legal data structures and variables for implementing garbage collection and capturing continuations. |
| Starting Page | 65 |
| Ending Page | 72 |
| Page Count | 8 |
| File Format | |
| ISBN | 9781450304702 |
| DOI | 10.1145/1869643.1869651 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2010-10-19 |
| Publisher Place | New York |
| Access Restriction | Subscribed |
| Subject Keyword | Extended c languages Proper tail recursion Continuations |
| Content Type | Text |
| Resource Type | Article |
