Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl> asks:

12 Sep 2001 12:37:25 -0000, kahl@heraklit.informatik.unibw-muenchen.de <kahl@heraklit.informatik.unibw-muenchen.de> pisze:

...

* Currently HOPS implements only one evaluation strategy, namely leftmost outermost graph rewriting with sharing preservation (without automatic sharing maximisation). With the standard rules in place, this corresponds to the original definition of lazy evaluation (also known as the ``D-rule''), which is different from the lazy pattern matching evaluation of sequential Haskell implementations.

What is the difference?

If you have f x [] = 0 f x (y:ys) = 1 + f x ys bot = bot and consider the redex f bot (enumFromTo 1 2) then leftmost outermost rewriting (sharing is irrelevant here) diverges: f bot (enumFromTo 1 2) -> f bot (enumFromTo 1 2) -> ... while the ``functional strategy'' finds out that the second argument needs to be evaluated first, and terminates: f bot (enumFromTo 1 2) -> f bot (1 : enumFromTo 2 2) -> 1 + f x (enumFromTo 2 2) -> 1 + f x (2 : enumFromTo 3 2) -> 1 + (1 + f x (enumFromTo 3 2)) -> 1 + (1 + f x []) -> 1 + (1 + 0) -> 1 + 1 -> 2 For a definition of the functional rewriting strategy see for example p. 139f in: @Book{Plasmeijer-vanEekelen-1993, author = {Rinus Plasmeijer and van Eekelen, Marko}, title = {Functional Programming and Parallel Graph Rewriting}, publisher = {Addison-Wesley}, year = 1993, series = {International Computer Science Series}, ISBN = {0-201-41663-8} } The fact that Haskell uses the functional strategy should also follow from the translation for function bindings given in the Haskell report, section 4.4.3 http://research.microsoft.com/~simonpj/haskell98-revised/haskell98-report-ht... in conjunction with the pattern matching semantics, section 3.17. http://research.microsoft.com/~simonpj/haskell98-revised/haskell98-report-ht... However, I already have troubles with the first sentence of 3.17.2 ``Informal Semantics of Pattern Matching'': http://research.microsoft.com/~simonpj/haskell98-revised/haskell98-report-ht... which says: ``Patterns are matched against values.'': Variables are patterns, and in the above example, the variable x is matched against the non-value bot --- if my understanding of values is correct. (Also, the direction of ``matching against'' in this sentence is contrary to that used in most of the explanations that follow after it.) For the examples section of 3.17.2, perhaps one might add an example under item 1. that illustrates this effect: | If (x,'b') is matched against (_|_,'b'), | the match succeeds and binds x to _|_. Wolfram