[plt-scheme] cost of closure?

YC wrote:

> I've heard that Scheme 
> doesn't keep variables on the stack, but want to verify. 

The explanation is a little involved. First the
concept of call stack. Consider:

   (define (f x) (g (+ x 1))
   (define (g y) (h (+ y 2))
   (define (h z) (+ x 3))
   (f 0)

Conceptually f calls g, which calls h. So we have
a stack of functions calls here. In most languages
the conceptually call stack is implemented as an
actual stack.

That strategy can't be used naïvely with Scheme.
due to call-with-current-continuation. The
problem is that call/cc allows a function to
return more than once - and thus conceptually
you get a call *tree* instead of a call stack.

In a simple Scheme implementations the tree is
represented as (you guessed it) a tree stored
in the normal garbage collected heap.

However it is possible to use a stack to store the
current branch of the call tree and then do
some trickery when control transfers to another
branch [actually a little trickery is needed prior
to this too].

In short, you can't say "Scheme doesn't keep variables
on the stack" because some implementations do and
others don't-

The canonical [I believe] reference is:

   "Three Implementation Models for Scheme"
   by R. Kent Dybvig.

It is very well-written and explains everything
in detail. See especially chapter 3 and 4.

-- 
Jens Axel Søgaard