[racket-dev] Changing call/cc

At Wed, 29 Aug 2012 23:06:52 -0400, Asumu Takikawa wrote:
> We have a proposal for changing `call/cc` so that it interacts better
> with delimited operators and would be safe to include in TR. The
> proposal is to remove the current `call/cc` and replace it with a
> function implemented with delimited control like the following:
> 
> (define (call/cc f tag)
>   (call-with-composable-continuation
>    (lambda (k)
>     (f (lambda vs
>         (abort-current-continuation
>          tag
>          (lambda ()
>           (call-with-continuation-prompt
>            (lambda ()
>             (apply k vs))
>            tag
>            (lambda (thunk) (thunk))))))))))
> 
> (taken from collects/tests/racket/prompt.rktl)

That variant is called `call/cc-via-composable' in the tests. It's
meant for use with `call-with-continuation-prompt-for-composable',
which is why there is an extra `call-with-continuation-prompt'.

Unless I'm missing something, this simpler function should do:

  (define (call/cc f tag)
    (call-with-composable-continuation
     (lambda (k)
       (f (lambda vs
            (abort-current-continuation 
             tag 
             (lambda () 
               (apply k vs))))))))


> The motivation for this change is that `call/cc` is currently difficult
> to locally reason about. In particular, if you set up a continuation
> prompt, you would expect that either its body happily returns with no
> control effects or the handler is invoked. For example,
> 
> ;; expect a number here
> (+ 1 (call-with-continuation-prompt
>        (lambda ()   ; f is a (-> Number) function
>          (f))       ; but might have control effects
>        prompt-tag
>        (lambda (x)  ; called on abort
>          5)))
> 
> you might expect this code to always return a number if it returns.
> Unfortunately, `call/cc` can violate this expectation. In particular, if
> `f` calls a continuation captured by `call/cc` elsewhere, then it
> will erase the body code and could return, say, a string and cause an
> error. The handler is not called on a `call/cc`-based abort.
> 
> This is a problem for Typed Racket as well, since if the programmer
> can't locally reason about this code, neither can the type system
> (without extra static *and* dynamic protection).
> 
>   ***
> 
> The alternative implementation has two semantic differences that could
> potentially be an issue:
> 
>   1) The alternative `call/cc` will trigger abort handlers, which means
>      an interceding prompt with the right prompt tag could interfere
>      with a `call/cc`.
> 
>   2) The alternative `call/cc` triggers more `dynamic-wind` handlers than
>      the original `call/cc`.
> 
> I've looked into whether 1) is actually an issue. [... no ...]

I agree that (1) is probably not an issue, though I would characterize
the problem as related to prompts with abort handlers that do not
behave like the default abort handler. Those handlers are rare, and
they interact with `call/cc' even more rarely.

Minor detail: Right now, a thread's initial abort handler ignores its
argument, instead of behaving like the default abort handler. That
mismatch seems bad --- it bit me recently --- independent of keeping or
changing `call/cc'.

> I've also looked at uses of `call/cc` in the PLaneT sources. There is a
> single package (murphy/amb.plt) where I am sure the change will break
> functionality, but there's a simple workaround.

Can you say more about the example that would break?


> 2) is an issue only in code that uses `call/cc` and `dynamic-wind`
> together. This is also uncommon and there is a good delimited
> workaround: install a prompt at the point at which you want
> `dynamic-wind` handlers to stop being called.

It's possible that this is a good enough for Racket code, but I don't
quite believe it. In any case, I think we'd need a better story for
supported Scheme dialects like R5RS and R6RS. I expect that many simple
R{5,6}RS `call/cc' programs to rely on jumps within, say,
`with-output-to-file'. More generally, I think supporting R{5,6}RS
requires a `call/cc' and `dynamic-wind' that work as specified.

The solution could be to define a compatibility `dynamic-wind' that
works with the compatibility `call/cc'. Each use of `dynamic-wind'
could install a prompt with a fresh tag and record it in a continuation
mark, along with a delimited variant of the continuation up to the
preceding prompt. A `call/cc' would need to capture all of the
`dynamic-wind'-delimited continuations. Application of the continuation
would inspect marks, find the shared chain of prompts, and decide which
continuations and prompt tag to use in place of the full continuation
and default prompt tag. (In other words, automate the workaround.)

I think this combination of replacing both `call/cc' and `dynamic-wind'
would be equivalent to a smaller change to the semantics of `call/cc',
which is that it behaves as it does now if there's a shared
`dynamic-wind' between the source and target continuations, but it
behaves like your replacement `call/cc' if there's no intervening
prompt (which addresses the reasoning problem). Also, implementing the
change directly in the existing `call/cc' implementation sounds fairly
easy to me.


> Summary: `call/cc` is problematic for local reasoning about programs and
> we'd like to replace it with a version implemented with delimited
> operators. Its semantics would be slightly different, but this impact
> should be limited. In a new language, the right choice is likely to
> avoid `call/cc` to begin with [1], but we need to provide backwards
> compatibility.
> 
> Any thoughts?

I agree that it would be better to avoid `call/cc' in the first place,
but I think we need a better compatibility story with respect to
`dynamic-wind' --- at least for Scheme variants, and possibly even for
Racket.

By making a smaller adjustment to `call/cc', I think we can break fewer
programs (only those that run afoul of non-default abort handlers)
while solving the local-reasoning problem.