Affect design notes

Choices and guidelines

1. Align mecanisms on syntactic and function scopes to ease reasoning. Structured concurrency, structured cancellation and structured user effect handling.
2. No distinction between parallelism and concurrency. That's not something one wants to ponder at every asynchronous call. Doing so is fine control over scheduling (see next point). It's also more complex to reason about (e.g. two mutual exclusion modes can be distinguished instead of one).
3. No fine grained control on scheduling. It's not compositional, function execution must be oblivious of its scheduling and insensitive to the way parallellism is configured by the running program. Still, functions are provided with three priority hints and request for execution on the main domain (in affect: the one which setups the scheduler).
4. No fiddling with domain and threads or pools thereof at the user level. It's not compositional and you don't want to thread these arguments in your libraries. Only the program's main function setups that.
5. No fiddling with fancy concurrency primitives or models. Only a simple, fixed model, allows to reasonably think about how it can be exploited compositionally. It becomes possible to understand the exact consequences of using an asynchronous function call in your library.
6. No fancy dynamic ressource tracking in the function's scope. This belongs to my type system and Fun.protect. It also keeps the difference between synchronous and asynchronous function calls small, which in turn allows to sprinkle or retract asynchronous calls in your code more easily.
7. Answer design questions by minimizing differences between regular functions and asynchronous function. Again it should be easy to retract or sprinkle code with calls to Fun.Async.call without too much surprises.

Asynchronous functions

1. Why give asynchronous function results a Affect.Cell.Once semantics instead of a rendez-vous or a single shot inclusive action semantics? It wouldn't be natural. Once a function has computed and you still have the call handle value you just want to be able to get that result regardless of whether the function has already returned or not. Trying to be different would clash with point 7. of Choices and guidelines.

2. Do not force functions to get the result of their asychronous function calls.

   Alternative would be at the end of the function:

   1. Report errors, that is enforce users to get results before.
   2. Do nothing on values but trap exceptions

   The first idea may make some pattern for imperative parallel or speculative computing (cancel and forget) more involved than they could be – it also means that you consider that asynchronous functions are a ressource which is not a view that we want to take (again point 7. of Choices and guidelines).

   The second idea it feels a bit odd to make a difference between values and exceptions. In both cases trying to track if a get was attempted would entail a fair amount of bookeeping (perhaps not in fact).

   This is not to say that this decision is not problematic as it may make unexpected exceptions go unoticed. We try to alleviate that by providing Affect.Fun.Async.call_trap_exn for those users who rely on structured concurrency to synchronize, but that remains something the user has to do explicitely and may forget to do.

3. Why not provide a way to escape the strict structured concurrency discipline, for example by providing a Fun.Async.detached_call, where either you can specify an arbitrary parent or simply makes the call attached to the root asynchronous function. We feel that:

   1. Doing so significantly weakens the value proposal of structured concurrency. Especially from a library usage perspective, it's nice to know that the asynchronous function call they invoke do not escape your control.
   2. If you really need that for more sophisticated application-level scenarios, affect is sufficiently flexible not to be stuck by that. Function synchronisation actions or function to call can be sent over ports, either to a listening asynchronous function call "server" you called at the start of your program in the root asynchronous function or even to another scheduler running in program.

Cancellation

1. No explicit cancellation context management or tokens. These things are like passing reference cells around: error prone and difficult to reason about. Like concurrency we want the effect of cancellation of a given asynchronous call to be aligned on function scopes.
2. Why does cancellation unblock Affect.Action.invoke? If the cancellation is due to something that the action expects, it becomes a "cancelock" that waits forever. So we participate in the choice of an Affect.Action.invoke with an invisible action primitive that raises Cancelled if the function marks as cancelled.
3. Why does cancellation "disable" actions afterwards? If we don't do so, cancellation becomes a racy operation, for example if the cancellation mark happens between two actions. It's good to have the guarantee that if you are using actions and the asynchronous call is marked as cancelled you get notified on the next action (if any, be careful).
4. Why is there a cancellation mask? The cleanup done on cancellation may need to invoke actions without those blowing in your face with Affect.Fun.Async.Cancelled.
5. Why doesn't the cancellation mask fully mask the effects of a cancellation? The cancellation mask is not supposed to be a way to escape cancellation, it's only there to invoke actions during cleanup without those raising Affect.Fun.Async.Cancelled. Besides a cancellation mask scope may be invoked regardless of cancellation and we may want to be able to reason about the cancellation mark of the caller in that scope.

Scheduling

1. What's the idea behind only main scheduling? In certain usage scenarios it is useful to have a coordinator (UI thread, worker coordinator) among available processor. This caters for these scenarios.
2. Why add priorities? We think it may be useful for applications to make some distinctions (e.g. between a backup task and interacting with humans), it may be premature design though. The current implementation of affect ignores them.

Names

Action vs Events

Why not stick with CML's Event terminology?

We use the term action derived from CCS to get full Milnerization. Thinking in term of actions that you invoke and that return values is easier to get an intuition about than with the notion of event – especially for combinators like Affect.Action.guard. Besides:

1. There's a lot of connotations for programmers about events that are unrelated what it stands for in CML.
2. It's often (but not always) a confusing way to think about the abstraction for example for combinators like Affect.Action.guard.
3. Ambiguity between event and its instances/occurences (which also exists in FRP). Here we have action for the abstraction and action invocation for the instance. This is easy to relate with function abstraction and function invocation which presumably programmers are familiar with.
4. There is already an Event (implementing CML events over threads) module upstream.
5. In the CML literature itself the event abstraction is often refered to as "first-class synchronization operation". In fact in the CML book on p. 53 we find this sentence "The type τ event is the type of a synchronous operation that returns a value of type τ when it is synchronized upon" (emphasis is mine). So what it is is not described by the event name.
6. The Guile implementation decided to go with operation insead of event. We do find operation a bit too generic and a term that can also be used to characterize functions (e.g. the operations of a data structure), so we did not reuse that.

This is not to say that event terminology never makes sense, especially for those actions that involve waiting on something that is not really under our control like waiting for readability – but it becomes weird when it is, like the Port.offer action. For those cases where we wait on something then wait_xxx is a natural way of naming this action of waiting on xxx. Sometimes we can turn that into a proper action for example on asynchronous function, we get the result rather than wait_result, notably because of the set-once cell semantics of call handles.

Ports vs Channels

Why not stick with CML's Channel, send and recv terminology?

1. send and recv have a remote and asynchronous transmission feel which we dislike.
2. We find it ambiguous as to whether this is buffered or not.
3. Action names and their complement represent a communication port in Milner's CCS – though he moved to channel terminology in the π-calculus.
4. A counter point could be that this is established terminology, for example in Go, but we don't find the names we propose to be horribly bad.
5. There are already channels in the standard library for IO and those are buffered.

Cells

We don't find mvar and ivar's to be particularly enlightening names if not contradicatory for ivar. We gather these synchronized cells in Affect.Cell module with following names:

Implementation

Differences with Parallel CML

A couple of things to note.

1. Our primitives are slightly simpler and follow the Guile implementation. We simply have an optimistic phase (poll) and a pessimitic one (block). The three function design (poll, doFn, block), also present in OCaml's implemention, has the advantage of producing a list of enabled events to consider. One of the paper mentions that it enables e.g. to support priorities or fairness. Except if priorities are dynamically set by poll I think the two function design also allows this: we have the list of primitive events before, it's just a matter of random shuffling and/or sorting that list before processing it.
2. Our implementation of ports doesn't use spinlocks like in the original paper, we followed Guile and used two synchronized queues instead which leads to a slightly different code structure and notably the need to publish the operations on the queues before attempting synchronization. We struggled however to implement Affect.Cell.Drop without a spinlock.
3. For now we didn't implement negative acknowledgement. While they provide an account of cancellation in Affect.Action.choose, they do so by side effect and if we use the CML API (not the OCaml one, which is rather a callback), it requires to run an asynchronous functions call to handle them which is slightly disasteful and may end up clashing with structured concurrency (more thought is needed :-). As mentioned in the papers it is possible to handle this outside the current core. Basically for now when we iterate over the primitive events to do the poll and block we always pass the same continue and unblock functions. These should be changed for each primitive to add invocations of the nacks for those other primitives that requested it. So it seems that the only disruption would actually happen only internaly to the Action module. It could change the costs of action invocations though.
4. We couldn't really wrap our head around the "horrible continuation hacking to implement" wrap (see section §6.4 of paper). I suspect that our Affect.Action.map, implemented without "horrible continuation hacking" is also less powerful due to the loss of context. We also dislike the fact that the unblocking entities are the ones that end up invoking the mapping function, we'd prefer to have the ready thunk do that back on the scheduler (which would likely also solve the loss of context problem).
5. They don't have structured concurrency. They have spawn : (unit -> unit) -> unit. Our enforcement of structured concurrency means that some of the patterns they use (a.k.a. threads everywhere) for example to implement synchronization mecanisms using ports can likely not be used (see for example §5.3.1 in the book). Since that's precisely the style we dislike (data structures having hidden threads) all the better, but we may need new books and have a better assement of what is exactly lost here.

Undecided and todo

• Unhandled exceptions on Action.guard do_poll and do_block, we throw them into the Action.invoke, should we rather Panic and fail the whole scheduler? See XXX in the code, it could break invariants.
• Should we keep Affect.Action.invoke_poll? It's one more effect to handle and it tempts people into performing their own scheduling. Some actions will always return None.
• The action metadata likely needs a new design round. It would also be nice to look at what implicit location could bring here.
• Should we add the nacks? See the discussion in Differences with Parallel CML.
• Built-in scheduler. Not super happy about scheduling queues. Could we have perhaps better data structures to eschew the only_main_queue. Basically one should not steal only_main ready work on the main queue.
• Built-in scheduler. Priorities are not implemented. Have one queue per priority? One question is how we can we adjust priorities if a low priority function tries to get the priority? We'd need to thread that info into actions, since waiting on an asynchronous function is no longer special, it's just invoking an action. Actions could have a priority field not used for leaning the choose but to indicate which priority should be given to the waiter and is returned on Affect.Action.Private.Action.Invocation.make.
• Affect_unix, solve the toplevel business, add printers and see if we can do something about Omod not succeeding without assuming affect.

References and acknowledgements

In some sense affect is simply an attempt at icing the cake of Parallel Concurrent ML with structured concurrency and structured cancellation. Synchronous actions are an implementation of the notion first-class synchronous events which can be found in the works mentioned below. They are just a parallel-safe and lock-free implementation of the OCaml Event module.

• John Reppy. Synchronous Operations as First-class Values. 1988

  The original CML paper.

• John Reppy. Concurrent Programming in ML. 1999

  Good book on CML with lots of examples, thoughts on concurrency, synchronicity and design rationales.

• Kevin Donnelly et al. Transactional events.

  Interesting monadic account of CML events, see also this technical report.

• John Reppy et al. Parallel Concurrent ML. 2009

  Describes the protocol for parallel event synchronization.

• Andy Wingo et al. Guile fibers library. 2017 See also this blog post.

  Guile implementation of Parallel CML. Our notion of primitive action is rooted in their notion of operation where they reduce the three function of Reppy 1999 to two. We also stole their implementation scheme for ports which avoids spinlocks. Like them we change the terminology, but did not follow theirs.

Here are two personal notes:

• The literature often present channels (ports in affect) as being the only mean to create actions, on receive and send operations on a channel. The OCaml Event implementation is an example of that. This limits a bit the presention since it entails one rendez-vous synchronization between two actions. First this is only one of the many synchronization modes you may be interested in. While those can be encoded on top of channels, it feels a bit weird to to so. Second it makes it harder to see it as a good interaction mecanism for dealing with the operating system. For the latter the synchronization protocol is in fact much simpler than the two phase protocol that you need in order to simulaneously synchronize two actions for implementing ports.
• While the CML book is a good book we dislike the resulting very imperative programming style where everything is a unit -> unit thread and channels are use to get out information from these black holes. We hope that in affect, by having structured concurrency with functions unit -> 'a that return values that can be synchronized like a set-once cell, we can put less emphasis on using "threads" and ports. In fact as we noted in the last point here, some of the patterns they use may not be feasible with affect

Affect timeline

May 2026

• Fully reframe the model on parallel asynchronous function calls. No longer mention "fibers" and tuck all that in Stdlib.Fun.Async where it naturally belongs.
• Provide support for the loss of handler problem mentioned here via Affect.Fun.Async.Call_handler which allows to recover a form of structured effect handling.
• Replace the ad-hoc notion of blocking we had in the previous iteration by CML synchronous events, which we expose under the term action. In fact our previous Fiber.block mecanism was almost the structure of a CML primitive event. Blocking on an asynchronous function call becomes blocking on the action to get its result which is very pleasing. Provide the full power of CML composable's synchronization to the system and unifies the synchronization mecanism for asynchronous function synchronisation, blocking on primitives (system calls) and synchronization structures (ivar, mvar, ports, byoss) which where previously separate and ad-hoc. For example in the previous iteration if you wanted to say, cancel a function after a timeout, you had to spawn a fucntion that would wait the timeout and use the ad-hoc "pick" combinator between two functions. In this new system you can simply ask for the function get a ction and choose it with a timeout primitive action which results in composite action that can be waited on, so it's not optimal.

October 2024

1. Only expose parallel asynchronous function calls with built-in priority hints and structured cooperative concurrency and cancellation. A fiber is just a handle on such a call.
2. Came up with most of the negations in choices.
3. Priority hints and cooperative cancellation were inspired by the Swift concurrency model. This ends up with a more more natural await (previously join) than the previous 2022 iteration of Affect which only had structured cancellation topped with a franken-semi-cooperative cancellation.
4. Growing feeling that CML is the answer and that we are reinventing it.

January 2022

First design round.