From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id C2D65BB94 for ; Mon, 3 Oct 2005 22:03:38 +0200 (CEST) Received: from web26809.mail.ukl.yahoo.com (web26809.mail.ukl.yahoo.com [217.146.176.85]) by concorde.inria.fr (8.13.0/8.13.0) with SMTP id j93K3cvE010868 for ; Mon, 3 Oct 2005 22:03:38 +0200 Received: (qmail 14094 invoked by uid 60001); 3 Oct 2005 20:03:37 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.de; h=Message-ID:Received:Date:From:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=J81xvTevfB3y0NYezAiR2H4+0v+kSLp+F+qaSPYoCm6yQQkvOyIsdqYL5ghApKLdgRV1ndZWSXbdtIYnIUrKvPlnlW7vGZVF8sXy4oc1eF+CQErbpPdT0BSw5SdAQrrv9NPTLhbkVWhI9GpsPZGXaafl9viy79w4hObXtAr5Cps= ; Message-ID: <20051003200337.14092.qmail@web26809.mail.ukl.yahoo.com> Received: from [213.103.158.2] by web26809.mail.ukl.yahoo.com via HTTP; Mon, 03 Oct 2005 22:03:37 CEST Date: Mon, 3 Oct 2005 22:03:37 +0200 (CEST) From: Martin Chabr Subject: Ant: Re: Ant: Re: Ant: Re: [Caml-list] Avoiding shared data To: Thomas Fischbacher Cc: caml-list@yquem.inria.fr In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Miltered: at concorde with ID 43418E9A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 avoiding:01 stack:01 avoiding:01 pointers:01 ocaml:01 haskell:01 compilers:01 transforming:01 rec:01 rec:01 abstraction:01 shivers:01 recursion:01 ocaml:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=DNS_FROM_RFC_ABUSE autolearn=disabled version=3.0.3 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 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