Lazy functional reactive programming


#1

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 :

  1. Every value of type t is either atomic or composite.
  2. A value returned by new_atomic is always atomic, and a value returned by one of the several _composite functions is always composite.
  3. Atomic values behave like ordinary refs with respect to change_value and get_current_value.
  4. change_value raises an exception if called on a non-atomic (i.e. composite) value.
  5. 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.
  6. 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 :

  1. Is there a GADT trick to translate the above snippet into valid OCaml code ?
  2. 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 ?

#2

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).


#3

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 ?


#4

Why do you use references in this example ?

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.


#5

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).

I’m not sure if I can do it with React.


#6

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 ?


#7

@Yaron_Minsky could probably say more, but if I remember correctly, janestreet’s Incremental library has exactly the semantics you want.


#8

That seems to fit what is described in the first section of this doc yes.


#9

Indeed ! _______________


#10

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.

y