Re: "Ref" and copy of functions

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

"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