Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!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: 30 Jul 90 08:16:27 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> <1539@sys.uea.ac.uk> Sender: news@sics.se Organization: The Royal Inst. of Technology (KTH), Stockholm, Sweden. Lines: 53 In-Reply-To: jrk@sys.uea.ac.uk's message of 30 May 90 14:20:25 GMT In article <1539@sys.uea.ac.uk> jrk@sys.uea.ac.uk (Richard Kennaway) writes: 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. Right. But there must be cases where some argument to a non-strict function has to be evaluated in order to determine what is to be done next, even in a lazy language. In all languages I've seen, lazy or not, this is done on a left to right basis. 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. Which is something that irritates me: that a function should change its semantics just because its arguments in the definition are written down in a different order (while the rest of the definition is the same). I guess this is hard to get around, though: in order to get reasonable simple evaluation rules some order must be chosen. 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. So Miranda then goes a little further than left to right: it checks for patterns that can be matched before evaluation takes place. This requires knowledge about the arguments: For the example function f above, I suppose that the evaluation of a more general term (f loop y) would not terminate even if y should happen to evaluate to 0. An even more general strategy than pattern matching would perhaps then try to do some transformation of y before the call, in order to see if it is equal to 0 so that the first rule can be applied. The most general transformation would of course be to evaluate y, but then termination is not guaranteed. Bjorn Lisper