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 EE203BB84 for ; Thu, 3 Aug 2006 22:56:31 +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 k73KuVnR009107 for ; Thu, 3 Aug 2006 22:56:31 +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 WAA06041 for ; Thu, 3 Aug 2006 22:56:30 +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.6/8.13.6) with ESMTP id k73KuSkL031764 for ; Thu, 3 Aug 2006 22:56:29 +0200 Received: from rosella (ppp30-178.lns1.syd6.internode.on.net [59.167.30.178]) by smtp1.adl2.internode.on.net (8.13.6/8.13.5) with ESMTP id k73KuJpO071116; Fri, 4 Aug 2006 06:26:20 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: RE: [Caml-list] strict? From: skaller To: Alexander Bottema Cc: caml-list@inria.fr In-Reply-To: References: Content-Type: text/plain Date: Fri, 04 Aug 2006 06:56:19 +1000 Message-Id: <1154638579.5206.50.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 44D262FF.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 44D262FC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; ocaml:01 mutable:01 semantics:01 compiler:01 inlined:01 inlining:01 ocaml:01 haskell:01 encodes:01 compiler:01 hof:01 2006:98 compilers:01 wrote:01 sourceforge: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 Thu, 2006-08-03 at 08:29 +0100, Alexander Bottema wrote: > When writing real compilers, strictness is not that interesting. What we > focus on is whether a function is side-effect free or program-effect > free. In Felix, procedures have side effects, and functions don't (they're both 'functions' in the C programming sense which is a bit confusing) However, a function can contain variables and modify them. In Ocaml, you can have a function with no side effects too, but which contains variables: let f () = let a = ref 0 in let g () = !a in let b = g () in a := 1; let c = g() in b + c Here 'a' is a mutable variable, however f doesn't have side effects. What's more the evaluation semantics for g() are critical because it depends on a variable. Clearly, we can't evaluate lazily or we get the 'wrong' answer: g() +g() would return 2 instead of 1. > We then allow certain transformations based on whether functions are > side-effect free or program-effect free. You can probably imagine other > categories as well. After all, it is what kind of > optimizations/transformations that you'd like to do that gives your > domain of parameters to control them. Indeed, but that's the question. Generally I want the compiler to chose whether to inline a function or not, and how to inline arguments into the inlined function. For simple functions lazy evaluation often yields faster code, because inlining basically flattens the code into primitives. However, sometimes the programmer expects eager evaluation and sometime lazy. Lazy is mandatory for most imperative control structures: if/then/else, match, loops, etc. Eager is mandatory when some calculation depends on a variable: you can defer calculation only up to the point the variable is modified. OTOH, sometimes lazy is expensive, particularly when you cannot inline, because then you have to pass a closure. Some languages define application as eager (Ocaml) and some lazy (Haskell) but Felix does both and neither :) The basic idea is some things are eager, some lazy, but most are 'up to the compiler'. So actually, three significant factors seem to exist: side effects or not, dependence on a variable or not, and finally whether the function is strict. > When I learned the concept of strictness it was in the context of pure > functional programming. For me the definition was mostly there to > distinguish non-strict functions, such as if(e,t,f) from other > functions. My understanding is you can evaluate strict functions eagerly, because the function is 'defined' to 'crash' if evaluation of one of its arguments does. As you say, if(e,t,f) isn't strict: e can be evaluated eagerly, but t and f must be evaluated lazily. But this is already somewhat confusing .. the 'function' actually has one argument, a tuple of three components. It's neither strict nor non-strict.. its strict in the first projection, but not the second and third. > Bottom encodes essentially two different things, > non-termination or "domain error". The non-termination aspect is crucial > for non-strict functions such as if, since the non-termination of 't' or > 'f' may not imply that if() itself will not terminate. However, in real > compiler design, the number of non-strict functions is very small and > usually built-ins. A real compiler for what? I think many HOF are non-strict, when they're control structures -- such as if/then/else. > However, this is of course not true if you implement > lazy functional programming languages where basically everything is > non-strict. I suspect many functions are still strict .. giving you a choice of when to evaluate. However the default is lazy evaluation (hence 'strictness analysis' to determine when it is equivalent to evaluate more eagerly). But in a procedural language .. well things seem more complex :) -- John Skaller Felix, successor to C++: http://felix.sf.net