Making continuations available within Axiom

A [W1] is a part of version 2 of the Axiom symbolic algebra package. The language provides a large number of relatively novel constructs, including first-class types, functions and iterators plus backward compatibility with the previous Axiom library language [JS]. As well as producing code for the Axiom system, it may also generate stand-alone programs in either Lisp or C. The dialect of Lisp that the compiler produces is heavily abstracted using macros, and has been designed in such a way that the macros may be modified for a Scheme system.

In order for A to produce both C and Lisp code, it first produces an intermediate representation called FOAM (for more details of the compiler's design, see [W2]). FOAM is a very small language which can be mapped to a particular target language. Both C and Lisp host languages have been implemented, but in practice the majority of imperative computer languages contain a FOAM-like subset. This makes the compiler retargetable to other host languages, which may provide other control mechanisms.

A also includes a foreign function interface which can call functions from the hosting language, and allows one to build abstractions over the imported functions. For example, the call/cc function and the continuations it produces may be turned into a type by importing call/cc into the compiler namespace, and wrapping a type around it. Thus we declare a type with the following signature:

    Continuation(T: Type): with {
        callWithCC: (% -> T) -> T;
        apply:      (%, T)   -> Exit;
    }

This states that Continuation is a function, which when applied to a type (called T), returns a new type which has two operations: apply and callWithCC. The apply operation invokes a continuation. The type Exit indicates that the call never returns -- in this case execution continues at the point of the corresponding callWithCC call. Calling this function apply indicates that using a continuation in a function position will call this function -- this is in order to mimic the Scheme syntax. In order to implement callWithCC, we have to write a small piece of Scheme which can call back the function passed to it. The function is an Axiom-level function, not a Scheme function, so we have to call it via a macro (CCall) from the FOAM package.

    (define (schemeCallWithCC clos)
          (call/cc (lambda (c)
                    (CCall clos c))))

We then incorporate this code into the definition of Continuation as follows (continuing from the declaration above):

    Continuation(T: Type): with {
        callWithCC: (% -> T) -> T;
        apply:      (%, T)   -> Exit;
    }
    == add {
        import { schemeCallWithCC: (% -> T) -> T }
               from Foreign Lisp;

        callWithCC(fn: % -> T): T ==
               schemeCallWithCC fn;

        ...
    }

The import statement asserts that the function schemeCallWithCC exists, has a particular type, and should be called as a Lisp function. Note that from the compiler's point of view the Scheme language is identical to Lisp.

These definitions now allow us to use continuations as first class objects within A .

We also implement a slightly modified version of continuations in terms of fork -- in this case, we import functions from C, and have to do more wrapping in order to achieve the desired semantics, but the declaration above is identical, and so the code using the Continuation type does not need to be changed.

The relative costs of the two implementations are hard to compare -- in the Scheme case, the act of taking a continuation is not too high unless there is a large amount of dynamic data. However, the cost of running any Scheme code is often much greater than that of running the same code under C. This is partially due to the implementation of loops in Scheme, which had to be hand crafted, and also because Scheme is a dynamically typed language, and therefore spends much time checking types. C, however runs code very fast, but a call to fork has to be carefully guarded, as this may double the amount of memory taken by the program. This doubling is worst case, as many operating systems only replicate information after a process has written to a page, which implies that we only need copy the working set of pages in the program. The overhead can also be reduced by ensuring that no more than a fixed number of processes are active at a time -- this ensures that the amount of space needed is proportional to the depth of the splitting tree, rather than the maximum width, at the worst case.