[Haskell-cafe] Re: Compiler backend question

[Derek Elkins]

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.