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

[Alex Shinn <alexshinn@x>]

Forwarding to the list.

Thank you very much for your comments, Oleg!

I'll reply separately.

-- 
Alex


---------- Forwarded message ----------
From:  <oleg@x>
Date: Mon, Feb 20, 2012 at 2:04 PM
Subject: Comments on draft 6 about call/cc
To: alexshinn@x



Hello!

       I have sent the following message to the discussion list on
Friday. I think it is still in the moderator queue, or got
discarded. I would appreciate it if the article could be posted
somehow.

       Thank you!
       Oleg

> Date: 18 Feb 2012 04:08:11 -0000
> From: oleg@x
> To: scheme-reports@x
> Subject: R7RSWG1 Proposal: Clarifying and potentially removing call/cc

I have a very positive impression of the R7RS draft: it retains the
elegance and spirit of R5RS adding clarifications and well-chosen set
of consistent and proven extensions. I'd like to congratulate the
authors and editors on the great work.

I'd like to draw attention to one part of R5RS that was in need of
clarifications or revisions -- call/cc. It is one of the most
confusing features of Scheme, for a good reason: it is a wrong
abstraction. The new features of R7RS, exceptions and parameters --
make clarifications or revisions more urgent. The interactions of
call/cc with exceptions and dynamic binding are highly non-trivial and
confusing, leading to unexpected consequences such as memory leaks,
exceptions handled with unexpected handlers or the files that should
be closed remaining open. At the very least, I would like to see the
Report warning about the problems caused by call/cc and advising
against its use unless strictly necessary. Ideally, I'd like to see
call/cc relegated to optional features, with opening a discussion for
better abstractions. (I have a few in mind.)

Let me give the background for my proposal. Removing call/cc from
Scheme has been discussed before, most notably by Matthias Felleisen
back in 2000. Matthias Felleisen has written a thesis on formalizing
control in Scheme, he knows very well the power and danger of control.

       http://srfi.schemers.org/srfi-18/mail-archive/msg00013.html

The primitive call/cc has been added to Scheme when little has been
known about expressiveness of undelimited and delimited
continuations. [I'm generous: a good alternative -- generators -- and
their efficient implementations have been known before Scheme was
invented.] Now we know that capturing undelimited continuations gives
us, per se, little power. We cannot even implement exceptions -- let
alone more interesting effects such as state or non-determinism --
without using other features such as mutation. Further references on
the limited expressiveness of undelimited control can be found on my
summary page
       http://okmij.org/ftp/continuations/undelimited.html

Using call/cc has many practical drawbacks -- for example, huge
resource leak. Capturing the whole continuation (where only a prefix
is really needed) prevents objects referenced from the unneeded suffix
of the continuations from being garbage collected. Trampolining has to
be used to avoid memory leak. Alas, trampolining does change the
semantics of programs (see below). The very need for trampolining
already points out that call/cc is a wrong and leaky abstraction.

All the uses of call/cc in practical programs that I'm aware of are
better served by more appropriate operations. For example, it has
been frequently observed that in most all the cases a captured
continuation is invoked at most once. As shown by Dybvig et al and
Feeley, one-shot continuations are much more efficient to implement.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.3782

(I must mention in passing that using call/cc for threads and
co-routines has an unacceptable cost due to dynamic-wind. That has
been the reason for notable opposition to dynamic-wind). The sole, it
seems, use case for multi-shot continuations is non-determinism. A
better abstractions for non-determinism, such as generators, have long
been known in Icon and Scheme predecessors.

R7RS adds dynamic binding (parameterize) and exceptions, which have
non-trivial and highly confusing interaction with control operators.
The ICFP06 paper Delimited Dynamic Binding
       http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding

See Section 4.1 of the paper (which shows that trampolining is not
semantically transparent) and the code described
       http://okmij.org/ftp/packages/DBplusDC-README.txt

for many Scheme systems. The code uses call/cc (for co-routines) and
various implementations of dynamic binding and exceptions. Please run
the code for yourself to see the unexpected results. The paper argues
that rather than using call/cc to implement needed abstractions such
as co-routines, threads or generators, these needed abstractions have
to be provided as primitives, with well-defined interaction with
dynamic binding and exceptions.

Ironically, the illustrating examples of call/cc in R7RS [p49 of the
draft 6] are better implemented with now provided exceptions. The
draft retains the phrase [p49, middle of the first column]
from R5RS that ``A common use of
call-with-current-continuation is for structured, non-local exits from
loops or procedure bodies''. I'd like to propose to add the phrase
``Non-local exists are so common that R7RS provides better tools for
that -- exceptions.''

My second suggestion is to modify the phrase
``The call-with-current-continuation procedure allows Scheme
programmers to do that by creating a procedure that acts just like the
current continuation.'' [p 49, middle of the first column]
to say that the procedure that acts like a current continuation is,
like the error or raise procedures, is special in that it never
returns and so cannot be meaningfully composed.

I would like the discussion of call/cc to mention non-trivial
interactions of call/cc with exception handlers and dynamic binding
(parameters) and the danger of memory leak.

My bigger suggestion is to remove call/cc and dynamic-wind from the
base library into an optional feature. I'd like to add the note
inviting the discussion for more appropriate abstractions to
supersede call/cc -- such generators, for example.

       Cheers,
       Oleg

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