Implict parameters and monomorphism

[John Hughes]

	(B) Monomorphism restriction "wins"
	    Bindings that fall under the monomorphism restriction can't
		be generalised
	    Always generalise over implicit parameters *except* for bindings
		that fall under the monomorphism restriction

	    Consequences
		* Inlining isn't valid in general
		* No unexpected loss of sharing
		* Simple bindings like
			z = ?y + 1
		  accepted (get value of ?y from binding site)
	
	(C) Always generalise over implicit parameters
	    Bindings that fall under the monomorphism restriction can't
		be generalised, EXCEPT for implicit parameters
	    
	    Consequences
		* Inlining remains valid
		* Unexpected loss of sharing (from the extra generalisation)
		* Simple bindings like
			z = ?y + 1
		  accepted (get value of ?y from occurrence sites)


	Discussion
	~~~~~~~~~~
	None of these choices seems very satisfactory.  But at least we should
	decide which we want to do.

	It's really not clear what is the Right Thing To Do.  If you see

		z = (x::Int) + ?y

	would you expect the value of ?y to be got from the *occurrence sites*
	of 'z', or from the valuue of ?y at the *definition* of 'z'?  In the
	case of function definitions, the answer is clearly the former, but
	less so in the case of non-fucntion definitions.   On the other hand,
	if we say that we get the value of ?y from the definition site of 'z',
	then inlining 'z' might change the semantics of the program.

	Choice (C) really says "the monomorphism restriction doesn't apply
	to implicit parameters".  Which is fine, but remember that every 
	innocent binding 'x = ...' that mentions an implicit parameter in
	the RHS becomes a *function* of that parameter, called at each
	use of 'x'.  Now, the chances are that there are no intervening 'with'
	clauses that bind ?y, so a decent compiler should common up all 
	those function calls.  So I think I strongly favour (C).  Indeed,
	one could make a similar argument for abolishing the monomorphism
	restriction altogether.

I disagree.

I think it's important to have a simple model of how many times expressions
are evaluated. Function bodies are clearly evaluated many times, once for each
call, but non-function bindings should be evaluated at most once to respect
call-by-need semantics. Breaking the monomorphism restriction in ANY case
makes both space and time cost of evaluation unpredictable, and brittle when
program changes elsewhere introduce or remove an implicit parameter. It isn't
good enough to say `the chances are' that a program has, for example, linear
time and constant space complexity: the programmer should be able to convince
himself of such properties.

As far as what one would `expect', it's in the very nature of dynamic binding
that it makes the meaning of an expression depend on its context. I for one
would certainly not expect that inlining a definition bound to such an 
expression should preserve its meaning! Inlining changes the context, so
`of course' can change the meaning. So I strongly prefer (B)!

John Hughes