From: Philip McGrath <philip@philipmcgrath.com>
To: "Maxime Devos" <maximedevos@telenet.be>,
"Ludovic Courtès" <ludo@gnu.org>,
guix-devel@gnu.org
Subject: Re: The Shepherd on Fibers
Date: Tue, 29 Mar 2022 07:11:25 -0400 [thread overview]
Message-ID: <4129627e-da0a-d73a-c754-0a9df765cc01@philipmcgrath.com> (raw)
In-Reply-To: <9c53fc57b6e4d81b5b4447b5ed2d0797668a70ff.camel@telenet.be>
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
next prev parent reply other threads:[~2022-03-29 11:15 UTC|newest]
Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-03-23 22:36 The Shepherd on Fibers Ludovic Courtès
2022-03-25 13:29 ` Maxim Cournoyer
2022-03-26 21:28 ` Ludovic Courtès
2022-03-26 11:06 ` pelzflorian (Florian Pelz)
2022-03-26 11:09 ` Zhu Zihao
2022-03-26 11:16 ` Zhu Zihao
2022-03-26 11:18 ` pelzflorian (Florian Pelz)
2022-03-26 11:27 ` Zhu Zihao
2022-03-26 16:56 ` pelzflorian (Florian Pelz)
2022-03-26 11:59 ` Maxime Devos
2022-03-26 16:52 ` pelzflorian (Florian Pelz)
2022-03-26 18:20 ` Maxime Devos
2022-03-29 11:44 ` Ludovic Courtès
2022-03-26 12:03 ` Maxime Devos
2022-03-29 12:47 ` Ludovic Courtès
2022-03-26 12:11 ` Maxime Devos
2022-03-29 12:48 ` Ludovic Courtès
2022-03-29 16:26 ` Maxime Devos
2022-03-30 15:14 ` Ludovic Courtès
2022-03-30 17:16 ` Maxime Devos
2022-03-26 12:16 ` Maxime Devos
2022-03-29 12:50 ` Ludovic Courtès
2022-03-29 12:52 ` Maxime Devos
2022-03-29 12:54 ` Maxime Devos
2022-03-29 15:29 ` Attila Lendvai
2022-03-30 10:05 ` Ludovic Courtès
2022-03-31 4:33 ` adriano
2022-03-31 7:56 ` Attila Lendvai
2022-03-26 12:44 ` Maxime Devos
2022-03-29 13:03 ` Ludovic Courtès
2022-03-26 19:24 ` Maxime Devos
2022-03-29 0:14 ` Philip McGrath
2022-03-29 0:22 ` Philip McGrath
2022-03-29 9:36 ` Maxime Devos
2022-03-29 11:11 ` Philip McGrath [this message]
2022-03-30 10:00 ` Ludovic Courtès
2022-03-29 10:13 ` Zhu Zihao
2022-03-29 10:40 ` Maxime Devos
2022-03-30 9:49 ` Ludovic Courtès
2022-03-29 13:16 ` Ludovic Courtès
-- strict thread matches above, loose matches on Subject: below --
2022-03-24 6:48 Brendan Tildesley
2022-03-24 16:57 Nathan Dehnel
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://guix.gnu.org/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4129627e-da0a-d73a-c754-0a9df765cc01@philipmcgrath.com \
--to=philip@philipmcgrath.com \
--cc=guix-devel@gnu.org \
--cc=ludo@gnu.org \
--cc=maximedevos@telenet.be \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/guix.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).