Which types systems are powerful enough to express this?

Question

Suppose that we define an interface like this:

interface Hashable {
   int hash();
}

Now we can make classes that implement this interface. For example a List class:

class List<T> : Hashable {
   int hash(){
      int h = 0;
      foreach(x in this){
         h = combineHash(h,x.hash());
      }
      return h;
   }
}

The problem is that we call hash on elements inside the List<T>, so T has to be Hashable. So we have to do:

class List<T : Hashable> : Hashable {
   ... same here ...
}

On the other hand, we also want to be able to construct lists with elements that are not hashable. In that case we simply don't want List<T> to implement Hashable. So:

List<AHashableType>      is itself Hashable
List<NotAHashableType>   is not Hashable

Furthermore, we want the hash method to be polymorphic (the OO kind of polymorphic, not parametrically polymorphic). So if we construct a List<Foo> with Bar's and Baz's inside, where Foo is Hashable and Bar and Baz are subtypes of Foo with different hash() methods, then that List<Foo>.hash() should call the right hash method at runtime.

This seems like a basic thing that languages should be able to express. The same pattern comes up in different cases, for example with ToString() and with IComparable. So far I haven't found a language and a solution in that language that lets me express this in a type safe way. Do you know of such a language and a solution in that langauge? Haskell comes quite close with its type classes, but unfortunately these are dispatched at compile time.

Answer 1

I think it's useful to separate the two issues you've described. The first is conditionally implementing an interface. Like you said, Haskell type classes do this. It would look something like:

class Hashable t where
  hash :: t -> Int

instance Hashable Int where
  hash i = i

-- Reads as "(List t) is Hashable if t is Hashable"
instance (Hashable t) => Hashable (List t) where
  hash l = ...

The second issue is OO polymorphism, which you can mimic in Haskell with a function-pointer-like mechanism.

-- Pretending we have some kind of OO method dispatch here
instance Hashable Foo where
    hash foo = foo.computeHash()

class Foo
   computeHash()

I've read a couple papers that add this sort of "conditional interface implementation" to a Java-like language. One of them is JavaGI (http://homepages.cwi.nl/~ralf/JavaGI/), which also adds the ability to implement an interface for a data type that you didn't originally define (like Haskell type classes). I can't remember what the other paper was called.