The dreaded M-R

[Ross Paterson]

On Thu, Jan 26, 2006 at 10:59:22AM +0100, John Hughes wrote:
> The fact is, Haskell has two different binding mechanisms--bind-by-name
> (used for overloaded definitions), and bind-by-need (monomorphic). Both
> are useful: bind-by-name lets us name overloaded expressions, while
> bind-by-need gives performance guarantees. The trouble is just the way
> we distinguish them--where the compiler is basically guessing from the
> form of a definition which one to use.
> [...]
> The solution I favour is simply to use *different syntax* for the two
> forms of binding, so that a definition is monomorphic, and computed
> at most once, if it uses the monomorphic binding operator, and
> polymorphic/overloaded, computed at each use, if it uses the other.
> Whether it's a function definition or not is irrelevant, as is whether
> or not it carries a type signature.
> 
> The trick is finding good syntax. I suggest = for bind-by-name, and
> := for bind-by-need. (Some object that := "means" assignment--but come
> on, we're not reserving := for future use as assignment in Haskell, are we?
> Why should we give up a perfectly good symbol because it's used elsewhere
> to mean something else?). With this notation, = would be appropriate
> for function definitions, and := for most non-function definitions. It
> would be instantly clear where there was a possibility of repeated
> evaluation, and where not.
> 
> The problem with making such a syntactic distinction is that, however
> it's done, many changes must be made to existing programs. Just because
> existing programs contain many bindings of each sort, there's no
> getting away from the fact that a syntactic distinction will force
> changes. In principle this could be automated, of course--not hard
> but somebody would have to do it. But perhaps it would be worth it,
> to eliminate probably the number one wart, and solve the problems
> above.

You're proposing that the =/:= distinction both decides whether
constrained type variables are monomorphic and whether the binding
should be implemented using sharing.  If it only did the former (and the
expectation was that all pattern bindings with unconstrained types used
sharing), then existing legal programs would still be legal, and the
examples that currently trip over the MR would be legal but inefficient.
(Also, what does the shared/unshared distinction mean for functions?)

What if one has mutually recursive bindings, some using = and some := ?
Does monomorphism kick in if some of the variables in a binding group
use :=, or would we just require that all bindings in the same group
use the same binder?  (At first I couldn't see why one would ever use :=
with function bindings, but perhaps that's the reason.)