Path: utzoo!attcan!uunet!mcsun!ukc!sys.uea!jrk From: jrk@sys.uea.ac.uk (Richard Kennaway CMP RA) Newsgroups: comp.lang.functional Subject: Re: Laziness and Back-to-front Lists Message-ID: <1547@sys.uea.ac.uk> Date: 1 Jun 90 16:49:29 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> Organization: UEA, Norwich, UK Lines: 91 In article bjornl@tds.kth.se (Bj|rn Lisper) writes: ... >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. Yes, it's easy to implement, and it lets you write "everything else" rules just by putting them last, e.g. fac 0 = 1 fac x = x * (fac (x-1)) Which is why it's nearly always done that way. The only exception I know is Hope+, which is still left-to-right within each rule, but orders different rules by specificity. That is, pattern-matching is always attempted with the most specific possible rule, regardless of tedtual order. E.g. in the above example, translated into Hope+, you could write the two rules in either order and they would behave in the same way. But it irritates me as well. It seems just as reasonable (with respect to understandability by people rather than machines) to write default rules first, followed by all the exceptions; and if I have a function of 12 arguments, I want to give those arguments in an order meaningful to me, rather than use that ordering to control the evaluation order. >In article <1539@sys.uea.ac.uk> jrk@sys.uea.ac.uk (Richard Kennaway) writes: ... > 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. No, for example (f loop (1-1)) would also evaluate to 0. The pattern- matcher looks at the first argument of the rule for f, finds that it doesnt need to know anything about it, looks at the second argument in the rule (0), and sees that it must evaluate the second argument of the given term (1-1), does so, finds the term now matches, and applies the rule. >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. As described above, that's exactly what Miranda, and all the other lazy functional languages do. >The most general >transformation would of course be to evaluate y, but then termination is not >guaranteed. It's guaranteed more than I suspect you think. Consider the following example: f x Nil = 0 f x (Cons y x) = 1 tail (Cons u v) = v (where Nil and Cons are the usual list constructors - Miranda actually has these built-in, but I forget what it calls them.) Now consider evaluating the term: f loop (tail (Cons loop (Cons loop loop))) This will be evaluated to 1. As before, the pattern-matcher skips the first argument, and sees that it must do some evaluation of the second. It applies the 'tail' rule, giving f loop (Cons loop loop) which matches the second f rule. None of the 'loop' subterms are ever evaluated. >Bjorn Lisper -- Richard Kennaway SYS, University of East Anglia, Norwich, U.K. Internet: jrk@sys.uea.ac.uk uucp: ...mcvax!ukc!uea-sys!jrk