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.