[ANN] Current_incr: a small incremental library with no dependencies

Community
1

The recent OCurrent 0.2 release included a little incremental library which might be interesting to some people. It is useful for writing programs that need to keep some computation up-to-date efficiently as the inputs change.

It is similar to the existing incremental and react libraries already in opam. Unlike incremental (which pulls in the whole of core_kernel), current_incr has no runtime dependencies (and build dependencies only on ocaml and dune). Unlike react, current_incr immediately stops computations when they are no longer needed (rather than relying on weak references and the garbage collector).

It is a fairly direct implementation of the Adaptive Functional Programming paper, and might be a good starting point for people wanting to learn about that.

You can get the library using opam:

opam install current_incr

Here’s a simple example (in utop):

#require "current_incr";;

let total = Current_incr.var 10
let complete = Current_incr.var 5

let status =
  Current_incr.of_cc begin
    Current_incr.read (Current_incr.of_var total) @@ function
    | 0 -> Current_incr.write "No jobs"
    | total ->
      Current_incr.read (Current_incr.of_var complete) @@ fun complete ->
      let frac = float_of_int complete /. float_of_int total in
      Printf.sprintf "%d/%d jobs complete (%.1f%%)"
                     complete total (100. *. frac)
      |> Current_incr.write
  end

This defines two input variables (total and complete) and a “changeable computation” (status) whose output depends on them. At the top-level, we can observe the initial state using observe:

# print_endline @@ Current_incr.observe status;;
5/10 jobs complete (50.0%)

Unlike a plain ref cell, a Current_incr.var keeps track of which computations depend on it. After changing them, you must call propagate to update the results:

# Current_incr.change total 12;;
# Current_incr.change complete 4;;
# print_endline @@ Current_incr.observe status;;
5/10 jobs complete (50.0%)	(* Not yet updated *)

# Current_incr.propagate ();
# print_endline @@ Current_incr.observe status;;
4/12 jobs complete (33.3%)

Computations can have side-effects, and you can use on_release to run some compensating action if the computation needs to be undone later. Here’s a function that publishes a result, and also registers a compensation for it:

let publish msg =
  Printf.printf "PUBLISH: %s\n%!" msg;
  Current_incr.on_release @@ fun () ->
  Printf.printf "RETRACT: %s\n%!" msg

It can be used like this:

# let display = Current_incr.map publish status;;
PUBLISH: 4/12 jobs complete (33.3%)

# Current_incr.change total 0;
# Current_incr.propagate ()
RETRACT: 4/12 jobs complete (33.3%)
PUBLISH: No jobs

A major difference between this and the react library (which I’ve used in previously in 0install’s progress reporting and CueKeeper) is that Current_incr does not depend on the garbage collector to decide when to stop a computation. In react, you’d have to be careful to make sure that display didn’t get GC’d (even though you don’t need to refer to it again) because if it did then the output would stop getting updated. Also, setting total to 0 in react might cause the program to crash with a division-by-zero exception, because the frac computation will continue running until it gets GC’d, even though it isn’t needed for anything now.

Current_incr's API is pretty small. You might want to wrap it to provide extra features, e.g.

  • Use of a result type to propagate errors.
  • Integration with Lwt to allow asynchronous computations.
  • Static analysis to render your computation with graphviz.
  • Persistence of state to disk.

If you need that, consider using the main OCurrent library, which extends current_incr with these features.

24 Likes
2

Very interesting!

I should probably dive deep into the referenced paper first but in case someone already has an answer — I’m wondering if there’s a comparison somewhere with Adapton (which I think is more recent than AFP) and dune’s memo library.

2 Likes
3

Thanks; Adapton does look interesting. It seems that its main feature is only updating the part of the output being displayed at the time. That sounds useful for UIs. However, in current_incr computations can have side-effects, so that wouldn’t work there. OCurrent needs to keep its pipelines up-to-date even when nobody is looking at it.

current_incr doesn’t do any memoisation itself, but current.cache adds some.

4

I’ve started using the current_incr library today and have enjoyed it so far. Though I’m having trouble with one thing, and I was hoping you might be able to help. What is the difference between a Current_incr.cc and a Current_incr.t? It seems like you can turn a Current_incr.t into a Current_incr.cc with Current_incr.read Fn.id and turn a Current_incr.cc into a Current_incr.t with of_cc . Is one of these expensive or to be avoided? Why not expose a single changeable type?

Thanks very much!

5

What is the difference between a Current_incr.cc and a Current_incr.t?

Good question - I didn’t explain it above!

A cc is like a function, whereas a t is like a ref cell.

So if you use a cc twice, then it has to be run twice, whereas if you use a t twice then you’re just reading a pre-computed value twice.

You could turn every cc into a t immediately. It’s just slightly more efficient to avoid creating a t, writing a value into it, and then immediately reading it out again. But if you need to use the result in more that one computation, it’s worth doing.

2 Likes
6

Looks very interesting, thanks!

Magnus Carlsson proposed a monadic-style interface for the original Adaptative Functional Programming (AFP) library. I’m not at all familiar with incremental computation library design, but from a distance the monadic style looks a bit simpler. Is there a strong reason to stick to the more imperative style of the original library?

7

You can make a monadic interface on top of the existing API very easily, e.g.

let return = const
let bind x f = read x (fun x -> read (f x) write) |> of_cc

It just adds one extra read and one extra write, because we have to copy the result from f into a new t.

I think I did look at that paper earlier - my recollection is that it was mainly about how to implement the library in a pure language such as Haskell. It’s much easier in OCaml, of course.

3 Likes