Add `choice` to Alacrity

[jeapostrophe]

Currently, there is only ever one "next message". There should be multiple options (including from multiple senders). This is necessary to express timeouts.

[jeapostrophe]

I think on the JS side, we are going to need a Concurrent ML-style sync operation on JS Promises. So if B should either receive a message from the chain or send their own message after a timeout, then in Racket we'd represent it as

(sync
  (handle-evt recv-evt recv-k)
  (handle-evt timeout-evt timeout-k))

As far as I can tell, there doesn't exist a nice reusable library for stuff like this in JS, but I am probably missing something.

I think some really simple could be made with Promises though. handle-evt would a Promise A x (A -> B) -> Promise B function and sync2 would be a Promise A x Promise A -> Promise A function. The main thing that Promises don't do that sync would need to do is arrange for the first event's fire to be ignored if it fires after the second. I think the way to do this is to not stick the kontinuation inside the argument to sync2 but instead write something like

(case
 (sync
  (handle-evt recv-evt inl)
  (handle-evt timeout-evt inr))
 of
 [(inl x) => (recv-k x)]
 [(inr x) => (timeout-k x)])

[jeapostrophe]

@mattaudesse I need your feedback on this way of implementing in JS

[mattaudesse]

As soon as we write a sync combinator I feel like we're going to want more generalized threading features, so I'm tempted to say we should use PureScript's aff package for this. I've used aff more than once and it's a very clean, robust and pleasant way to address async code.

I could either model our hand-written JS after their API or transpile their PureScript into JS and write a thin wrapper around it (which feels like something we should at least try, and again, something I have prior experience with).

Or perhaps this is our first transpile-from-OCaml enhancement (although I'm still not really in favor of using OCaml, truth be told).

I'm sure we could identify existing libraries in vanilla JS that offer race behavior similar to what's being asked for but I wouldn't have the same degree of confidence in them. My gut tells me we should build our own that does exactly what's necessary and nothing more... API bloat is one of JS' many serious problems, IMHO.

Random note: Based on this morning's standup I know @MathieuDutSik will be needing a more general thread-like API soon.

[jeapostrophe]

I don't want to push too hard on this, because I trust your judgement about JS more than my own. So, with that salt, here's my push back:

We can do all of the heavy lifting inside of the Alacrity compiler to structure the events and promises in a way that is easy for an implementation. We want the standard library (i.e. the implementation of these things) to satisfy two goals: (1) it must be verifiable or at least auditable (i.e. it must be simple) and I do not believe the options you've mentioned satisfy this goal; (2) it should be typical of JS style (so that it more auditable) and I don't believe these approaches do that either.

I would rather you not block this issue on solving a more complicated problem of some sort of general threading system and so on. For now, the only thing we need is a very small set of options. In Racket terminology: sync, choice-evt, handle-evt, and alarm-evt (where time is expressed in the block number). I believe it would be simple as well to support a way to have the JS front-end provide a standard Promise that is a valid event in our system. (BTW, the docs for these things in Racket is here: https://docs.racket-lang.org/reference/sync.html; but they are just the same as other CML primitives you've seen.)

I believe, perhaps wrongly, that those four features are typical in JS. handle-evt seems to be built-in to the Promise type. alarm-evt is a basic Promise as well. The only complexity I see in sync/choice-evt is that once an event is selected, the others are ignored. There's a trivial way to do this with a stateful handler that sets a boolean once it is fired. The correct way to do this, from a CML perspective, is with negative acknowledgment, but I think that is overkill for us.

[mattaudesse]

In that case, if I'm understanding everything correctly, I can probably get us most of the way there with the standard Promise.race and Promise.all functions + a little additional fiddling.

Are you concerned about preemption/cancellation at all right now with regard to CPU cycles? When chucking raw Promises there's a potential for wasted computation unless you perform some extra contortions, but most JS developers safely disregard this since they're primarily interested in IO-bound work.

Personally, I'm a little wary of not having cancellation baked-in but more because the increased potential for bugs. Perhaps we should start small and see it goes, though.

[jeapostrophe]

I am not very worried now and think that your idea of starting small and seeing how easy it is to cancel is a good idea. I feel like this can't possibly be a problem with Promises that only we would be experiencing, so I anticipate the creation of a standard across JS and perhaps built-in to the standard Promise class to develop. Doing something simple now and adopting that in the future is far more productive, IMHO, than compiling some other language's weird monad to JS and programming to the generated assembly :)

[jeapostrophe]

A basic kind of choice is when A wants to do X or Y. Currently, this is not allowed because ifs must be consensual, since B needs to know what kind of message it should expect to get. In session types, the only choices have someone offering a choice and someone else making it. In this case, B would be offering to A the choice. It would make the choice by sending an extra message W that is a just a boolean and in the consensus we'd select between the two continuations. In this sense, Alacrity already has choice.