Avoiding shared data

Avoiding shared data

[Martin Chabr]

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?

What about marshaling and unmarshaling the data? This
should produce a deep copy of data objects. I have
tried it, it works, but it seems to me wasteful to
copy all the data twice only to get rid of the
sharing.

It would be great to know of a completely general (any
nested structures) and fast solution (without copying)
how to produce unshared data structures.

My environment is OCaml 3.08.02 for Windows on Win
2000, New Windows Interface v1.9RC4.

I am looking forward to you reply.

Regards,

Martin

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


		
___________________________________________________________ 
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

[Bill Wood]

   . . .
> 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?

Funny you should mention it, I wrestled with this just this week.  I'm
building a square, i.e. array of N elements, each of which is itself an
array of N cells, where a cell is a record with several fields.  Here's
the way I did it:

1) I defined a function initial_cell : unit -> cell as

   let initial_cell () =
     let c = {field1 = val1; ...; fieldN = valN} in
       c;;

2) I defined a function initial_row : int -> cell array as:

   let initial_row n = Array.init n (fun i -> initial_cell ());;

3) I defined a function initial_square : int -> cell array array by:

   let initial_square n = Array.init n (fun i -> initial_row ());;

I think the essential point is the Array.init function; since it expects
to set the i-th element of the new array to (f i) for unknown f, it
can't make an array that shares.

I hope this is of some help,

 -- Bill Wood
    bill.wood@acm.org

Re: [Caml-list] Avoiding shared data

[Claudio Sacerdoti Coen]

> It would be great to know of a completely general (any
> nested structures) and fast solution (without copying)
> how to produce unshared data structures.

 If you like to play with fire you can use this unsharing function
 (that is not complete with respect to any data type, but it is sufficient
 for my needs). Since it works on the run-time representation of data,
 it can even unshare abstract data types.

exception CanNotUnshare;;

(* [unshare t] gives back a copy of t where all sharing has been removed   *)
(* Physical equality becomes meaningful on unshared terms. Hashtables that *)
(* use physical equality can now be used to associate information to evey  *)
(* node of the term.                                                       *)
val unshare: ?already_unshared:('a -> bool) -> 'a -> 'a

let unshare ?(already_unshared = function _ -> false) t =
 let obj = Obj.repr t in
  let rec aux obj =
   if already_unshared (Obj.obj obj) then
    obj
   else
    (if Obj.is_int obj then
      obj
     else if Obj.is_block obj then
      begin
       let tag = Obj.tag obj in
        if tag < Obj.no_scan_tag then
         begin
          let size = Obj.size obj in
           let new_obj = Obj.new_block 0 size in
            Obj.set_tag new_obj tag ;
            for i = 0 to size - 1 do
             Obj.set_field new_obj i (aux (Obj.field obj i))
            done ;
            new_obj
         end
        else if tag = Obj.string_tag then
         obj
        else
         raise CanNotUnshare
      end
     else
      raise CanNotUnshare
    )
  in
   Obj.obj (aux obj)
;;

-- 
----------------------------------------------------------------
Real name: Claudio Sacerdoti Coen
Doctor in Computer Science, University of Bologna
E-mail: sacerdot@cs.unibo.it
http://www.cs.unibo.it/~sacerdot
----------------------------------------------------------------

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

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

[Martin Chabr]

Hello Wolfgang,

you are quite right, most loops can easily be
transformed by using map, filter, fold_left or
fold_right. I just tend to forget about it or find it
uneasy if the problem is more complex. It may be just
a matter of habit.

Regards,

Martin

--- Wolfgang Lux <wlux@uni-muenster.de> schrieb:

> 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
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 



	

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

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

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

[Martin Chabr]

Hello Pal-Kristian,

I agree with you that functional code written in a
tail recursive style is hard to read. Sometimes you
have to do it that way if you want to avoid a stack
overflow.

I hope that one day functional language compilers will
do that optimization for you - convert a
non-tail-recursive code into a tail-recursive one. Do
you know of some progress in that direction?

Regards,

Martin

--- Pal-Kristian Engstad <pal_engstad@naughtydog.com>
wrote:

> 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!



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

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

[skaller]

On Sat, 2005-10-01 at 23:05 +0200, Martin Chabr wrote:
> Hello Pal-Kristian,
> 
> I agree with you that functional code written in a
> tail recursive style is hard to read. Sometimes you
> have to do it that way if you want to avoid a stack
> overflow.
> 
> I hope that one day functional language compilers will
> do that optimization for you - convert a
> non-tail-recursive code into a tail-recursive one. Do
> you know of some progress in that direction?

Isn't that just CPS? 

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

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

[Seth J. Fogarty]

On 10/2/05, skaller <skaller@users.sourceforge.net> wrote:
> On Sat, 2005-10-01 at 23:05 +0200, Martin Chabr wrote:
> > Hello Pal-Kristian,
> >
> > I agree with you that functional code written in a
> > tail recursive style is hard to read. Sometimes you
> > have to do it that way if you want to avoid a stack
> > overflow.
> >
> > I hope that one day functional language compilers will
> > do that optimization for you - convert a
> > non-tail-recursive code into a tail-recursive one. Do
> > you know of some progress in that direction?
>
> Isn't that just CPS?


--
Seth Fogarty             sfogarty@[gmail.com|rice.edu|livejournal]
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

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

[Thomas Fischbacher]

On Mon, 3 Oct 2005, skaller wrote:

> > I hope that one day functional language compilers will
> > do that optimization for you - convert a
> > non-tail-recursive code into a tail-recursive one. Do
> > you know of some progress in that direction?
> 
> Isn't that just CPS? 

He presumably wanted to see a different thing, e.g. 
automatically transforming


let rec fac1 x =
  if x = 0
  then 1
  else x*(fac1 (x-1))
;;

into

let fac2 x =
  let rec walk so_far todo =
    if todo = 0
    then so_far
    else walk (todo*so_far) (todo-1)
  in walk 1 x
;;


My impression is that it may indeed be possible to do something like this 
for simple applications, but that the cases that can be covered 
automatically presumably are so limited that an experienced programmer 
will usually want to attack them by going to a higher form of abstraction 
and not waste time on such things anyway.

I think that Olin Shivers indeed does have a valid point in pointing out 
that writing loops in tail-recursive style has major disadvantages. 
However, my impression still is that as soon as someone thinks in terms of 
"I have to write a loop for this", chances are good that he may improve 
his design by going back one step and ask the question "what do I want to 
use that loop for?". In quite many situations, it is possible to express 
one's thoughts more directly via other means, such as Array.map, 
fold_left, etc. 

What I (as a pedestrian) especially do not like about loops is that it is
much easier to make off-by-one errors than with any form of recursion 
which contains a base-case/recursive-case analysis.


Unfortunately, the OCaml native code compiler apparently is not yet smart 
enough to optimize code written in such a higher-order style well enough 
so that it can compete with imperative or tail-recursive code in 
time-critical applications. (Though quite many applications in fact are 
not.) At present, one can expect to lose about a factor of ~3 in
performance.

Example:

===>
let timing_apply f x =
  let t0 = Unix.gettimeofday() in
  let f_x = f x in
  let t1 = Unix.gettimeofday() in
  (f_x,t1-.t0)
;;

let my_array_fold_left f init arr =
  let len = Array.length arr in
  let rec walk so_far pos =
    if pos=len
    then so_far
    else walk (f so_far arr.(pos)) (1+pos)
  in walk init 0
;;


let test m n =
  let arr =
    Array.init m
      (fun j -> Array.init n (fun k -> j*k+k))
  in
  let scratchpad = ref 0 in
  (* -- *)
  let rec frobenius1 mx =
    Array.fold_left
      (fun so_far row ->
	Array.fold_left
	  (fun so_far entry ->
	    so_far+entry*entry)
	  so_far row)
      0 mx
  in
  let frobenius2 mx =
    my_array_fold_left
      (fun so_far row ->
	my_array_fold_left
	  (fun so_far entry ->
	    so_far+entry*entry)
	  so_far row)
      0 mx
  in
  let frobenius3 mx =
    begin
      scratchpad := 0;
      for i=0 to (Array.length mx)-1 do
	let row = mx.(i) in
	for j=0 to (Array.length row)-1 do
	  scratchpad:= !scratchpad + row.(j)*row.(j);
	done;
      done;
      !scratchpad
    end
  in
  let frobenius4 mx =
    let nr_rows = Array.length mx in
    let rec walk_rows so_far nr_row =
      if nr_row = nr_rows
      then so_far
      else
	let row = mx.(nr_row) in
	let len_row = Array.length row in
	let rec walk_cols so_far nr_col =
	  if nr_col = len_row
	  then so_far
	  else walk_cols (so_far+row.(nr_col)*row.(nr_col)) (1+nr_col)
	in 
	walk_rows (walk_cols so_far 0) (1+nr_row)
    in
    walk_rows 0 0
  in
  let frobenius5 mx =
    let nr_rows = Array.length mx in
    let rec walk_rows so_far nr_row =
      if nr_row = nr_rows
      then so_far
      else
	let row = mx.(nr_row) in
	let len_row = Array.length row in
	let rec walk_cols row so_far nr_col =
	  if nr_col = len_row
	  then so_far
	  else walk_cols row (so_far+row.(nr_col)*row.(nr_col)) (1+nr_col)
	in 
	walk_rows (walk_cols row so_far 0) (1+nr_row)
    in
    walk_rows 0 0
  in
  let compute_n_times n f x =
    let rec walk k =
      if k = n then f x
      else
	let () = ignore(f x) in
	walk (k+1)
    in walk 1
  in
  Array.map
    (fun f -> timing_apply (compute_n_times 1000 f) arr)
    [|frobenius1;frobenius2;frobenius3;frobenius4;frobenius5|]
;;

let result = test 1000 3 in
Array.iteri (fun nr (_,t) -> Printf.printf "%d: %f\n" (1+nr) t) result
;;
<===

ocamlc:

1: 0.987257
2: 1.196910
3: 0.709074
4: 0.858948
5: 0.984935

ocamlopt:

1: 0.066404
2: 0.075691
3: 0.025450
4: 0.025756
5: 0.023472

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

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

[skaller]

On Mon, 2005-10-03 at 15:09 +0200, Thomas Fischbacher wrote:
> On Mon, 3 Oct 2005, skaller wrote:
> 
> > > I hope that one day functional language compilers will
> > > do that optimization for you - convert a
> > > non-tail-recursive code into a tail-recursive one. Do
> > > you know of some progress in that direction?
> > 
> > Isn't that just CPS? 
> 
> He presumably wanted to see a different thing, e.g. 
> automatically transforming

I know. But his comment 'that's different' is inadequate.
CPS transforms code so there are no function calls at all,
(procedural form), or, in functional form, every function
contains exactly one call which is always in tail position.

So it certainly does what is required. Therefore the
question is nonsense. The real question is more like
asking if it is possible to transform a routine
using O(n^k) store into one using O(n^j) store, where j < k.

It is always possible to eliminate recursion: for example,
a recursive descent of a simple tree can always be replaced by a using
an iterator .. of course the iterator will have to retain
a list of parent nodes to allow the traversal, so eliminating
the 'recursion' does not save any storage.



-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

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

[Martin Chabr]

Thomas,

what I am especially concerned about is the stack
overflow for non-tail-recursive programs. Speed is of
less importance.

By the way, we are diverting from the subject of this
thread and from the main cause of my concern:

Avoiding shared data. Why is it done that way? Who
wants to have an array or list of identical records or
sub-arrays or other sub-structures which are all
updated at the same time in the same way? In other
words, who wants to have an array or a list of
pointers which are pointing to the same thing?

Does it ever happen in OCaml if programming is done in
a purely functional way? Does it happen in Haskell?

Martin


--- Thomas Fischbacher
<Thomas.Fischbacher@Physik.Uni-Muenchen.DE> schrieb:

> 
> On Mon, 3 Oct 2005, skaller wrote:
> 
> > > I hope that one day functional language
> compilers will
> > > do that optimization for you - convert a
> > > non-tail-recursive code into a tail-recursive
> one. Do
> > > you know of some progress in that direction?
> > 
> > Isn't that just CPS? 
> 
> He presumably wanted to see a different thing, e.g. 
> automatically transforming
> 
> 
> let rec fac1 x =
>   if x = 0
>   then 1
>   else x*(fac1 (x-1))
> ;;
> 
> into
> 
> let fac2 x =
>   let rec walk so_far todo =
>     if todo = 0
>     then so_far
>     else walk (todo*so_far) (todo-1)
>   in walk 1 x
> ;;
> 
> 
> My impression is that it may indeed be possible to
> do something like this 
> for simple applications, but that the cases that can
> be covered 
> automatically presumably are so limited that an
> experienced programmer 
> will usually want to attack them by going to a
> higher form of abstraction 
> and not waste time on such things anyway.
> 
> I think that Olin Shivers indeed does have a valid
> point in pointing out 
> that writing loops in tail-recursive style has major
> disadvantages. 
> However, my impression still is that as soon as
> someone thinks in terms of 
> "I have to write a loop for this", chances are good
> that he may improve 
> his design by going back one step and ask the
> question "what do I want to 
> use that loop for?". In quite many situations, it is
> possible to express 
> one's thoughts more directly via other means, such
> as Array.map, 
> fold_left, etc. 
> 
> What I (as a pedestrian) especially do not like
> about loops is that it is
> much easier to make off-by-one errors than with any
> form of recursion 
> which contains a base-case/recursive-case analysis.
> 
> 
> Unfortunately, the OCaml native code compiler
> apparently is not yet smart 
> enough to optimize code written in such a
> higher-order style well enough 
> so that it can compete with imperative or
> tail-recursive code in 
> time-critical applications. (Though quite many
> applications in fact are 
> not.) At present, one can expect to lose about a
> factor of ~3 in
> performance.
> 
> Example:
> 
> ===>
> let timing_apply f x =
>   let t0 = Unix.gettimeofday() in
>   let f_x = f x in
>   let t1 = Unix.gettimeofday() in
>   (f_x,t1-.t0)
> ;;
> 
> let my_array_fold_left f init arr =
>   let len = Array.length arr in
>   let rec walk so_far pos =
>     if pos=len
>     then so_far
>     else walk (f so_far arr.(pos)) (1+pos)
>   in walk init 0
> ;;
> 
> 
> let test m n =
>   let arr =
>     Array.init m
>       (fun j -> Array.init n (fun k -> j*k+k))
>   in
>   let scratchpad = ref 0 in
>   (* -- *)
>   let rec frobenius1 mx =
>     Array.fold_left
>       (fun so_far row ->
> 	Array.fold_left
> 	  (fun so_far entry ->
> 	    so_far+entry*entry)
> 	  so_far row)
>       0 mx
>   in
>   let frobenius2 mx =
>     my_array_fold_left
>       (fun so_far row ->
> 	my_array_fold_left
> 	  (fun so_far entry ->
> 	    so_far+entry*entry)
> 	  so_far row)
>       0 mx
>   in
>   let frobenius3 mx =
>     begin
>       scratchpad := 0;
>       for i=0 to (Array.length mx)-1 do
> 	let row = mx.(i) in
> 	for j=0 to (Array.length row)-1 do
> 	  scratchpad:= !scratchpad + row.(j)*row.(j);
> 	done;
>       done;
>       !scratchpad
>     end
>   in
>   let frobenius4 mx =
>     let nr_rows = Array.length mx in
>     let rec walk_rows so_far nr_row =
>       if nr_row = nr_rows
>       then so_far
>       else
> 	let row = mx.(nr_row) in
> 	let len_row = Array.length row in
> 	let rec walk_cols so_far nr_col =
> 	  if nr_col = len_row
> 	  then so_far
> 	  else walk_cols (so_far+row.(nr_col)*row.(nr_col))
> (1+nr_col)
> 	in 
> 	walk_rows (walk_cols so_far 0) (1+nr_row)
>     in
>     walk_rows 0 0
>   in
>   let frobenius5 mx =
>     let nr_rows = Array.length mx in
>     let rec walk_rows so_far nr_row =
>       if nr_row = nr_rows
>       then so_far
>       else
> 	let row = mx.(nr_row) in
> 	let len_row = Array.length row in
> 	let rec walk_cols row so_far nr_col =
> 	  if nr_col = len_row
> 	  then so_far
> 	  else walk_cols row
> (so_far+row.(nr_col)*row.(nr_col)) (1+nr_col)
> 	in 
> 	walk_rows (walk_cols row so_far 0) (1+nr_row)
>     in
>     walk_rows 0 0
>   in
>   let compute_n_times n f x =
>     let rec walk k =
>       if k = n then f x
>       else
> 	let () = ignore(f x) in
> 	walk (k+1)
>     in walk 1
>   in
>   Array.map
>     (fun f -> timing_apply (compute_n_times 1000 f)
> arr)
>    
>
[|frobenius1;frobenius2;frobenius3;frobenius4;frobenius5|]
> ;;
> 
> let result = test 1000 3 in
> Array.iteri (fun nr (_,t) -> Printf.printf "%d:
> %f\n" (1+nr) t) result
> ;;
> <===
> 
> ocamlc:
> 
> 1: 0.987257
> 2: 1.196910
> 3: 0.709074
> 4: 0.858948
> 5: 0.984935
> 
> ocamlopt:
> 
=== message truncated ===



	

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

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

[Thomas Fischbacher]

On Mon, 3 Oct 2005, Martin Chabr wrote:

> Avoiding shared data. Why is it done that way? Who
> wants to have an array or list of identical records or
> sub-arrays or other sub-structures which are all
> updated at the same time in the same way?

Thoughts about substructure updates and sharing structure do not mix.

There are situations where the one way to think about things is 
appropriate, and there are situations when it's the other one.

> In other
> words, who wants to have an array or a list of
> pointers which are pointing to the same thing?

Suppose I give you a tree representing the filesystem structure on my 
machine. Now I ask you to map this to the tree describing the filesystem 
with one directory renamed and another one (and everythinbg beneath it) 
deleted. You surely do not want to copy the entire tree, so this is an 
example where sharing structure perfectly makes sense. And as you do not 
destructively modify the data in the nodes, it does not matter at all for 
the semantics of the program that you actually share a lot of data.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

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

[Jon Harrop]

On Monday 03 October 2005 21:03, Martin Chabr wrote:
> what I am especially concerned about is the stack
> overflow for non-tail-recursive programs. Speed is of
> less importance.

Yes. Many useful algorithms are non-tail recursive and do not cause stack 
overflows, e.g. those that recurse O(log n) times.

> By the way, we are diverting from the subject of this
> thread and from the main cause of my concern:
>
> Avoiding shared data. Why is it done that way? Who
> wants to have an array or list of identical records or
> sub-arrays or other sub-structures which are all
> updated at the same time in the same way? In other 
> words, who wants to have an array or a list of
> pointers which are pointing to the same thing?

If you mean this:

# let a = Array.make 3 (ref 0) in (a.(0) := 3; a);;
- : int ref array = [|{contents = 3}; {contents = 3}; {contents = 3}|]

I don't want arrays of elements referencing the same value. So I don't create 
them.

> Does it ever happen in OCaml if programming is done in
> a purely functional way?

If you mean "is referential transparency useful?" then the answer is 
definitely yes. I use data structures that share data all the time but not in 
the form of an array or list of the same repeated value.

For example, computing set unions, differences and intersections using the Set 
module reuses branches of old tree when possible. This reduces the asymptotic 
algorithmic complexity of these operations so they can run asymptotically 
faster than imperative implementations.

> Does it happen in Haskell? 

You'll get a suboptimal answer to such questions on this list.

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

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

[Martin Chabr]

--- Jon Harrop <jon@ffconsultancy.com> wrote:

> If you mean this:
> 
> # let a = Array.make 3 (ref 0) in (a.(0) := 3; a);;
> - : int ref array = [|{contents = 3}; {contents =
> 3}; {contents = 3}|]
> 
> I don't want arrays of elements referencing the same
> value. So I don't create 
> them.

I do not disagree. The trouble on my side is that it
is very easy to get them and difficult not to get them
or get rid of them, once the programs get more
complex.

Martin



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

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

[Jon Harrop]

On Tuesday 04 October 2005 19:06, you wrote:
> I do not disagree. The trouble on my side is that it
> is very easy to get them and difficult not to get them
> or get rid of them, once the programs get more
> complex.

Yes, misuse of Array.make is certainly a caveat. The easiest solution is to 
use Array.init instead.

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

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

[skaller]

On Mon, 2005-10-03 at 22:03 +0200, Martin Chabr wrote:

> Avoiding shared data. Why is it done that way? Who
> wants to have an array or list of identical records or
> sub-arrays or other sub-structures which are all
> updated at the same time in the same way?

Mutable shared data is very useful: caching is
an obvious example where this is precisely what you want.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Avoiding shared data

[Brian Hurt]

On Tue, 4 Oct 2005, skaller wrote:

> Mutable shared data is very useful: caching is
> an obvious example where this is precisely what you want.

Also, occassionally mutable data allows you to do something in O(1) 
instead of O(log N).  If this extra cost is in your inner loop, it can 
slow the whole algorithm down by a factor of 10-30 fold easy.  Graph 
algorithms are especially bad for this.  Want to get a name for yourself? 
Come up with a way to represent cyclic graphs in a purely functional way 
such that given any arbtirary node, I can find out what other nodes it has 
edges to (and what their weights are) in O(1).

Brian

FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

Hello,


is there a general overvie (paper or book), where
functional and imperative approaches to solve a problem are
compared directly?

Most often people say, imperative is faster in most of all
cases, and only in some cases FP might be faster.

If there is a paper/book about problem solving and performance,
comparing different approaches I would be happy to have a pointer
to it.

Also it would be nice to find something about how
classical imperative style, OO-style and FP-style
are solving problems, and which patterns can be done
easier in the one or the other way.

I recently had a discussion about some OO-patterns
( so called "GoF"-Book) and tried to solve some of them with
OCamls module system.
Adapter and bridge was talked about. Adapter was easy in writing a simple
wrapper.
Bridge could be done with a functor. :)


So, if there are direct translations possible, where to find
comparisons?

Another interesting theme in this respect is: If not only some patterns
were adapted to Fp, but the whole problem solving approach is different,
which patterns will be unnevcessary then, because the whole structure of
the software will be different...?!



Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Michael Wohlwend]

On Tuesday 04 October 2005 18:47, Oliver Bandel wrote:
>
> So, if there are direct translations possible, where to find
> comparisons?
>

there is a paper "Design Patterns in OCaml"  which describes various patterns:
http://people.csail.mit.edu/dnj/teaching/6898/projects/vicente-wagner.pdf

cheers,
 Michael

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Tuesday 04 October 2005 23:38, Michael Wohlwend wrote:
> there is a paper "Design Patterns in OCaml"  which describes various
> patterns:
> http://people.csail.mit.edu/dnj/teaching/6898/projects/vicente-wagner.pdf

I think I read this paper some time ago but it was interesting to read it 
again. Firstly, it gives only 3 references, doesn't appear to be complete, I 
think it is out of date and it appears to be written from the point of view 
of a dynamic typer. Secondly, I was never a fan of "design patterns".

As they say, several "design patterns" have trivial counterparts in FPLs, 
roughly: Singleton = module structure, Facade = module signature, Command = 
currying, Memento = dynamic type checking, and Strategy = HOFs.

The paper repeatedly states that modules cannot be mutually recursive. AFAIK, 
this has not been true for some time.

In the section about the "Observer" pattern, they state "a meaningless method 
call must be inserted into the code because OCaml's static checker cannot 
infer the type of the ...". Can the meaningless method not be replaced with a 
type declaration?

Perhaps the "State" pattern can be better represented by reusing polymorphic 
variants.

Overall, I'd say that the idea of design patterns is reasonable but the GOFs 
work is not relevant to OCaml - the study will need to be redone from 
scratch. I am much more interested in the automation of the factoring of code 
patterns, although I've yet to actually study it...

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

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Christopher A. Watford]

On 10/4/05, Oliver Bandel <oliver@first.in-berlin.de> wrote:
> Hello,
>
> is there a general overvie (paper or book), where
> functional and imperative approaches to solve a problem are
> compared directly?
>
> Most often people say, imperative is faster in most of all
> cases, and only in some cases FP might be faster.
>
> If there is a paper/book about problem solving and performance,
> comparing different approaches I would be happy to have a pointer
> to it.
>
> Also it would be nice to find something about how
> classical imperative style, OO-style and FP-style
> are solving problems, and which patterns can be done
> easier in the one or the other way.
>
> I recently had a discussion about some OO-patterns
> ( so called "GoF"-Book) and tried to solve some of them with
> OCamls module system.
> Adapter and bridge was talked about. Adapter was easy in writing a simple
> wrapper.
> Bridge could be done with a functor. :)
>
> So, if there are direct translations possible, where to find
> comparisons?
>
> Another interesting theme in this respect is: If not only some patterns
> were adapted to Fp, but the whole problem solving approach is different,
> which patterns will be unnevcessary then, because the whole structure of
> the software will be different...?!
>
> Ciao,
>   Oliver

Sigh, your question only begs for trolls to pop out of the corners.

It would probably be best to keep these questions off this list. Far
too often they go off into the deep end of the 'my language is better
than your language' debates. Obviously members of this list are going
to be biased towards functional languages and will probably give you
biased articles to read or biased papers. Not necessarily biased in a
bad way, just more likely to show functional languages in a good
light.

A poor place to start reading on the subject of what language is best
is The Computer Language Shootout [1]. An even worse place to start
reading is this list.

The actual performance for any program will depend largely on your
ability to program well for the language and for the specific compiler
you choose.

I would say it's obvious that some patterns are easier to *write* in a
certain language, but that hardly shows which language is *best* speed
wise. Your example shows one pattern functional languages are well
suited for, however, I'm sure an experienced C programmer could show
you an example of that pattern which is both efficient and easy to
read (I know I know people on this list may disagree).

This list is best for asking OCaml questions and is awful for asking
for what language is best for what, nobody agrees.

--
Christopher A. Watford
christopher.watford@gmail.com

[1] http://shootout.alioth.debian.org/

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Tuesday 04 October 2005 23:39, Christopher A. Watford wrote:
> This list is best for asking OCaml questions and is awful for asking
> for what language is best for what, nobody agrees.

Oliver was asking which of three programming paradigms is best under different 
circumstances. OCaml provides all three so I think this can be taken as an 
OCaml-specific question and is fine for this list.

I for one would be very interested in reading information on this. I'll check 
out the design patterns paper - thanks Michael.

My impression is that:

1. Data structure heavy code is often easier to write in a functional style. 
See the "n"th-nearest neighbour example from my book:

  http://www.ffconsultancy.com/products/ocaml_for_scientists/complete/

2. GUI code is more easily written with a stateful imperative front and often 
a functional back end.

I have yet to really exploit OCaml's OO capabilities.

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

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

On Tue, Oct 04, 2005 at 06:39:28PM -0400, Christopher A. Watford wrote:
[...] 
> This list is best for asking OCaml questions and is awful for asking
> for what language is best for what, nobody agrees.
[...] 


I was not asking, what language is better for soimething, or best at all.
I asked for what programming style/paradigm is best used to solve
certain problems.

As OCaml provides more than one programming paradigm, for me
it's the best language I ever had programmed in (some
other features are also fine).

So the question goes in a different direction:
  How to solve problems best, if you have the possibility
  do do it in different ways.

Well, every programmer can choose it's own way, but if certain areas
are well known to do them in a certain way best, it  makes sense
to go that direction.

For example, I'm not really a fan of OO-programming, but when
programming GUI-software I think it would be the best choice,
and FP-programming lacks flexibility here (if not using
a DSL to create GUI-code, which then is separately compiled).

Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Wednesday 05 October 2005 13:10, Oliver Bandel wrote:
> For example, I'm not really a fan of OO-programming, but when
> programming GUI-software I think it would be the best choice,
> and FP-programming lacks flexibility here (if not using
> a DSL to create GUI-code, which then is separately compiled).

I am finding ordinary FP perfectly adequate for GUI programming. My GUI 
programming may be unorthodox, however. :-)

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

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[skaller]

On Wed, 2005-10-05 at 14:10 +0200, Oliver Bandel wrote:

> For example, I'm not really a fan of OO-programming, but when
> programming GUI-software I think it would be the best choice,
> and FP-programming lacks flexibility here 

I contend that concurrent programming is best here.
However, I don't know: I have a tool (Felix) to explore
this, but haven't got around to actually trying the
one-thread/one-widget paradigm. 

The OO solution is reactive and requires you to maintain
the whole widget state without use of the stack, thereby
discarding everything that is known about block structured
and functional programming, and going back to the bad old
days of the early 70s with a flat state space, except that
the state space is partitioned into objects.

The thread based solution control inverts this paradigm,
giving you a stack and control flow for every widget,
this is *active* or algorithmic programming. So I content
it must be better, because it not only partitions the state
space as OO does, it *also* partitions the control space,
and allows you to use all the advantages of a functional
or block structured style.

Actually, in practice, I expect a mix of the solutions
will be best. The reason is: we know a LOT about
state machines. So subparts of problems which correspond
to them can easily be programmed and reasoned about,
simply because we have lots of mature theory.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Ant: Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Martin Chabr]

>From my limited experience I see it this way:

Mathematical computations, algorithms, interfacing
(complicated data conversions), text translations,
parsing, anything which can be well represented by
dataflow diagrams and where there is no changing state
==> 
use FP

User interfaces, business systems, anything with
objects which have changing states and which react to
events and interact with each other ==> use OOP

Martin

--- Oliver Bandel <oliver@first.in-berlin.de> wrote:

> On Tue, Oct 04, 2005 at 06:39:28PM -0400,
> Christopher A. Watford wrote:
> [...] 
> > This list is best for asking OCaml questions and
> is awful for asking
> > for what language is best for what, nobody agrees.
> [...] 
> 
> 
> I was not asking, what language is better for
> soimething, or best at all.
> I asked for what programming style/paradigm is best
> used to solve
> certain problems.
> 
> As OCaml provides more than one programming
> paradigm, for me
> it's the best language I ever had programmed in
> (some
> other features are also fine).
> 
> So the question goes in a different direction:
>   How to solve problems best, if you have the
> possibility
>   do do it in different ways.
> 
> Well, every programmer can choose it's own way, but
> if certain areas
> are well known to do them in a certain way best, it 
> makes sense
> to go that direction.
> 
> For example, I'm not really a fan of OO-programming,
> but when
> programming GUI-software I think it would be the
> best choice,
> and FP-programming lacks flexibility here (if not
> using
> a DSL to create GUI-code, which then is separately
> compiled).
> 
> Ciao,
>    Oliver
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 



	

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

Re: Ant: Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Markus Mottl]

On 10/5/05, Martin Chabr <martin_chabr@yahoo.de> wrote:
> User interfaces, business systems, anything with
> objects which have changing states and which react to
> events and interact with each other ==> use OOP

FWIW, we use OCaml for fairly large systems (> 100 KLOCs, > 1000
modules) with very complicated business logic handling high-volume
realtime events.  Even though OCaml supports OOP very well, probably
much better than most mainstream languages, we do not use OOP and are
not intending to do so.  Mutable records together with modules are
perfectly fine for handling changing states safely and efficiently and
are in the general case semantically more transparent than objects. 
Your mileage may vary...

Regards,
Markus

--
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

Re: Ant: Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[brogoff]

On Wed, 5 Oct 2005, Markus Mottl wrote:
> FWIW, we use OCaml for fairly large systems (> 100 KLOCs, > 1000
> modules) with very complicated business logic handling high-volume
> realtime events.  Even though OCaml supports OOP very well, probably
> much better than most mainstream languages, we do not use OOP and are
> not intending to do so.  Mutable records together with modules are
> perfectly fine for handling changing states safely and efficiently and
> are in the general case semantically more transparent than objects.
> Your mileage may vary...

I don't disagree with anything above, but thought I'd mention that OCaml
classes can be used as more polymorphic records (giving up pattern matching
and some performance), without using the late-binding/open-recursion aspect
which is the sine qua non of OOP.

-- Brian

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Brian Hurt]

On Tue, 4 Oct 2005, Oliver Bandel wrote:

> Most often people say, imperative is faster in most of all
> cases, and only in some cases FP might be faster.

The general argument here is that if the FP solution is faster, the 
imperitive language can just implement the FP solution.  My answer to that 
is that imperitive programming languages discourage you from thinking in 
certain ways rather strongly- while the FP solution may be faster, it's 
not "natural".

The big advantage of FP programming IMHO is not performance, but instead 
*correctness*.  With today's multi-gigahertz machines with multi-gigabytes 
of memory, performance isn't as critical as it used to be.  But 
correctness- especially automatically gaurenteed correctness on projects 
spanning hundreds of thousands of lines of code and dozens of developers 
maintained over decades of time- starts becoming critical.  I'd quite 
happily trade off 10% performance for correctness, or even 50% 
performance.

FP is a huge gain in correctness, because it allows me to *control 
mutability*.  If I pass a mutable data structure to a block of code there 
is an instant implicit contract between the caller and the callee on how 
(or wether) to modify the mutable data structure.  It doesn't matter what 
the contract is- wether it's to not modify the structure at all, to allow 
optional modification (either unlimited or only in certain ways), or to 
require certain modifications- a dependency between the two different 
peices of code exists.  And this dependency, this contract, is probably 
undocumented and always unchecked by the compiler, which means it's a 
maintaince nightmare waiting to happen.  One peice of code gets modified 
to violate the contract, perhaps even unknowingly, or perhaps due to some 
changing requirement, and untouched code thousands of lines away suddenly 
breaks.

Note that such a bidirectional dependency can be implemented in functional 
code- the called code returns a new copy of the modified structure to the 
calling code, which the calling code then adopts and uses.  But notice 
that such a bidirectional dependency is explicitly stated in the code, and 
automatically checked by the compiler.  And the calling code has the 
option of wether or not to allow the modification (or to use both the old 
and the new copy).

Java programmers are begining to tumble to this advantage- notice the 
increasing popularity of immutable objects (starting with Int and Float), 
and Java Beans.

> I recently had a discussion about some OO-patterns
> ( so called "GoF"-Book) and tried to solve some of them with
> OCamls module system.
> Adapter and bridge was talked about. Adapter was easy in writing a simple
> wrapper.
> Bridge could be done with a functor. :)

Some of the patterns are doable with modules.  Singleton, for example, is 
a classic module pattern.  Many of the patterns aren't, however.  An 
important comment here is that modules are NOT weird and broken objects. 
A better point of comparison is C++ templates, except that 95+% of the use 
of templates in C++ is to implement universal types, i.e. a C++ programmer 
writes "list<A>" where an Ocaml programmer would write "'a list".

>
> Another interesting theme in this respect is: If not only some patterns
> were adapted to Fp, but the whole problem solving approach is different,
> which patterns will be unnevcessary then, because the whole structure of
> the software will be different...?!

There are patterns in every programming idiom.  The GoF book was just 
Object Oriented patterns- but there are procedural patterns, and 
functional patterns, and logic patterns, etc.

Brian

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

[Martin Chabr]

--- skaller <skaller@users.sourceforge.net> wrote:

> On Mon, 2005-10-03 at 22:03 +0200, Martin Chabr
> wrote:
> 
> > Avoiding shared data. Why is it done that way? Who
> > wants to have an array or list of identical
> records or
> > sub-arrays or other sub-structures which are all
> > updated at the same time in the same way?
> 
> Mutable shared data is very useful: caching is
> an obvious example where this is precisely what you
> want.
> 
> -- 
> John Skaller <skaller at users dot sf dot net>
> Felix, successor to C++: http://felix.sf.net
> 
> 

This sounds very interesting. Can you say a little
more about it please?

Martin



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

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

[skaller]

On Tue, 2005-10-04 at 20:09 +0200, Martin Chabr wrote:

> > Mutable shared data is very useful: caching is
> > an obvious example where this is precisely what you
> > want.

> This sounds very interesting. Can you say a little
> more about it please?

Well others know more about techniques like HashConsing 
and memoisation than I do .. but basically it is sometimes
useful for a pure function which is expensive to evaluate,
to have a cache of results already computed.

For example, in Felix I have to do 'lookup' to bind
string names of functions to entries in the symbol table.

The lookup is very expensive for functions, because Felix
supports overloading, which means the argument type has
to be calculated, and unification against bound signatures
of candidates is used to select the most specialised matching
function.

the problem is that to bind the types required to do this
*also* requires lookup (and it can even be recursive).

So in the process of doing all this lookup, it would be nice
to cache the results so that the 'expensive' lookup is only
done once, and after that the cached value is used.

In fact I tried that using a Hashtbl .. but because the keys 
were complex, it turned out that polymorphic compare and hash
functions were actually *slower* than my nasty purely functional
lookup code.

However, I do cache the environments, and this save some
time: environments are created by a call like

	build_env (parent)

which follows the chain of parents to ground, gathering
all the symbols defined in each one (resulting in a list
of hashtables). This process isn't all that slow .. the
problem is that in a purely functional system with
random symbol lookups, it has to be done once for EVERY
lookup .. not just once when you do a lookup, since as
noted above doing a lookup can spawn a hundreds of other
lookups. So caching the 'environment' in which to do the
lookups was a good way to speed up the process, without
changing the functional style of the code.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Avoiding shared data

[Andrej Bauer]

Thomas Fischbacher wrote:
> He presumably wanted to see a different thing, e.g. 
> automatically transforming

> let rec fac1 x =
>   if x = 0
>   then 1
>   else x*(fac1 (x-1))
> ;;
> 
> into
> 
> let fac2 x =
>   let rec walk so_far todo =
>     if todo = 0
>     then so_far
>     else walk (todo*so_far) (todo-1)
>   in walk 1 x
> ;;
> 
> My impression is that it may indeed be possible to do something like this 
> for simple applications, but that the cases that can be covered 
> automatically presumably are so limited that an experienced programmer 
> will usually want to attack them by going to a higher form of abstraction 
> and not waste time on such things anyway.

Incidentally, I recently wrote a little piece on how to transform one
kind of recursion into another kind of recursion via
propositions-as-types http://math.andrej.com/2005/09/16/proof-hacking/
which may be of interest to some of you. I only considered a very simple
kind of recursion on natural numbers. My impression is that quite a
general form of recursion could be treated (replace natural numbers by a
well-founded type, for example).

This sort of thing is probably not immediately useful in programming
practice. But even "real" programmers should be aware of abstract
mathematical ideas because they they indirectly make them write better
programs.

Best regards,

Andrej

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

[Martin Chabr]

Hello Oliver,

I am trying to find a programming style within the
spectrum of possibilities which OCaml supports. This
programming style should be easy to produce, easy to
read and efficient in runtime.

Sometimes a nested system of "for" or "while" loops
appears simpler to me than a system of recursive
calls. Sometimes such systems of recursive calls
remind me of undisciplined goto jumps.

There is an excellent OCaml tutorial at:
http://www.ocaml-tutorial.org/.

In this tutorial the author gives a simple example of
a stack-blowing, non-tail-recursive code. The
following tail-recursive version takes two functions
instead of one and is relatively much more complex. In
general, for the real world problems, it is much
worse. I cite the author:
"That was a brief overview of tail recursion, but in
real world situations determining if a function is
tail recursive can be quite hard." I believe him.
This is at:
http://www.ocaml-tutorial.org/if_statements,_loops_and_recursion
section tail recursion.

I think that some problems, like simple operations on
lists, can be easier described by pattern matching and
recursion, whereas for others it appears more natural
to take loops.

I also think that what looks simple or not depends on
the person. I myself have spent half of my life with
imperative languages.

Regards,

Martin

--- Oliver Bandel <oliver@first.in-berlin.de> wrote:

> 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
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 



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

getting used to FP-programming (Re: Ant: Re: Ant: Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

Hello Martin,

On Sat, Oct 01, 2005 at 11:36:08PM +0200, Martin Chabr wrote:
> Hello Oliver,
> 
> I am trying to find a programming style within the
> spectrum of possibilities which OCaml supports. This
> programming style should be easy to produce, easy to
> read and efficient in runtime.
> 
> Sometimes a nested system of "for" or "while" loops
> appears simpler to me than a system of recursive
> calls. Sometimes such systems of recursive calls
> remind me of undisciplined goto jumps.
[...]
> general, for the real world problems, it is much
> worse. I cite the author:
> "That was a brief overview of tail recursion, but in
> real world situations determining if a function is
> tail recursive can be quite hard." I believe him.

I doubt it is.
Or maybe if the people write functions that are some
pages of code long. But it's better to keep the functions short,
and FP makes this very easy.

[...]
> I think that some problems, like simple operations on
> lists, can be easier described by pattern matching and
> recursion, whereas for others it appears more natural
> to take loops.

Yes, but when you are used to FP-style and recursions
the amount of problems one would rather use the
for/while loops for, gets smaller.

I just dome days ago saw this on an example-code I wrote
in a discussion on the berlin' Linux-User-Groups mailing list
(I'm doing some marketing for OCaml;-))
I first thought, well the better version is with loops.
But I tried the recursive definition and it was astouningly
easy to read. :)

So IMHO it's how often you tried the different programming style,
what makes you thinking different about this.

> 
> I also think that what looks simple or not depends on
> the person. I myself have spent half of my life with
> imperative languages.

Mee too for many years, and "depends on the person" could also be said
as: "depends on the experience of the person", and as I more and more
get used to FP constructs, I see the problem solving diferently than
some time ago.

Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

On Tue, Oct 04, 2005 at 07:45:12PM -0500, Brian Hurt wrote:
[...] 
> The big advantage of FP programming IMHO is not performance, but instead 
> *correctness*.  With today's multi-gigahertz machines with multi-gigabytes 
> of memory, performance isn't as critical as it used to be.  But 
> correctness- especially automatically gaurenteed correctness on projects 
> spanning hundreds of thousands of lines of code and dozens of developers 
> maintained over decades of time- starts becoming critical.

Yes, I agree on this.
I get daily messages from an buglist-mailinglist, where most often
things like typical memory-exploits are the reason of why a system
or a process can be exploited.

So, the typical "out of bounds" and "format string" problems
are typical security risks.
(Btw: is OCaml's format-string stuff from the Printf-module save in
this respect?!)


> I'd quite 
> happily trade off 10% performance for correctness, or even 50% 
> performance.

Well, if the code with correctness is nearly as fast as the code without,
it would be best.


> 
> FP is a huge gain in correctness, because it allows me to *control 
> mutability*.  If I pass a mutable data structure to a block of code there 
> is an instant implicit contract between the caller and the callee on how 
> (or wether) to modify the mutable data structure.  It doesn't matter what 
> the contract is- wether it's to not modify the structure at all, to allow 
> optional modification (either unlimited or only in certain ways), or to 
> require certain modifications- a dependency between the two different 
> peices of code exists.  And this dependency, this contract, is probably 
> undocumented and always unchecked by the compiler, which means it's a 
> maintaince nightmare waiting to happen.  One peice of code gets modified 
> to violate the contract, perhaps even unknowingly, or perhaps due to some 
> changing requirement, and untouched code thousands of lines away suddenly 
> breaks.


Yes, this is a very well description of the FP-advantages.
Nevertheless, if a solution is too slow, it hinders
people from adopting FPLs for their programmig, and
software remains unsecure/unsafe, because they again and again
will choose the unsafe langauges... :(


Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[William Lovas]

On Wed, Oct 05, 2005 at 03:45:52PM +0200, Oliver Bandel wrote:
> So, the typical "out of bounds" and "format string" problems
> are typical security risks.
> (Btw: is OCaml's format-string stuff from the Printf-module save in
> this respect?!)

As far as i understand the "format string" bugs, they arise when a
programmer writes a call to printf whose first argument comes from
user input.  In O'Caml the various *printf functions require their
first argument to have type "('a, 'b, 'c) format", for some values
of 'a, 'b, and 'c.  As far as i can tell there's no way to produce
a value of this type from user input, so O'Caml should be safe.

In fact, there might even be a better reason O'Caml is safe, like
that it doesn't automatically keep looking for arguments until it
runs out of %expandos, but rather it just produces a closure that
can be applied to more arguments later.  But this is just a guess,
based on a quick 5-minute perusal of the O'Caml standard library.

cheers,
William