Type classes and code generation

[Keith Wansbrough]

Alistair Bayley writes:

>     Warning: Defaulting the following constraint(s) to type `Integer'
> 	     `Num a' arising from the literal `2' at Main.lhs:3
> 
> This implies to me that the compiler is generating the code for (+) for the
> particular instance, rather than using a run-time dispatch mechanism to
> select the correct (+) function. Is this correct, or am I way off?  Does the
> compiler *always* know what the actual instances being used are?

Yes, roughly.  In Haskell, the compiler always figures out the types of 
everything at compile time.  This means it can often figure out which 
bit of code to use at compile time as well - but because of 
polymorphism, not always.  Consider this bit of code:

double :: Num a => a -> a
double x = x + x

The function "double" will work on any type in the class Num, so the 
compiler can't know which "+" function to use.  But it *doesn't* solve 
this by run-time dispatch, like in C++.  Instead, it compiles double 
like this:

double' :: NumDict a -> a -> a
double' d x = let f = plus d
              in x `f` x

where NumDict is a record a bit like this:

data NumDict a = NumDict { plus :: a -> a -> a,
                           minus :: a -> a -> a,
	                   fromInteger :: Integer -> a
	                   ...
                         }

NumDict is called a "dictionary", and any time double' is called, the 
caller must supply the right dictionary.  If you write

double 2.0

then the compiler sees that you've written a Double, and so supplies 
the NumDict Double dictionary:

double' doubleNum 2.0

where doubleNum :: NumDict Double contains the methods for adding 
Doubles, subtracting them, and converting from Integers to them.

Whenever it can, a good optimising compiler (like GHC) will try to 
remove these extra "dictionary applications", and use the code for the 
right method directly.  This is called "specialisation".

Getting back to your original question, there's a little subtlety in 
Haskell to do with literals.  Whenever you type an integer literal like 
"2", what the compiler actually sees is "fromInteger 2".  fromInteger 
has type Num a => Integer -> a, so this means that when you type an 
integer literal it is automatically converted to whatever numeric type 
is appropriate for the context.  In the context you give, there's still 
not enough information - it could be Int, or Integer, or Double, or 
several other things.  Another little subtlety called "defaulting" (see 
the Haskell 98 Report, in section 4.3.4) arranges that in this 
situation, the compiler will assume you mean Integer if that works, and 
failing that, it will try Double before giving up.  That's what the 
warning message you give is telling you.

> Is there
> some way of preventing the type mechanism from generating code for the
> instance type, as opposed to the class? 

I don't understand this question - does the explanation above help?

> If I am correct, does it work the same way across module boundaries? (I
> would think so.)

Yes, it does work automatically across instance boundaries.

> If a module exports a class but no instances for that
> class, then a user of that class would have to install their own instances.

Instance exporting is not easy to control in Haskell; if you export a 
type, then all its instances are exported along with it automatically.

> OTOH, if the class plus one or more instances were exported, then a user
> could use the supplied instance types, and the compiler would still generate
> code to use the specific instances.

>From the explanation above, you should see that the compiler generates
polymorphic code for any function with a type class in its type (e.g.,
"Num a => ..."), and it's the *caller* that supplies the code for the
specific instances (the dictionary).  But if the type is known at
compile time, then the compiler will fill in the dictionary itself,
and may even specialise it away.

The intention is that there is only one, global "instance space" - you
can't tightly control the export or not of specific instances, they
are pretty much always exported and all visible.  This isn't quite
true in practice, but it's the idea.

Hope this helps.

If you don't mind, I'm going to put this conversation up on the Wiki,
at

http://www.haskell.org/hawiki/TypeClass

--KW 8-)