Ant: Re: [Caml-list] Avoiding shared data

Ant: Re: [Caml-list] Avoiding shared data

[Martin Chabr]

Hello Brian,

thank you for the whole lot of useful tips and nice
explanations. It is immediately clear to me how to
copy a record and a tuple, but I will need some time
to think about your suggestions using a map.

Intuitively I feel that it needs a method to create
non-shared data structures in the first place, so that
no copying whatsoever is needed.

Regards,

Martin


--- Brian Hurt <bhurt@spnz.org> schrieb:

> 
> 
> On Sun, 25 Sep 2005, Martin Chabr wrote:
> 
> > Working with non-shared data structures in OCaml
> > Deep copy of OCaml structures, marshaling
> > ================================================
> >
> > Dear group members,
> >
> > I need to process arrays of pairs of integers and
> > records ((int * record) array) in which all
> elements
> > must be updated individually, which means that
> > unshared data structures must be used. For arrays
> of
> > arrays I can produce unshared data by using the
> > library functions Array.copy and Array.append to
> > append the individual arrays into the embedding
> array.
> > It works, the low level arrays can be updated
> > individually. But I cannot use the same scheme to
> the
> > array of the (int * record) structures, because I
> do
> > not know how to copy these structures to dissolve
> the
> > sharing. I do not even know how to copy records.
> It
> > seems to me that this problem occurs always when I
> > want to produce an array of data with a fixed
> > structure automatically (rather than entering the
> > array [| ... |] by hand at the top level
> interpreter
> > using constants only). How can I produce
> completely
> > unshared structures?
> 
> First of all, you can copy a structure easily enough
> using the with key 
> word.  Say you have:
> 
> type my_struct = {
>      foo: int;
>      bar: float;
>      baz: string;
> }
> 
> You can write a copy function just like:
> 
> let copy_my_struct x = { x with foo = x.foo };;
> 
> In this case, the "with" construct says "create a
> new structure with the 
> same elements as the old structure, except give the
> foo member this new 
> value (which in this case just happens to be the
> same value as the old 
> value)".  Unfortunately you have to specify at least
> one new value to use 
> the with construct, even if it doesn't get a new
> value.  This is 
> especially usefull if there are other value you want
> to copy, for example, 
> you probably want to write:
> 
> let copy_my_struct x = { x with baz = String.copy
> x.baz }
> 
> As this doesn't just create a new copy of the
> structure, it also creates a 
> new copy of the string as well (foo and bar get
> whatever values the 
> original structure had).
> 
> I can create a new tuple just by breaking the old
> tuple apart and putting 
> it back together again.  For all two element tuples,
> I can create a new 
> copy of them just by going:
> 
> let copy_tuple (a,b) = a,b
> 
> This function, given a tuple of two elements,
> creates a new tuple with the 
> same two elements.
> 
> The easiest way to create a new list from old values
> is to just use the 
> map function.  The output list type of List.map can
> be the same type as 
> the input list.  This is really usefull- imagine
> that I want to add 1 each 
> to a list of floats, I can just write:
> 
> List.map (fun i -> i + 1) lst
> 
> So, to answer you specific question, say I have an
> (int * my_struct) list 
> (where t is the structure I defined above).  The
> function to create a 
> whole new copy of this list (assuming I've written
> copy_t like I did 
> above) is just:
> 
> let copy_list lst = List.map (fun (i,s) -> i,
> (copy_my_struct s)) lst
> 
> Notice that I made copy_tuple an anonymous (unnamed)
> function there.  With 
> a couple of more tricks I can fit the whole thing on
> one line:
> 
> let cplst = List.map (fun (i,s) -> i, {s with baz =
> String.copy s.baz})
> 
> Which is nice for bragging rights, but I kind of
> like the more unpacked 
> version.
> 
> Now, I'm going to jump from the question you asked
> to the question you 
> didn't ask, and make a big assumption along the way.
>  I'd bet dollars to 
> donuts that you really don't want to be using either
> lists or array- you 
> really want to be using a map.  Let me guess: you've
> written a function 
> like:
> 
> let rec find i lst = (* find element i in list lst)
>      match lst with
>          | (j, s) :: t ->
>              if i == j then
>                  s
>              else
>                  find i t
>          | [] -> raise Not_found
> 
> and are calling it a lot (or rewritting it a lot). 
> If this is the case, 
> then what you really want to be using is a map, not
> a list or an array. 
> You can do this with the following code:
> 
> module Int = struct
>      type t = int
>      let compare (x: int) y =
>          if x < y then
>             -1
>          else if x > y then
>              1
>          else
>              0
> end;;
> 
> module IntMap = Map.Make(Int);;
> 
> Now you can just keep your structures in a my_struct
> IntMap.t.  The find 
> function is now:
> let find i lst = (* lst is a IntMap, not a list *)
>      IntMap.find i lst
> ;;
> 
> The big difference here is that IntMap.find is O(log
> N) cost, while the 
> list-based find I wrote above is O(N) cost.  What
> this means is that if 
> the list is 1000 elements long, the list-based find
> will have to do (on 
> aveage) about 500 steps of processing to find the
> answer- it has to walk 
> halfway down the list.  The IntMap.find function,
> however, only has to do 
> about 10 steps on average to find the answer- it's
> literally 50 times 
> faster to do the IntMap.find in this case than the
> list-based find.  If 
> we're dealing with a million elements, the
> list-based find will take 
> 500,000 steps to find the answer on average, the
> IntMap.find only 20, for 
> an incredible speed up of 25,000 times.
> 
> Note that IntMap has a map function as well- so I
> can steal the exact same 
> trick to copy it (but note that I don't have to
> allocate the new tuples):
> 
> let copy_list lst = (* list is an IntMap, not a list
> *)
>      IntMap.map copy_my_struct lst
> ;;
> 
> If you actually want the associated integers as
> well, use mapi instead of 
> map.
> 
> Note that O(log N) vr.s O(N) thing applies to
> updates as well.  Let's say 
> 
=== message truncated ===



		
___________________________________________________________ 
Was denken Sie über E-Mail? Wir hören auf Ihre Meinung: http://surveylink.yahoo.com/wix/p0379378.aspx

Re: [Caml-list] Avoiding shared data

[William Lovas]

Hi Martin,

On Sun, Sep 25, 2005 at 11:32:02PM +0200, Martin Chabr wrote:
> [...]  But I cannot use the same scheme to the
> array of the (int * record) structures, because I do
> not know how to copy these structures to dissolve the
> sharing. I do not even know how to copy records.
> [...] How can I produce completely
> unshared structures?

Maybe i'm missing something, but if these are unmutable records, then why
do you need to concern yourself with any potential sharing?  As long as the
array cells are not "shared" -- which they can't be, as far as i know --
you can update each one individually no matter what the sharing status of
their contents is.

If the records *are* mutable, then the suggestion to use Array.init should
be sufficient.

Hoping i might save you some work :)

William

Ant: Re: [Caml-list] Avoiding shared data

[Martin Chabr]

Hello William,

I am using a mutable record. I am programming this 90%
in the imperative (non-functional) style, so that I
can rewrite critical parts into Fortran easily.
Another reason is, I am an intermediate user and
finding out whether the recursion is a tail-one or not
is difficult for me. This is a kind of number
crunching problem and the data structures will be
huge.

Blessed are the creators of OCaml for the inclusion of
all imperative constructs.

Martin

--- William Lovas <wlovas@stwing.upenn.edu> schrieb:

> Hi Martin,
> 
> On Sun, Sep 25, 2005 at 11:32:02PM +0200, Martin
> Chabr wrote:
> > [...]  But I cannot use the same scheme to the
> > array of the (int * record) structures, because I
> do
> > not know how to copy these structures to dissolve
> the
> > sharing. I do not even know how to copy records.
> > [...] How can I produce completely
> > unshared structures?
> 
> Maybe i'm missing something, but if these are
> unmutable records, then why
> do you need to concern yourself with any potential
> sharing?  As long as the
> array cells are not "shared" -- which they can't be,
> as far as i know --
> you can update each one individually no matter what
> the sharing status of
> their contents is.
> 
> If the records *are* mutable, then the suggestion to
> use Array.init should
> be sufficient.
> 
> Hoping i might save you some work :)
> 
> William
> 


Martin Chabr
Hochstrasse 28
8044 Zürich
Schweiz / Switzerland
Tel.P.: 01-261 17 24


	
		
___________________________________________________________ 
Gesendet von Yahoo! Mail - Jetzt mit 1GB Speicher kostenlos - Hier anmelden: http://mail.yahoo.de

Re: Ant: Re: [Caml-list] Avoiding shared data

[Jon Harrop]

On Monday 26 September 2005 22:07, Martin Chabr wrote:
> I am using a mutable record. I am programming this 90%
> in the imperative (non-functional) style, so that I
> can rewrite critical parts into Fortran easily.

In case you haven't already - I'd advise you to write a simple working version 
first.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: Ant: Re: [Caml-list] Avoiding shared data

[Oliver Bandel]

On Mon, Sep 26, 2005 at 11:07:30PM +0200, Martin Chabr wrote:
> Hello William,
> 
> I am using a mutable record. I am programming this 90%
> in the imperative (non-functional) style, so that I
> can rewrite critical parts into Fortran easily.
> Another reason is, I am an intermediate user and
> finding out whether the recursion is a tail-one or not
> is difficult for me.

When you 90% of your code are writing in imperative style
and do not go deeper into the functional/recursive
world, you will never be able to distinguish between
tail-rec and non-tail-rec style.

But: It is not really hard to find the distinction betwen
 the two styles, but often the explanations are not made
 well.
 Sometimes it's only one or two words in an explanation about
 tail-rec/non-tail-rec that must be substituted by other words,
 and the distinction can be made visible very easy.

On the other hand: writing mor funtional/recursive code will
make you more used to to this...

Ciao,
   Oliver

Re: Ant: Re: [Caml-list] Avoiding shared data

[Pal-Kristian Engstad]

On Friday 30 September 2005 03:57 pm, Oliver Bandel wrote:
> On the other hand: writing mor funtional/recursive code will
> make you more used to to this...

I've always thought that this was a really bad argument from the ML camp. The 
logic of complicated control-paths is very easily made a zillion times worse 
by writing in a tail-recursive style. It is *not* a good programming practice 
to make hard-to-read code!

I encourage people to read the paper by Olin Shivers: "The Anatomy of a Loop - 
A story of scope and control", which was presented at ICFP 2005, and can be 
found at http://www.cc.gatech.edu/~shivers/papers/loop.pdf.

The author argues that "Writing loops with tail-recursive function calls is 
the equivalent of writing them with goto’s." and gives an example that I've 
rewritten from Scheme-ish into OCaml-ish:

let myfunc l =
  let rec loop rest result =
    match rest with 
      | [] -> List.rev result
      | x::xs -> 
	  if xpred x then
	    let y = verbose_code_using_x x in
	      if ypred y then 
		let z = verbose_code_using_y y in
		  loop xs (z_expression :: result)
	      else
		loop xs result
	  else
	    loop xs result
  in
    loop l [] 
;;

Obviously, one would like to refactor this into HOF, but in this situation it 
is hard to see how one should do it. The author instead proposes to use loops 
in a monadic style, which I've again rewritten:

let myfunc l =
   loop [ for x in l
	; when xpred x 
	;   let y = verbose_code_using_x x
	;   when ypred y
	;     let z = verbose_code_using_y y
	;     save z
	]

The point being (syntax aside) that this code is much more readible, easier to 
change and easier to verify than the code given above. [Of course, Haskell 
has the really cool list-comprehension syntax that alleviates some of ML's 
problems, but still.]

Thanks,

PKE.
-- 
  _       
  \`.       Pål-Kristian Engstad, Lead Programmer,
   \ `|     Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
  __\ |`.   Santa Monica, CA 90404, USA. (310) 633-9112. 
    /  /o   mailto:engstad@naughtydog.com http://www.naughtydog.com
   /  '~    mailto:mrengstad@yahoo.com    http://www.engstad.com
  / ,'      Hang-gliding Rulez!
  ~'

Re: Ant: Re: [Caml-list] Avoiding shared data

[Bill Wood]

   . . .
> I've always thought that this was a really bad argument from the ML camp. The 
> logic of complicated control-paths is very easily made a zillion times worse 
> by writing in a tail-recursive style. It is *not* a good programming practice 
> to make hard-to-read code!
> 
> I encourage people to read the paper by Olin Shivers: "The Anatomy of a Loop - 
> A story of scope and control", which was presented at ICFP 2005, and can be 
> found at http://www.cc.gatech.edu/~shivers/papers/loop.pdf.
> 
> The author argues that "Writing loops with tail-recursive function calls is 
> the equivalent of writing them with goto’s." and gives an example that I've 
> rewritten from Scheme-ish into OCaml-ish:
> 
> let myfunc l =
>   let rec loop rest result =
>     match rest with 
>       | [] -> List.rev result
>       | x::xs -> 
> 	  if xpred x then
> 	    let y = verbose_code_using_x x in
> 	      if ypred y then 
> 		let z = verbose_code_using_y y in
> 		  loop xs (z_expression :: result)
> 	      else
> 		loop xs result
> 	  else
> 	    loop xs result
>   in
>     loop l [] 
> ;;
> 
> Obviously, one would like to refactor this into HOF, but in this situation it 
> is hard to see how one should do it. The author instead proposes to use loops 
> in a monadic style, which I've again rewritten:
> 
> let myfunc l =
>    loop [ for x in l
> 	; when xpred x 
> 	;   let y = verbose_code_using_x x
> 	;   when ypred y
> 	;     let z = verbose_code_using_y y
> 	;     save z
> 	]
> 
> The point being (syntax aside) that this code is much more readible, easier to 
> change and easier to verify than the code given above. [Of course, Haskell 
> has the really cool list-comprehension syntax that alleviates some of ML's 
> problems, but still.]

I about half agree with Mr. Engstad's observation.  I have often used
the fact that the accumulator passed around in tail-recursive functions
acts like a state (some people call these *state threads*), and I've
used techniques like pushing Dijkstra's weakest-precondition predicate
transformers over accumulators to reason about tail-recursive functional
code almost as if it were imperative (the only difference with Mr.
Shivers is that my programming is goto-less :-).

However, the example is a little unfortunate in that transforming it to
an arguably cleaner HOF form is fairly easy.  If we first define
function composition as an operator (shouldn't this be an OCaml
Pervasive?), say

  let ($@) fyz fxy x = fyz (fxy x);;

then the tail-recursive version of myfunc transforms into my_hof_func:

   let my_hof_func l =
     let fumble =
       let save = rev $@ (fold_left (fun la i -> i :: la) []) in
         save $@
	   (map verbose_code_using_y) $@
	     (filter ypred) $@
	       (map verbose_code_using_x) $@
	         (filter xpred)
   in fumble l;;

where packaging and return of the result has been encapsulated in the
local function 'save' (I'm also assuming z_expression was supposed to be
z).

A minor problem is that the textual order of the predicates and
functions is reversed.  Even this can be handled by a sleazy trick --
reverse the order of the operands to the compose operator like so:

   let ($@) fxy fyz x = fyz (fxy x);;

We can then rewrite my_hof_func as

   let my_hof_func l =
     let fumble =
       let save = (fold_left (fun la i -> i :: la) []) $@ rev in
         (filter xpred)             $@
         (map verbose_code_using_x) $@
         (filter ypred)             $@
         (map verbose_code_using_y) $@
         save
   in fumble l;;

The actions/functions are read in the order they are performed/applied,
and trivial reformatting even makes it look sorta like imperative code.

A very similar transformation could be done on the "Scheme-ish"
original, where a variable-arity form (compose f1 ... fn) is used to
equally good effect.

I think the ease-of-reading issue can now be revisited on a slightly
more even playing field.  The transformed, HOF, code is a couple of
lines longer, but the meaning is fairly transparent because native OCaml
facilities are used throughout.  The monadic form above is a trifle
shorter, but has the liability that the new syntax has complex semantics
-- what *exactly* is going on with "when" and "save"?.  I note also that
the monadic form looks very similar to the infamous Common Lisp "loop"
facility (the one towards the back of The Book, with all the keywords).
Many lispers love it, and many loathe it.

Does anybody know if MLers have looked at either the Series or the
Generators-and-Gatherers described in Appendices A and B of Common Lisp
the Language, 2nd ed.?  Some of the ideas there look interesting.

Interesting topic,

 -- Bill Wood
    bill.wood@acm.org

Re: Ant: Re: [Caml-list] Avoiding shared data

[Wolfgang Lux]

Pal-Kristian Engstad wrote:

> The author argues that "Writing loops with tail-recursive function 
> calls is
> the equivalent of writing them with goto’s." and gives an example that 
> I've
> rewritten from Scheme-ish into OCaml-ish:
>
> let myfunc l =
>   let rec loop rest result =
>     match rest with
>       | [] -> List.rev result
>       | x::xs ->
> 	  if xpred x then
> 	    let y = verbose_code_using_x x in
> 	      if ypred y then
> 		let z = verbose_code_using_y y in
> 		  loop xs (z_expression :: result)
> 	      else
> 		loop xs result
> 	  else
> 	    loop xs result
>   in
>     loop l []
> ;;
>
> Obviously, one would like to refactor this into HOF, but in this 
> situation it
> is hard to see how one should do it.

Oh come on! IMHO, most loops can easily be transformed by using map, 
filter,
fold_left, and fold_right. The example given is no exception. The loop
essentially applies some complex code to every element of the list and
includes the result in the output list only if a condition is satisfied
that is computed along with result. This is always the structure of a 
fold.
(If the condition were independent from the result one could combine a 
filter
and a map.) Thus, a straight forward rewrite of the loop is:

   let myfunc l =
     let f x result =
           if xpred then
             let y = verbose_code_using_x x in
               if ypred y then
                 let z = verbose_code_using_y y in
                   z_expression :: result
               else
                 result
           else
             result
     in
       fold_right f l []

Furthermore, I would turn the two if expressions into local functions

   let myfunc l =
     let g y result =
           if ypred y then
             let z = verbose_code_using_y y in z_expression :: result
           else
             result
     in let f x result =
          if xpred x then
            let y = verbose_code_using_x x in g y result
          else
            result
     in fold_right f l []

Regards
Wolfgang

Re: Ant: Re: [Caml-list] Avoiding shared data

[Wolfgang Lux]

Wolfgang Lux wrote:

>   let myfunc l =
>     let g y result =
>           if ypred y then
>             let z = verbose_code_using_y y in z_expression :: result
>           else
>             result
>     in let f x result =
>          if xpred x then
>            let y = verbose_code_using_x x in g y result
>          else
>            result
>     in fold_right f l []

Just correcting myself. The code should use fold_left rather than 
fold_right
(and thus switch the parameters in the call as well as that of the local
functions f and g) because the former is tail recursive and therefore 
should
be preferred in a strict language (have been programming too much 
Haskell
lately where a right fold is better).

Wolfghang

Re: Ant: Re: [Caml-list] Avoiding shared data

[Oliver Bandel]

On Fri, Sep 30, 2005 at 05:07:00PM -0700, Pal-Kristian Engstad wrote:
> On Friday 30 September 2005 03:57 pm, Oliver Bandel wrote:
> > On the other hand: writing mor funtional/recursive code will
> > make you more used to to this...
> 
> I've always thought that this was a really bad argument from the ML camp.


It is not a bad argument from the ML camp.

It's always so, that if you have more practice you will be
more used to something and you learn it better.
If you don't practise, learning is abandoned.

This has nothing to do with programming languages.


[...]
> The 
> logic of complicated control-paths is very easily made a zillion times worse 
> by writing in a tail-recursive style. It is *not* a good programming practice 
> to make hard-to-read code!

Some things are better wriiten down functionally, others are better
suited for using impoerative code.

Since I get more and more used to using functional and recursive
code writing, I can better decide, which way is better.
And more and more often I decide to use the recursive style.

In OCaml you are not restricted to it, but if you only use one
style of programming, and never practise the other programming styles,
you can't see, when which programming style/paradigm is better,
and the original poster said something about the distinction
of tail-rec vs. non tail-rec. (It was not about if that style makes sense or not.)
If you practise more of that stuff, and reading some good explanations,
then it's obvious, which solution is tail-rec and which is not.


> 
> I encourage people to read the paper by Olin Shivers: "The Anatomy of a Loop - 
> A story of scope and control", which was presented at ICFP 2005, and can be 
> found at http://www.cc.gatech.edu/~shivers/papers/loop.pdf.

Thanks for the link.


> 
> The author argues that "Writing loops with tail-recursive function calls is 
> the equivalent of writing them with goto???s."

I doubt that the author writes that.
You mean for/while instead of goto's as a substitute for
recursive functions...?!



Ciao,
    Oliver

Re: Ant: Re: [Caml-list] Avoiding shared data

[Bill Wood]

   . . .
> > The author argues that "Writing loops with tail-recursive function calls is 
> > the equivalent of writing them with goto???s."
> 
> I doubt that the author writes that.
> You mean for/while instead of goto's as a substitute for
> recursive functions...?!

Actually, the author does say that.  More precisely, Shivers refers to
Steele's characterization of lambda as "gotos with arguments"; I think
the source is the paper "Lambda: the Ultimate GOTO".

 -- Bill Wood
    bill.wood@acm.org