[ANN] cumulus 0.0.1 - differential FRP

I would like to announce a new FRP library built on the React library. The purpose of cumulus is to help organize code which work on differential updates. The main type is the cumulus signal, which is analogous to a react signal, except that information about the difference from the previous value is provided to consumers along with the new value, when the cumulus signal changes.

So, why does a cumulus signal provide both the state and the difference to downstream signals? That is, what is the difference between the following:?

type t1 = state * change React.E     (* initial value and even of changes *)
type t2 = (state, change) Cumulus.t  (* the cumulus signal *)

The former type presumes that after the consumer has received the initial state, it will only need to know what changes on successive updates. This seems quite natural. It works well if, for instance, we want to reconstruct a signal holding a set of strings, given an initial set and a series of additions and removals:

module String_set = Set.Make (String)

type 'a set_patch = [`Add of string | `Remove of string]
type 'a update = 'a -> 'a

let patch_string_set : string set_patch -> String_set.t update = function
 | `Add x -> String_set.add x
 | `Remove x -> String_set.remove x

let integrate_strings (init, changes) =
  React.E.fold (fun l p -> patch_string_set p l) init changes

But what if we want to maintain a signal holding the intersection of two sets of strings? If we try to lift the intersection operation to work on patches, we discover that learning about the addition of an element to left-hand set is not sufficient to determine whether the element shall the added to the resulting set; we also need to know whether the element is a member of the right-hand set. So, in this case we would instead use cumulus signals:

let cu : (String_set.t, string set_patch) Cumulus.t = ...
let cv : (String_set.t, string set_patch) Cumulus.t = ...
let cuv =
  let init u v = String_set.inter u v in
  let patch (u, du) (v, dv) r' =
    (match du, dv with
     | None, Some x when String_set.mem x u ->
        Cumulus.Patch (String_set.add x r', `Add1 x)
     ...)
  in
  Cumulus.l2 ~init ~patch cu cv

For the complete example, using integers instead of strings, see test_isecn.ml from the testsuite.

(Footnote: If consumers know how to integrate the states they depend on, they could in principle keep their own record of the full states of the arguments. But this would be inefficient if there are many consumers, and there is also a simplification of code and possibly improved abstraction in letting the producer maintain its own state.)

Formally, we can understand the difference between t1 and t2 in terms of calculus. For instance, the differential of a product d(x·y) = dx·y + x·dy contains a mix of both the differentials and values of the two variables. But if the expression is linear, only differentials will will occur: d(a·x + b·y + c) = a·dx + b·dy. So, when t1 is sufficient, we are dealing with the analogue of a linear function. The above example could be turned into a linear one by making Labels.t a multiset type and considering the multiset union operation.

Thus far we only considered purely functional code, but a cumulus signal may chose to modify and return the same physical state during an update. Also note when designing the differential component of the cumulus signal, that we may exploit the fact the consumers also may inspect the corresponding new state. Combining these two points, a cumulus signal holding an array might have the type ('a array, [Set of int | Resize of int]). Here the state may be reused for `Set and replaced for `Resize.

On a related not, there is also the reactiveData library which deals with (linear) patching of containers.

I must also mention that there there is an OCaml project with the same name (except casing). Sorry for not checking thoroughly in advance. I hope it is not an issue in pratcise, otherwise there is still time to rename while the library is fresh.

5 Likes

Interesting! I like how React.E and React.S are projections of the new Cumulus.t. I was wondering how the new type relates to the ‘infinitesimally delayed’ event that React provides to refer to the prior value of a signal or event. From the documentation:

The fixed point combinators E.fix and S.fix allow to refer to the value an event or signal had an infinitesimal amount of time before.

Is Cumulus just a different/more convenient way to deal with these fixed point combinators or does it allow us to express something that React does not?

I don’t think there is any surprises there, since this has more to do with timing and dependencies that the data transmitted, though I haven’t tried to implement it. The cumulus signal is in fact implemented as a react signal over the 'a change type:

type ('a, 'da) change = Init of 'a | Patch of 'a * 'da | Keep of 'a
type ('a, 'da) t = ('a, 'da) change signal

The new semantics is introduced by wrapping reactive combinators with functions and extra state which on one side turns already seen Patch values into Keep on the receiving end and filters out Keep on the transmitting end.