Obj.magic and existential types.

Obj.magic and existential types.

[Guillaume Yziquel]

Hello.

Please don't scream: I've been using Obj.magic...

But the result is rather interesting. It can record a flow of 
computations, and recompute them only when upstream data has been modified:

> # let (n', n) = Dependent.encapsulate 1;;
> val n' : int Dependent.data = <abstr>
> val n : int Dependent.t = <abstr>
> # let (_, next) = Dependent.encapsulate (fun x -> x + 1);;
> val next : (int -> int) Dependent.t = <abstr>
> # let m = Dependent.apply next n;;
> val m : int Dependent.t = <abstr>
> # Dependent.access m;;
> - : int = 2
> # Dependent.set n' 3;;
> - : unit = ()
> # Dependent.access m;;
> - : int = 4

The piece of code responsible for this behaviour is at the end of the 
message.

I learnt that I could perhaps overcome the use of Obj.magic by using 
existential types. I was advised to read the following post on this topic:

http://caml.inria.fr/pub/ml-archives/caml-list/2004/01/52732867110697f55650778d883ae5e9.en.html

However, I do not really understand how Daniel implemented existential 
types there, and I do not really see how it can be adapted to my code. 
Suggestions welcomed.

Here's the code, rather disorganised at the moment.

All the best,

Guillaume Yziquel.


> type read;;
> type write;;
> 
> type 'a computation = (Obj.t -> 'a) t * Obj.t t
> 
> and ('a, 'b) aux_t = Dependent of
>   ( 'a option ref *
>     'a computation option *
>     Obj.t t list ref)
> 
> and 'a data = ('a, write) aux_t
> and 'a t    = ('a, read)  aux_t;;
> 
> let encapsulate (x : 'a) : ('a data) * ('a t) =
>   let z = Dependent ((ref (Some x)), None, (ref [])) in (z, z);;
> 
> let add_dependency (alpha : 'a t) (beta : 'b t) =
>   let Dependent (_, _, dep) = alpha in
>   dep := ((Obj.magic beta) : Obj.t t)::!dep;;
> 
> let apply (f : ('b -> 'a) t) (x : 'b t) : 'a t =
>   let computation : 'a computation =
>     ((Obj.magic f) : (Obj.t -> 'a) t),
>     ((Obj.magic x) : Obj.t         t) in
>   let f_x : 'a t = Dependent (
>     ((ref None)         : 'a option ref),
>     ((Some computation) : 'a computation option),
>     ((ref [])           : Obj.t t list ref)) in
>   add_dependency f f_x;
>   add_dependency x f_x;
>   f_x;;
> 
> exception Undefined;;
> 
> module rec Aux :
> sig
> 
>   val access : 'a t -> 'a
>   val update : 'a t -> ('b -> 'a) t -> 'b t -> 'a
>   val reset  : 'a t -> unit
> 
> end = struct
> 
>   let rec access y =
>     let Dependent (opt_ref_x, comp_opt, _) = y in
>     match !opt_ref_x with | Some x -> x | None ->
>     begin match comp_opt with
>       | None -> raise Undefined
>       | Some (fun_t, arg_t) -> Aux.update y fun_t arg_t
>     end
> 
>   and update y fun_t arg_t =
>     let Dependent (opt_ref_x, _, dependencies) = y in
>     List.iter Aux.reset !dependencies;
>     let result = (Aux.access fun_t) (Aux.access arg_t) in
>     opt_ref_x := Some result; result
> 
>   and reset z =
>     let Dependent (opt_ref_x, _, dependencies) = z in
>     match !opt_ref_x with
>     | None -> () | Some _ -> begin
>         opt_ref_x := None;
>         List.iter Aux.reset !dependencies
>     end;;
> 
> end;;
> 
> include Aux;;
> 
> exception Flawed_implementation;;
> 
> let set (x : 'a data) (v : 'a) : unit =
>   let Dependent (opt_ref_x, comp_opt, dependencies) = x in
>   match comp_opt with | Some _ -> raise Flawed_implementation | None ->
>   begin List.iter Aux.reset !dependencies;
>         opt_ref_x := Some v
>   end;;

-- 
      Guillaume Yziquel
http://yziquel.homelinux.org/

Re: Obj.magic and existential types.

[Daniel Bünzli]

Le 19 juin 09 à 19:42, Guillaume Yziquel a écrit :

> But the result is rather interesting. It can record a flow of  
> computations, and recompute them only when upstream data has been  
> modified:

Not directly responding to your question but you are looking for  
functional reactive programming (frp).

http://erratique.ch/software/react

I rewrote your example below with react (no magic used).

Best,

Daniel

 > ocaml react.cmo
         Objective Caml version 3.11.0

# open React;;
# let n, set_n = S.create 1;;
val n : int React.signal = <abstr>
val set_n : int -> unit = <fun>
# let m = S.map (fun x -> x + 1) n ;;
val m : int React.signal = <abstr>
# S.value m;;
- : int = 2
# set_n 3;;
- : unit = ()
# S.value m;;
- : int = 4

Re: Obj.magic and existential types.

[Guillaume Yziquel]

Daniel Bünzli a écrit :
> 
> Not directly responding to your question but you are looking for 
> functional reactive programming (frp).
> 
> http://erratique.ch/software/react
> 
> I rewrote your example below with react (no magic used).
> 
> Best,
> 
> Daniel

Thanks a lot. Very good to know. That will save me time.

Just a side question: how thread-safe is React?

All the best,

Guillaume Yziquel.

Re: Obj.magic and existential types.

[Daniel Bünzli]

Le 19 juin 09 à 20:30, Guillaume Yziquel a écrit :

> Just a side question: how thread-safe is React?

Read the documentation.

http://erratique.ch/software/react/doc/React#update

Best,

Daniel

Re: [Caml-list] Re: Obj.magic and existential types.

[Jake Donham]

On Fri, Jun 19, 2009 at 11:21 AM, Daniel
Bünzli<daniel.buenzli@erratique.ch> wrote:
> Not directly responding to your question but you are looking for functional
> reactive programming (frp).
>
> http://erratique.ch/software/react

You can also find FRP in froc (which is quite similar to React; the
main difference is that it works in browsers):

  http://code.google.com/p/froc/

# open Froc_afp;;
# let n = return 1;;
val n : int Froc_afp.t = <abstr>
# let m = n >>= fun x -> return (x + 1);;
val m : int Froc_afp.t = <abstr>
# read m;;
- : int = 2
# write n 3;;
- : unit = ()
# propagate ();;
- : unit = ()
# read m;;
- : int = 4

Re: [Caml-list] Re: Obj.magic and existential types.

[Daniel Bünzli]

Le 19 juin 09 à 20:47, Jake Donham a écrit :

> You can also find FRP in froc (which is quite similar to React; the
> main difference is that it works in browsers):

Theoretically React may also work in browsers via o'browsers (http://ocsigen.org/obrowser 
) but I never tried.

Correct me if I'm wrong but from my perspective froc is different from  
react in that it leaks memory (see example below) and is less thread  
friendly (because it uses global datastructures).

Best,

Daniel

The following froc program consumes an unbounded amount of memory :

> open Froc_afp;;
>
> let n = return 1;;
>
> let () =
>   while true do
>     let m = n >>= fun x -> return (x + 1) in
>     print_int (read m);
>     Gc.full_major ();
>   done

The following equivalent react program consumes a bounded amount of  
memory :

> open React;;
>
> let n, _ = S.create 1
>
> let () =
>   while true do
>     let m = S.map (fun x -> x + 1) n in
>     print_int (S.value m);
>     Gc.full_major ();
>   done
>

Re: [Caml-list] Re: Obj.magic and existential types.

[Jake Donham]

On Sat, Jun 20, 2009 at 1:30 AM, Daniel
Bünzli<daniel.buenzli@erratique.ch> wrote:
> Theoretically React may also work in browsers via o'browsers
> (http://ocsigen.org/obrowser) but I never tried.

I have not tried either, but from a cursory glance at the code I have
the impression that React's space safety relies on support for weak
references, which standard Javascript does not have.

> Correct me if I'm wrong but from my perspective froc is different from react
> in that it leaks memory (see example below) and is less thread friendly
> (because it uses global datastructures).

Less thread-friendly, sure. Leaks memory, yes in your example, but in
a less contrived usage, where dead references are underneath a bind,
froc cleans up after itself. E.g.:

  open Froc_afp;;

  let n = return 1;;
  let i = return 0;;

  let _ = i >>= fun i ->
    let m = n >>= fun x -> return (x + 1) in
    print_int (read m);
    return ();;

  let () =
    let iref = ref 0 in
    while true do
      incr iref;
      write i !iref;
      propagate ();
      Gc.full_major ();
    done;;

As before a new value of m is created each time around the loop, but
since it is under the bind of i, froc is able to clean it up when i's
dependencies are recomputed.

Without weak references I don't know how else to implement space
safety. But I am prepared to be enlightened :). Best regards,

Jake

Re: [Caml-list] Re: Obj.magic and existential types.

[Yaron Minsky]

[-- Attachment #1: Type: text/plain, Size: 318 bytes --]

On Sun, Jun 21, 2009 at 2:08 PM, Jake Donham <jake@donham.org> wrote:

> Without weak references I don't know how else to implement space
> safety. But I am prepared to be enlightened :). Best regards,
>

I believe you can pull it off with finalizers as well, but I don't know
whether Javascript has those, either.

y

[-- Attachment #2: Type: text/html, Size: 634 bytes --]

Re: [Caml-list] Re: Obj.magic and existential types.

[Daniel Bünzli]

Le 21 juin 09 à 20:08, Jake Donham a écrit :

> I have not tried either, but from a cursory glance at the code I  
> have the impression that React's space safety relies on support for  
> weak references, which standard Javascript does not have.

Yes.

The weak module is available in obrowser, but I don't know if it  
implements its semantics. If the author of obrowser is on this list  
would he be kind enough to enlight us ?

> Leaks memory, yes in your example, but in a less contrived usage,  
> where dead references are underneath a bind,

Does that mean the only values froc knows how to garbage collect are  
those values that are dynamically created in an update cycle and not  
used further ? (because that's rather contrived IMHO)

While excessive in allocation rate the example I gave is not that  
contrived e.g. the same pattern occurs naturally in the terminal  
breakout game present in react's distribution : each time a new game  
starts a record of signals is created to manage the simulation and  
game logic and these signals need to be eventually gc'd when the game  
is over.

Best,

Daniel

Re: [Caml-list] Re: Obj.magic and existential types.

[Benjamin Canou]

Daniel Bünzli a écrit :
>
> Le 21 juin 09 à 20:08, Jake Donham a écrit :
>
>> I have not tried either, but from a cursory glance at the code I have 
>> the impression that React's space safety relies on support for weak 
>> references, which standard Javascript does not have.
>
> Yes.
>
> The weak module is available in obrowser, but I don't know if it 
> implements its semantics. If the author of obrowser is on this list 
> would he be kind enough to enlight us ?
Abstract: The weak.js file remaining in the distro is a mistake. I see 
possibilities to implement them but have no short term plans for a 
perfect solution.

Well... there is no such a file as this garbage weak.js in the 
distribution, it must have spawn by itself in your computer ;-)
Indeed there is no such mechanism in JS. I have ideas to implement them 
on top of JS, in particular a trivial solution involving reference 
counters and updating weak arrays incrementally every N VM instructions 
could suffice in some cases (but induce memory leaks in presence of 
cycles through the weak value, of course). There are more satisfying 
possibilities but I have yet to figure out one with good complexity, 
incremental, and not too hard to implement (in particular not too 
intrusive in other parts of the VM).
 
  Cheers.

PS: btw, there is now a darcs repo for obrowser at ocsigen.org for those 
who didn't know

Re: [Caml-list] Re: Obj.magic and existential types.

[Jake Donham]

On Sun, Jun 21, 2009 at 5:03 PM, Daniel
Bünzli<daniel.buenzli@erratique.ch> wrote:
> Does that mean the only values froc knows how to garbage collect are those
> values that are dynamically created in an update cycle and not used further
> ? (because that's rather contrived IMHO)

Everything in froc happens on a "timeline". When you bind a changeable
value, there's a chunk of the timeline that corresponds to the dynamic
scope of the bind function. When the value changes, that chunk is
removed, which unregisters any dependencies created in the course of
evaluating the bind function.

So it is true that dependencies created outside a bind are not
removed; but you can always fix this by wrapping everything in a
top-level bind (as in the code I posted).

Best regards,

Jake

Re: [Caml-list] Re: Obj.magic and existential types.

[Daniel Bünzli]

Le 22 juin 09 à 11:19, Benjamin Canou a écrit :

> Abstract: The weak.js file remaining in the distro is a mistake. I  
> see possibilities to implement them but have no short term plans for  
> a perfect solution.

Thanks for your response. Since it allows to compile more sources  
without changes I'd leave the weak support in obrowser, but I'd make  
it clear in the documentation that so far no weak pointer will ever be  
reclaimed.

So to sum up using react in obrowser will leak, however it doesn't  
leak in "traditional" environments.

Le 22 juin 09 à 19:02, Jake Donham a écrit :

> Everything in froc happens on a "timeline". When you bind a changeable
> value, there's a chunk of the timeline that corresponds to the dynamic
> scope of the bind function. When the value changes, that chunk is
> removed, which unregisters any dependencies created in the course of
> evaluating the bind function.

But in this "chunk" can you repeatedly get external (in the sense  
primitive) input ?

Because _if_ you can't then in the breakout game example where you  
need to constantly gather (external) time and keyboards events you  
cannot "pipe" those under a single bind where you create the game  
simulation and logic signals needed  for a game run as any new  
keyboard or time event would garbage collect them. In that case the  
game signals need to be defined outside a toplevel bind and cannot be  
garbage collected by froc, it wouldn't be fixed "by wrapping  
everything in a top-level bind".

Best,

Daniel

Re: [Caml-list] Re: Obj.magic and existential types.

[Jake Donham]

On Mon, Jun 22, 2009 at 5:24 PM, Daniel
Bünzli<daniel.buenzli@erratique.ch> wrote:
> But in this "chunk" can you repeatedly get external (in the sense primitive)
> input ?
>
> Because _if_ you can't then in the breakout game example where you need to
> constantly gather (external) time and keyboards events you cannot "pipe"
> those under a single bind where you create the game simulation and logic
> signals needed  for a game run as any new keyboard or time event would
> garbage collect them. In that case the game signals need to be defined
> outside a toplevel bind and cannot be garbage collected by froc, it wouldn't
> be fixed "by wrapping everything in a top-level bind".

I don't totally understand your objection here. Perhaps the question
could be resolved (one way or the other) if I were to port the
breakout game to froc. In the meantime, there are several web browser
examples here:

  http://froc.googlecode.com/svn/examples/index.html

which take external input and do not leak memory. Best regards,

Jake

Re: [Caml-list] Re: Obj.magic and existential types.

[Jake Donham]

On Mon, Jun 22, 2009 at 5:24 PM, Daniel
Bünzli<daniel.buenzli@erratique.ch> wrote:
> But in this "chunk" can you repeatedly get external (in the sense primitive)
> input ?

I looked at your breakout implementation and I think I understand your
concern now. In your code there is a top-level select loop that feeds
keystrokes and clock ticks into the system, so you are asking whether
those events can be fed into the top-level bind.

I think the answer is yes. A froc event (same as a React event) can be
created outside the top-level bind, and behaviors (React signals) can
depend on it. But of course the proof is in the implementation; I will
give it a try.

Best regards,

Jake