From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id D553DBC6B for ; Wed, 27 Jun 2007 18:43:47 +0200 (CEST) Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.183]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RGhlGa004688 for ; Wed, 27 Jun 2007 18:43:47 +0200 Received: from [141.84.136.30] (helo=[152.78.96.56]) by mrelayeu.kundenserver.de (node=mrelayeu1) with ESMTP (Nemesis), id 0MKwpI-1I3acM1sXP-00041x; Wed, 27 Jun 2007 18:43:46 +0200 Message-ID: <468293D4.3000100@functionality.de> Date: Wed, 27 Jun 2007 17:44:04 +0100 From: Thomas Fischbacher User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.12) Gecko/20060607 Debian/1.7.12-1.2 X-Accept-Language: en MIME-Version: 1.0 To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments References: <200706271314.35134.jon@ffconsultancy.com> <1A1D6F56-B3DB-4552-969C-9859482175AC@lrde.epita.fr> <46826C69.5060802@functionality.de> <200706271618.54156.jon@ffconsultancy.com> In-Reply-To: <200706271618.54156.jon@ffconsultancy.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Provags-ID: V01U2FsdGVkX1+nxFtGHgyTfYtrlmbM9F7FCnHXL+MyXIUPHa3 PpuzWHswD3xfv/h/mykuthtFiEPFeB7l5fWTbgxqnGaSvbpYdj 67xwcY6+vdlTvSwBgqnHg== X-Miltered: at discorde with ID 468293C3.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; stack:01 factorial:01 factorial:01 computations:01 constructors:01 1.0:98 1.0:98 2.0:98 heap:01 wrote:01 rec:01 dynamically:01 avoids:01 caml-list:01 lisp:01 Jon Harrop wrote: > This seems to be something that Lisp uses to allocate data structures on the > stack rather than the heap. Why would you want that? In order to avoid dynamic memory management and get dynamically scoped pre-allocated "implicit context" buffers to which I can refer as if they were ordinary variables. > >>let float_factorial = >> let _known_factorials = ref [|1.0;1.0;2.0;6.0;24.0;120.0;720.0|] in >> (fun n -> >> let known_factorials = !_known_factorials in >> let nr_known = Array.length known_factorials in >> if n < nr_known >> then >> known_factorials.(n) >> else >> let new_known_factorials = Array.make (n+1) 0.0 in >> begin >> for i=0 to nr_known-1 do >> new_known_factorials.(i) <- known_factorials.(i) >> done; >> (let rec fill f_pos pos = >> if pos > n then () >> else >> let () = new_known_factorials.(pos) <- f_pos in >> fill (f_pos *. (float_of_int (pos+1))) (pos+1) >> in >> fill (known_factorials.(nr_known-1)*.(float_of_int nr_known)) nr_known); >> _known_factorials := new_known_factorials; >> new_known_factorials.(n) >> end) > > > I can't quite follow that. Is it doing something cleverer than this: > > let float_factorial = > let m = ref [||] in > fun n -> > try (!m).(n) with _ -> > let m' = Array.make (n + 1) 1. in > for i=1 to n do > m'.(i) <- float i *. m'.(i - 1) > done; > m := m'; > m'.(n);; Well, it avoids some of the computations in your example, which re-does all the array whenever it has to be extended. >>Other advanced optimization techniques that can be used for benefit >>in very specialized situations include (explicit) continuation coding: >>rather than returning a value (e.g. a tuple), you take as an argument >>a function to which you then pass on your return value(s). This is quite >>useful whenever "execution flow branches out into multiple paths that >>have to be taken", > > Are you referring to CPS? Yes, but not the call/cc implicit CPS, but explicitly passing around continuations. >>and may sometimes (though rarely) also be used for >>good as a poor man's VALUES/MULTIPLE-VALUE-BIND substitute. > > Weren't values and multiple-value-bind completely superceded by pattern > matching? No. :-) Pattern matching requires constructors, which cons. I am talking about dynamical memory management avoidance techniques. There are a lot. -- best regards, Thomas Fischbacher tf@functionality.de