Path: utzoo!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!uunet!comp.vuw.ac.nz!brian From: brian@comp.vuw.ac.nz (Brian Boutel) Newsgroups: comp.lang.functional Subject: Re: Laziness and Back-to-front Lists Message-ID: <1990May29.234840.29162@comp.vuw.ac.nz> Date: 29 May 90 23:48:40 GMT Article-I.D.: comp.1990May29.234840.29162 References: <14531@dime.cs.umass.edu> <2535@skye.ed.ac.uk> <8691@cs.utexas.edu> <4170@castle.ed.ac.uk> <3738@moondance.cs.uq.oz.au> <4289@castle.ed.ac.uk> Sender: news@comp.vuw.ac.nz (News Admin) Reply-To: brian@comp.vuw.ac.nz (Brian Boutel) Organization: Dept. of Comp. Sci., Victoria Uni. of Wellington, New Zealand. Lines: 86 In article , bjornl@tds.kth.se (Bj|rn Lisper) writes: > In article <4289@castle.ed.ac.uk> aipdc@castle.ed.ac.uk (Paul D. Crowley) > writes: > %WARNING: Uninformed opinions ahead! > > %I was under the impression that in a truly "pure" functional language > %the problem doesn't arise because nothing has more than one argument. > %Things that look as if they should have more than one argument are dealt > %with lambda-calculus style: > > %2+3: ((plus 2) 3) > %(plus 2) means plus applied to two, and equals a function which adds two > %to its argument. > > %so ((plus 2) 3) = (plus2 3) = 5 > > %Under these circumstances you _expect_ order of arguments to be > %significant, so it doesn't surprise you that you get different results > %if you change it. > > Yes, this is exactly the "problem" with lazy functional languages as I see > it: they rely on a serial evaluation order of arguments obtained from the > currying of functions in order to get unary functions only, as in lambda > calculus. HOWEVER, this ordering is an imposed, arbitrary one. As I > understand it this is inherent in the lambda calculus itself. So, there's a > problem with the very theoretical foundations of functional programming! > > My last comment is deliberately provocative. It would be interesting to hear > any comments on it from people more involved in the field than me. > > Bjorn Lisper I think there is a misunderstanding here. There is no need to *evaluate* the argument of a curried function before you need its value. If I define f x y = E, I may be defining f to be a function which takes an argument x and produces a function which takes an argument y etc., but all this implies is that I can use f 3, for example, as a function. It says nothing about the order of evaluation of x and y. In lazy evaluation, evaluation only occurs when a value is needed. Ultimately, this is because it has to be output, but within a program, evaluation is driven by pattern matching (a need to know which case applies), or by a conditional ( a need to know which branch to take) or by a strict primitive function like plus (needs the values of its arguments before it can be applied). In all other cases, arguments are passed to functions without prior evaluation. (Actually, if you do strictness analysis, it may be possible to determine at compile time that a particular argument is always evaluated, and so, to improve efficiency, it can safely be evaluated before being passed to the function.) In plus x y, plus is strict in both its arguments, and they will both be evaluated. The order in which this happens is unimportant. Real implementations do not implement plus as taking one argument and producing a new function, they implement it by using ordinary machine arithmetic, where addition is an operation that adds two values. In f (complex expression), I can still pass this as a functional argument to something without evaluating (complex expression) first. With call-by-need, when (complex expression) is eventually evaluated, it will be replaced by its value, and will not need to be evaluated again. None of this invalidates the semantics of a non-strict language. The issue of the order in which cases and arguments are checked in pattern matching is different. If you are primarily interested in reasoning about programs, you will want all equations in a function definition to be disjoint, so at most one equation can match the actual arguments. In practice this is inconvenient, as you often need a case that matches "everything else" after some special values have been dealt with. If you are interested in writing programs, you want semantics that are easy to understand, and if you can't have a situation where equation sequence and argument order make no difference, at least you will want something obvious like top-to-bottom, left-to-right. Even if this is not totally pure, lazy evaluation with these restrictions is still very useful, and should not be rejected. --brian Internet: brian@comp.vuw.ac.nz Postal: Brian Boutel, Computer Science Dept, Victoria University of Wellington, PO Box 600, Wellington, New Zealand Phone: +64 4 721000 Fax: +64 4 712070