Re: The Shepherd on Fibers

[Philip McGrath]

Hi,

On 3/29/22 05:36, Maxime Devos wrote:
> Philip McGrath schreef op ma 28-03-2022 om 20:14 [-0400]:
> > Maybe it would be enough for this case for Fibers to provide 
> > variants of `dynamic-wind` and/or `call-with-continuation-barrier` 
> > that cooperate with the Fibers implementation. I don't know if
> > that would be possible of not—in addition to my limited familiarity
> > with Fibers, I have not read all of the related literature that
> > Alexis, Matthew, and Matthias Felleisen discuss in [5] and
> > [6]—again, I am not an expert!
>
> Fibers' context switching is based on continuations.  By definition,
>  ‘call-with-continuation-barrier’ must create a continuation barrier
>  (and as a consequence, interfere with Fibers' context switching).
>
> It can be important to let 'call-with-continuation-barrier' (*) 
> actually create a continuation barrier, even when fibers is used, 
> e.g. to not create deadlocks (or livelocks or whatever, I don't know 
> the terminology) when POSIX mutexes are used.  As such, as-is, I 
> don't think so.
>
> [...]
>
> (*) Actually, 'call-with-continuation-barrier' and 'dynamic-wind' are
> already a bit of a lie, since the kernel ignores them when context
> switching ... Maybe continuation barriers and {un,re}winding is a
> matter of perspective?

Yes, that's the crux of the problem.

All of the references I know of are discussed in mailing list threads
[1] and [2], plus the more recent Flatt & Dybvig, "Compiler and Runtime
Support for Continuation Marks" (PLDI 2020) [3], which discusses the
Racket-on-Chez implementation of delimited control. In [1], Matthew
Flatt wrote:

> For an implementation that relies on a representation choice instead 
> of tracing or analysis, Racket CS's implementation of delimited 
> control is the state of the art --- mostly by building on Chez 
> Scheme's implementation of continuations.

Again, I am very far from an expert, but I'll try to distill the
relevant parts here.

To quote from the abstract and introduction of "Adding Delimited and
Composable Control to a Production Programming Environment" [4]
(internal citations omitted),

> Operators for delimiting control and for capturing composable 
> continuations litter the landscape of theoretical programming 
> language research.  Numerous papers explain their advantages, how
> the operators explain each other (or don’t), and other aspects of
> the operators’ existence.  Production programming languages, however,
> do not support these operators, partly because their relationship to 
> existing and demonstrably useful constructs—such as exceptions and 
> dynamic binding—remains relatively unexplored.
>
> [...]
>
> Due to this semantic interference, simulations of delimited control 
> do not immediately yield production-quality implementations.  For 
> example, a Scheme library can use `call/cc` to simulate delimited 
> continuations, but other libraries that use `call/cc` directly or 
> that use `dynamic-wind` can interfere with the simulation.
>
> Over the past year, we have integrated a full set of delimited- 
> control operators within PLT Scheme, ensuring that all of them 
> interact properly with the rest of the Scheme programming language
> as well as pre-existing extensions in PLT Scheme. Specifically, PLT 
> Scheme’s prompts and composable continuations have a well-defined
> and useful interaction with `call/cc`, `dynamic-wind`, dynamic
> binding via continuation marks, and exceptions.

Racket's Concurrent ML subsystem also falls into that category.

The result of this paper is `racket/control` library[5].

To take Racket CS as an example, Chez Scheme doesn't provide delimited
continuations or "green" threads/fibers, but it does provide an
efficient and powerful implementation of continuations (even including
support for `equal?`!). The Racket CS runtime system implementation uses
Chez's `call/cc`, `dynamic-wind`, etc. to implement Racket's primitive
control operators (from the built-in module '#%kernel). Then, a larger
set of control operators can be implemented as a library in terms of the
primitives.

But, as the above paper says, this means that Chez's `call/cc`,
`dynamic-wind`, etc. are *unsafe* from the perspective of Racket's
control primitives. From the docs for Racket's `ffi/unsafe/vm` library [6]:

> Beware of directly calling a Chez Scheme primitive that uses Chez 
> Scheme parameters or `dynamic-wind` internally. Note that `eval`, in 
> particular, is such a primitive. The problem is that Chez Scheme’s 
> `dynamic-wind` does not automatically cooperate with Racket’s 
> continuations or threads. To call such primitives, use the 
> `call-with-system-wind primitive`, which takes a procedure of no 
> arguments to run in a context that bridges Chez Scheme’s
> `dynamic-wind` and Racket continuations and threads.

Anything that has the potential to block Racket's scheduler (as opposed 
to a fiber/thread), like POSIX mutexes, is likewise unsafe and should be 
encapsulated in a safe abstraction. For more on this, see the docs for 
`ffi/unsafe/atomic`[7], `ffi/unsafe/schedule`[8], `ffi/unsafe/port`[9], 
`ffi/unsafe/os-thread`[10], `ffi/unsafe/global`[11], and the 
`#:atomic?`, `#:async-apply`, `#:lock-name`, `#:in-original-plce?`, 
`#:blocking?`, `#:callback-exns?`, and `#:save-errno` arguments to 
`_cprocedure`[12], plus the section titled "Threads, Threads, Atomicity, 
Atomicity, and Atomicity" (yes, there are that many layers!) in the file 
"racket/src/cs/README.txt" [13] from the main Racket Git repository.

The key difference with Guile's Fibers is that it uses continuations at 
the same layer of abstraction available to other Guile code.

By "variants of `dynamic-wind` and/or `call-with-continuation-barrier` 
that cooperate with the Fibers implementation", I meant maybe Fibers 
could provide something like 
`call-with-continuation-barrier/except-for-fibers` and the Shepherd 
could use it. But I don't know enough about the implementation details 
to know if that would actually be a viable option.

It seems like `dynamic-wind` and reliable resource finalization are 
particular problems in this respect. Yesterday I started looking at the 
technical report Alexis King mentioned in [1], “Algebraic Effect 
Handlers with Resources and Deep Finalization”[14]. (Apparently there is 
a deep correspondence between algebraic effect handlers and delimited 
control.) In § 8.7 "Dynamic Wind", it says (internal citations omitted):

> The Scheme language always supported delimited continuations and
> they have also struggled with initialization- and finalization
> for continuations that resumed more than once. The
> `unwind-protect` in Scheme is like a `finally` clause, while
> `dynamic-wind` is like `initially`/finally with a pre- and
> postlude. Sitaram describes how the standard dynamic-wind is not
> good enough in general:
>
> > While this may seem like a natural extension of the first-order
> > `unwind-protect` to a higher-order control scenario, it does not
> > tackle the pragmatic need that `unwind-protect` addresses,
> > namely, the need to ensure that a kind of “clean-up” happens only
> > for those jumps that significantly exit the block, and not for
> > those that are a minor excursion.  The crux is identifying which
> > of these two categories a jump falls into.
>
> Interestingly, this is exactly what is addressed by algebraic
> effects where “significant exit”s are operations that do not
> resume, while “minor excursions” are regular operations that
> resume with a result.

(That Sitaram quote is from [15].)

This sounds more promising than anything else I've heard of! Enough to 
make me want to finish reading that paper :)

However, I know extremely little about algebraic effects, and I have no 
idea how this might translate into delimited control in the Scheme 
tradition, much less Guile or Fibers specifically. I think Alexis might 
be the most likely person to be able to answer that question.

-Philip

[1]: https://groups.google.com/g/racket-users/c/AAeEp_llxaY/m/uRviksPGAgAJ
[2]: https://groups.google.com/g/racket-dev/c/PyetqHSjtAA/m/slBdazdqAwAJ
[3]: https://www.cs.utah.edu/plt/publications/pldi20-fd.pdf
[4]: https://www.cs.utah.edu/plt/publications/icfp07-fyff.pdf
[5]: https://docs.racket-lang.org/reference/cont.html
[6]: https://docs.racket-lang.org/foreign/vm.html
[7]: https://docs.racket-lang.org/foreign/Atomic_Execution.html
[8]: https://docs.racket-lang.org/foreign/Thread_Scheduling.html
[9]: https://docs.racket-lang.org/foreign/Ports.html
[10]: https://docs.racket-lang.org/foreign/Operating_System_Threads.html
[11]: https://docs.racket-lang.org/foreign/unsafe-global.html
[12]: https://docs.racket-lang.org/foreign/foreign_procedures.html
[13]: https://github.com/racket/racket/blob/master/racket/src/cs/README.txt
[14]: 
https://www.microsoft.com/en-us/research/uploads/prod/2018/04/resource-v1.pdf
[15]: 
https://web.archive.org/web/20200223020813/http://www.ccs.neu.edu/~dorai/uwcallcc/uwcallcc.html