Path: utzoo!attcan!uunet!mcsun!ukc!sys.uea!jrk From: jrk@sys.uea.ac.uk (Richard Kennaway) Newsgroups: comp.lang.functional Subject: Re: Laziness and Back-to-front Lists Message-ID: <1539@sys.uea.ac.uk> Date: 30 May 90 14:20:25 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> Organization: UEA, Norwich, UK Lines: 73 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 Perhaps I can clear up some of the confusion in this thread. Laziness has nothing to do with currying. There is no reason why order of arguments should be any more significant in a curried language than in an uncurried one. The lack of laziness apparent in the supposedly lazy functional languages also has nothing to do with currying. They impose a particular evaluation strategy based on textual order, but only because it simplifies the implementation. It is not required by laziness; on the contrary, it loses some laziness (and is therefore a Bad Thing :-)). The fact that leftmost-outermost reduction works for the lambda calculus (in the sense that this strategy will find the normal form of any lambda expression which has one) is an uninteresting quirk of its usual concrete syntax. Write all your applications in reverse order, and rightmost-outermost becomes the preferred strategy. The "sequentiality" possessed by lambda calculus and certain term rewrite systems has nothing to do with left-to-right pattern matching. Left-to-right pattern matching does not imply that arguments to functions are evaluated from left to right, but that matching against rules is attempted from left to right, evaluation of arguments only being triggered when the matcher attempts to match a constructor symbol in a rule against an unevaluated subterm. For example, take the following Miranda rules: f x 0 = 0 loop = loop Miranda will use these rules to evaluate the term (f loop 0) to 0, without attempting to evaluate the first argument to f, because the rule for f does not need to know the value of that argument. (The Miranda syntax is a little confusing: in the above rules, "f" and "loop" are function symbols, but "x" is a variable.) -- Richard Kennaway SYS, University of East Anglia, Norwich, U.K. Internet: jrk@sys.uea.ac.uk uucp: ...mcvax!ukc!uea-sys!jrk