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 IAA00329; Sat, 4 Sep 2004 08:30:10 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id IAA00092 for ; Sat, 4 Sep 2004 08:30:09 +0200 (MET DST) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i846U6jn027065 for ; Sat, 4 Sep 2004 08:30:08 +0200 Received: from [192.168.1.200] (ppp192-107.lns1.syd2.internode.on.net [203.122.192.107]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i846U14Y095257 for ; Sat, 4 Sep 2004 16:00:05 +0930 (CST) Subject: [Caml-list] laziness From: skaller Reply-To: skaller@users.sourceforge.net To: caml-list@pauillac.inria.fr Content-Type: text/plain Message-Id: <1094279400.3352.240.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 04 Sep 2004 16:30:00 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 413960EE.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; sourceforge:01 fiddling:01 inlined:01 inlining:01 eagerly:01 avoids:01 haskell:01 immutable:01 inlining:01 quirks:01 9660:01 glebe:01 compiler:01 semantics:01 evaluates:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Since I've been fiddling with various optimisations in my own compiler, I've become quite curious about laziness and its relation to both performance and semantic guarrantees. As motivation consider: let f c a b = if c then a else b As I understand it Ocaml will handle a call f c' a' b' 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. [As I understand it, inlining is substitution aka normal order evaluation for lambda terms; that is, a lazy evaluation strategy.] In particular my 'impression' that ocaml evaluates function arguments eagerly would be wrong. It seems that procedural code (which includes functional expressions) is actually a way to specify evaluation order and timing and typically control flow is used to delay evaluation -- so that procedural programming is actually quite lazy. OTOH procedural languages (including Ocaml) also allow early evaluation. >>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. 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 .. ) There seems to be some kind of sliding scale like this for functional code: C/C++ --> sequence points (functions have side effects) Ocaml --> looser assurances Felix --> no side effects but not fully parametric Haskell --> everything is lazy, immutable, and parametric So I have two questions: (1) exactly what does Ocaml guarrantee? (2) what kind of performance and semantic tradeoffs are involved with perturbations on these assurances? What I'm actually finding at the moment with Felix is that my optimisation efforts, mainly inlining, are actually 'lazifying' code, and thus involve a change in semantics -- although Felix functions can't have side effects, there are also procedures which can, and functions may depend on variables which procedures modify, so that in general the result of a function does depend on when it is executed. This effect is also available in Ocaml via references. I used to think the difference between lazy and eager evaluation were minor quirks -- I'm tending to think now the difference is quite fundamental, eg a purely functional language is necessarily lazy, because lazy evaluation is mandatory -- an eager evaluation strategy *requires* procedural constructions to provide the laziness, and so can't work with a purely functional language. Any comments would be appreciated. -- John Skaller, mailto:skaller@users.sf.net voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ------------------- 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