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.