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

[Ray Dillinger <bear@x>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 02/26/2012 09:46 PM, Alex Shinn wrote:
> A forwarded message from Oleg.

>> 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'm not at all convinced of this.  And there are other implementations
for amb besides the one that needs continuations.  One nice one uses
the Chinese Remainder Theorem (and a numeric binding for state) to
create a stateful  generator that iterates over all the possible
combinations one at a time. Alternatively, FP fans may use a similar
approach, but instead of a stateful generator, must use a series of
thunks which each generate one state and the next thunk. The approach
is equivalent.

This can be used to generate a lazy list with 'require' just being the
filter on the list.  And for my money trading on a bit of number
theory is drastically less confusing than the interaction of
multiple undelimited continuations.

>> 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.  

Ergh.  No....  it could be used to implement delimited continuations
as a library, *IF* it didn't have to fight with implementations of
dynamic environments and exception handling, possibly also using call/cc.

The problem is that the two different models of non-local control
flow (exceptions, continuations) don't really play nice with
each other.  Especially in the presence of a dynamic environment,
and especially if that dynamic environment is also implemented
using continuations.

I'm increasingly convinced that undelimited continuations with
dynamic-wind is a problem.  The features you can implement in
terms of it (amb, continuations, exceptions, dynamic
environments) do not easily or reasonably compose.

That is, if you implement each feature by itself in what
seems to be the most straightforward way, and then try to
use all the features together, there are generally emergent
bugs in the combination not present in the implementation of
any one of the features.

While it *may* be possible to come up with a combined solution
that implements all of these features together, the fact is
that independently-created, straightforward implementations of
features using call/cc do not compose. That means that call/cc
is failing to serve as a good abstraction.

And then Oleg brings out some serious specific problems, I'm
going to just repeat a few of the high points for emphasis.

Clip: Filinski code, failure to handle dynamic envs, and
      memory leak
Clip: Chung-Chieh Shan's ICFP 06 paper demonstrating
      insufficiency of exceptions to maintain invariants
      such as file closure on exit from environment when used
      in combination with dynamic-wind,
Clip: ICFP 06 paper, possible solution explained - but is
      unexpressible in scheme standard (hacked into S48 and
      Racket as primitives)
Clip: Stack-based exceptions in Racket, leaks and
      bugs exposed in standard exception system
Clip: Parameterize SRFI, reference implementation
      incompatible with exception system,

And finally....

> 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 increasingly convinced of the same thing.  It has not
functioned as a means of implementing good, composable
abstractions in practice. The more we've tried to use it to
do, the more trouble we've gotten ourselves into.

				Bear
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJPS8jdAAoJEAOzWkqOibfNn7QH/2KhLFiMX+qqBL2S9BAFGQv/
ULJrDEiEdNnBmkHnEUiYke0RxJZUP6ljwwTDKIr6NkQrGsHQtYSZunDcpwuoAYJP
DpxNIbO3he44qAEz5ZfKnIbf72C2ZFdMiwSQsIODajneWJ/avssCGdIYW1SYhAl1
o/ZtV4gL+SBIyH8zjSHYK7WDdT7b6FwDBUjedK1l7uqGv8GMT5u3Kz0YAXHU0Ol2
391968mKjCQAej+2NuSeWkTHxYsSpUxJvjdn5Z9hDC9fQ5qGjYGqWZm2xhsaHcNC
pyzczXSy0nzFp5TRnHeoIRz3tI/+bF81vV8LsAFigzIMak1h4nrm1N1Uio6nTyc=
=ekJc
-----END PGP SIGNATURE-----

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