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

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: "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: "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

"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/