This essay Continuations in TLS Scheme has a total of 1988 words and 11 pages.
Continuations in TLS Scheme
Implementation of Continuations in TLS Interpreter
Adam Ibrahim, Miguel Rodriguez, Kaitlyn Chait
Table of Contents
Continuations are defined as first class values that contain abstractions of control states of a program. In containing a state of a program, a procedure can use the pointer to a certain state and refer to the evaluation at that point. Our main goal throughout this project was to develop a strategy to implement continuations successfully in TLS Scheme.
We gave a skeleton implementation of continuations in TLS Scheme in order to get the feel for how continuations would fit into the language. We found that a new datatype was necessary, as even with the skeleton implementation, we couldn't fit the evaluation of a continuation into either primitive functions or non-primitive functions, despite them being quite similar.
The skeleton implementation just guides TLS Scheme toward R5RS continuations, and uses those continuations as the continuation value. Our goal was to create actual continuation values with other values inside, in much the same way that function values were handled in TLS Scheme for non-primitive functions. The information necessary to work out the evaluation of non-primitives were all values that one using the interpreter could see; we wanted to do the same for continuations.
In order to support and test this skeleton functionality, we needed to make the following additions to TLS Scheme:
Addition of the following arithmetic/comparison functions:
Add: addition of two integers
< : Integer comparison, check if one integer less than another.
Begin: A special form which evaluated a sequence of expressions, similar to R5RS begin. This was mainly for making interesting test functions to tease out the behavior of continuations which could run in both R5RS and TLS Scheme.
Addition of call/cc as a primitive to TLS Scheme
Addition of a continuation datatype, which is a list whose first entry is the atom ‘continuation and whose second entry is an R5RS continuation.
Addition of apply-continuation, which evaluates the meaning of a continuation with an argument. This applies the continuation to the given argument, which causes a jump to a different state of the interpreter.
Our implementation of the call/cc primitive mirrors the call/cc function in R5RS: TLS Scheme's call/cc primitive function takes a single non-primitive function value as an argument. It then makes a call to R5RS call/cc to obtain the current continuation from underlying R5RS; it then creates a TLS Scheme continuation value out of the R5RS continuation, and then applies that value to the non-primitive using apply-closure. That completely mirrors the functionality of R5RS call/cc, which takes a single function as an argument, then applies that function to the current continuation.
Figure 1: Skeleton implementation of call/cc in TLS Scheme. It makes a call to R5RS scheme's call/cc, then translates the R5RS continuation into a TLS Scheme continuation, then applies the argument non-primitive to the TLS Scheme continuation.
We decided that we needed some form of benchmarking for our work. We needed to find bugs in our skeleton implementation, and test it against R5RS's behavior. We would need that even more as we worked on a more transparent implementation of continuations in TLS Scheme. We decided that a proper test should be recursive, since continuations preserve chains of deferred calls. Our test function was remove-last: a two argument function which takes a list of atoms and an atom, then returns a copy of the list with the last occurrence of the atom removed, if such an occurrence should exist.
Figure 2: Our test function for testing continuations. This expression is valid in both R5RS and TLS Scheme, so we can use it to compare the behavior of the two side-by-side.
In order to successfully implement continuations in TLS Scheme we need to consider two tasks: 1. Implementing continuations as a datatype 2. Successfully implementing a program counter reference to a location within a program.
Continuations, as a data - type, are not implemented in the interpreter for TLS Scheme, we have to go in and create one. Our new implementation of TLS Scheme involved a third parameter in the meaning definition in that we need to add a continuation value:
(lambda (e table)
((expression-to-action e) e table)))