Type classes and code generation

[Andreas Rossberg]

Bayley, Alistair wrote:
> 
> When it's applied, the compiler will know the types of the arguments, won't
> it?. Which means that you would generate a version of double for each
> (applied) instance of Num. I don't doubt that there's a good reason this is
> not done: code bloat? or are there simply some expressions that can't be
> statically resolved?
> 
> I suppose I was thinking: is the language design sufficiently clever that
> it's *always* possible for the compiler to infer the type instance in use,
> or are there some situations where it's not possible to infer the instance,
> so some kind of function dispatch mechanism is necessary?

This almost is an FAQ. Short answer: in general it is impossible to 
determine statically which instances/dictionaries are needed during 
evaluation. Their number may even be infinite. The main reason is that 
Haskell allows polymorphic recursion.

Consider the following (dumb) example:

f :: Eq a => [a] -> Bool
f []     = True
f (x:xs) = x == x && f (map (\x -> [x]) xs)

The number of instances used by f depends on the length of the argument 
list! Determining that statically is of course undecidable. If the list 
is infinite, f will use infinitely many instances (potentially, 
depending on lazy evaluation).

Another (non-Haskell-98) feature that prevents static resolution of type 
class dispatch are existential types, which actually provide the 
equivalent to "real" OO-style dynamic dispatch.

Of course, for most practical programs, the optimization you have in 
mind would be possible. I doubt compilers generally do it globally, 
though, because it requires whole program analysis, i.e. does not 
interfer well with separate compilation (beside other reasons).

| Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
  as kids, we would all be running around in darkened rooms, munching
  magic pills, and listening to repetitive electronic music."
  - Kristian Wilson, Nintendo Inc.