I would like to combine lazy computation with reactive functional programming. In other words, I would like to be able to create a module with the following signature :
module Memoized_Reference : sig
type 'a t
val change_value : ('a t) -> 'a -> unit
val get_current_value : ('a t) -> 'a
val new_atomic : 'a -> ('a t)
val new_univariate_composite ('a->'b) -> ('a t) -> 'b
val new_bivariate_composite ('a1 -> 'a2 ->'b) -> ('a1 t) -> ('a2 t) -> 'b
val new_trivariate_composite ('a1 -> 'a2 -> 'a3 -> 'b) -> ('a1 t) -> ('a2 t) -> ('a3 t) -> 'b
end
and with the following proprerties :
Every value of type t is either atomic or composite.
A value returned by new_atomic is always atomic, and a value returned by one of the several _composite functions is always composite.
Atomic values behave like ordinary refs with respect to change_value and get_current_value.
change_value raises an exception if called on a non-atomic (i.e. composite) value.
If a value y has been created as new_bivariate_composite f x1 x2, then at any moment in time get_current_value y will coincide with f (get_current_value x1) (get_current_value x2). Similarly for the other _composite functions.
Computations are as lazy and deferred as possible.
In OCaml pseudo-code, type t could be implemented as something like
type 'a t=
Atomic of 'a
|Uni_composite of ('b->'a)*('b t) for some 'b
|Bi_composite of ('b1->'b2->'a)*('b1 t)*('b2 t) for some 'b1,'b2
|Tri_composite of ('b1->'b2->'b3->'a)*('b1 t)*('b2 t)*('b3 t) for some 'b1,'b2,'b3
I have two questions :
Is there a GADT trick to translate the above snippet into valid OCaml code ?
What about the implementation of the whole module ? My guess is that it cannot be done directly in OCaml. If so, what would be the next best thing ?
What you describe sound a bit like functional reactive programming. Maybe take a look at react ?
In any case, your type could be defined as:
type 'a t =
| Atomic: 'a -> 'a t
| Uni_composite : ('b->'a) * ('b t) -> 'a t
| Bi_composite : ('b1->'b2->'a) * 'b1 t * 'b2 t -> 'a t
| Tri_composite : ('b1->'b2->'b3->'a) * 'b1 t * 'b2 t * 'b3 t -> 'a t
What you describe should then be fairly reasonably implementable If I understand correctly (If react doesn’t match your use case).
React certainly resembles what I’m looking for, but I’m not sure it’s the answer.
I tried the following with it :
open React;;
let (x1,set_x1)=E.create ();;
let ref_for_x1=ref(0);;
let store_x1=E.map (fun v->ref_for_x1:=v) x1;;
let (x2,set_x2)=E.create ();;
let ref_for_x2=ref(0);;
let store_x2=E.map (fun v->ref_for_x2:=v) x2;;
let x3 =E.l2 (fun t1 t2->t1+t2) x1 x2;;
let ref_for_x3=ref(0);;
let store_x3=E.map (fun v->ref_for_x3:=v) x3;;
set_x1 7;;
set_x2 100;;
ref_for_x1;;
ref_for_x2;;
ref_for_x3;;
Unfortunately, ref_for_x3 does not hold the expected value after this code
is executed. Perhaps I can access the “current value” of x1 directly without using refs ?
From what I read, you actually want what react calls a signal, which can be seen as a reference whose value can be updated. So you would actually use the following code:
let x1, set_x1 = React.S.create 0
let x2, set_x2 = React.S.create 0
let x3, set_x3 = React.S.create 0
let () =
set_x1 7;
set_x2 100;
assert (React.S.value x1 = 7);
assert (React.S.value x2 = 100);
assert (React.S.value x3 = 0);
EDIT: sorry for the syntax errors, I misclicked and it sent the post before I finished it.
So, when the typos have been corrected, your snippet becomes :
let (x1,set_x1)=React.S.create 0;;
let (x2,set_x2)=React.S.create 0;;
let x3=React.S.l2 (fun x y->x+y) x1 x2;;
set_x1 7;;
set_x2 100;;
assert(React.S.value x3 =107);;
This yields the expected result, but only solves part of my problem, because with this implementation when a ref is changed all the refs depending on it are automatically recomputed. As I said in my original question, I need a more lazy implementation, so that when a ref is changed all the refs depending on it are merely marked as out-of-date (and will be recomputed only if asked).
Oh right ! The more I think about it, the more it looks like you have some kind of (potentially dynamic) computation graph, which you want to lazily memoize and evaluate, which kinda feels like what a build system does. Maybe you can have a look at maki, which implements a way to memoize computations, and only recompute them if a dependency has changed ?
Indeed, Incremental sounds like a decent match. You can read a bit more about it here:
There’s also a slightly out-of-date tutorial here that teaches you how to use some useful companion libraries, notably Incr_map. Incr_map provides nice ways of operating incrementally over maps in a way that takes advantage of their diffability, while fitting nicely into the Incremental framework.