Re: The fundamental concept of continuations

[Rob Warnock]

David Kastrup  <dak@gnu.org> wrote:
+---------------
| George Neuner <gneuner2/@/comcast.net> writes:
| > Upward continuations can be stack implemented.  On many CPU's, using
| > the hardware stack (where possible) is faster than using heap
| > allocated structures.  For performance, some Scheme compilers go to
| > great lengths to identify upward continuations and nested functions
| > that can be stack implemented.
| 
| There is a Scheme implementation (I keep forgetting the name) which
| actually does both: it actually uses the call stack but never returns,
| and the garbage collection includes the stack.
+---------------

You're thinking of "Chicken Scheme":

    http://www.call-with-current-continuation.org/

Chicken Scheme is actually using the C call stack *as* the heap[1],
and thus all its continuations are *heap*-allocated, and thus
not actually "stack-allocated" at all.

But that's not what George Neuner is talking about, as I read it,
but rather probably about such things as Kent Dybvig's PhD thesis:

    http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
    "Three Implementation Models for Scheme"
    R. Kent Dybvig, UNC Chapel Hill, 1987 (thesis) (190pp)
    ...
    Chapter 4: The Stack-Based Model
    ...
    Early Scheme implementors believed that because of the need to
    support first class functions, the standard techniques used for
    block-structured languages were not suitable for Scheme. The
    need to optimize tail calls and support continuations further
    convinced early implementors that the standard stack techniques
    were unsuitable. However, as this chapter will show, these
    techniques can be made to work for Scheme with a few modications.
    The resulting implementation model allows most function calls to
    be performed with little or no allocation, and allows variable
    references to be performed in one or two memory references.
    Heap allocation remains necessary to support closures, assigned
    variables, and continuations. Since function calls and variable
    references are faster and heap allocation is limited, the running
    time for most programs is greatly decreased.
    ...


-Rob

[1] As suggested in:

       http://home.pipeline.com/~hbaker1/CheneyMTA.html
       "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A"
       Henry G. Baker (1994)

-----
Rob Warnock                     <rpw3@rpw3.org>
627 26th Avenue                 <URL:http://rpw3.org/>
San Mateo, CA 94403             (650)572-2607