[Haskell-cafe] Re: Compiler backend question

Derek Elkins derek.a.elkins at gmail.com
Mon Jan 7 17:38:37 EST 2008

On Mon, 2008-01-07 at 20:26 +0000, 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.

(This reply is aimed primarily at Peter.)

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.

Polymorphic recursion is one of the things the Haskell standard wasn't
conservative about.  I'm not sure if any widely used language supports
it besides Haskell.  (Maybe Clean?)  This turned out to be rather
fortunate as nested data types effectively require it.

As a toy example which illustrates this problem is:

f :: Show a => Int -> a -> String -- type signature required
f 0 x = show x
f n x = f (n-1) (x,x)

The dictionary to use depends on the input.  There are (well, switching
to Integer) an infinite number of potential types, so being able to
statically resolve them would not help.  Some kind of run-time witness
will need to be passed around.

More information about the Haskell-Cafe mailing list