Re: continuation efficiency

[Thomas Bushnell, BSG]

Klaus Schilling <address@hidden> writes:

> Are there any Scheme Interpreters where call-with-current-continuation is
> not slow? How can they do that?

If you implement the execution stack as a linked list, then call/cc is
trivial.

Those systems which do use a regular machine stack as the execution
stack have many clever tricks.  One is to have it be almost a machine
stack, and link machine stacks to each other instead of requiring the
whole machine stack to be there at once.  Some function returns just
pop off the machine stack and others switch to the next stack segment
in the linked chain.

Another strategy is to use Clever Virtual Memory Tricks to "copy" the
stack.

And, any good Scheme system includes a compiler that can prove things
about the dynamic extent of continuation objects and detect what's
going on, and avoid a stack copy.

For example, it's easy for a good compiler to prove that in the
following case no stack copy is necessary:

(call/cc
  (lambda (c)
    (first-task)
    (if (execute-some-test)
      (c)
      (second-task))))

It can tell this, because it knows that C is not aliased, and
therefore is only an escape continuation and never an entry
continuation.  If C is passed to some other procedure, then it needs
to look at that procedure to see if C has longer dynamic extent or
not.  But a good compiler can detect what's going on in many many
cases and DTRT.

(f course, in the example code, it doesn't even need an escape
continuation; a good compiler will turn that into:

(begin
  (first-task)
  (if (not (execute-some-test))
    (second-task)))