Re: continuation efficiency

[Jim Blandy]

address@hidden (Thomas Bushnell, BSG) writes:
> I.  Is A substantially worse than B:
> 
>     A: (call/cc (lambda (c) (do-something)))
>     B: (do-something)
> 
>     (Note that the continuation in A is never used.)

It's been forever since I looked at this part of Guile, but as far as
I know, Martin's answers are correct.  The procedure call/cc passes to
its argument refers to its own copy of the entire call stack, so
simply creating that procedure is rather expensive.  Call stacks are
usually [hands waving] only a few kilobytes, but still, it's more
expensive than the obvious implementation in an implementation that
allocates activation frames in the heap.

The sense in the Scheme community is that allocating frames in the
heap is slower for typical code than using a stack because:
- frames are created often, so you GC more often
- call stacks have good locality of reference

Dybvig has published clever ways to get the locality and low-gc
advantages of call stacks, but keep continuation creation overhead
constant.  When I talked with Bill Rozas about it, he said he
considered the problem closed, given Dybvig's solution.  Not that
Bill hasn't had some unusual opinions in the past...

But Guile doesn't use Dybvig's solution.  Guile considers it more
important to interoperate in a simple way with C code, and its call/cc
implementation (like half the rest of its design) pretty much follows
from that.


> II. Is A substantially worse than B:
> 
>     A: (call/cc (lambda (c) (do-some-things) (c do-something)))
>     B: (begin (do-some-things) (do-something))
> 
>     (Note that the escape procedure is only used as a tail call in the
>     argument to call/cc.)

Yes.  I assume you meant B to be:

        (begin (do-some-things) do-something)

> Does the following expression (which runs forever) run forever, or
> does it run out of space?  (The astute will notice a connection
> between this question and number I above.)
> 
> (letrec
>   ((whizzie 
>    (lambda (argument)
>     (argument (call/cc whizzie)))))
>   (call/cc whizzie))

Are you sure this is what you meant to write?

This runs forever, and its current continuation grows in size without
bound, since the (lexically) first call to call/cc is not a tail call,
and we never return from it.  So this expression will consume all
memory on any implementation too dumb to realize that `argument' is
dead and the control structure is equivalent to:

        (letrec ((whizzie (lambda () (whizzie))))
          (whizzie))

It seems to me that figuring that out would require some pretty clever
flow analysis, and certainly some integration of knowledge about
call/cc.