The future of Haskell discussion

[kahl@heraklit.informatik.unibw-muenchen.de]

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-html/decls.html#sect4.4.3

in conjunction with the pattern matching semantics, section 3.17.

http://research.microsoft.com/~simonpj/haskell98-revised/haskell98-report-html/exps.html#pattern-matching


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-html/exps.html#sect3.17.2

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