Type parameters

Dave Herman dherman at ccs.neu.edu
Wed Sep 6 07:24:59 PDT 2006


[Excuse my thinking out loud here... I'm not so much making an argument 
as trying to clarify the issues.]

Graydon Hoare wrote:

> I hate to sound like the broken record here, but can you give a concrete
> example? I'm looking for a case that satisfies all these properties:
> 
>   - A real idiom you see a lot
>   - That needs a parametric type
>   - That needs the parametric type to carry a type bound

Let me take a look at the ordered list example.

     class List.<T is Comparable> {
         ...
         cons: function(x:T):List.<T> { ... }
         head: function():T { ... }
         tail: function():List.<T> { ... }
         quicksort: function():List.<T> {
             ... x.compare(y) ...
         }
         ...
     }

This is seemingly not much different from a non-generic type with subtyping:

     class List {
         ...
         cons: function(x:Comparable):List { ... }
         head: function():Comparable {
             ... x.compare(y) ...
         }
         tail: function():List { ... }
         quicksort: function():List { ... }
         ...
     }

In both cases, the implementation of the collection is type-correct with 
no runtime down-casts. The difference is at the point of use, though. 
The bounded parametric implementation allows clients to write programs 
like this:

     var ls : List.<Foo> = new List.<Foo>(...);
     var x : Foo = ls.head();

Whereas in the non-generic example, the client code looks like:

     var ls : List = new List(...);
     var x : Foo = cast Foo(ls.head());

>   - That can't get by -- just as safely -- with helper functions

I'm assuming you mean something like the following?

     class List.<T> {
         type Comparator = function(T,T):int;
         ...
         quicksort: function(compare:Comparator):List.<T> {
             ... compare(x, y) ...
         }
     }

To summarize:

1) Generics are important not so much for the implementation of 
parametric libraries as for their clients: you only write a library once 
(for suitable values of "once"), but there are an unbounded number of 
uses of that library, so requiring extra casts of the clients of the 
library is a much bigger burden/danger.

2) Bounded generics allow you to specify additional operations the 
library can perform on its generic elements.

3) But you can always implement this equivalently with an unbounded 
parametric type, by passing in the additional operations as an argument 
to the constructor or the individual methods that require them. (You 
could equivalently have the API require multiple functional arguments, 
or a single object with multiple methods.)

Nicolas Canasse wrote:

> Fortunately, there is already big a good amount of papers written on
> both implementation and correctness of bounded type-parameters. That
> disables at least the first two points.

Can you give some references?

> You can of course emulate them by passing a functional API as
> constructor parameters, but that's more an ML functor-styled solution

I contend that higher-order functions are perfectly idiomatic in 
ECMAScript. They already play a large role in very widely used API's 
(which has had the pleasant side effect of educating a lot of people 
about higher-order functions!).

ECMAScript is both a functional and OO language-- it's a false dichotomy.

> than a OO one. Plus, unless you have proper functional types and at

We do have functional types. I realize the wiki is a bit disorganized 
(sorry about that, we're reorganizing it little by little), but the type 
system does include structural types for functions, arrays, objects, and 
unions.

> least a bit of type inference, it's very difficult to have everything
> being sound.

I don't know what you mean; inference may be a handy tool, but it isn't 
required for type soundness.

> 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.

They are certainly a concise way of expressing this, but Graydon's point 
is that if they are only a small improvement over the equivalent program 
written with unbounded types, then they aren't worth the overhead. After 
going through the examples above, it seems to me that the approach of 
passing additional operations as extra arguments scales up just fine, 
requiring no more than a small, fixed amount of extra code for each 
additional operation than the solution with bounded polymorphism.

But maybe to complete the gedankenexperiment I'd need to try to 
construct a larger example with lots of operations on the bounds.

Dave



More information about the Es4-discuss mailing list