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 DAA30740; Sun, 5 Sep 2004 03:07:54 +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 DAA30966 for ; Sun, 5 Sep 2004 03:07:53 +0200 (MET DST) Received: from cantvc.canterbury.ac.nz (cantvc.canterbury.ac.nz [132.181.2.36]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8517p5B030096 for ; Sun, 5 Sep 2004 03:07:52 +0200 Received: from CONVERSION-A1.it.canterbury.ac.nz by it.canterbury.ac.nz (PMDF V6.2-X27 #30791) id <01LEICG1ISR4DR4GLE@it.canterbury.ac.nz> for caml-list@pauillac.inria.fr; Sun, 05 Sep 2004 13:07:48 +1200 (NEW ZEALAND STANDARD TIME) Received: from webmail (cantwm.giga.canterbury.ac.nz [132.181.2.26]) by it.canterbury.ac.nz (PMDF V6.2-X27 #30791) with ESMTP id <01LEICG1G1VEDR3TBA@it.canterbury.ac.nz>; Sun, 05 Sep 2004 13:07:48 +1200 (NEW ZEALAND STANDARD TIME) Date: Sun, 05 Sep 2004 13:07:48 +1200 From: Jason Smith Subject: RE: [Caml-list] laziness To: caml-list , skaller@users.sourceforge.net Message-id: <413879B6@webmail> MIME-version: 1.0 X-Mailer: WebMail (Hydra) SMTP v3.61 Content-type: text/plain; charset=ISO-8859-1 Content-transfer-encoding: 7bit X-WebMail-UserID: jns28 X-EXP32-SerialNo: 00002797 X-Miltered: at nez-perce with ID 413A66E7.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; jns:99 canterbury:99 caml-list:01 inlined:01 conforms:01 unspecified:01 inlining:01 inlining:01 applicative:01 strictness:01 thunk:01 thunk:01 compiler:01 semantics:01 semantics:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk >> > However if the call is *inlined* to get >> > >> > if c' then a' else b' >> > >> > then perhaps a' or b' will never be evaluated. >I understand that argument -- but that doesn't mean the >compiler conforms to the specification, nor that the >specification is best. I'm not sure about OCaml but in GHC we could garuentee that the arguments a' and b' would be reduced using the 'case' syntax in GHC's intermediate language "Core". This the code would become something like this: case c' of { c'' -> case a' of { a'' -> case b' of { b'' -> if c'' then a'' else b''; } } } case forces evaluation to WHNF form, thereby garuenteeing correct eager order evalation. I presume O'Caml would do the same to keep side-effects evaluting correctly. >> E.g. the order of evaluation of arguments is >> unspecified, so it might be different depending on inlining; but >> OCaml does specify that each argument are evaluated exactly once >> and inlining doesn't change that. > >Must they be evaluated before the function is called? If O'Caml follows the usual eager order semantics then evaluation is AOR or Applicative order redection. (Which is what I use in Mondrian). There are several locations where we may attempt to reduce this overhead. Strictness analysis: Determines usuing some form of abstract reduction semantics weather the argument is "strict" in the function, i.e. that it will be used at all. If it isn't then there is no need to reduce it. The problem with this is that in O'Caml u once again have side-effect's raise there ugly head. This means that even if the argument is not used in the function, the results of evaluating the argument which uses side-effects is. So you may have to analyse the argument itself and see if it uses any reference semantics. Usage analysis: Determines "how many times" an argument is used. Not so much applicable to eager order evaluation but very handy in lazy languages. We can save the cost of a THUNK update by determining if we actually need to update the thunk with the new value once the argument has been reduced. There are a range of other analysis techniques that "increase the degree of laziness" aka full-laziness transformation, reduce the cost of creating intermediate data structures aka deforestation, let-floating etc.. refer to a great body of literature for comments on these area's. HTH Jason. ------------------- 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