The dreaded M-R

[John Meacham]

On Sat, Jan 28, 2006 at 03:41:53PM -0500, Cale Gibbard wrote:
> Is it really so impossible to implement typeclasses in a way which
> avoids this problem altogether? Perhaps the need for the MR in the
> first place is simply an indication that dictionary passing is not a
> complete solution to implementing typeclasses. It seems quite
> plausible that there should be an implementation which preserves
> polymorphism, and yet doesn't result in horrific inefficiency. Do we
> have a proof (or at least strong evidence) that such a thing can't
> exist?

interestingly enough, the monomorphism restriction in jhc actually
should apply to all polymorphic values, independently of the type class
system.

x :: a 
x = x 

will transform into something that takes a type parameter and is hence
not shared. I doubt this will cause a problem in practice since there
arn't really any useful values of type forall a . a other than bottom.
type classes don't introduce anything new at runtime that normal
polymorphism didn't already require.


An optimization that jhc implements which should be portable to other
compilers is the 'type analysis' pass. it does a fixpoint iteration to
determine every possible type every polymorhpic value is called at and
then goes through and specializes all that are called at exactly one
type, which is a surprisingly large amount. This is tied to the
monomorphism restriction in that given foo :: Num a . a which is only
used as an Int, should I turn it into a caf or give it a phantom
argument to prevent sharing? I have not made up my mind on the issue...


it would also be possible to require the compiler 'memoize' all top
level bindings on their type parameter. then the problem goes away, but
at the cost of hiding some machinery under the hood. however the type
analysis pass mentioned above would often be able to discard of this
'under the hood' memoization and.


        John


-- 
John Meacham - ⑆repetae.net⑆john⑈