Type parameters

Graydon Hoare graydon at mozilla.com
Wed Sep 6 11:25:16 PDT 2006


Nicolas Cannasse wrote:

> The question is wether you allow users to write containers that know at
> least a bit the API of the objects they are containing. One simple
> example is a Hash, you might require its items to have method
> getHashCode() : Int . Same for a sorted list which might require a
> comparison function. I'm making quite generic examples but users can
> easily comeup with their own problems.

As I said in the previous mail, "ISortable" and its kin are bad examples 
here. I'll give some details:

   - The first implementation people aim for is this:

     interface ISortable {
        function lessThan(other: ISortable): bool;
     }

     This implementation is wrong because it suggests that one "sortable"
     can meaningfully compare itself to all other sortables. If I make
     Ducks and Artichokes both ISortable, the type system will not
     prevent me from comparing them (and getting a runtime error).

   - The second implementation tries to correct this:

     interface ISortable.<T> {
        function lessThan(other: ISortable.<T>): bool;
     }

     now instances have to do something like:

     class foo implements ISortable.<foo> {
     }

     But even this suffers from a problem that is in some sense the
     dual of the problem you pointed out when complaining that the
     dynamic behavior of the sort functions might change.

     Specifically, the dynamic behavior of the ISortable.<foo> subtypes
     might change. Worse, they might change *inside* the same container.

     A container that makes any use of a sort operator needs an
     antisymmetric binary operator: it needs "a < b implies !(b < a)".
     But since you're using a *method* on ISortable.<foo> you get dynamic
     dispatch on the left operand, and it's still totally possible to
     have a.lessThan.<foo>(b) and b.lessThan.<foo>(a) be true
     simultaneously, if a and b are of different subclasses, that choose
     different logic.

     The same weakness is present in hashing-by-method: a and b might
     both implement .hashCode() with incompatible logic.

But suppose you're willing to live with this weakness, and live with the 
comparative eyesore of interfaces that are parametric on the 
inheritee-subtype (again, see Java 5; users hate it).

Even then, you still have a problem: primitive and structural types. In 
ES4, these are subtypes of non-parametric parent types, and you can only 
add "methods" to structural types via their prototypes. You will not be 
able to implement anything like SortedList.<int>, for example, since 
neither int nor Number implement your novel ISortable interface. Of 
course integers *are* sortable in some logical sense, they just don't 
happen to implement *your* nominal interface.

Indeed, part of the inherent rigidity of interface-based work is that 
you have to know, a priori, which interfaces to inherit. Since you can't 
know -- the required interfaces may not even be written yet -- you can 
sometimes paint future library-users into a corner: if Alice wants to 
use Bob's library with Carol's library, Bob's classes might need to have 
been written in such a way as to implement Carol's interfaces. Alice 
might need to subclass Bob's classes; and this is not always easy, if 
Bob's public classes are themselves abstract or final.

If Carol's library is defined in terms of helper functions, Alice can 
write some glue code to connect it to Bob's library. There's no need for 
her glue code to be "part" of Bob's types. In a sense, the set of 
function types are a "neutral zone" shared between Bob's and Carol's 
libraries: expressive enough to be useful, but provided by the system in 
advance, so not imposing any co-ordination between multiple library 
developers. I think that gives function types an important idiomatic role.

As I said before, I don't claim to know for certain that there are *no* 
high-value concrete examples that might make type parameter bounds 
cost-effective. I'm just ... pretty sure sorted and/or hashed containers 
aren't one of them. Can you propose any others?

-graydon



More information about the Es4-discuss mailing list