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⑈