Thursday, August 23, 2007

James Gosling, it turns out, thought harder about type inference than I did

So for a while, I'd been wondering about the type system in Java, thinking that perhaps I'd found a shortcoming -- if you have a more general type (say, "Thing"), and a more specific type (say, "Chair", which extends "Thing") -- then why isn't List<Chair> a subtype of List<Thing>, meaning that you could pass a List of Chairs into a method that takes a List of Things?

The mighty Toby R, in a conversation with me and Strick, shed some light on the situation and led me to understand why this is not the case. The particular use-case is: when you're in the method that takes List<Thing>, you can add Things to that list. And the Things you add could well be Basketballs. So when the method returns, the caller is still expecting to have a list of Chairs, not realizing that there are now Basketballs in the list... so Java cleverly disallows this case.

(also, somehow I missed an anonymous comment, probably from my mother, well-respected for her work on type theory, which explained that exact case)

Now in a purely functional language, where you don't go around getting references to objects and modifying them, I'd like to posit that this wouldn't be a problem -- but perhaps there are other problematic situations? ...

3 comments:

ynniv said...

This is also true for C++ member function pointers. Part of the definition of inheritance is that an instance of a subclass can be used wherever a base class instance is required. However, a pointer to a member function of a subclass can't be used where a pointer to a member function of the base class, because you can't apply a subclass member function to a base class instance.

In my experience, the most important part of a type system is for it to be optional. If it isn't, you'll find yourself occasionally needing to subvert it, and the results are never pretty.

WRudin said...

Unrelated but in reply, Peta will help euthanize animals that are to sick to be adopted or treated (due to overcrowding in some facilities in NC), which is what happened in the case of PETA people testifying that they had killed animals. It is never to harm them, only a sad decision that must be made in the most extreme cases. ABC News (after I wrote my blog) had a report on the Consumer Group that printed the ad in the NYTimes. The amount they paid for it was around 130,000 dollars (the most expensive ad ever purchased by a non-profit!). They are also run by a man who used to run a PR campaign for Phillip Morris and the 'non-profit' is heavily subsidized by large corporations (such as tobacco companies and fast food chains).

Lindsey Kuper said...

This is exactly the situation I was talking about today when I said that array types needed to be invariant. Since writes are covariant (you can insert a PapasanChair into a List) and reads are contravariant (you can take an Object out of a List), the only safe choice is to make arrays invariant -- unless you can guarantee that you're never going to read or write! (For more on this: http://en.wikipedia.org/wiki/Covariance_and_contravariance_%28computer_science%29, or (much more fun) http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Unsoundness/.)