How to implement the continuation?

Question

I am working on a Schema interpreter written in C. He currently uses the C runtime stack as his own stack, which is a small issue with executing continuations. My current solution is to manually copy the C stack to the heap, and then copy as necessary. Besides the fact that it is not standard C, this solution is hardly ideal.

What is the easiest way to implement continuations for a Schema in C?

Answer 1

I remember reading an article that might help you: Cheney on the MTA :-)

Some implementations of the Schema that I know of, such as SISC , allocate their call frames on the heap.

@ollie: you don’t need to do an upgrade if all your call frames are on the heap. Of course, there is a tradeoff in performance: the rise time, as well as the overhead required to distribute all the frames on the heap. Perhaps this should be a custom runtime parameter in the interpreter. :-P

Answer 2

A good summary is available in the Implementation Strategy for first-class continuums , an article by Klinger, Hartheimer and Ost. I recommend looking, in particular, the implementation of Chez Scheme.

Copying copies is not that difficult, and there are a number of well-understood methods to improve performance. Using heaped frames is also pretty simple, but you compromise between creating overhead for a “normal” situation where you are not using explicit extensions.

If you convert the input code to a Continued Transfer Style (CPS), you can get away with deleting the stack altogether. However, although CPS is elegant, it adds another processing step in the interface and requires additional optimization to overcome certain performance implications.

Answer 3

If you are starting from scratch, you really need to move on to transition style conversion (CPS).

Good sources include LISP in Small Chunks and Mark Fili's Scheme in a 90-minute presentation .

Answer 4

It seems that Dibwig's thesis is not mentioned so far. It is a pleasure to read. The heap-based model is easiest to implement, but the stack-based model is more efficient. Ignore the string model.

R. Kent Dibwig. "Three implementation models for the circuit." http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Also check out the implementation docs on ReadScheme.org. https://web.archive.org/http://library.readscheme.org/page8.html

The summary is as follows:

This dissertation presents three models for implementing a circuit programming language. The first is a heap-based model used in one form or another in most Scheme implementations today; the second is a new stack-based model, which is much more efficient than a heap-based model in most programs; and the third is a new string model intended for use in the multiprocessor implementation of the Scheme.

The heap-based model highlights several important data structures on the heap, including actual parameter lists, binding environments, and call frames.

A stack-based model distributes the same structures on the stack whenever possible. This results in less heap allocation, fewer memory references, shorter instruction sequences, reduced garbage collection, and more efficient use of memory.

The string model places versions of these structures directly in the program text, which is presented as a string of characters. In the string model, Scheme programs are translated into the FFP language, designed specifically to support Scheme. Programs in this language are executed directly by the FFP machine, a multiprocessor computer for cutting lines.

A stack-based model has immediate practical benefits; This is the model used by the author of the Chez Scheme system, a high-performance implementation of Scheme. The string model will be useful for providing Schema as a high-level alternative to FFP on an FFP machine as soon as the machine is implemented.

Answer 5

Besides the good answers you have received so far, I recommend Andrew Appel Compiling with Continuations . It is very well written and, although not directly related to C, it is a source of really good ideas for compiler authors.

The Chicken Wiki also has pages that you will find very interesting, such as the internal structure and the compilation process (where CPS is explained using a real compilation example).

Answer 6

The traditional way is to use setjmp and longjmp , although there are caveats.

Here is a good enough explanation

Answer 7

Examples you can see are: Chicken (an implementation of a circuit written in C that supports continuations); Paul Graham In Lisp - where he creates a CPS transformer to implement a subset of extensions in Common Lisp; and Weblocks, a continuation -based web framework that also implements a limited form of continuations in Common Lisp.

Answer 8

Continuity is not a problem: you can implement those that have higher order regular functions using CPS. The problem with the naive stack distribution is that tail calls are never optimized, which means you can't be a circuit.

The best current approach to the spaghetti scheme on the stack is to use trampolines: essentially an additional infrastructure for handling non-C-like calls and exits from procedures. See Trampolined Style (ps) .

There is some code illustrating both of these ideas.

Answer 9

Continuations mainly consist of the saved state of the stack and CPU registers at the point of context switches. At the very least, you do not need to copy the entire stack to the heap when switching, you can redirect the stack pointer.

Continuations are trivially implemented using fibers. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 , The only things that need to be carefully encapsulated are the values ​​for passing and returning parameters.

On Windows, fibers are run using the CreateFiber / SwitchToFiber call family. on Posix-compatible systems, this can be done using makecontext / swapcontext.

boost :: coroutine has a working implementation of coroutines for C ++, which can serve as a starting point for the implementation.

Answer 10

As soegaard noted, R. Kent Dybvig. "Three Implementation Models for Scheme" remains the primary reference R. Kent Dybvig. "Three Implementation Models for Scheme" R. Kent Dybvig. "Three Implementation Models for Scheme" R. Kent Dybvig. "Three Implementation Models for Scheme" R. Kent Dybvig. "Three Implementation Models for Scheme" . R. Kent Dybvig. "Three Implementation Models for Scheme"

The idea is that the continuation is a closure that retains its evaluation control stack. The control stack is needed to continue the evaluation from the moment the continuation was created using call/cc .

Often, a continuation call makes the execution time long and fills the memory with duplicate stacks. I wrote this stupid code to prove that the circuit is failing in the mit circuit,

The code sums the first 1000 numbers 1+2+3+...+1000 .

 (call-with-current-continuation (lambda (break) ((lambda (s) (ss 1000 break)) (lambda (sn cc) (if (= 0 n) (cc 0) (+ n ;; non-tail-recursive, ;; the stack grows at each recursive call (call-with-current-continuation (lambda (__) (ss (- n 1) __))))))))) 

If you switch from 1000 to 100 000, the code will spend 2 seconds, and if the number of input is increased, it will fail.

Answer 11

Use an explicit stack instead.

Answer 12

Patrick is right, the only way you can really do this is to use the explicit stack in your interpreter and raise the corresponding stack segment to the heap when you need to convert it to continued.

This is basically the same as for supporting closures in the languages ​​that support them (closures and continuation are somewhat related).