fcontrol and dynamic-wind

[Alexis King]

Hello,

I have been playing with implementing algebraic effects using delimited control, and Dorai Sitaram’s `fcontrol` and `%` operators are a natural fit. For example, it’s straightforward to implement McCarthy’s `amb` operator using them:

(define amb-tag (make-continuation-prompt-tag 'amb))

; -> none/c
(define (fail) (fcontrol 'fail #:tag amb-tag))
; -> boolean?
(define (choice) (fcontrol 'choice #:tag amb-tag))

(define-syntax amb
(syntax-rules ()
[(_) (fail)]
[(_ e) e]
[(_ e0 e ...) (if (choice) e0 (amb e ...))]))

The whole point of algebraic effect handlers is that we can interpret the same effect multiple ways, and `%` makes that easy. For example, we can write one `amb` handler that returns only the first result and another one that returns all results:

(define (run-amb/first proc)
(% (proc)
(λ (op k)
(match op
['fail #f]
['choice (or (run-amb/first (thunk (k #t)))
(run-amb/first (thunk (k #f))))]))
#:tag amb-tag))

(define (run-amb/all proc)
(let go ([proc (thunk (list (proc)))])
(% (proc)
(λ (op k)
(match op
['fail '()]
['choice (append (go (thunk (k #t)))
(go (thunk (k #f))))]))
#:tag amb-tag)))

This mostly works nicely, but the way it interacts with `dynamic-wind` leaves something to be desired:

> (run-amb/first
(thunk
(dynamic-wind
(thunk (displayln "--> in"))
(thunk (+ (amb 1 2) (amb 3 4)))
(thunk (displayln "<-- out")))))
--> in
<-- out
--> in
<-- out
--> in
<-- out
4

This is a little bit silly, since control is jumping out of the extent of `dynamic-wind` only to immediately re-enter it. If `dynamic-wind` is being used to guard access to a lock or pooled resource, we probably don’t want it to be released and reacquired on every call to `amb`.

However, I’m not sure how I can rearrange things to make that possible. I can’t just store the current `amb` handler in a parameter/continuation mark because it really does need to extend the continuation of the whole computation. Is there any way to do that with Racket’s continuation machinery, or would I need to use mutable state to imperatively extend a list of continuations maintained by the current handler? Also, is this kind of thing discussed anywhere in the literature?

Thanks,
Alexis

[Matthew Flatt]

You're trying to implement `amb` where a client can mix `amb` and
`dynamic-wind` and get sensible behavior, right?

The `dynamic-wind` operation certainly interferes with building new
control forms. Racket threads and other control forms that need to
interact a certain way with `dynamic-wind` end up being built in at the
same level as `dynamic-wind`.

At Sat, 30 Nov 2019 06:15:16 -0600, Alexis King wrote:
> Is there any way to do that with Racket’s continuation machinery,

There's not a safe way. In many cases, Racket lets you write new things
that have the power of built-in through unsafe APIs --- and it turns
out that there are unadvertised procedures (provided by the primitive
`#%unsafe` module) for this particular case:

unsafe-abort-current-continuation/no-wind
unsafe-call-with-composable-continuation/no-wind

These are currently used to implement `ffi/unsafe/try-atomic`. Using
the `/no-wind` operations will make `amb` interact with `dynamic-wind`
in the way you have in mind, I think.

At Sat, 30 Nov 2019 06:15:16 -0600, Alexis King wrote:
> Also, is this kind of thing discussed anywhere in the literature?

I don't know of any published work on this topic (so let me know if you
find something!). As you probably have seen already, our ICFP'07 paper
just points out that `dynamic-wind` causes problems, but doesn't try to
hold `dynamic-wind` itself responsible for those problems.

An opinion and some pointers to newsgroup discussions:

http://okmij.org/ftp/continuations/against-callcc.html#dynamic_wind

It would be interesting to check whether `dynamic-wind` is really
needed in Racket libraries, at least in its current form. Most uses are
really a "finally" mechanism that could be tied to explicit escapes
like exceptions, instead of imposed for all continuation jumps. Maybe
the uses that don't fit that pattern would be better expressed with
another mechanism. Maybe the guarantees on `dynamic-wind` just need to
be weakened and the `/no-wind` variants declared "safe" by defining
away the unsafety.


Matthew

[Alexis King]

> On Nov 30, 2019, at 09:23, Matthew Flatt <mfl...@cs.utah.edu> wrote:
>
> There's not a safe way. In many cases, Racket lets you write new things
> that have the power of built-in through unsafe APIs --- and it turns
> out that there are unadvertised procedures (provided by the primitive
> `#%unsafe` module) for this particular case:
>
> unsafe-abort-current-continuation/no-wind
> unsafe-call-with-composable-continuation/no-wind

Thanks, those operations look helpful. I do worry a little bit that maybe they only solve the `dynamic-wind` problem, though, and don’t solve some other, related problems. For example, imagine I were to replace `dynamic-wind` with `parameterize-break`:

(run-amb/first
(thunk
(parameterize-break #f
(+ (amb 1 2) (amb 3 4)))))

Presumably, breaks would still be re-enabled and local exception handlers would be uninstalled during the handling of `amb`, even with the use of those unsafe operations, right? That seems wrong, too, since presumably the client would be surprised if a break were delivered inside the scope of `(parameterize-break #f _)`.

I think what it comes down to is I somehow want the ability to “atomically” insert some new continuation frames around the current prompt without uninstalling the current break state, exception handlers, continuation marks, and so on. I want to be able to go from

E_1[(run-amb/first E_2[(amb e_1 e_2)])]

to

E_1[(run-amb/first (or E_2[e_1] E_2[e_2]))]

in a single “step.” I guess I could resort to atomic mode, but that seems like a very heavy hammer, and I’m not even sure if continuation operations are safe in atomic mode. On the other hand, I don’t really know what a safe API for what I’m trying to do would look like.

> I don't know of any published work on this topic (so let me know if you
> find something!). As you probably have seen already, our ICFP'07 paper
> just points out that `dynamic-wind` causes problems, but doesn't try to
> hold `dynamic-wind` itself responsible for those problems.
>
> An opinion and some pointers to newsgroup discussions:
>
> http://okmij.org/ftp/continuations/against-callcc.html#dynamic_wind
>
> It would be interesting to check whether `dynamic-wind` is really
> needed in Racket libraries, at least in its current form. Most uses are
> really a "finally" mechanism that could be tied to explicit escapes
> like exceptions, instead of imposed for all continuation jumps. Maybe
> the uses that don't fit that pattern would be better expressed with
> another mechanism. Maybe the guarantees on `dynamic-wind` just need to
> be weakened and the `/no-wind` variants declared "safe" by defining
> away the unsafety.

Yes, most of the relevant discussions I’ve found have been about Lisp’s `unwind-protect` and how it relates to Scheme’s `dynamic-wind`. It’s alluded to in Matthias’s original POPL ’88 paper and mentioned explicitly in the following LASC paper, but neither address this particular issue. I also found Dorai Sitaram’s “Unwind-protect in portable Scheme”[1] and the related commentary by Kent Pitman[2] and Will Clinger[3], but though obviously related, both Sitaram and Clinger seem to imagine a system where the author of the program defines all control operations, so there isn’t as much of a problem. I’ve also been trying to find if any of these issues are discussed in any algebraic effects literature, but I haven’t found anything there yet, either.

[1]: http://www.ccs.neu.edu/~dorai/uwcallcc/uwcallcc.html
[2]: http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuations-overview.html
[3]: http://www.ccs.neu.edu/home/will/UWESC/uwesc.sch

[Matthew Flatt]

At Sat, 30 Nov 2019 20:38:26 -0600, Alexis King wrote:
> I’m not even sure if continuation operations are safe
> in atomic mode.

They are, as long as any invoked `dynamic-wind` thunks are safe in
atomic mode. (After all, `unsafe-abort-current-continuation/no-wind`
and `unsafe-call-with-composable-continuation/no-wind` were created to
support `unsafe/try-atomic`.)

[Alexis King]

On Nov 30, 2019, at 20:52, Matthew Flatt <mfl...@cs.utah.edu> wrote:

They are, as long as any invoked `dynamic-wind` thunks are safe in

atomic mode. (After all, `unsafe-abort-current-continuation/no-wind`
and `unsafe-call-with-composable-continuation/no-wind` were created to
support `unsafe/try-atomic`.)

Alright, thanks, that does make sense. I think it’s still probably not the right solution, since the idea is that effect handlers ought to be implementable in user code, and I wouldn’t want to ask users to regularly interact with atomic mode. Maybe it can play a role in a safe abstraction, though.

Also, I realized shortly after I wrote my last email that I actually did see an effect system paper a while back that addressed these issues: “Algebraic Effect Handlers with Resources and Deep Finalization” by Daan Leijen. Looking at it again, it even cites Sitaram’s “Unwind-protect in portable Scheme” article I mentioned earlier! I may have forgotten about it because it appears to have only ever been released as a Microsoft Research technical report, not published at any academic conference. In any case, I didn’t really understand it when I first saw it, so I need to reread it more carefully, but an initial skim seems promising.