Re: Non-stack-copying call-with-current-continuation?

[Mark H Weaver]

David Kastrup <address@hidden> writes:

> Andy Wingo <address@hidden> writes:
>
>> On Sun 04 Mar 2012 13:01, David Kastrup <address@hidden> writes:
>>
>>> The global symbol space is a different identity space than heap
>>> equality, and it never gets garbage collected: the lifetime of a
>>> gensym is eternal.
>>
>> This is not true in Guile, where symbols can be garbage collected.
>
> The symbol name is not garbage collected.  That is the difference
> between gensym and make-symbol.

Integers are plentiful and cheap.  Anyway, there's a well-known
"Efficient Gensym Hack" where gensyms are given names lazily.  We
haven't yet implemented that in Guile, but I hope to add it before 2.2.
With that optimization, if you never ask for the name of a gensym
(e.g. by printing it) then it is never assigned a name or even a number.
Dybvig reports that in Chez Scheme, this optimization made gensym 25
times faster.

Also, in Guile 2, prompt tags need not be symbols.  Anything that can be
compared with 'eq?' will work.

>>> And frankly: the manual talks about prompts being composable and
>>> gives an example which seems utterly wrong to me since it does not
>>> actually abort a computation but rather half-finishes it.  It is
>>> unclear what part of the computation will finish and what will
>>> complete.
>>
>> That is an interesting point.  I guess there are two ways of answering
>> it.  One is to note that in Scheme, it's difficult in general to
>> determine whether a computation is finished or will finish, because of
>> call/cc.
>>
>> But you ask about a specific point, here: an abort to a prompt is
>> basically boils down to a longjmp to the prompt's handler.  The
>> partial continuation is logically passed as an argument to the
>> handler.
>
> But where does the "partial continuation" start and where does it end?

A partial continuation captures the stack from the prompt to the abort.
If you later call the partial continuation with some values, those
values will be returned by 'abort-to-prompt', and the computation will
continue until it returns to the prompt, at which point the partial
continuation will return the values returned to the prompt.

An approximate way to think about it is as follows.  In the following:

  (call-with-prompt
   'foo
   (lambda () (let ((x (abort-to-prompt 'foo))) (+ 34 x)))
   (lambda (k) k))

The returned partial continuation will be equivalent to the following
procedure:

  (lambda xs (let ((x (apply values xs))) (+ 34 x)))

To a first (very rough) approximation, you can imagine that you took the
body of the thunk passed to 'call-with-prompt', wrapped it within
(lambda xs ...), replaced the 'abort-to-prompt' that was invoked with
(apply values xs), and that's sort of what the partial continuation acts
like.

How does this approximation fall short?  First of all, it's not quite
right to replace the 'abort-to-prompt' with (apply values xs), because
if that 'abort-to-prompt' is called again (e.g. if it's within a loop)
then it will abort again.  More importantly, when you call a partial
continuation, it jumps directly to the 'abort-to-prompt', rather than
re-running the outer layers of code.  Any mutable local variables bound
between prompt and abort will have whatever values they were last set!
to, rather than being rebound.

> If I am doing a "longjmp to the prompt's handler", how can it be that
> the calling stack frame inside of the thunk that is supposed to be
> exited can finish a calculation?

If the compiler cannot prove that the partial continuation is ignored by
the handler passed to 'call-with-prompt', then the stack segment between
the prompt and abort must be copied.  If the partial continuation is
later called, that stack segment will be copied back.

> Where is the difference between
>
> (+ 34 (abort-to-prompt 'foo))
>
> and
>
> (let ((x (abort-to-prompt 'foo))) (+ 34 x)) ?
>
> Why is the first allowed to complete and return a result, and the second
> (presumably) not?  Or _if_ the second is allowed to complete, what does
> "abort" in "abort-to-prompt" even mean?

What makes you think that the second would not be allowed to complete?
In both of these cases, assuming that what you've written above is the
entire body of the thunk passed to 'call-with-prompt', the partial
continuation will be equivalent to (lambda (x . rest) (+ 34 x)).

> All this does not really make discernible sense to me.  Whereas call/ec
> has rather clear semantics and usage.  The one thing that is not
> self-evident is its behavior in case of misuse, namely when it is asked
> to do a job only call/cc can.

I agree that Guile should have 'call/ec' (ideally backed by an efficient
VM instruction), and that for many purposes 'call/ec' is more natural.
However, it should be noted that prompts are strictly more powerful than
'call/ec', and that 'call/ec' can be implemented easily and efficiently
using prompts.

For now, you can use this definition:

  (cond-expand
   (guile-2 (define (call-with-escape-continuation proc)
              (let ((tag (make-prompt-tag "call/ec")))
                (call-with-prompt
                 tag
                 (lambda () (proc (lambda xs (abort-to-prompt tag xs))))
                 (lambda (k xs) (apply values xs))))))
  
   (guile (define (call-with-escape-continuation proc)
            (let ((key (gensym "call/ec")))
              (catch key
                (lambda () (proc (lambda xs (throw key xs))))
                (lambda (key xs) (apply values xs)))))))
  
  (define call/ec call-with-escape-continuation)

      Mark