CODEWITHSUNDEEP
genericstypesinterfacetype-systems
Jules
Jules

Reputation: 6346

Which types systems are powerful enough to express this?

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.

Upvotes: 2

Views: 146

Answers (4)

supercat
supercat

Reputation: 81159

The problem you describe is IMHO a good justification for going against the Interface Segregation Principle in a number of situations, especially in limited type systems such as those of Java or .NET. While there is great value in being able to use type checking as a means of ensuring that objects are only asked to perform actions of which they are capable, not all questions of ability can be decided before a program is run. There are many situations where code will receive a reference to an object with optional abilities which it should use if present and work around if not. If an interface includes methods for such optional abilities, along with a means of determining whether those methods should be used, then compositions or aggregates of such objects can likewise expose such optional abilities. If interfaces only include actions which implementers are guaranteed to be able to perform, then an immutable aggregation must, on construction, identify all abilities it's ever going to want to advertise, and mutable aggregations cannot advertise any abilities they wouldn't require from every item that's added.

If there is an ability which some implementations of an interface will have and others will not, and if there's a significant likelihood that the same objects will have to deal with things that have the ability and things that don't, and should be able use such ability when present, I would suggest including the ability in the interface along with a means of determining when it is available. For example, if a collection identifies IFoo instances, some of which can Boz(), and the collection itself should implement IFoo and calling Boz on the collection should be legal when and only when all elements can Boz, I'd suggest having IFoo include Boz() along with a CanBoz property. The CanBoz property can ask each item in the collection whether it can Boz, and return affirmative only when all the contained items do so. You would lose the compile-time assurances that could come from stricter type-checking, but you would gain the ability to use the method in those cases where static type checking could not allow it.

Upvotes: 0

tsm
tsm

Reputation: 3658

Maybe I'm misreading the OP, but it seems like it'd be necessary to know at compile-time whether a given List was Hashable or not. Otherwise, what would happen to a call to hash() on a non-Hashable List?

I'm sure, however, that a solution exists with the CLOS. (Multiple dispatch would certainly come in handy, and I'm dimly aware of its more expressive way of dealing with subclasses.)

Upvotes: 2

Kannan Goundan
Kannan Goundan

Reputation: 5232

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.

Upvotes: 1

Michael B
Michael B

Reputation: 7567

Unfortunately, you need some how a conditional type constraint for generics (note templates could support this through partial specialization and private inheritance). I don't know a staticly typed language that has them but could be solved with monkeypatching through extension methods.Here is an example in C#.

public static int GetHash<T>(this List<T> list) where T:IEquatable<T>
{
      if(list == null) throw new ArgumentNullException("list");
      int h = 0;
      foreach(var x in list){
         h = CombineHash(h,x.GetHashCode());
      }
      return h;
}

Where CombineHash combines your hashcodes. Note that every method in C# actually has a hashcode by default, but IEquatable<T> is an interface that specifies GetHashCode as a member. Thus List<int>. can call GetHash, but List<object> can't as object doesn't implement the interface. Since GetHashCode isn't particularly interesting let's say we did this:

interface IFoo{
    string Bar();
}
class Foo:IFoo{
    public virtual string Bar(){return "Foo";}
}
class Baz:Foo{
     public override string Bar(){return "Baz";}
}
public static string Bar(this List<T> list) where T:IFoo
{
    if(list == null) throw new ArgumentNullException("list");
    StringBuilder sb = new StringBuilder();
    foreach(var x in list){
       sb.Append(x.Bar());
    }
    return sb.Bar();
}

Here since we constrained T To be an IFoo we are now able to invoke this method on either a List<IFoo>,List<Foo>, or a List<Baz> but not a List<int> as int doesn't implement IFoo. e.g.

public static void SomeMethod()
{
      Console.WriteLine(new List<IFoo>{new Baz(),new Foo()}.Bar()); //compiles
      Console.WriteLine(new List<int>{1,2,3,4,}.Bar()); // does not compile.
}

Upvotes: 2

Related Questions