From ...
Date: Wed, 7 Sep 88 12:27:15 EST
From: ...
To: franco
Subject: Re:  Generalizing
Status: R

There is a standard philosohpy by the implementors of Scheme that
they want to be competitive with C/Pascal, etc.  Thus they are
willing to charge exhorbitantly for features that are not available
in these languages.  Here is a quote from a dissertation I am reading
this morning:

"The important thing to recognize is that Pascal and C are really just
restricted subsets of Scheme, in particular those parts of Scheme which
can be efficiently implemented using conventional compiler technology!
It seems reasonable that a Scheme program that uses only the restricted
subset should have the same performance as the same program written in
Pascal.  What is needed is a "pay as you go" implementation; the most
general language constructs should be implemented as efficiently as
possible, but should not reduce the efficiency of less general constructs.
In other words, a simple loop written in Scheme should not run more slowly
than it would just because Scheme allows first-class procedures and
continuations."

ORBIT: An Optimizing Compiler for Scheme
David Andrew Kranz
Yale U
DCS/RR-632
February, 1988

He goes on to say:  (that was page 11)
On page 70-71

The Scheme procedure call-with-current-continuation is a very powerful
construct that can be very expensive to implement.  Because this
language feature allows continuations to be manipulated by the
programmer in arbitrary ways, continuations cannot, in general, be
treated in a stack-like manner.  The most straightforward approach is
to actually heap-allocate continuations.  This strategy is
prohibitively expensive in both time and space, {\it even if no call
to call-with-current-continuation} {\it are ever made}.  An
alternative is to "freelist" continuations (stack frames).  This
improves the heap storage problem but still must always be paid for.

The other alternative, the one used here, is to have a single stack.
When a continuation is captured by a call to {\tt call-with-current-
continuation}, the active portion of the stack is copied into the heap.
Each time the continuation is invoked, the stack which was copied into
the heap is copied back into the stack.  The advantage of this strategy
is that the presence of this language feature incurs almost no cost,
unless it is actually used.  The only restriction imposed is that once
an object is allocated on the stack, it must not be updated to ensure
that all stack references are consistent whenever a continuation is
invoked.  In particular, this means that cells corresponding to
variables in stack closures may not be collapsed.  The disadvantage
of the stack copying strategy is that the copying and copying back of
stacks can be very expensive if they are large.

....

The approach (of Scheme 84) which is not quite up to the standard
(the language keeps changing and I haven't had time to stay up with
all the changes) is that we allocate the continuations in the heap
and all the closures in the heap, as well.  In Chez, when I looked 
last, clsoures were in the heap, but continuations were on the stack
uless they were captured, then they went to the heap s well.  Kranz
can put many closures on the stack through program analysis.  Does
that make Chez brain-damaged?  I don't mind if you don't use Scheme 84,
but ... and I cannot use Chez for our research because it does not
support, F, and partial continuations.  ... is still using just
Scheme 84.  Without Hygienic Macros in Chez, he cannot do anything
that he wants to do.  He has even implemented it in Common LISP.
I think Chez is a super implementation, but it's efficiency is at
the cost of making call/cc inexpensive.  Because the vendors want to
say to the world "Look we aren't slow on your simple-minded programs,
therefore why not use us."  I don't blame the vendors, but if there
is a G-d we will discover a way to make everything fast and make the
vendors happy too.