Re: monomorphic pattern binding

["Prof. John Hughes" <rjmh@cs.glasgow.ac.uk>]

Original-Via: uk.ac.nsf; Fri, 7 Sep 90 18:58:06 BST
From: "Prof. John Hughes" <rjmh@cs.glasgow.ac.uk>
Date: Fri, 7 Sep 90 14:27:40 BST
To: haskell@cs.yale.edu
Subject: Re: monomorphic pattern binding
Original-Sender: rjmh%uk.ac.glasgow.cs@yale.edu
Sender: haskell-request@cs.glasgow.ac.uk

John Peterson writes:

	Amir Kishon & I are trying to start a crusade against the `pattern
	binding law'.

I don't think anyone on the committee would claim that the pattern-binding
rule was anything other than the best of a bad lot, and indeed this was
quite a controversial issue. Since I favoured the rule, let me have a go
at defending it.

First let's be clear about what the rule says. To quote:

  "Variables not bound directly to a lambda abstraction may be
  polymorphic and overloaded, but must also obey the rule: variables not
  bound directly to lambda abstractions must not be used at more than
  one distinct overloading."

The restriction applies only to overloading. Pattern bindings in
Haskell can still be polymorphic, but they cannot be overloaded. So
it's quite OK to define, say,

	reverse = foldr snoc [] where snoc x xs = xs++[x]

and the function so defined is polymorphic. What is NOT OK is to define,
say,

	x = fac 6

and then use x both as an Int and an Integer. Sorry if I'm teaching
grandmothers to suck eggs. I'm labouring the point because John
Peterson often says monomorphic when he means non-overloaded, and I
want to make sure we are not confusing the two.

In particular, any program which does not make use of overloading should
type-check in Haskell if its translation would type-check in ML.
Polymorphic functions are therefore no more second class citizens in
Haskell than they are in ML, although overloaded functions are distinctly
second class in Haskell. Moreover, since the transformation that
introduces dictionary parameters into a Haskell program also eliminates
overloading, resulting declarations of the form "dict = (f1,f2,f3...)"
are unaffected by the pattern-binding rule.

Certainly the pattern-binding rule is a wart which adds to the conceptual
burden on the programmer and makes some transformations invalid. But 
without it, Haskell would suffer from what I regard as an infinitely more
serious problem. Consider the definition

	f n = (y,y) where y=nfib 20

Without the pattern-binding rule, the two occurrences of y could be at
different overloadings. Since Haskell has no implicit coercions, that
would force the implementation to compute nfib 20 twice. To anyone who
has programmed in any other functional language, this would come as
a complete surprise. Moreover, it's possible to construct programs of
size O(n) in which overloaded bindings are evaluated exponentially
many times. As John Peterson points out, it's possible for the wary programmer
to ensure this doesn't happen by adding appropriate type signatures...
but what about the unwary programmer? Similarly, one can imagine
optimising compilers which avoid unexpected recomputation in the majority
of cases...but the committee could not see how to GUARANTEE that
recomputation would never happen.

John Peterson says in conclusion:

	As a final note, we believe that the efficiency we gain by the pattern
	binding typing law is far less substantial than the eventual
	complications to Haskell.  As we understand, this law came up mainly
	to solve efficiency problems.

But the pattern binding rule is NOT there to improve efficiency, although
of course it does. It's there so that Haskell programs have a predictable
time and space complexity. Without it, slight changes such as modifying
an implementation of sets to use equality tests internally (thus making
more functions overloaded) could dramatically affect the complexity -- not
just efficiency -- of distant parts of the program. Such obscure
behaviour would be a trap even for the wary.

In my view, a programming language in which you cannot predict the
complexity of your programs is a disaster.

John Hughes