🚀 go-pugleaf

In article <BJORNL.90Jul30101627@tarpon.tds.kth.se> 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