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 nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id E8547BC29 for ; Sat, 5 Aug 2006 03:19:26 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k751JP5L014347 for ; Sat, 5 Aug 2006 03:19:26 +0200 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 DAA25694 for ; Sat, 5 Aug 2006 03:19:25 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k751JNRq022201 for ; Sat, 5 Aug 2006 03:19:24 +0200 Received: from rosella (ppp30-178.lns1.syd6.internode.on.net [59.167.30.178]) by smtp3.adl2.internode.on.net (8.13.6/8.13.5) with ESMTP id k751JD7E091427; Sat, 5 Aug 2006 10:49:14 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: [Caml-list] strict? From: skaller To: Alan Falloon Cc: caml-list@inria.fr, Alexander Bottema In-Reply-To: <44D38C06.5060602@synopsys.com> References: <1154638579.5206.50.camel@rosella.wigram> <44D38C06.5060602@synopsys.com> Content-Type: text/plain Date: Sat, 05 Aug 2006 11:19:13 +1000 Message-Id: <1154740753.5926.121.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 44D3F21E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 44D3F21B.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; citeseer:01 citeseer:01 lambda:01 compiler:01 bug:01 ocaml:01 compiler:01 optimising:01 val:01 'val:01 val:01 'as:01 conversely:01 'let: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.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Fri, 2006-08-04 at 14:03 -0400, Alan Falloon wrote: > skaller wrote: > > It sounds like you are talking about "lenient" evaluation. I was looking > into this stuff a while ago. As far as I can tell, there aren't many > papers out there about it, but this one is pretty good: > http://www.cs.cmu.edu/~seth/lenient.pdf. > > The citeseer page might get you some more info > http://citeseer.ist.psu.edu/schauser95how.html I had a read of some of that, but it isn't clear to me whether my 'sloppy' evaluation is the same as 'lenient'. As I understand it, lambda calculus has a few possible orders of applying reductions, which are the evaluation strategies. 'Lenient' evaluation looks like just another determinate order, whereas 'sloppy' means the order is indeterminate (but I'm sure I didn't understand the paper!) However what I'm aiming for is to provide both lazy and eager evaluation, and let the programmer specify which to do on a 'case by case' basis .. as well as provide for 'default' cases whether the compiler makes the choice. I'm trying to wrap my brain around the ideas so I can understand the right constructions .. perhaps another way of saying this is: when something gets evaluated at the wrong time, when it is a design bug in my system, and when can I just blame the programmer for not being specific enough about their intent? In Ocaml, for example, it is the programmers fault if side effects in f e1 e2 e3 don't happen in the expected order: the manual says the order of evaluation is indeterminate AND there is a way to force the order: let a1 = e1 in let a2 = e2 in let a3 = e3 in f a1 a2 a3 To turn that around, if you want the compiler to try to do a good job optimising, you give it freedom and write f e1 e2 e3 when e1,e2,e3 *dont* have side effects. This has the downside you can't factor complex expressions .. so in Felix: var a1 = e1; // note 'var=variable' var a1 = e2; var a3 = e3; return f a1 a2 a3; forces eager evaluation, but perhaps you could write val a1 = e1; // note 'val=value' val a2 = e2; val a3 = e3; return f a1 a2 a3; and it doesn't. The compiler is free to substitute the values to which a1,a2,a3 are bound for occurrences of a1,a2,a3 respectively (this is just illustration). Of course even in the 'eagerly strict' case, the compiler can use the 'as if' rule to perform optimisations based on analysis. And, conversely, in the sloppy case the compiler can also perform the analysis and warn in some cases that behaviour is indeterminate. The difference is when the compiler's analysis is incomplete, what assumptions it makes in the two cases. (Also add 'lazy' option, which I think I'll encode 'fun a1 => e1 ..') So basically most languages provide constructions with explicit evaluation orders, but not very many 'let the compiler chose' constructions: order of argument evaluation is one in Ocaml. For inlining functions, the 'sloppy' case allows usage analysis followed by a choice of substitution where used (lazy evaluation) or eager evaluation (to save recomputations). Substitution is particularly efficient in some cases because it helps eliminate closures. So I want the programmer to use 'val'ues where possible .. and the question arises, what exactly does 'where possible' mean? The only way to reason in the presence of indeterminate evaluation order is when it makes no difference. So the question is -- exactly when doesn't it matter? -- John Skaller Felix, successor to C++: http://felix.sf.net