From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA13957; Sun, 5 Sep 2004 12:54:44 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA13921 for ; Sun, 5 Sep 2004 12:54:43 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i85Asg8Z008311 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sun, 5 Sep 2004 12:54:42 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1C3ufR-000A3V-Mb for caml-list@pauillac.inria.fr; Sun, 05 Sep 2004 10:54:41 +0000 From: Jon Harrop To: caml-list@pauillac.inria.fr Subject: Re: [Caml-list] laziness Date: Sun, 5 Sep 2004 11:50:39 +0100 User-Agent: KMail/1.6.2 References: <1094279400.3352.240.camel@pelican.wigram> In-Reply-To: <1094279400.3352.240.camel@pelican.wigram> MIME-Version: 1.0 Content-Disposition: inline Message-Id: <200409051150.39306.jon@jdh30.plus.com> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 413AF072.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 2004:99 inlined:01 inlining:01 inlining:01 eagerly:01 eagerly:01 pierre:01 weis:01 closures:01 haskell:01 avoids:01 memoizing:01 closures:01 non-trivial:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Saturday 04 September 2004 07:30, skaller wrote: > ... > by evaluating f,c',a',b' in some order then > applying f to c' a' b' -- eager evaluation. > However if the call is *inlined* to get > > if c' then a' else b' > > then perhaps a' or b' will never be evaluated. That is true for manual inlining but false for automatic inlining by the compiler (which must retain obide by the specifications). Actually, for any single evaluation a' or b' will never be evaluated. ;-) > In particular my 'impression' that ocaml evaluates > function arguments eagerly would be wrong. OCaml evaluates eagerly by default. There are some lazy special cases. Specifically the usual binary infix boolean operators, the "if" expression and pattern matches. There was a discussion fairly recently, by Pierre Weis among others, that it might be cool to be able to declare your own functions as non-strict. The functionality can be obtained regardless, by wrapping expressions in closures and only evaluating them when you need to, but it's a pfaff. > It seems that procedural code (which includes > functional expressions) is actually a way to > specify evaluation order I would say that imperative style allows you to determine evaluation order, not specify it. > and timing and typically > control flow is used to delay evaluation -- so that > procedural programming is actually quite lazy. I think inability to build a closure makes imperative languages even more strict. You may be referring to a way of "faking it" using imperative style but I wouldn't say that writing Haskell in C makes C lazy. > From a performance viewpoint, both eager and lazy > evaluation have advantages -- lazy evaluation avoids > gratuitously evaluating a term which the result does > not depend on, whereas eager evaluation can be used to > prevent an evaluation being done twice. Lazy evaluation is often (typically?) used to refer to memoizing as well as evaluating on demand. In which case lazy evaluation also prevents an evaluation being done twice. > Hence procedural > languages like Ocaml can be very fast because you can > hand tune the tradeoffs (also making it harder to > reason about the outcome .. ) Reasoning about lazy programs is difficult, AFAIK. I imagine this is because lazy programs end up building stacks of closures which act as data structures (require memory etc.) and which are a function of the input (i.e. they have non-trivial complexities). Such problems can appear in OCaml. For example, I'd assume that converting (I'm using Array to avoid discussions of tail recursion ;-): Array.map f (Array.map f l) to: Array.map (fun e -> f (f e)) l would be a deforesting optimisation. However, for short arrays and longer stacks of composited functions, there will probably come a time when an equivalent "optimisation" slows things down by "foresting" stacks of functions. > (1) exactly what does Ocaml guarrantee? I think you're looking for: "strict evaluation of function and constructor arguments in an unspecified order by default". > (2) what kind of performance and semantic > tradeoffs are involved with perturbations > on these assurances? Are you asking if it would be productive to change the specs to something like in-order evaluation? I'm no expert but I think the non-specific order of evaluation is a good opportunity for optimising and the strictness vs laziness choices set OCaml in a nice position with regard to imperative programming. > a purely functional > language is necessarily lazy, because lazy evaluation > is mandatory I'd have thought that you cannot determine evaluation order in a purely functional language and, therefore, you couldn't distinguish between eager and lazy evaluation in this case. > -- an eager evaluation strategy *requires* > procedural constructions to provide the laziness, and so > can't work with a purely functional language. I think that the way OCaml provides (memoized) laziness is inherently imperative but you could write a functional equivalent by providing an API which lets you recreate the lazy construct each time you use it. Cheers, Jon. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners