I had a discussion with someone over the type class mechanism and would like to clarify something. When I compile this trivial program:
module Main where main = putStrLn (show (1 + 2))
with ghc -Wall, the compiler says: Main.lhs:3: 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? Is there some way of preventing the type mechanism from generating code for the instance type, as opposed to the class? If I am correct, does it work the same way across module boundaries? (I would think so.) 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. 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. ***************************************************************** The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. *****************************************************************
I had a discussion with someone over the type class mechanism and would like to clarify something.
When I compile this trivial program:
module Main where main = putStrLn (show (1 + 2))
with ghc -Wall, the compiler says:
Main.lhs:3: 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?
Hi, I hope I've understod your question. What this message is telling you is that the compiler is applying Haskell 98's "defaulting" mechanism. The numeric literals 1 and 2 in the code are overloaded, that is they have type: Num a => a When the program is run the calls to '+' and 'show' must be resolved to particular instances. However the overloading of their arguments prevents that. The overloading is thus ambiguous. Haskell 98 has a rule that (very roughly) says when overloading is ambiguous and it involves standard numeric classes, apply some defaults to resolve the ambiguity. In this case the default rule is to resolve the outstanding constraint 'Num a' with Integer (making the type of 1 and 2 Integer). After defaulting the instances of + and show can be resolved. You can change the behaviour of defaulting, and even turn it off, try: module Main where default () ... Compiling again with -Wall gives: Ambiguous type variable(s) `a' in the constraint `Num a' arising from the literal `2' at Foo.hs:6 In the second argument of `(+)', namely `2' In the first argument of `show', namely `(1 + 2)' You can also get the same effect as defaulting by putting explicit type annotations in your program: main = putStrLn (show ((1 + 2) :: Integer)) The Haskell Report doesn't say a whole lot about _how_ to implement the type class overloading, though from what I understand, most implementations use a similar algorithm (dictionary passing). You can read all about typical implementations in the literature. Google for "Type Class", "Implementation", and maybe even "Haskell".
Does the compiler *always* know what the actual instances being used are?
A smart compiler can specialise the calls to overloaded functions in circumstances when the type(s) of its arguments are also known. This is a good thing because it tends to reduce the cost of overloading at runtime. More aggresive forms of specialisation are also possible and discussed in the literature. I think if you look up the papers on implementing type classes your questions should be answered. Mail me if you need some references. Cheers, Bernie.
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-)
participants (3)
-
Bayley, Alistair -
Bernard James POPE -
Keith Wansbrough