`Picos.Computation`

A cancelable computation.

A computation basically holds the status, i.e.

- running,
- returned, or
- canceled,

of some sort of computation.

A hopefully enlightening analogy is that a computation is a kind of single-shot atomic event.

Another hopefully helpful analogy is that a computation is basically like a cancelable promise and a basic non-cancelable promise can be implemented trivially on top of a computation.

To define a computation, one first creates it and then arranges for the computation to be completed by returning a value through it or by canceling it with an exception at some point in the future. There are no restrictions on what it means for a computation to be running. The cancelation status of a computation can be polled or checked explicitly. Observers can also attach triggers to a computation to get a signal when the computation is completed or await the computation.

Here is an example:

```
run begin fun () ->
let computation =
Computation.create ()
in
let computer =
Domain.spawn @@ fun () ->
let rec fib i =
Computation.check computation;
if i <= 1 then
i
else
fib (i - 1) + fib (i - 2)
in
Computation.capture computation
fib 10
in
let finally () =
Domain.join computer
in
Fun.protect ~finally @@ fun () ->
let canceler =
Domain.spawn @@ fun () ->
Unix.sleepf 0.1;
Computation.cancel computation
@@ Exn_bt.get_callstack 2 Exit
in
let finally () =
Domain.join canceler
in
Fun.protect ~finally @@ fun () ->
Computation.await computation
end
```

In this framework, a fiber is always associated with at least a single computation. However, it is possible for multiple fibers to share a single computation and it is also possible for a single fiber to perform multiple computations.

Computations are not hierarchical. In other words, computations do not directly implement structured concurrency. However, it is possible to propagate cancelation to implement structured concurrency on top of computations.

Operations on computations are either wait-free or lock-free and designed to avoid starvation and complete in amortized constant time. The properties of operations to complete a computation depend on the properties of actions attached to the triggers.

Represents a cancelable computation. A computation is either *running* or has been *completed* either with a return value or with canceling exception with a backtrace.

âšī¸ Once a computation becomes completed it no longer changes state.

đī¸ A computation that has been completed is a small object that only holds onto the return value or the canceling exception with a backtrace.

â ī¸ In the running state a computation may refer to any number of triggers and it is important to make sure that any triggers attached to a computation are detached when they are no longer needed unless the computation has been completed.

`val create : ?mode:[ `FIFO | `LIFO ] -> unit -> 'a t`

`create ()`

creates a new computation in the running state.

The optional `mode`

specifies the order in which triggers attached to the computation will be signaled after the computation has been completed. ``FIFO`

ordering may reduce latency of IO bound computations and is the default. ``LIFO`

may improve thruput of CPU bound computations and be preferable on a work-stealing scheduler, for example.

âšī¸ Typically the creator of a computation object arranges for the computation to be completed by using the `capture`

helper, for example. However, it is possible and safe to race multiple threads of execution to complete a computation.

`val finished : unit t`

`finished`

is a constant finished computation.

`val try_return : 'a t -> 'a -> bool`

`try_return computation value`

attempts to complete the computation with the specified `value`

and returns `true`

on success. Otherwise returns `false`

, which means that the computation had already been completed before.

`val return : 'a t -> 'a -> unit`

`return computation value`

is equivalent to `try_return computation value |> ignore`

.

`val try_finish : unit t -> bool`

`try_finish computation`

is equivalent to `try_return computation ()`

.

`val finish : unit t -> unit`

`finish computation`

is equivalent to `try_finish computation |> ignore`

.

`val try_capture : 'a t -> ('b -> 'a) -> 'b -> bool`

`try_capture computation fn x`

calls `fn x`

and tries to complete the computation with the value returned or the exception raised by the call and returns `true`

on success. Otherwise returns `false`

, which means that the computation had already been completed before.

`val capture : 'a t -> ('b -> 'a) -> 'b -> unit`

`capture computation fn x`

is equivalent to `try_capture computation fn x |> ignore`

.

`try_cancel computation exn_bt`

attempts to mark the computation as canceled with the specified exception and backtrace and returns `true`

on success. Otherwise returns `false`

, which means that the computation had already been completed before.

`cancel computation exn_bt`

is equivalent to `try_cancel computation exn_bt |> ignore`

.

`cancel_after ~seconds computation exn_bt`

arranges to `cancel`

the computation after the specified time with the specified exception and backtrace. Completion of the computation before the specified time effectively cancels the timeout.

âšī¸ The behavior is that `cancel_after`

first checks that `seconds`

is not negative, and then

- on OCaml 5,
`cancel_after`

will perform the`Cancel_after`

effect, and - on OCaml 4,
`cancel_after`

will call the`cancel_after`

operation of the current handler.

`val is_running : 'a t -> bool`

`is_running computation`

determines whether the computation is in the running state meaning that it has not yet been completed.

`val is_canceled : 'a t -> bool`

`is_canceled computation`

determines whether the computation is in the canceled state.

`canceled computation`

returns the exception that the computation has been canceled with or returns `None`

in case the computation has not been canceled.

`val check : 'a t -> unit`

`check computation`

is equivalent to `Option.iter Exn_bt.raise (canceled computation)`

.

`peek computation`

returns the result of the computation or `None`

in case the computation has not completed.

`try_attach computation trigger`

tries to attach the trigger to be signaled on completion of the computation and returns `true`

on success. Otherwise returns `false`

, which means that the computation has already been completed or the trigger has already been signaled.

â ī¸ Always `detach`

a trigger after it is no longer needed unless the computation is known to have been completed.

`detach computation trigger`

signals the trigger and detaches it from the computation.

đī¸ The `try_attach`

and `detach`

operations essentially implement a lock-free bag. While not formally wait-free, the implementation is designed to avoid starvation by making sure that any potentially expensive operations are performed cooperatively.

`val await : 'a t -> 'a`

`await computation`

waits for the computation to complete and either returns the value of the completed computation or raises the exception the computation was canceled with.

âšī¸ If the computation has already completed, then `await`

returns or raises immediately without performing any effects.

`val wait : _ t -> unit`

`wait computation`

waits for the computation to complete.

`canceler ~from ~into`

creates a trigger that propagates cancelation `from`

one computation `into`

another on signal. The returned trigger is not attached to any computation.

The returned trigger is usually attached to the computation `from`

which cancelation is to be propagated and the trigger should usually also be detached after it is no longer needed.

The intended use case of `canceler`

is as a low level building block of structured concurrency mechanisms. Picos does not require concurrent programming models to be hierarchical or structured.

â ī¸ The returned trigger will be in the awaiting state, which means that it is an error to call `Trigger.await`

or `Trigger.on_signal`

on it.

Schedulers may handle the `Cancel_after`

effect to customize the behavior of `cancel_after`

.

The scheduler should typically attach a trigger to the computation passed with the effect and arrange the operation to be canceled upon signal.

The scheduler should measure time using a monotonic clock.

In case the fiber permits propagation of cancelation and the computation associated with the fiber has been canceled the scheduler is free to discontinue the fiber before setting up the timeout.

`with_action x y resume`

is equivalent to

```
let computation = create () in
let trigger = Trigger.from_action x y resume in
let _ : bool = try_attach computation trigger in
computation
```

â ī¸ The same warnings as with `Trigger.from_action`

apply.

The computation concept can be seen as a kind of single-shot atomic event that is a generalization of both a cancelation context or token and of a promise. Unlike a typical promise mechanism, a computation can be canceled. Unlike a typical cancelation mechanism, a computation can and should also be completed in case it is not canceled. This promotes proper scoping of computations and resource cleanup at completion, which is how the design evolved from a more traditional cancelation context design.

In this framework, every fiber has an associated computation. Being able to return a value through the computation means that no separate promise is necessarily required to hold the result of a fiber. On the other hand, in this framework, multiple fibers may share a single computation. This allows multiple fibers to be canceled efficiently through a single atomic update. In other words, the design allows various higher level patterns to be implemented efficiently.

Instead of directly implementing a hierarchy of computations, the design allows attaching triggers to computations and a special trigger constructor is provided for propagating cancelation. This helps to keep the implementation lean, i.e. not substantially heavier than a typical promise implementation.

Finally, just like with `Trigger.Await`

, a key idea is that the handler of `Computation.Cancel_after`

does not need to run arbitrary user defined code. The action of any trigger attached to a computation either comes from some scheduler calling `Trigger.on_signal`

or from `Computation.canceler`

.