13
45
Fork
You've already forked fibers
10

Missing basic combinators guard-operation and nack-guard-operation #97

Open
opened 2023年09月14日 07:10:53 +02:00 by LiberalArtist · 4 comments
LiberalArtist commented 2023年09月14日 07:10:53 +02:00 (Migrated from github.com)
Copy link

It looks like (fibers operations) provides two basic operation combinators:

  1. choice-operation, corresponding to Concurrent ML's choose and Racket's choice-evt; and
  2. wrap-operation, like CML's wrap and Racket's wrap-evt.

But AFAICT, this library seems to be missing the other two basic combinators (of the four enumerated in Concurrent Programming in ML § 6.5):

  1. guard, like Racket's guard-evt; and
  2. withNack, a.k.a. nack-guard-evt.

Reppy writes that "the first three combinators have analogs in many concurrent languages, but the withNack combinator is unique to CML."

The guard combinator constructs an operation that encapsulates a thunk. Each time the guard-based operation is supplied to perform-operation (directly or indirectly), the thunk is called to produce a fresh operation that is used in place of the guard-based operation. (More precisely, the thunk is called at most once for each call to perform-operation: it may be skipped if some other ready operation is chosen before the guard-based operation is considered.)

The withNack combinator is similar, but the function it encapsulates takes an argument: perform-operation calls it with a "negative acknowledgment" operation which will become ready if and when the operation returned by the callback definitely will never be chosen (e.g. normally because perform-operation has committed to some other operation, but also if the fiber blocked on it has terminated or if control escapes in some other way).

It's hard to write a short motivating example, but I'd point to the paper "Kill-Safe Synchronization Abstractions", which walks through the implementation of the racket/async-channel library. Quite apart from the kill-safety aspects, guard-evt is needed to implement an async-channel-put-evt with the same guarantee as channel-put-evt (a.k.a put-operation) that the put takes place if and only if the operation is chosen by perform-operation.

I don't think make-base-operation is sufficient to implement either the guard or the withNack combinator. A naïve implementation of guard-operation could use try and block functions that close over some shared mutable state, but there doesn't seem to be any way for an implementation to distinguish each call to perform-operation, which it needs to do in order to get a fresh underlying operation from the thunk for each call. More obviously, nack-guard-operation would need perform-operation to cooperate by signaling the "negative acknowledgment" operations.

It looks like [`(fibers operations)`](https://github.com/wingo/fibers/wiki/Manual#22-operations) provides two basic operation combinators: 1. [`choice-operation`](https://github.com/wingo/fibers/wiki/Manual#index-choice_002doperation), corresponding to Concurrent ML's `choose` and Racket's [`choice-evt`](https://docs.racket-lang.org/reference/sync.html#%28def._%28%28quote._~23~25kernel%29._choice-evt%29%29); and 2. [`wrap-operation`](https://github.com/wingo/fibers/wiki/Manual#index-wrap_002doperation), like CML's `wrap` and Racket's [`wrap-evt`](https://docs.racket-lang.org/reference/sync.html#%28def._%28%28quote._~23~25kernel%29._wrap-evt%29%29). But AFAICT, this library seems to be missing the other two basic combinators (of the four enumerated in *Concurrent Programming in ML* § 6.5): 3. `guard`, like Racket's [`guard-evt`](https://docs.racket-lang.org/reference/sync.html#%28def._%28%28lib._racket%2Fprivate%2Fmisc..rkt%29._guard-evt%29%29); and 4. `withNack`, a.k.a. [`nack-guard-evt`](https://docs.racket-lang.org/reference/sync.html#%28def._%28%28quote._~23~25kernel%29._nack-guard-evt%29%29). Reppy writes that "the first three combinators have analogs in many concurrent languages, but the `withNack` combinator is unique to CML." The `guard` combinator constructs an operation that encapsulates a thunk. Each time the `guard`-based operation is supplied to `perform-operation` (directly or indirectly), the thunk is called to produce a fresh operation that is used in place of the `guard`-based operation. (More precisely, the thunk is called at most once for each call to `perform-operation`: it may be skipped if some other ready operation is chosen before the `guard`-based operation is considered.) The `withNack` combinator is similar, but the function it encapsulates takes an argument: `perform-operation` calls it with a "negative acknowledgment" operation which will become ready if and when the operation returned by the callback definitely will never be chosen (e.g. normally because `perform-operation` has committed to some other operation, but also if the fiber blocked on it has terminated or if control escapes in some other way). It's hard to write a short motivating example, but I'd point to the paper ["Kill-Safe Synchronization Abstractions"](https://users.cs.utah.edu/plt/publications/pldi04-ff.pdf), which walks through the implementation of the [`racket/async-channel`](https://docs.racket-lang.org/reference/async-channel.html) library. Quite apart from the kill-safety aspects, `guard-evt` is needed to implement an `async-channel-put-evt` with the same guarantee as `channel-put-evt` (a.k.a `put-operation`) that the put takes place if and only if the operation is chosen by `perform-operation`. I don't think `make-base-operation` is sufficient to implement either the `guard` or the `withNack` combinator. A naïve implementation of `guard-operation` could use try and block functions that close over some shared mutable state, but there doesn't seem to be any way for an implementation to distinguish each call to `perform-operation`, which it needs to do in order to get a fresh underlying operation from the thunk for each call. More obviously, `nack-guard-operation` would need `perform-operation` to cooperate by signaling the "negative acknowledgment" operations.

Is this something we should consider adding to 2.0, while we’re at making incompatible changes with #180? Any volunteer?

Now that we have nack-other-operations, I feel like nack-operation would be doable. Thoughts, @stund?

Is this something we should consider adding to 2.0, while we’re at making incompatible changes with #180? Any volunteer? Now that we have `nack-other-operations`, I feel like `nack-operation` would be doable. Thoughts, @stund?
Contributor
Copy link

Hey @civodul,

I'd be interested in working on that, but have limited time at the moment, and wouldn't want to hold up the release.

Maybe you feel like there should be something more for a Fibers 2.0 release? I know I do...

In the meantime, consider this: if timer-operation remained public, but the documentation was clarified as to how to actually get the "internal time units" currently mentioned (i.e., use internal-monotonic-time) ... would this really rise to the definition of a breaking API change? And if not, could this be labelled, say, a 1.5 release?

Perhaps timer-operation could be marked as deprecated. Or it could just live on in obscurity -- the reality is, aside from reading the timers.scm source code, it's not clear how (or why) to use timer-operation. There are no examples, unlike for sleep-operation and sleep. It's used exactly once in Fibers itself -- to implement sleep-operation.

To the best of my knowledge, the only visible usage of timer-operation was in the Shepherd. (I believe you know the maintainer? ;)

That'd be my suggestion: ship the monotonic-clock-based timer wheels implementation as Fibers 1.5, and save 2.0 for something more featureful.

Hey @civodul, I'd be interested in working on that, but have limited time at the moment, and wouldn't want to hold up the release. Maybe you feel like there should be something _more_ for a Fibers 2.0 release? I know I do... In the meantime, consider this: if `timer-operation` remained public, but the documentation was clarified as to how to actually get the "internal time units" currently mentioned (i.e., use `internal-monotonic-time`) ... would this _really_ rise to the definition of a breaking API change? And if not, could this be labelled, say, a **1.5** release? Perhaps `timer-operation` could be marked as deprecated. Or it could just live on in obscurity -- the reality is, aside from reading the `timers.scm` source code, it's not clear how (or why) to use `timer-operation`. There are no examples, unlike for `sleep-operation` and `sleep`. It's used exactly once in Fibers itself -- to implement `sleep-operation`. To the best of my knowledge, the only visible usage of `timer-operation` was in the Shepherd. (I believe you know the maintainer? ;) That'd be my suggestion: ship the [monotonic-clock-based timer wheels](https://codeberg.org/guile/fibers/issues/180) implementation as Fibers **1.5**, and save 2.0 for something more featureful.

Hey @stund,

I think it makes sense to follow SemVer. Removing timer-operation (or even changing the interpretation of its argument) is a breaking change, hence 2.0.

I think numbers are cheap so I’m not afraid of calling it "2.0" even if that’s the only significant change.

Now, while we’re at making breaking changes, my thought is that it’s a good opportunity to work on nack/guard support, if someone is able to do it (I don’t think I can make time for this).

I started looking at adjusting Shepherd to the monotonic Fibers (along the lines of what you did in shepherd/shepherd#104 but with a timerfd-first approach). My guess is that it won’t ship until a while, possibly waiting for 1.1.0, which could be in July at best, and we could release Fibers 2.0 at about the same time.

So if you think you can make time for Fibers hacking by then, that’s okay. WDYT?

Hey @stund, I think it makes sense to follow SemVer. Removing `timer-operation` (or even changing the interpretation of its argument) is a breaking change, hence 2.0. I think numbers are cheap so I’m not afraid of calling it "2.0" even if that’s the only significant change. Now, while we’re at making breaking changes, my thought is that it’s a good opportunity to work on `nack`/`guard` support, if someone is able to do it (I don’t think I can make time for this). I started looking at adjusting Shepherd to the monotonic Fibers (along the lines of what you did in shepherd/shepherd#104 but with a timerfd-first approach). My guess is that it won’t ship until a while, possibly waiting for 1.1.0, which could be in July at best, and we could release Fibers 2.0 at about the same time. So if you think you can make time for Fibers hacking by then, that’s okay. WDYT?
Contributor
Copy link

That timeframe suits me. Count me in!

That timeframe suits me. Count me in!
Sign in to join this conversation.
No Branch/Tag specified
main
revert-110-wip-cancel-timer-operations
fdless-draft
pr-60-adjust
more-operations
timer-wheel
cross
nice-dynamic-wind-experiment
v1.4.3
v1.4.2
v1.4.1
v1.4.0
v1.3.1
v1.3.0
v1.2.0
v1.1.1
v1.1.0
v1.0.0
v0.5.0
v0.4.0
v0.3.0
v0.2.0
v0.1.0
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
3 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
guile/fibers#97
Reference in a new issue
guile/fibers
No description provided.
Delete branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?