[Scheme-reports] Fwd: Comments on draft 6 about call/cc

[Alex Shinn <alexshinn@x>]

A forwarded message from Oleg.


---------- Forwarded message ----------
From:  <oleg@x>
Date: Mon, Feb 27, 2012 at 1:56 PM
Subject: Re: Comments on draft 6 about call/cc
To: alexshinn@x
Cc: scheme-reports <scheme-reports@x>



Hello!

       Thank you indeed for such detailed comments. Since your
comments have touched so many different issues, let me reply to them
in different messages. In this message I'd like to comment on the
following:

> With mutation, call/cc can implement delimited continuations.  The
> inverse is not so - delimited continuations can't implement call/cc
> nor many uses of it such as amb.
>
> Thus call/cc makes Scheme strictly more expressive than delimited
> continuations.  Since it can be used to implement delimited
> continuations as a library, it is preferable from a theoretical
> standpoint.  From a practical standpoint implementations are free to
> implement the delimited conts more efficiently (and in fact use the
> same infrastructure to implement call/cc by wrapping a delimiter
> around the whole program).  So in the long term I think it makes the
> most sense to provide both, treat call/cc as more fundamental, yet
> encourage use of delimited conts wherever possible.

The implementation of delimited control in terms of call/cc is much more
complex and subtle than it appears from Filinski's code. If we wish to
use native Scheme exception handling, then delimited control cannot be
portably implemented in terms of call/cc at all. I further argue that
in practice call/cc captures a delimited continuation, and hence is
implementable with shift.

First recall that Filinski expression did not take into account
dynamic environment such as parameters and exceptions. A limited form
of dynamic environment existed in earlier Schemes (e.g,
current-input-port). R7RS has these forms explicitly. One can give a
very simple operational semantics of exceptions and dynamic
binding. Informally, the semantics will associate exception handling
(or dlet) to some parts of the continuation (stack). Incidentally,
this is how exception handling is commonly implemented. (Racket uses
such a semantics explicitly, btw, to reason about control and
environment). Since delimited control captures the prefix of the
continuation, it should likewise capture the associated exception
handlers. Why this is a reasonable position?  There are _practical_
reasons for that, and our ICFP 06 paper and the code showed many
examples. If you implement shift/reset in terms of call/cc and use
dynamic binding facilities of Scheme (such as provided by the
parameterize SRFI at the time of the writing, which is now part of
R7RS) then several confusing things happen.

First, Filinksi code has a memory leak. If we fix the memory leak using
trampolines,  the result of the program changes. So, we no longer have
one `canonical' implementation of delimited control in terms of
call/cc. Subtle details such as trampolining become exposed.

There are far bigger practical problems. See the slides of Chung-chieh
Shan's ICFP06 talk
       http://www.cs.rutgers.edu/~ccshan/dynscope/talk.pdf

particularly slide 31 and the ones leading to it. A program
uses delimited control to implement generators to make enumeration over
a file convenient. The program relies on exception handling to make
sure the file is always closed when the enumeration finishes,
normally or abnormally. If you use Filinksi implementation of
shift/reset and native facilities for exceptions (we use many versions
of Scheme plus SML plus OCaml), the file may remain unclosed. One may
say this is a bug -- a very subtle bug.

See slide 33 of the talk for the overview of the problem.

There are two solutions. We may accept Filinksi definition of shift in
terms of call/cc and mutation -- but then we have to re-implement our
own exception handling and dynamic binding forms, in terms of
shift. The ICFP06 paper mainly described that solution. Thus we are saying
to the users: your Scheme system may have dynamic binding and exception
handling; R7RS has exception handling and dynamic binding. *DON'T USE
THEM*. Use our forms. I guess many people will find a problem with
such an advice, recommending them not to use the facilities provided
in the standard.

The paper mentioned an alternative: if we wish to use native exception
handling and dynamic binding, we have to find a different expression
for shift. Filinksi expression no longer applies. Alas, the new
expression for shift relies on the ability to capture a part of a
dynamic environment and splice it in. None of the Scheme standards
provide the needed primitives. I have implemented the alternative
solution specifically for Scheme 48 (which doesn't directly provide
the needed primitives either. Fortunately, it was possible to convince
some of its internal functions to do the desired things). The ICFP06
paper's code archive has the code.


Thus, if some form of delimited control has to be provided, it has to
be provided as a primitive. We can't in general rely on the call/cc
plus mutation. Racket has took exactly that approach (described in an
ICFP07 paper).

> With mutation, call/cc can implement delimited continuations.  The
> inverse is not so - delimited continuations can't implement call/cc
> nor many uses of it such as amb.

I am yet to come across any practical use of specifically undelimited
continuations at all. I came to believe that call/cc per se has no
practical use. I am intrigued by your mention of amb: certainly amb
can be expressed using delimited control, I've done it many times in
many languages. Could you send me an example of using amb that you
think must use undelimited control?

Finally, practically speaking call/cc captures a delimited
continuation anyway. Many Scheme systems put an implicit reset around
the REPL. (When a debugger is entered, the reset is put around it as
well. If a Scheme provides a threading facility, sometimes implicit
resets are placed around threads.)


For example, in Petite Chez:

(let ((k0 #f))
 (call/cc (lambda (k) (set! k0 k)))
 (display "OK") (newline)
 (k0 #f))

That code prints the unending stream of OK.

Now, I change the code to put each operation on its own line
(evaluated by its own REPL).


(define k0 #f)
(call/cc (lambda (k) (set! k0 k)))
(display "OK") (newline)
(k0 #f)

The result:
OK
#f

So, call/cc has captured the identity continuation. Not only
undelimited continuations have no practical use -- undelimited
continuations don't even exist in practice. In practical systems,
call/cc captures delimited continuation, which can certainly be
implemented with shift.

       Cheers,
       Oleg

P.S. If my message doesn't show up in the list archive, could you
forward it? Thank you.

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports