Change apply to prefer concurrent execution

[neoeinstein]

The current implementation of Job.apply is equivalent to x2yJ >>= fun x2y -> xJ >>- x2y, which means that x2yJ is resolved first, then xJ is resolved. Once both are resolved, the result of xJ is applied to the result of x2yJ. This is explicitly sequential.

Being a concurrent library, the default for the apply function ought to be a concurrent implementation. We currently have an operator <*> : Job<'x> -> Job<'y> -> Job<'x * 'y>. Thus a concurrent implementation of apply could be defined as x2yJ <*> xJ >>- fun (x2y, x) -> x2y x.

Changes:

• Introduce Job.combineSequential and Job.combineConcurrent as replacements for <&> and <*>, respectively
• Introduce <!> as an alias for Job.map. Follows convention for F# map operator.
• Change <*> to be a concurrent apply with alias Job.apply. This brings the use of this operator more inline with common F# or Haskell usage (as an equivalent to apply)
• Change <&> to be a sequential apply with alias Job.applySequential

The story for Alts is a little bit more interesting. In order to wait for two Alts to become ready simultaneously, we do a concurrent wait for either followed by a wait for the second one. This means that if the combined Alt is nacked after one Alt has been committed to, but while the other Alt is still running, we only have the ability to nack the running Alt. There is no great way to commit to both only when both are ready. This issue doesn't suggest a fix for that.

• Introduce Alt.combine as replacement for <+>
• Change <+> to be a concurrent apply with alias Alt.apply.

Old API:

module Job =
  val apply: Job<'x> -> Job<'x -> 'y> -> Job<'y>
module Infixes =
  val ( <&> ): Job<'x> -> Job<'y> -> Job<'x * 'y>
  val ( <*> ): Job<'x> -> Job<'y> -> Job<'x * 'y>
  val ( <+> ): Alt<'x> -> Alt<'y> -> Alt<'x * 'y>

New API:

module Job =
  val apply: Job<'x> -> Job<'x -> 'y> -> Job<'y>
  val applySequential: Job<'x> -> Job<'x -> 'y> -> Job<'y>
  val combineSequential: Job<'x> -> Job<'y> -> Job<'x * 'y>
  val combineConcurrent: Job<'x> -> Job<'y> -> Job<'x * 'y>
module Alt =
  val apply: Alt<'x> -> Alt<'x -> 'y> -> Alt<'y>
  val combine: Alt<'x> -> Alt<'y> -> Alt<'x * 'y>
module Infixes =
  val ( <!> ): ('x -> 'y) -> Job<'x> -> Job<'y>
  val ( <&> ): Job<'x> -> Job<'x -> 'y> -> Job<'y>
  val ( <*> ): Job<'x> -> Job<'x -> 'y> -> Job<'y>
  val ( <+> ): Alt<'x> -> Alt<'x -> 'y> -> Alt<'y>

API Diff:

 module Job =
   val apply: Job<'x> -> Job<'x -> 'y> -> Job<'y> //semantic change
+  val applySequential: Job<'x> -> Job<'x -> 'y> -> Job<'y>
+  val combineSequential: Job<'x> -> Job<'y> -> Job<'x * 'y>
+  val combineConcurrent: Job<'x> -> Job<'y> -> Job<'x * 'y>
 module Alt =
+  val apply: Alt<'x> -> Alt<'x -> 'y> -> Alt<'y>
+  val combine: Alt<'x> -> Alt<'y> -> Alt<'x * 'y>
 module Infixes =
-  val ( <&> ): Job<'x> -> Job<'y> -> Job<'x * 'y>
-  val ( <*> ): Job<'x> -> Job<'y> -> Job<'x * 'y>
-  val ( <+> ): Alt<'x> -> Alt<'y> -> Alt<'x * 'y>
+  val ( <!> ): ('x -> 'y) -> Job<'x> -> Job<'y>
+  val ( <&> ): Job<'x> -> Job<'x -> 'y> -> Job<'y>
+  val ( <*> ): Job<'x> -> Job<'x -> 'y> -> Job<'y>
+  val ( <+> ): Alt<'x> -> Alt<'x -> 'y> -> Alt<'y>

[polytypic]

In the case of an infix symbol, the arguments should be flipped:

-val ( <*> ): Job<'x> -> Job<'x -> 'y> -> Job<'y>
+val ( <*> ): Job<'x -> 'y> -> Job<'x> -> Job<'y>

Hmm... I think there are good points in this proposal: The current use of <*> in Hopac is non-standard. Also, there is use for having applicative operators for expressing parallelism.

There is an important difference between concurrent and parallel programming. In concurrent programming one specifically embraces non-determinism (the order of events is non-deterministic and is allowed to affect the end result) while in parallel programming the goal is to be deterministic: given a parallel program, simply running it sequentially should give the same result.

The current <*> is intended for parallel programming and it does not guarantee that two independent threads of control would be introduced. This is valid for a parallel construct, but would not be valid for a concurrent programming construct. A concurrent version of <*> should guarantee that two independent threads of control are always created. The reason that <*> does not guarantee independent execution of the two given Jobs is that it allows the construct to potentially avoid creating new independent threads of control when there is already plenty to run.

The primary feature of Job is to allow one to define a linear sequential flow of control that can be started to run independently and can be suspended in order to wait for something. So, I think that it is reasonable that the default for Jobs is indeed to be sequential rather than concurrent or parallel. With that said, for practical reasons, you probably want to have such parallel applicative operators defined for Jobs.

In Hopac, Alts do not allow for a simultaneous commit of multiple Alts. So, Alts should not be given (a monadic) or applicative interface—at least not without a warning.

The case with Promises, which are a subtype of Alts, is different. Unlike with arbitrary Alts, with Promises we know that once a Promise becomes available, it will stay available. So, it is reasonable to give Promises an applicative interface that operates in parallel. Promises are indeed, IMHO, fundamentally a parallel programming construct.

[neoeinstein]

Thanks for catching the infix miss.

I understand where you are going with the concurrent vs. parallel distinction, and can see where sequential would be a better default, with some way to buy in to concurrent/parallel execution.

If <*> meaning parallel fits better with Promise, then I would propose that it be the type that gets that operator rather than Job. I agree with the trouble for giving an applicative to Alt, and will remove that from the proposal for now.

Revised Diff:

 module Job =
   val apply: Job<'x> -> Job<'x -> 'y> -> Job<'y> //no change
+  val applyParallel: Job<'x> -> Job<'x -> 'y> -> Job<'y>
+  val combineSequential: Job<'x> -> Job<'y> -> Job<'x * 'y>
+  val combineParallel: Job<'x> -> Job<'y> -> Job<'x * 'y>
 module Alt =
   // Warnings to be added in XML doc, similar to <+> now.
+  val apply: Alt<'x> -> Alt<'x -> 'y> -> Alt<'y>
+  val combine: Alt<'x> -> Alt<'y> -> Alt<'x * 'y>
 module Promise =
   // Uses parallel semantics
+  val apply: Promise<'x> -> Promise<'x -> 'y> -> Promise<'y>
+  val combine: Promise<'x> -> Promise<'y> -> Promise<'x * 'y>
 module Infixes =
-  val ( <&> ): Job<'x> -> Job<'y> -> Job<'x * 'y>
-  val ( <*> ): Job<'x> -> Job<'y> -> Job<'x * 'y>
-  val ( <+> ): Alt<'x> -> Alt<'y> -> Alt<'x * 'y>
   // Give precedence to Promise
+  val ( <!> ): ('x -> 'y) -> Promise<'x> -> Promise<'y>
+  val ( <*> ): Promise<'x -> 'y> -> Promise<'x> -> Promise<'y>
+  val ( <^> ): ('x -> 'y) -> Job<'x> -> Job<'y>
   // Sequential apply (similar to current definition)
+  val ( <&> ): Job<'x -> 'y> -> Job<'x> -> Job<'y>
   // Parallel apply (ParTuple, then map)
+  val ( <+> ): Job<'x -> 'y> -> Job<'x> -> Job<'y>

Another option for the <!> and <*> is to place them into separate sub-modules, like Hopac.Infixes.Job.Sequential, Hopac.Infixes.Job.Parallel and Hopac.Infixes.Promise. That separation might help clear up what type construct was being used while introducing fewer total operators.

[polytypic]

A few random thoughts.

I believe there are use cases for all of

• "ordered sequential" (generalization of current <&>),
• "unordered parallel" (generalization of current <*>), and
• "non-deterministic once" (generalization of current <+>)

semantics of applicative composition and for all the types Job, Alt, and Promise although there are multiple combinations that produce the same semantics.

Also, Promise is a kind of memoized Job or Alt. Given operators for Job (or Alt) one can obtain operators returning Promises via memo.

Having sub-modules for different semantics would allow all the relevant combinations to be provided.