"Ref" and copy of functions

"Ref" and copy of functions

[Pierre-Evariste Dagand]

Hi Caml-list,

I'm looking for advices about a "clean way" of doing something which,
by design, isn't. So, let states the problem.

I'm doing a combinator library based on Arrows for a Yampa-like system :

type ('a,'b) arrow = Arrow of ( 'a -> 'b )

Thus, I can instantiate an arrow with :

let arr f = Arrow ( f )
val arr : ('a -> 'b) -> ('a, 'b) arrow

Then, I have, for example, the composition of arrows :

let (>>>) (Arrow f) (Arrow g) =Arrow ( fun  c -> g  ( f  c ) )
val ( >>> ) : ('a, 'b) arrow -> ('b, 'c) arrow -> ('a, 'c) arrow

Right here, everything plays well (excepted some weak type variables
issues but that's not a big deal).

But (and that's here that the trouble is) I need a "loop" combinator,
that I wrote this way :

let loop init (Arrow f) =
  let state = ref init in
    Arrow (
      fun c ->
        let new_state , output = f ( !state , c ) in
          state := new_state;
          output
    )
val loop : 'a -> ('a * 'b, 'a * 'c) arrow -> ('b, 'c) arrow

Finally, I can write a small arrow  :

let arr_counter = loop 0 ( arr ( fun ( counter , x ) -> counter+1 ,
counter+x ) )
let arr_double = arr ( fun x -> 2*x )
let arr_my_small_arrow = arr_counter >>> arr_double

And I execute it with :

let run (Arrow f) input =
  f  input
val run : ('a, 'b) arrow -> 'a -> 'b

And it works. Right.

But now, I would like to be able to "copy" a built arrow and to be
able to execute the copy without side-effecting on the first one.
Obviously, I cannot do that in this implementation.

My current solution is really *ugly* :

let arrow_string = Marshal.to_string arrow [ Marshal.No_sharing ;
Marshal.Closures ]

Then I "Marshal.from_string arrow_string". I'm not even sure if it
will not blow out of my hands with "strange" things in the Ref cell.

I'm aware of implementations in CPS but I use to think that it has a
performance cost that I'm not ready to pay (I'm fighting against a C++
code so...).

So if someone knows an elegant solution to my problem (if someone has
read this mail until here), please let me know :-)


Best regards,



P.S.: For those who are just curious, these combinators are used in a
functional-reactive library for Peer-to-Peer overlays programming.

-- 
Pierre-Evariste DAGAND
http://perso.eleves.bretagne.ens-cachan.fr/~dagand/

Re: "Ref" and copy of functions

[Zheng Li]

 
Hi,  "Pierre-Evariste Dagand" <pedagand@gmail.com> writes: > I'm 
looking for advices about a "clean way" of doing something which, 
> by design, isn't. So, let states the problem.  > I'm doing a 
combinator library based on Arrows for a Yampa-like system :  I 
don't understand what "arrow" is and the rational behind it, so 
don't take my suggestion seriously.   > type ('a,'b) arrow = Arrow 
of ( 'a -> 'b ) > let arr f = Arrow ( f ) > val arr : ('a -> 'b) 
-> ('a, 'b) arrow > let (>>>) (Arrow f) (Arrow g) =Arrow ( fun  c 
-> g  ( f  c ) ) > let loop init (Arrow f) = >   let state = ref 
init in >     Arrow ( >       fun c -> >         let new_state , 
output = f ( !state , c ) in >           state := new_state; > 
output >     ) > let arr_counter = loop 0 ( arr ( fun ( counter , 
x ) -> counter+1 , > counter+x ) ) > let arr_double = arr ( fun x 
-> 2*x ) > let arr_my_small_arrow = arr_counter >>> arr_double > 
let run (Arrow f) input = >   f  input  At least on this 
particular example, you can use the following encoding (I 
deliberately use rectypes here, but you can always use extra 
variant instead)

---definition---
 
(* Only in mind: type ('a,'b) arrow = 'a -> 'b * ('a, 'b) arrow;; 
*)

let rec arr f x = f x, arr f;;

let rec (>>>) f g x = 
  let rf,nf = f x in let rg,ng = g rf in
  rg, nf >>> ng;;

let rec loop init f x =
  let ((init', r), n) = f (init,x) in
  r, loop init' n;;

let rec run f = function
  | [] -> []
  | h::t -> let r,n = f h in r :: run n t;;

---test---

let arr_counter = loop 0 (arr (fun (c,x) -> c+1,c+x));;

let arr_double = arr (( * ) 2);;

let arr_my_small_arrow = arr_counter >>> arr_double;;

run arr_my_small_arrow [6;5;4;3];;
- : int list = [12; 12; 12; 12]
 
Since it doesn't use mutable variable, it's free to make copy.   > 
P.S.: For those who are just curious, these combinators are used 
in a > functional-reactive library for Peer-to-Peer overlays 
programming.   It looks like "arrow" is for some kind of flow-like 
programming, then you may also take a look at SDFlow [1]. Your 
example can be encoded in a point-free style as 

---flow---
 
let arr_counter = 
  comb |- map (fun (x,c) -> x+c,c+1) |- split |> curry |- 
  feedr[<'0>];;

let arr_double = map (( * ) 2);;

let arr_my_small_arrow = arr_counter |- arr_double;;

arr_my_small_arrow [<'6;'5;'4;'3>] |> to_list;;
- : int list = [12; 12; 12; 12]

Note however, SDFlow is just a proof of concept. The syntax on 
recursion can be made much more straightforward with some camlp4 
script to allow recursive value with preconditions. I just don't 
have time to do that. 

HTH.

-- 
Zheng Li
http://www.pps.jussieu.fr/~li

Re: [Caml-list] Re: "Ref" and copy of functions

[David Teller]

Speaking of SDFlow, I've slightly extended it with three functions
to_array, to_stream and of_array. I may extend it a bit further, but I
don't think so. Do you accept submissions ?

I've also made use of SDFlow in a Camlp4 extension for stream
comprehension, by the way. I'll try and publish this within a few days.

Cheers,
 David


On Fri, 2007-12-14 at 11:49 +0100, Zheng Li wrote:

> Note however, SDFlow is just a proof of concept. The syntax on 
> recursion can be made much more straightforward with some camlp4 
> script to allow recursive value with preconditions. I just don't 
> have time to do that. 
> 
> HTH.

-- 
David Teller
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
 Angry researcher: French Universities need reforms, but the LRU act brings liquidations. 

Re: "Ref" and copy of functions

[Zheng Li]

Hello, 

David Teller <David.Teller@ens-lyon.org> writes:
> Speaking of SDFlow, I've slightly extended it with three functions
> to_array, to_stream and of_array. I may extend it a bit further, but I
> don't think so. Do you accept submissions ?
Sure, submissions are always welcome, or you may derive new version
based on it as you like. 

> I've also made use of SDFlow in a Camlp4 extension for stream
> comprehension, by the way. I'll try and publish this within a few days.
Glad to know.

Best wishes.
-- 
Zheng Li
http://www.pps.jussieu.fr/~li

Re: [Caml-list] Re: "Ref" and copy of functions

[Pierre-Evariste Dagand]

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

Hi,

> At least on this
> particular example, you can use the following encoding (I
> deliberately use rectypes here, but you can always use extra
> variant instead)
>
> (...)
>
> Since it doesn't use mutable variable, it's free to make copy.

Yes, that's a CPS-way of doing things. I am aware of it and my first
implementation was in this style.

The reasons why I decided to switch to Ref were that :
  1/ The implementation is much more "intuitive" (I don't have a CPS
pre-processor in my brain)
  2/ I thought I could get rid of my hack (Marshal/UnMarshal) easily
  3/ I used to think that I will be faster

Point 1 is not a problem, Santa Claus might bring me this CPS
pre-processor in a few days.

Point 2 seems to be wrong : being fast is nice but if it's for hitting
the wall, well... one should slow down. And for the moment, I haven't
found a clean solution and I'm not sure whether my hack is safe or
not.

So, remains point 3. That's why I have carried out an experience on my
initial Ref implementation, your Rectypes implementation and a CPS
implementation without rectypes (because rectypes frighten me).

%%%%%%%%%%%%%%%%%%%

----------------------------
Ref implementation :
----------------------------

type ('a,'b) arrow = Arrow of ( 'a -> 'b )
let arr f = Arrow (  f )
let (>>>) (Arrow f) (Arrow g) =Arrow ( fun  c -> g  ( f  c ) )
let loop init (Arrow f) =
  let state = ref init in
    Arrow ( fun c ->
                   let new_state , output = f ( !state , c ) in
                     state := new_state;
                     output
              )
let run (Arrow f) input =
  f  input

-----------------------------------
Rectypes implementation :
------------------------------------

let rec arr f x = f x, arr f

let rec (>>>) f g x =
  let rf,nf = f x in let rg,ng = g rf in
 rg, nf >>> ng

let rec run f x ?(i=0) max_inc =
  if i = max_inc then
    x
  else
    let _,n = f x in
      run n x ~i:(i+1) max_inc

--------------------------------------
Variant CPS implementation :
--------------------------------------

type ('a,'b) arrow = Arrow of ( 'a -> 'b * ('a,'b) arrow )

let rec arr f = Arrow ( fun x -> f x , arr f );;

let rec (>>>) (Arrow f) (Arrow g) =
  Arrow (
    fun x ->
      let rf,nf = f x in
      let rg,ng = g rf in
        rg , nf >>> ng
  )

let loop init f  =
  let rec loop_aux c (Arrow f) =
    Arrow (
      fun x->
        let ((c', r), n) = f (c,x) in
          r , loop_aux c' n
    )
  in
    loop_aux init f

let rec run (Arrow f) x ?(i=0) max_inc =
  if i = max_inc then
    x
  else
    let _,n = f x in
      run n x ~i:(i+1) max_inc


%%%%%%%%%%%%%%%%%%%%%

Then I wrote a small test :

%%%%%%%%%%%%%%%%%%%%%

let pair_to_simple (x,y) = x
let arr_pair_to_simple () = arr pair_to_simple
let simple_to_pair x = (x,x)
let arr_simple_to_pair () = arr simple_to_pair
let arr_incr = arr ( fun ( c , x ) -> c + 1 , c + x )
let arr_counter1 = loop 1 arr_incr
let arr_incr1 = (arr_pair_to_simple ()) >>> arr_counter1 >>>
(arr_simple_to_pair ())
let arr_counter2 = loop 2 arr_incr1
let arr_incr2 = (arr_pair_to_simple ()) >>> arr_counter2 >>>
(arr_simple_to_pair ())
let arr_counter3 = loop 3 arr_incr2
let arr_incr3 = (arr_pair_to_simple ()) >>> arr_counter3 >>>
(arr_simple_to_pair ())
let arr_counter4 = loop 4 arr_incr3
let arr_incr4 = (arr_pair_to_simple ()) >>> arr_counter4 >>>
(arr_simple_to_pair ())
let arr_counter5 = loop 5 arr_incr4
let arr_incr5 = (arr_pair_to_simple ()) >>> arr_counter5 >>>
(arr_simple_to_pair ())
let arr_counter6 = loop 6 arr_incr5
let arr_incr6 = (arr_pair_to_simple ()) >>> arr_counter6 >>>
(arr_simple_to_pair ())
let arr_counter7 = loop 7 arr_incr6
let arr_incr7 = (arr_pair_to_simple ()) >>> arr_counter7 >>>
(arr_simple_to_pair ())
let arr_counter8 = loop 8 arr_incr7
let arr_incr8 = (arr_pair_to_simple ()) >>> arr_counter8 >>>
(arr_simple_to_pair ())
let arr_counter9 = loop 9 arr_incr8
let arr_incr9 = (arr_pair_to_simple ()) >>> arr_counter9 >>>
(arr_simple_to_pair ())
let arr_counter10 = loop 10 arr_incr9
let arr_incr10 = (arr_pair_to_simple ()) >>> arr_counter10 >>>
(arr_simple_to_pair ())
let arr_counter11 = loop 11 arr_incr10
let arr_incr11 = (arr_pair_to_simple ()) >>> arr_counter11 >>>
(arr_simple_to_pair ())
let arr_counter12 = loop 12 arr_incr11
let arr_incr12 = (arr_pair_to_simple ()) >>> arr_counter12 >>>
(arr_simple_to_pair ())
let arr_my_arrow () = ( arr_simple_to_pair () ) >>> arr_incr12

%%%%%%%%%%%%%%%%%%%%%%%%

Finally, I measured the processing time with :

%%%%%%%%%%%%%%%%%%%%%%%%

-------------
For Ref
-------------

let _ =
  let ntest =  100000 in
  let start_time = Unix.gettimeofday () in
  let arr_my_arrow = arr_my_arrow () in
    for i=0 to ntest-1 do
      let _ = run arr_my_arrow 2 in
        ()
    done;
    let end_time = Unix.gettimeofday () in
    let time = ( end_time -. start_time ) /. (float_of_int ntest) *.
1000000.0 in
      Printf.printf "Mean processing time : %f microseconds\n" time;

--------------------
For CPS (both)
--------------------

let _ =
  let ntest = 100000 in
  let arr_my_arrow = arr_my_arrow () in
  let start_time = Unix.gettimeofday () in
  let _ = run arr_my_arrow 2 ntest in
    ();
    let end_time = Unix.gettimeofday () in
    let time = ( end_time -. start_time ) /. (float_of_int ntest) *.
1000000.0 in
      Printf.printf "Mean processing time : %f microseconds\n" time;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

And the results are ...
  1/ Ref : 0.75 microseconds
  2/ Variant CPS : 2.69 microseconds
  3/ Rectypes : 2.80 microseconds
[ compiled with ocamlopt.opt, with -rectypes for 3/ ]

It's about 4 times longer and, against a C++ code, I fear that I can't
afford it.

> It looks like "arrow" is for some kind of flow-like
> programming, then you may also take a look at SDFlow [1].

Yes, it does. For more info : http://www.haskell.org/arrows/

I will take a look at SDFlow, thanks for the hint.

> HTH.

Thanks,

-- 
Pierre-Evariste DAGAND

[-- Attachment #2: measure_ref.ml --]
[-- Type: application/octet-stream, Size: 2495 bytes --]

type ('a,'b) arrow = Arrow of ( 'a -> 'b )

let arr f = Arrow (  f )

let (>>>) (Arrow f) (Arrow g) =
  Arrow ( 
    fun  c ->
      g  ( f  c )
  )

let loop init (Arrow f) = 
  let state = ref init in
    Arrow (
      fun c ->
	let new_state , output = f ( !state , c ) in
	  state := new_state;
	  output
    )

let run (Arrow f) input =
  f  input



let pair_to_simple (x,y) = x
let arr_pair_to_simple () = arr pair_to_simple

let simple_to_pair x = (x,x)
let arr_simple_to_pair () = arr simple_to_pair

let arr_incr = arr ( fun ( c , x ) -> c + 1 , c + x )

let arr_counter1 = loop 1 arr_incr
let arr_incr1 = (arr_pair_to_simple ()) >>> arr_counter1 >>> (arr_simple_to_pair ())

let arr_counter2 = loop 2 arr_incr1
let arr_incr2 = (arr_pair_to_simple ()) >>> arr_counter2 >>> (arr_simple_to_pair ())

let arr_counter3 = loop 3 arr_incr2
let arr_incr3 = (arr_pair_to_simple ()) >>> arr_counter3 >>> (arr_simple_to_pair ())

let arr_counter4 = loop 4 arr_incr3
let arr_incr4 = (arr_pair_to_simple ()) >>> arr_counter4 >>> (arr_simple_to_pair ())

let arr_counter5 = loop 5 arr_incr4
let arr_incr5 = (arr_pair_to_simple ()) >>> arr_counter5 >>> (arr_simple_to_pair ())

let arr_counter6 = loop 6 arr_incr5
let arr_incr6 = (arr_pair_to_simple ()) >>> arr_counter6 >>> (arr_simple_to_pair ())

let arr_counter7 = loop 7 arr_incr6
let arr_incr7 = (arr_pair_to_simple ()) >>> arr_counter7 >>> (arr_simple_to_pair ())

let arr_counter8 = loop 8 arr_incr7
let arr_incr8 = (arr_pair_to_simple ()) >>> arr_counter8 >>> (arr_simple_to_pair ())

let arr_counter9 = loop 9 arr_incr8
let arr_incr9 = (arr_pair_to_simple ()) >>> arr_counter9 >>> (arr_simple_to_pair ())

let arr_counter10 = loop 10 arr_incr9
let arr_incr10 = (arr_pair_to_simple ()) >>> arr_counter10 >>> (arr_simple_to_pair ())

let arr_counter11 = loop 11 arr_incr10
let arr_incr11 = (arr_pair_to_simple ()) >>> arr_counter11 >>> (arr_simple_to_pair ())

let arr_counter12 = loop 12 arr_incr11
let arr_incr12 = (arr_pair_to_simple ()) >>> arr_counter12 >>> (arr_simple_to_pair ())

let arr_my_arrow () = ( arr_simple_to_pair () ) >>> arr_incr12;;


let _ =
  let ntest =  100000 in
  let start_time = Unix.gettimeofday () in
  let arr_my_arrow = arr_my_arrow () in
    for i=0 to ntest-1 do
      let _ = run arr_my_arrow 2 in
	()
    done;
    let end_time = Unix.gettimeofday () in
    let time = ( end_time -. start_time ) /. (float_of_int ntest) *. 1000000.0 in
      Printf.printf "Mean processing time : %f microseconds\n" time;

[-- Attachment #3: measure_rectypes.ml --]
[-- Type: application/octet-stream, Size: 2434 bytes --]

let rec arr f x = f x, arr f;;

let rec (>>>) f g x =
  let rf,nf = f x in let rg,ng = g rf in
 rg, nf >>> ng;;

let rec loop init f x =
  let ((init', r), n) = f (init,x) in
 r, loop init' n;;

let rec run f x ?(i=0) max_inc = 
  if i = max_inc then
    x
  else
    let _,n = f x in
      run n x ~i:(i+1) max_inc
	

let pair_to_simple (x,y) = x
let arr_pair_to_simple () = arr pair_to_simple

let simple_to_pair x = (x,x)
let arr_simple_to_pair () = arr simple_to_pair

let arr_incr = arr ( fun ( c , x ) -> c + 1 , c + x )

let arr_counter1 = loop 1 arr_incr
let arr_incr1 = (arr_pair_to_simple ()) >>> arr_counter1 >>> (arr_simple_to_pair ())

let arr_counter2 = loop 2 arr_incr1
let arr_incr2 = (arr_pair_to_simple ()) >>> arr_counter2 >>> (arr_simple_to_pair ())

let arr_counter3 = loop 3 arr_incr2
let arr_incr3 = (arr_pair_to_simple ()) >>> arr_counter3 >>> (arr_simple_to_pair ())

let arr_counter4 = loop 4 arr_incr3
let arr_incr4 = (arr_pair_to_simple ()) >>> arr_counter4 >>> (arr_simple_to_pair ())

let arr_counter5 = loop 5 arr_incr4
let arr_incr5 = (arr_pair_to_simple ()) >>> arr_counter5 >>> (arr_simple_to_pair ())

let arr_counter6 = loop 6 arr_incr5
let arr_incr6 = (arr_pair_to_simple ()) >>> arr_counter6 >>> (arr_simple_to_pair ())

let arr_counter7 = loop 7 arr_incr6
let arr_incr7 = (arr_pair_to_simple ()) >>> arr_counter7 >>> (arr_simple_to_pair ())

let arr_counter8 = loop 8 arr_incr7
let arr_incr8 = (arr_pair_to_simple ()) >>> arr_counter8 >>> (arr_simple_to_pair ())

let arr_counter9 = loop 9 arr_incr8
let arr_incr9 = (arr_pair_to_simple ()) >>> arr_counter9 >>> (arr_simple_to_pair ())

let arr_counter10 = loop 10 arr_incr9
let arr_incr10 = (arr_pair_to_simple ()) >>> arr_counter10 >>> (arr_simple_to_pair ())

let arr_counter11 = loop 11 arr_incr10
let arr_incr11 = (arr_pair_to_simple ()) >>> arr_counter11 >>> (arr_simple_to_pair ())

let arr_counter12 = loop 12 arr_incr11
let arr_incr12 = (arr_pair_to_simple ()) >>> arr_counter12 >>> (arr_simple_to_pair ())

let arr_my_arrow () = ( arr_simple_to_pair () ) >>> arr_incr12;;

let _ =
  let ntest =  100000 in
  let arr_my_arrow = arr_my_arrow () in
  let start_time = Unix.gettimeofday () in
  let _ = run arr_my_arrow 2 ntest in
    ();
    let end_time = Unix.gettimeofday () in
    let time = ( end_time -. start_time ) /. (float_of_int ntest) *. 1000000.0 in
      Printf.printf "Mean processing time : %f microseconds\n" time;
      

[-- Attachment #4: measure_pure_cps.ml --]
[-- Type: application/octet-stream, Size: 2651 bytes --]

type ('a,'b) arrow = Arrow of ( 'a -> 'b * ('a,'b) arrow )

let rec arr f = Arrow ( fun x -> f x , arr f );;

let rec (>>>) (Arrow f) (Arrow g) =
  Arrow (
    fun x ->
      let rf,nf = f x in 
      let rg,ng = g rf in
	rg , nf >>> ng 
  )
;;

let loop init f  =
  let rec loop_aux c (Arrow f) =
    Arrow (
      fun x->
	let ((c', r), n) = f (c,x) in
	  r , loop_aux c' n
    )
  in
    loop_aux init f
;;

let rec run (Arrow f) x ?(i=0) max_inc = 
  if i = max_inc then
    x
  else
    let _,n = f x in
      run n x ~i:(i+1) max_inc


let pair_to_simple (x,y) = x
let arr_pair_to_simple () = arr pair_to_simple

let simple_to_pair x = (x,x)
let arr_simple_to_pair () = arr simple_to_pair


let arr_incr = arr ( fun ( c , x ) -> c + 1 , c + x )

let arr_counter1 = loop 1 arr_incr
let arr_incr1 = (arr_pair_to_simple ()) >>> arr_counter1 >>> (arr_simple_to_pair ())

let arr_counter2 = loop 2 arr_incr1
let arr_incr2 = (arr_pair_to_simple ()) >>> arr_counter2 >>> (arr_simple_to_pair ())

let arr_counter3 = loop 3 arr_incr2
let arr_incr3 = (arr_pair_to_simple ()) >>> arr_counter3 >>> (arr_simple_to_pair ())

let arr_counter4 = loop 4 arr_incr3
let arr_incr4 = (arr_pair_to_simple ()) >>> arr_counter4 >>> (arr_simple_to_pair ())

let arr_counter5 = loop 5 arr_incr4
let arr_incr5 = (arr_pair_to_simple ()) >>> arr_counter5 >>> (arr_simple_to_pair ())

let arr_counter6 = loop 6 arr_incr5
let arr_incr6 = (arr_pair_to_simple ()) >>> arr_counter6 >>> (arr_simple_to_pair ())

let arr_counter7 = loop 7 arr_incr6
let arr_incr7 = (arr_pair_to_simple ()) >>> arr_counter7 >>> (arr_simple_to_pair ())

let arr_counter8 = loop 8 arr_incr7
let arr_incr8 = (arr_pair_to_simple ()) >>> arr_counter8 >>> (arr_simple_to_pair ())

let arr_counter9 = loop 9 arr_incr8
let arr_incr9 = (arr_pair_to_simple ()) >>> arr_counter9 >>> (arr_simple_to_pair ())

let arr_counter10 = loop 10 arr_incr9
let arr_incr10 = (arr_pair_to_simple ()) >>> arr_counter10 >>> (arr_simple_to_pair ())

let arr_counter11 = loop 11 arr_incr10
let arr_incr11 = (arr_pair_to_simple ()) >>> arr_counter11 >>> (arr_simple_to_pair ())

let arr_counter12 = loop 12 arr_incr11
let arr_incr12 = (arr_pair_to_simple ()) >>> arr_counter12 >>> (arr_simple_to_pair ())

let arr_my_arrow () = ( arr_simple_to_pair () ) >>> arr_incr12;;


let _ =
  let ntest = 100000 in
  let arr_my_arrow = arr_my_arrow () in
  let start_time = Unix.gettimeofday () in
  let _ = run arr_my_arrow 2 ntest in
    ();
    let end_time = Unix.gettimeofday () in
    let time = ( end_time -. start_time ) /. (float_of_int ntest) *. 1000000.0 in
      Printf.printf "Mean processing time : %f microseconds\n" time;

Re: "Ref" and copy of functions

[Zheng Li]

Hi,

"Pierre-Evariste Dagand" <pedagand@gmail.com> writes:
> Yes, that's a CPS-way of doing things. I am aware of it and my first
> implementation was in this style.
>
> The reasons why I decided to switch to Ref were that :
>   1/ The implementation is much more "intuitive" (I don't have a CPS
> pre-processor in my brain)
>   2/ I thought I could get rid of my hack (Marshal/UnMarshal) easily
>   3/ I used to think that I will be faster
>
> Point 1 is not a problem, Santa Claus might bring me this CPS
> pre-processor in a few days.
>
> Point 2 seems to be wrong : being fast is nice but if it's for hitting
> the wall, well... one should slow down. And for the moment, I haven't
> found a clean solution and I'm not sure whether my hack is safe or
> not.

I guess you won't be able to find such a solution. In the Ref-based
implementation, the result arrow type is stateful. You won't be able to
_implicitly_ copy a state _inside_ the language, otherwise first-class
continuation would already appear. 

A related issue appears on the "arr" function, if the argument "f" is
itself stateful, even with a functional encoding like CPS won't help to
copy the state inside. You can only solve this with a out-of-language
solution such as Marshal or independent process evaluation . However,
they also charge you cost. AFAIR, marshal (native code) has some
cross-module safety problem.

> So, remains point 3. That's why I have carried out an experience on my
> initial Ref implementation, your Rectypes implementation and a CPS
> implementation without rectypes (because rectypes frighten me).

Since the corresponding mechanics in Ref and CPS are mutation and
closure (de)construction, no wonder the former is faster. One ad-hoc
solution, if you only have to provide high-level functional API to
outside, is to make states explicit, like

type ('a,'b) arrow = {mutable state: 'c; eval: 'c -> 'a -> 'b}

This is not valid OCaml, since the 'c type is out of scope. You can
either encode it with existential type (which also involve closure
(de)construction, but I'm not sure about the cost). Or simply using
Obj.t instead of 'c as far as you won't expose it, at least it won't be
unsafer than Marshal and faster.

-- 
Zheng Li
http://www.pps.jussieu.fr/~li

Re: [Caml-list] Re: "Ref" and copy of functions

[Pierre-Evariste Dagand]

> I guess you won't be able to find such a solution. In the Ref-based
> implementation, the result arrow type is stateful. You won't be able to
> _implicitly_ copy a state _inside_ the language, otherwise first-class
> continuation would already appear.

That's why I asked this to the Caml-list : to find a black magic recipe :-)

> Since the corresponding mechanics in Ref and CPS are mutation and
> closure (de)construction, no wonder the former is faster. One ad-hoc
> solution, if you only have to provide high-level functional API to
> outside, is to make states explicit, like
>
> type ('a,'b) arrow = {mutable state: 'c; eval: 'c -> 'a -> 'b}
>
> This is not valid OCaml, since the 'c type is out of scope. You can
> either encode it with existential type (which also involve closure
> (de)construction, but I'm not sure about the cost). Or simply using
> Obj.t instead of 'c as far as you won't expose it, at least it won't be
> unsafer than Marshal and faster.

This solution looks promising, I will look at it and see if it suits my needs.

Thanks,

-- 
Pierre-Evariste DAGAND

Re: [Caml-list] Re: "Ref" and copy of functions

[Loup Vaillant]

2007/12/14, Pierre-Evariste Dagand <pedagand@gmail.com>:
> And the results are ...
>   1/ Ref : 0.75 microseconds
>   2/ Variant CPS : 2.69 microseconds
>   3/ Rectypes : 2.80 microseconds
> [ compiled with ocamlopt.opt, with -rectypes for 3/ ]
>
> It's about 4 times longer and, against a C++ code, I fear that I can't
> afford it.

Err, Is this likely to be a bottoleneck? Or do you want it to be a
library, so it has to be fast anyway?

Loup

[Caml-list] Re: "Ref" and copy of functions

[Pierre-Evariste Dagand]

[I forgot to cc the list, sorry]

> Err, Is this likely to be a bottoleneck? Or do you want it to be a
> library, so it has to be fast anyway?

Indeed, it will be a library and I would like to get it the faster I can.

These arrows can be connected to :
  1/ A simulator that simulates a whole network (target size : 10.000 nodes)
  2/ A network interface that connects the arrow with the World
  3/ If I have enough time, a debugger and a model checker

In the 2/ case, I'm looking for documentation about the granularity of
the Unix/Windows threads switching (as I rely on threads to interact
with the world).

For the other cases, the faster, the better.

--
Pierre-Evariste DAGAND

Re: [Caml-list] "Ref" and copy of functions

[Jacques Garrigue]

From: "Pierre-Evariste Dagand" <pedagand@gmail.com>

> I'm looking for advices about a "clean way" of doing something which,
> by design, isn't. So, let states the problem.
> 
> I'm doing a combinator library based on Arrows for a Yampa-like system :
> 
> type ('a,'b) arrow = Arrow of ( 'a -> 'b )

[...]

> But now, I would like to be able to "copy" a built arrow and to be
> able to execute the copy without side-effecting on the first one.
> Obviously, I cannot do that in this implementation.

Here is yet another solution, using objects, which actually combines
Zheng's and Oleg's ideas. That is, it separates state and function,
but provides only access to state through a cloning method, so that it
is completely type safe. This is just what objects are good at!

class ['a,'b] arrow (f : 'a -> 'b) =
  object (self) method call = f method copy = self end

let (>>>) rf rg : ('a,'b) arrow =
  object
    val rf : ('a,'c) arrow = rf
    val rg : ('c,'b) arrow = rg
    method call x = rg#call (rf#call x)
    method copy = {< rf = rf#copy; rg = rg#copy >}
  end

let loop init rf : ('b,'c) arrow =
  object
    val mutable state = init
    val rf : ('a*'b,'a*'c) arrow = rf
    method call x =
      let state', y = rf#call (state, x) in
      state <- state'; y
    method copy = {< rf = rf#copy >}
  end

let arr = new arrow
let arr_counter = loop 0 (arr (fun (counter,x) -> counter+1, counter+x))
let arr_double = arr (fun x -> 2*x)
let arr_my_small_arrow = arr_counter >>> arr_double

The key here is the {< ... >} construct, which creates a shallow copy
of an object, eventually with some fields changed. As a result, in
loop there is no need to handle the state explicitly: the state field
in the copied object will be distinct from the state field in the
original object. On the other hand, you must explicitly update fields
holding arrows, since the copy is shallow. Note that the explicit
"val" fields are needed to allow updating their contents when copying.

One difference with Oleg's approach is that we take a copy of the
original object, rather than creating a completely new record. In this
case, this doesn't mean much, since there is no extra computation
involved. Still, the state after copying is not the original but the
current one. And this may matter more if the construction is more
complicated.

Jacques Garrigue

Re: [Caml-list] "Ref" and copy of functions

[Pierre-Evariste Dagand]

> Here is yet another solution, using objects, which actually combines
> Zheng's and Oleg's ideas. That is, it separates state and function,
> but provides only access to state through a cloning method, so that it
> is completely type safe. This is just what objects are good at!
>
> class ['a,'b] arrow (f : 'a -> 'b) =
>   object (self) method call = f method copy = self end

Yet another nice solution I would never have imagined :-)

And the performance is quite good :

1.428032 microseconds on my small benchmark

(the unsafe Ref implantation takes 0.75 microseconds while the CPS
implantation takes 2.7 microseconds).

Nevertheless, I have carried out my benchmark on Oleg's implementation
and find an impressive performance :

0.74 microseconds !

Now, I will re-write my combinators and see which style better suits my needs.

Thanks,

-- 
Pierre-Evariste DAGAND
http://perso.eleves.bretagne.ens-cachan.fr/~dagand/

Re: [Caml-list] "Ref" and copy of functions

[Pierre-Evariste Dagand]

> Now, I will re-write my combinators and see which style better suits my needs.

Finally, impressed by the speed of the record solution, I have
re-written the whole library with records.

I have measured the performance of this implementation against the
Ref-based one on "real" code. Thus, I have simulated my Chord [1]
implementation with a simulator instrumented such that it drops the
processing time for each arrow processing.

The results can be found at [2].

In a nutshell : the record solution has a negligible overhead compared
to the Ref solution.

Thanks all,

[1]: http://pdos.csail.mit.edu/chord/
[2]: http://perso.eleves.bretagne.ens-cachan.fr/~dagand/projets/opis/processing_speed_records.pdf

-- 
Pierre-Evariste DAGAND

Re: "Ref" and copy of functions

[oleg]

If you like using the mutable state, perhaps you might find the
following code helpful. The key idea is packaging the clone function
along with the arrow. There is no longer any need in any unsafe
features. The lesson from our tagless final APLAS paper is that many
things are significantly easier if we do the work at the production
site rather than at the consumption site.

(* The first component is the arrow itself, the second one is the clone
   function*)
type ('a,'b) arrow = {arrow: 'a -> 'b; clone: unit -> ('a,'b) arrow};;

let rec arr f = {arrow = f; clone = fun () -> arr f};;

let rec (>>>) f g = {arrow = (fun c -> g.arrow (f.arrow c)); 
		     clone = (fun () -> f.clone () >>> g.clone ())};;

(* Here, our clone function uses the initial state rather than the
current state. It is trivial to clone from the current state, if
desired.*)

let rec loop init f =
  let state = ref init in
  {arrow =
      (fun c ->
        let new_state , output = f.arrow ( !state , c ) in
          state := new_state;
          output);
   clone = (fun () -> loop init (f.clone ()))};;

let arr_counter = loop 0 (arr (fun (counter, x) -> counter+1 ,counter+x));;
let arr_double = arr (fun x -> 2*x);;
let arr_my_small_arrow = arr_counter >>> arr_double;;

let run f input = let v1 = f.arrow input in
                  let v2 = f.arrow input in
		  (v1,v2);;


let test1 = run arr_my_small_arrow 10;;
  val test1 : int * int = (20, 22)

let test2 = run arr_my_small_arrow 10;;
  val test2 : int * int = (24, 26)  (*obviously, counter keeps
  counting *)

let test3 = run (arr_my_small_arrow.clone ()) 10;;
val test3 : int * int = (20, 22)  (* cloning `resets' the counter *)

Re: "Ref" and copy of functions

[Pierre-Evariste Dagand]

> If you like using the mutable state, (...)

Now, I feel guilty to have used a Ref :-)

One Ref for ~5000 lines of code, it's not so bad to me :-)

(To be honnest, there are 8 Refs but 7 are used in order to emulate
the Thread.kill function)

> perhaps you might find the
> following code helpful. The key idea is packaging the clone function
> along with the arrow. There is no longer any need in any unsafe
> features. The lesson from our tagless final APLAS paper is that many
> things are significantly easier if we do the work at the production
> site rather than at the consumption site.
>
> (* The first component is the arrow itself, the second one is the clone
>    function*)
> type ('a,'b) arrow = {arrow: 'a -> 'b; clone: unit -> ('a,'b) arrow};;

I see... It's disappointing of simplicity...

Thanks !

-- 
Pierre-Evariste DAGAND