On Tue, 2008-01-08 at 11:33 +0100, Peter Verswyvelen wrote:
Jon Harrop wrote:
On Monday 07 January 2008 20:27:17 Peter Verswyvelen wrote:
If your compiler (pretty amazing job btw) does whole program optimization, can it remove the dictionary (aka v-table in C/C++ parlance?) overhead of type classes? Because if I understand it correctly, unless one uses existential types, a dictionary can be compiled away since the type in question is known at compile time?
Yes. This is essentially what F# does.
Hang on.
When I asked a similar question in the F# forum, it seemed that F# simply does not have type classes (but it does support .NET interfaces), and root functions are only fully polymorphic when you mark them *inline*.
For example, the following will not work in the current version of F#:
**let add x y = x + y let t1 = add 1 2 let t2 = add 1.0 2.0**
The first usage of add forces it to work on integers, and then its type is settled once and for all. If I understood it correctly, this is because the "root polymorphic" add function can only work on specific types because it gets compiled into an object file.
You can force it to work on any type on which + can be applied by forcing the function to be inline, like
let inline add x y = x+y let t1 = add 1 2 let t2 = add 1.0 2.0
Then I guess the code will not be part of the object file, but it will be inserted inplace whenever it gets used (which could result in code bloat?)
Can the same trick be used in GHC?
Regarding Derek Elkins excellent example
f :: Show a => Int -> a -> String -- type signature required f 0 x = show x f n x = f (n-1) (x,x)
this indeed cannot be inlined nor optimized away, since you generally don't know the value of the first parameter at runtime. But this is a very specific case no? According to what I interpret from John Meacham's email, this case is an exception, and in many cases class type dictionary overhead gets compiled away?
Quoting my previous email with added emphasis, "Even in Haskell 98 it is not quite possible to do this. <<You can get rid of the vast majority of them>>, but the type is not always known at compile-time. There is one situation where the types depend on values. This occurs when you utilize polymorphic recursion." The point of my email was that it is not possible to -completely- eliminate dictionaries (or some other run-time witness) in general.