Path: utzoo!attcan!uunet!cs.utexas.edu!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!sics.se!sics!bjornl From: bjornl@tds.kth.se (Bj|rn Lisper) Newsgroups: comp.lang.functional Subject: Re: Laziness and Back-to-front Lists Message-ID: Date: 28 Jul 90 08:08:43 GMT 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> <1990May29.234840.29162@comp.vuw.ac.nz> Sender: news@sics.se Organization: The Royal Inst. of Technology (KTH), Stockholm, Sweden. Lines: 81 In-Reply-To: brian@comp.vuw.ac.nz's message of 29 May 90 23:48:40 GMT In article <1990May29.234840.29162@comp.vuw.ac.nz> brian@comp.vuw.ac.nz (Brian Boutel) writes: > I (Bjorn Lisper) wrote: %> 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. %I think there is a misunderstanding here. %There is no need to *evaluate* the argument of a curried function before %you need its value. Oops, I never claimed this. What I meant to say was that there is an imposed order for arguments whenever the value of the function call itself is needed. (Unless you know that the function is strict in some arguments, of course, in which case you can safely evaluate those in any order.) %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. Doesn't it? Unless you know that f is strict, I'd say that whenever the value of f x y is needed, f x must be evaluated first and then, if needed, (f x) y. All this assuming that we want to follow the semantics given by lambda calculus (which imposes this order). (Please correct me if I'm wrong. I'm not a lambda calculus expert.) %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. But in some sense, a conditional is a function. To call some functions conditionals is a way to hide the basic "problem". For instance, if(b,x,y) defined by b => if(b,x,y) = x not b => if(b,x,y) = y is a (non-strict) function in three arguments. Left-to-right lazy evaulation will give the ordinary "conditional" semantics. As I pointed out, there are cases where other evaluation orders terminate whereas this doesn't. %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. Of course. A more interesting example is multiplication, that strictly speaking (sic!) is non-strict, since whenever one argument returns zero the other argument is not needed. if f(x) is non-terminating, then 0*f(x) still terminates (and returns zero) if '*' is treated as a non-strict function with left-to-right evaluation order. Is '*' usually implemented as a strict or as a non-strict operator in lazy functional languages? %The issue of the order in which cases and arguments are checked in %pattern matching is different. ... % ...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. Oh, I've never rejected lazy evaluation. I've just tried to point out that there are cases where "usual" lazy evaluation does not terminate but other evaluation orders do. So any claim that lazy evaluation is the "best" kind of evaluation must draw its support from other arguments than superior termination properties or "purity". I can for instance buy your "easy to understand" argument above. (Since I use the latin alphabet, so I naturally read from left to right.... :^)) Bjorn Lisper