Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!ucbvax!bloom-beacon!eru!luth!sunic!mcsun!ukc!edcastle!aipdc From: aipdc@castle.ed.ac.uk (Paul D. Crowley) Newsgroups: comp.lang.functional Subject: Re: Laziness and Back-to-front Lists Message-ID: <4356@castle.ed.ac.uk> Date: 30 May 90 12:17:15 GMT Reply-To: aipdc@castle.ed.ac.uk (Paul D. Crowley) Organization: Edinburgh University Computing Service Lines: 83 Article: 120 of comp.lang.functional Path: edcastle!ukc!mcsun!sunic!sics.se!sics!bjornl From: Newsgroups: comp.lang.functional 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 bjornl@tds.kth.se (Bj|rn Lisper) sez in /In article <1990May29.234840.29162@comp.vuw.ac.nz> brian@comp.vuw.ac.nz \(Brian Boutel) writes: /%> (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. As far as I can see, the only kind of laziness that lambda-calculus is open to is a curried function which says "Ignore the argument: the answer is ...". If such a function is produced the argument need not be evaluated. /%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. The kind of laziness I was talking about above applies particularly well to if - you can use it to produce a version of if which only evaluates the appropriate half. I can't see any way of implementing breadth-first evaluation of the kind that would cope with (((if forever) x) x) using lambda-calculus notions. Of course, what would solve all this would be a program that tests whether an expression halts... :-) -- \/ o\ Paul Crowley aipdc@uk.ac.ed.castle /\__/ "Trust me, I know what I'm doing" - Sledge Hammer