Type parameters

# Peter Hall (19 years ago)

I have a few questions/comments on this proposal. (developer.mozilla.org/es4/proposals/type_parameters.html)

I don't see any discussion about optional Type parameteres (default values). Wouldn't you sometimes want to be able to something like

class Factory.<A=Bar> { // etc }

It is possible to work around this by extending the class with a non-parametrised type, which provides the parameter. eg:

class FactoryTemplate.<A> { // etc }

class BarFactory extends FactoryTemplate.<Bar> { }

While this works great, it isn't symmetrical with function arguments. It would be equivalent to creating additional differently-named functions in place of using optional arguments.

I am also wondering about the implications of not being able to enforce any constraints on the types that may be used a parameter. But I'm struggling to find a convincingly realistic example where it would be useful - so perhaps I will leave that alone...

How will static code be exectuted in such classes?

class Example.<A> {

 {
     // when does code that is placed here run?
     // and, consequently, can it determine A?
 }

 static var a:A;

}

How would reflection implementations be affected by type parameters? I'm thinking of AS3 here.

Apologies if my questions are naive - I am just an enthusiast in all this :-) Thanks,

Peter

I have a few questions/comments on this proposal.
(http://developer.mozilla.org/es4/proposals/type_parameters.html)

1. I don't see any discussion about optional Type parameteres (default
values). Wouldn't you sometimes want to be able to something like

   class Factory.<A=Bar> {
        // etc
   }


It is possible to work around this by extending the class with a
non-parametrised type, which provides the parameter. eg:

   class FactoryTemplate.<A> {
        // etc
   }

   class BarFactory extends FactoryTemplate.<Bar> {   }


While this works great, it isn't symmetrical with function arguments.
It would be equivalent to creating additional differently-named
functions in place of using optional arguments.



2. I am also wondering about the implications of not being able to
enforce any constraints on the types that may be used a parameter. But
I'm struggling to find a convincingly realistic example where it would
be useful - so perhaps I will leave that alone...



3. How will static code be exectuted in such classes?

   class Example.<A> {

        {
            // when does code that is placed here run?
            // and, consequently, can it determine A?
        }

        static var a:A;
   }



4. How would reflection implementations be affected by type
parameters? I'm thinking of AS3 here.



Apologies if my questions are naive - I am just an enthusiast in all this :-)
Thanks,


Peter

# Nicolas Cannasse (19 years ago)

I am also wondering about the implications of not being able to enforce any constraints on the types that may be used a parameter. But I'm struggling to find a convincingly realistic example where it would be useful - so perhaps I will leave that alone...

There are a lot of useful cases. Basically when you don't have any contraints on the type parameter, all you can do is manipulate it abstractly. It works well for all kind of data structures and containers, but fails to express reusable components.

For instance in haXe you can do the following

interface Required { ... }

class Api< T : Required > { }

That means that in the implementation of Api you can call any method defined in "Required". The type parameter is restricted to classes "implementing" Required.

It is a bit difficult to deal with these contrainted type parameters when having type inference at the same time, but this should not be a problem of ES4.

How will static code be exectuted in such classes?

class Example.<A> {
 {
     // when does code that is placed here run?
     // and, consequently, can it determine A?
 }

 static var a:A;
}

Type parameters are usualy forbidden in static variables, since it does not makes sense. Allowing them creates a type hole since you can do

Example.<Int>.a = 3

var s : String = Example.<String>.a;

How would reflection implementations be affected by type parameters? I'm thinking of AS3 here.

This is an interesting question. haXe has reflection (also when targeting Flash9) but does not enforce type parameters at runtime. Two reasons for that :

a) the Flash9 VM does not support them

b) haXe philosophy is about providing maximum compile-time typing and maximum runtime flexibility. So enforcing too much typing at runtime would prevent the second goal. This is for instance the reason Java is so much static.

But this might not be the case for ES4...

> 2. I am also wondering about the implications of not being able to
> enforce any constraints on the types that may be used a parameter. But
> I'm struggling to find a convincingly realistic example where it would
> be useful - so perhaps I will leave that alone...

There are a lot of useful cases. Basically when you don't have any
contraints on the type parameter, all you can do is manipulate it
abstractly. It works well for all kind of data structures and
containers, but fails to express reusable components.

For instance in haXe you can do the following

interface Required {
...
}

class Api< T : Required > {
}

That means that in the implementation of Api you can call any method
defined in "Required". The type parameter is restricted to classes
"implementing" Required.

It is a bit difficult to deal with these contrainted type parameters
when having type inference at the same time, but this should not be a
problem of ES4.

> 3. How will static code be exectuted in such classes?
> 
>    class Example.<A> {
> 
>         {
>             // when does code that is placed here run?
>             // and, consequently, can it determine A?
>         }
> 
>         static var a:A;
>    }

Type parameters are usualy forbidden in static variables, since it does
not makes sense. Allowing them creates a type hole since you can do

Example.<Int>.a = 3
var s : String = Example.<String>.a;

> 4. How would reflection implementations be affected by type
> parameters? I'm thinking of AS3 here.

This is an interesting question. haXe has reflection (also when
targeting Flash9) but does not enforce type parameters at runtime. Two
reasons for that :

a) the Flash9 VM does not support them

b) haXe philosophy is about providing maximum compile-time typing and
maximum runtime flexibility. So enforcing too much typing at runtime
would prevent the second goal. This is for instance the reason Java is
so much static.

But this might not be the case for ES4...

Nicolas

# Peter Hall (19 years ago)

There are a lot of useful cases. Basically when you don't have any contraints on the type parameter, all you can do is manipulate it abstractly. It works well for all kind of data structures and containers, but fails to express reusable components.

This was my feeling too. I am just struggling to concoct a convincing code example that is not contrived.

Type parameters are usualy forbidden in static variables, since it does not makes sense. Allowing them creates a type hole since you can do

Example.<Int>.a = 3 var s : String = Example.<String>.a;

I wrote my example badly. I was trying to understand how parametrised types are treated. That is, is each parametrisation a proper type, having it's static code run once per parametrisation, or is static code run once when the definition is imported?

e.g.

class Example.<A> { { print("hello"); } }

eStr = new Example.<String>(); eObj = new Example.<Object>();

Should I expect "hello" to be output once or twice?

Peter

> There are a lot of useful cases. Basically when you don't have any
> contraints on the type parameter, all you can do is manipulate it
> abstractly. It works well for all kind of data structures and
> containers, but fails to express reusable components.


This was my feeling too. I am just struggling to concoct a convincing
code example that is not contrived.


> Type parameters are usualy forbidden in static variables, since it does
> not makes sense. Allowing them creates a type hole since you can do
>
> Example.<Int>.a = 3
> var s : String = Example.<String>.a;
>


I wrote my example badly. I was trying to understand how parametrised
types are treated. That is, is each parametrisation a proper type,
having it's static code run once per parametrisation, or is static
code run once when the definition is imported?

e.g.


  class Example.<A> {
       {
            print("hello");
       }
  }

  eStr = new Example.<String>();
  eObj = new Example.<Object>();


Should I expect "hello" to be output once or twice?

Peter

# Graydon Hoare (19 years ago)

Nicolas Cannasse wrote:

There are a lot of useful cases. Basically when you don't have any contraints on the type parameter, all you can do is manipulate it abstractly. It works well for all kind of data structures and containers, but fails to express reusable components.

This is a sort of general comment. The point I'd like to address is a sort of mental arithmetic, or weighting of features and comparison with existing forms of safety and expressiveness. Add up these things in your mind:

Complexity of implementing the feature
Complexity of proving the feature correct
Complexity of explaining feature to users
Complexity of resulting "clever" API-code that users will have to understand in the wild (eg. note the difficulty many Java 5 users have with the parametric bounds all over its standard library)

and compare them to some mental weight of:

Set of things you can express most conveniently with this feature, that you otherwise cannot express if this one feature is missing.

My feeling is that bounded type parameters just aren't worth the cost. That's why I avoided them in my proposal. Of course others might perform the "mental arithmetic" above with different weights and come to a different conclusion. But let's try to be concrete with examples.

For instance in haXe you can do the following

interface Required { ... }

class Api< T : Required > { }

That means that in the implementation of Api you can call any method defined in "Required". The type parameter is restricted to classes "implementing" Required.

Sure, but again this is a sort of vague example. In a lot of real examples, if you want an object of type "Required" that's actually all you need to know about the type; you don't need to name the subtype of "Required" because all you're going to do is call a few interface methods on it. In other words, in most real examples I've encountered the code:

class foo< T : Bar> { function bleh(t : T) { ... use some Bar methods ... } }

where Bar is some interface, can often be written as:

class foo { function bleh(t : Bar) { ... use some Bar methods ... } }

without type parameters at all.

The point I'd like you to focus on is whether there are any important real examples wherein you need both a type parameter and a bound on the parameter. I'd argue that there are very few.

One example everyone likes to give is a container with sorting; the idea is that once a type "implements Sortable" it can be put in a sorted associative map, or such, even while the map enforces type identity on the key and value types. But this is not a very good example, because it's actually a lot of work to express the constraint that two "Sortable" subtypes can sort with respect to their own subtype, but not necessarily with respect to one another. It's much easier in this case to present the following style of Map:

class Map.<K,V> { lessThan : func(K,K):Boolean; Map(lt : (func(K,K):Boolean)) : lessThan(lt) {} ... }

This is the kind of thing I meant in my comments on the parametric type proposal: since we have first class functions, a lot of the "utility interfaces" that people often want to use parameter bounds for can just be passed along as auxiliary functions. And moreover that it's actually easier to express common patterns in, a lot of the time.

I'm happy to consider counterexamples, of course, but I'd like you to try holding them up to that criterion before assuming that "the feature can be done so it should be done". It's an expensive feature, complexity-wise. We want to keep complexity down. Take some time in an editor-buffer and work through your examples. See if they're really any more convenient with the bounded parameter vs. the parametric first-class function.

Nicolas Cannasse wrote:

> There are a lot of useful cases. Basically when you don't have any
> contraints on the type parameter, all you can do is manipulate it
> abstractly. It works well for all kind of data structures and
> containers, but fails to express reusable components.

This is a sort of general comment. The point I'd like to address is a 
sort of mental arithmetic, or weighting of features and comparison with 
existing forms of safety and expressiveness. Add up these things in your 
mind:

   - Complexity of implementing the feature
   - Complexity of proving the feature correct
   - Complexity of explaining feature to users
   - Complexity of resulting "clever" API-code that users will have
     to understand in the wild (eg. note the difficulty many Java 5
     users have with the parametric bounds all over its standard
     library)

and compare them to some mental weight of:

   - Set of things you can express most conveniently with this
     feature, that you otherwise cannot express if this one
     feature is missing.

My feeling is that bounded type parameters just aren't worth the cost. 
That's why I avoided them in my proposal. Of course others might perform 
the "mental arithmetic" above with different weights and come to a 
different conclusion. But let's try to be concrete with examples.

> For instance in haXe you can do the following
> 
> interface Required {
> ...
> }
> 
> class Api< T : Required > {
> }
> 
> That means that in the implementation of Api you can call any method
> defined in "Required". The type parameter is restricted to classes
> "implementing" Required.

Sure, but again this is a sort of vague example. In a lot of real 
examples, if you want an object of type "Required" that's actually *all* 
you need to know about the type; you don't need to name the subtype of 
"Required" because all you're going to do is call a few interface 
methods on it. In other words, in most real examples I've encountered 
the code:

   class foo< T : Bar>
   {
     function bleh(t : T) { ... use some Bar methods ... }
   }

where Bar is some interface, can often be written as:

   class foo
   {
     function bleh(t : Bar) { ... use some Bar methods ... }
   }

without type parameters *at all*.

The point I'd like you to focus on is whether there are any important 
*real* examples wherein you need *both* a type parameter *and* a bound 
on the parameter. I'd argue that there are very few.

One example everyone likes to give is a container with sorting; the idea 
is that once a type "implements Sortable" it can be put in a sorted 
associative map, or such, even while the map enforces type identity on 
the key and value types. But this is not a very good example, because 
it's actually a lot of work to express the constraint that two 
"Sortable" subtypes can sort with respect to their own subtype, but not 
necessarily with respect to one another. It's much *easier* in this case 
to present the following style of Map:

class Map.<K,V> {
   lessThan : func(K,K):Boolean;
   Map(lt : (func(K,K):Boolean)) : lessThan(lt) {}
   ...
}

This is the kind of thing I meant in my comments on the parametric type 
proposal: since we have first class functions, a lot of the "utility 
interfaces" that people often want to use parameter bounds for can just 
be passed along as auxiliary functions. And moreover that it's actually 
*easier* to express common patterns in, a lot of the time.

I'm happy to consider counterexamples, of course, but I'd like you to 
try holding them up to that criterion before assuming that "the feature 
can be done so it should be done". It's an expensive feature, 
complexity-wise. We want to keep complexity down. Take some time in an 
editor-buffer and work through your examples. See if they're really any 
more convenient with the bounded parameter vs. the parametric 
first-class function.

-graydon

# Peter Hall (19 years ago)

That means that in the implementation of Api you can call any method defined in "Required". The type parameter is restricted to classes "implementing" Required.

Sure, but again this is a sort of vague example. In a lot of real examples, if you want an object of type "Required" that's actually all you need to know about the type; you don't need to name the subtype of "Required" because all you're going to do is call a few interface methods on it.

I don't think this is correct. It is true that, inside methods of Api, you are only going to use methods of Required. But without type restrictions Api couldn't call any methods without a lot of unpleasant runtime tests and coercions. Clients of Api could quite usefully parametrize it with several subtypes of Required, and gain the benefit of type-safety when using the subtype functionality - which is the whole point of parametrized types after all. So my feeling is that lack of type restriction consigns parametrized types to be used only for dumb collections (or objects that could be constructed equivalently by aggregating such a collection).

Peter

> > That means that in the implementation of Api you can call any method
> > defined in "Required". The type parameter is restricted to classes
> > "implementing" Required.
>
> Sure, but again this is a sort of vague example. In a lot of real
> examples, if you want an object of type "Required" that's actually *all*
> you need to know about the type; you don't need to name the subtype of
> "Required" because all you're going to do is call a few interface
> methods on it.

I don't think this is correct. It is true that, inside methods of Api,
you are only going to use methods of Required. But without type
restrictions Api couldn't call *any* methods without a lot of
unpleasant runtime tests and coercions. Clients of Api could quite
usefully parametrize it with several subtypes of Required, and gain
the benefit of type-safety when using the subtype functionality -
which is the whole point of parametrized types after all. So my
feeling is that lack of type restriction consigns parametrized types
to be used only for dumb collections (or objects that could be
constructed equivalently by aggregating such a collection).

Peter

# Graydon Hoare (19 years ago)

Peter Hall wrote:

I don't think this is correct. It is true that, inside methods of Api, you are only going to use methods of Required. But without type restrictions Api couldn't call any methods without a lot of unpleasant runtime tests and coercions.

Perhaps I am mis-parsing this sentence. It sounds like you're saying:

'Api' is only going to want to use methods of 'Required', and this is no good because 'Api' can only use methods of 'Required'.

If that's what you're saying, I don't understand the problem. Api can only call the methods it's interested in. Seems fine to me. I'm probably misunderstanding.

usefully parametrize it with several subtypes of Required, and gain the benefit of type-safety when using the subtype functionality - which is the whole point of parametrized types after all.

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
That can't get by -- just as safely -- with helper functions

Perhaps this is just my own language bias. I've done more ML and C++ than Java 5, but my hunch is that Java only included it because they lack function types: they habitually shoe-horn every form of abstraction into a form of inheritance.

feeling is that lack of type restriction consigns parametrized types to be used only for dumb collections (or objects that could be constructed equivalently by aggregating such a collection).

"Dumb collections" are one of the most universal programming idioms. You would find it hard to write an ecmascript program that didn't at least use the array type. We want to support typed arrays. Further, most useful programs contain hashtables or sorted maps. We can type those precisely by adding opaque type parameters. The universality of need and limited complexity of the feature makes it seem like a worthwhile purchase.

I don't get the same feeling from type-parameter bounds. Maybe I just haven't seen the canonical example yet. I'm happy to reconsider my position if there's some Very Important Idiom that's inexpressible without them. I'm just not interested in supporting the feature for the sake of completeness. The language design is already "too complete".

Peter Hall wrote:

> I don't think this is correct. It is true that, inside methods of Api,
> you are only going to use methods of Required. But without type
> restrictions Api couldn't call *any* methods without a lot of
> unpleasant runtime tests and coercions. 

Perhaps I am mis-parsing this sentence. It sounds like you're saying:

   'Api' is only going to want to use methods of 'Required', and
    this is no good because 'Api' can only use methods of 'Required'.

If that's what you're saying, I don't understand the problem. Api can 
only call the methods it's interested in. Seems fine to me. I'm probably 
misunderstanding.

> usefully parametrize it with several subtypes of Required, and gain
> the benefit of type-safety when using the subtype functionality -
> which is the whole point of parametrized types after all. 

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
   - That can't get by -- just as safely -- with helper functions

Perhaps this is just my own language bias. I've done more ML and C++ 
than Java 5, but my hunch is that Java only included it because they 
lack function types: they habitually shoe-horn every form of abstraction 
into a form of inheritance.

> feeling is that lack of type restriction consigns parametrized types
> to be used only for dumb collections (or objects that could be
> constructed equivalently by aggregating such a collection).

"Dumb collections" are one of the most universal programming idioms. You 
would find it hard to write an ecmascript program that didn't at least 
use the array type. We want to support typed arrays. Further, most 
useful programs contain hashtables or sorted maps. We can type those 
precisely by adding opaque type parameters. The universality of need and 
limited complexity of the feature makes it seem like a worthwhile purchase.

I don't get the same feeling from type-parameter bounds. Maybe I just 
haven't seen the canonical example yet. I'm happy to reconsider my 
position if there's some Very Important Idiom that's inexpressible 
without them. I'm just not interested in supporting the feature for the 
sake of completeness. The language design is already "too complete".

-graydon

# Nicolas Cannasse (19 years ago)

I wrote my example badly. I was trying to understand how parametrised types are treated. That is, is each parametrisation a proper type, having it's static code run once per parametrisation, or is static code run once when the definition is imported?

e.g.

class Example.<A> { { print("hello"); } }

eStr = new Example.<String>(); eObj = new Example.<Object>();

Should I expect "hello" to be output once or twice?

Only one. Either the VM supports type parameters, then it will only have one class instance, or it simply "forget them" after compiling, and insert runtime casts in the generated bytecode (like Java 1.5 Generics).

> I wrote my example badly. I was trying to understand how parametrised
> types are treated. That is, is each parametrisation a proper type,
> having it's static code run once per parametrisation, or is static
> code run once when the definition is imported?
> 
> e.g.
> 
> 
>   class Example.<A> {
>        {
>             print("hello");
>        }
>   }
> 
>   eStr = new Example.<String>();
>   eObj = new Example.<Object>();
> 
> 
> Should I expect "hello" to be output once or twice?

Only one. Either the VM supports type parameters, then it will only have
one class instance, or it simply "forget them" after compiling, and
insert runtime casts in the generated bytecode (like Java 1.5 Generics).

Nicolas

# Nicolas Cannasse (19 years ago)

There are a lot of useful cases. Basically when you don't have any contraints on the type parameter, all you can do is manipulate it abstractly. It works well for all kind of data structures and containers, but fails to express reusable components.

This is a sort of general comment. The point I'd like to address is a sort of mental arithmetic, or weighting of features and comparison with existing forms of safety and expressiveness. Add up these things in your mind:

Complexity of implementing the feature

Complexity of proving the feature correct

Complexity of explaining feature to users

Complexity of resulting "clever" API-code that users will have to understand in the wild (eg. note the difficulty many Java 5 users have with the parametric bounds all over its standard library)

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.

"Explaining" the feature to users is not mandatory. At first, users don't need it. Then at the time they will need it, they should have enough knowledge in the language to understand at least how it works.

Not having it mandatory of course means not to follow Java by having a standard library making big usage of the feature. This is not because they had this problem that the same will happen, of course.

What is important is the ability of users to express middly-complex architectures easily, and without relying on dynamic typing. That's exactly what the bounded type parameters are providing.

You can of course emulate them by passing a functional API as constructor parameters, but that's more an ML functor-styled solution than a OO one. Plus, unless you have proper functional types and at least a bit of type inference, it's very difficult to have everything being sound.

My feeling is that bounded type parameters just aren't worth the cost. That's why I avoided them in my proposal. Of course others might perform the "mental arithmetic" above with different weights and come to a different conclusion. But let's try to be concrete with examples.

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.

>>There are a lot of useful cases. Basically when you don't have any
>>contraints on the type parameter, all you can do is manipulate it
>>abstractly. It works well for all kind of data structures and
>>containers, but fails to express reusable components.
> 
> 
> This is a sort of general comment. The point I'd like to address is a 
> sort of mental arithmetic, or weighting of features and comparison with 
> existing forms of safety and expressiveness. Add up these things in your 
> mind:
> 
>    - Complexity of implementing the feature
>    - Complexity of proving the feature correct
>    - Complexity of explaining feature to users
>    - Complexity of resulting "clever" API-code that users will have
>      to understand in the wild (eg. note the difficulty many Java 5
>      users have with the parametric bounds all over its standard
>      library)

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.

"Explaining" the feature to users is not mandatory. At first, users
don't need it. Then at the time they will need it, they should have
enough knowledge in the language to understand at least how it works.

Not having it mandatory of course means not to follow Java by having a
standard library making big usage of the feature. This is not because
they had this problem that the same will happen, of course.

What is important is the ability of users to express middly-complex
architectures easily, and without relying on dynamic typing. That's
exactly what the bounded type parameters are providing.

You can of course emulate them by passing a functional API as
constructor parameters, but that's more an ML functor-styled solution
than a OO one. Plus, unless you have proper functional types and at
least a bit of type inference, it's very difficult to have everything
being sound.

> My feeling is that bounded type parameters just aren't worth the cost. 
> That's why I avoided them in my proposal. Of course others might perform 
> the "mental arithmetic" above with different weights and come to a 
> different conclusion. But let's try to be concrete with examples.

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.

Nicolas

# Dave Herman (19 years ago)

[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:

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.
Bounded generics allow you to specify additional operations the library can perform on its generic elements.
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.

[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

# Nicolas Cannasse (19 years ago)

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?

I don't have any link there, but I assume that the appropriate work has been done before (and completed after) integration of bounded type parameters in Java.

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.

Yes, this is something that I didn't know. Can I find somewhere the references for these ?

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.

Sure. But when you deal with type parameters, it surely helps to cleanup the resulting program ;)

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.

Having programmed in OCaml for many years, I understand how HOF can be used to replace bounded types. However there are some restrictions to this :

such API methods needs to be passed to the constructor, they are not par of the type "per-se". In particular, let's say you want to get the intersection of two Maps. This operation is sound only if both maps have been constructed with the same function for generating keys. With bounded type parameters, you can tie the type and the function together (unless you allow variance which would allow overriding, but then the semantic is also different).
it doesn't work well with interfaces. People might already use IComparable or such interfaces in their architecture. They will have then to rewrap their methods into static functions for the sake of changing paradigm (from OO to functional).

While i love Functional programming a lot, I'm not sure this is the correct way to deal with the problem in a OO world such as ES4.

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

I don't have any link there, but I assume that the appropriate work has
been done before (and completed after) integration of bounded type
parameters in Java.

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

Yes, this is something that I didn't know.
Can I find somewhere the references for these ?

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

Sure. But when you deal with type parameters, it surely helps to cleanup
the resulting program ;)

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

Having programmed in OCaml for many years, I understand how HOF can be
used to replace bounded types. However there are some restrictions to this :

- such API methods needs to be passed to the constructor, they are not
par of the type "per-se". In particular, let's say you want to get the
intersection of two Maps. This operation is sound only if both maps have
been constructed with the same function for generating keys. With
bounded type parameters, you can tie the type and the function together
(unless you allow variance which would allow overriding, but then the
semantic is also different).

- it doesn't work well with interfaces. People might already use
IComparable or such interfaces in their architecture. They will have
then to rewrap their methods into static functions for the sake of
changing paradigm (from OO to functional).

While i love Functional programming a lot, I'm not sure this is the
correct way to deal with the problem in a OO world such as ES4.

Nicolas

# Peter Hall (19 years ago)

Perhaps I am mis-parsing this sentence. It sounds like you're saying:

'Api' is only going to want to use methods of 'Required', and this is no good because 'Api' can only use methods of 'Required'.

If that's what you're saying, I don't understand the problem. Api can only call the methods it's interested in. Seems fine to me. I'm probably misunderstanding.

It is fine :-) However, this scenario is not possible without bounding the type.

I think you are misunderstanding because what I am saying is quite obvious, and maybe you are expecting that I am saying something profound...

Dave Herman has covered all I had to say - and a lot more eloquently - so I will leave it at that.

I hate to sound like the broken record here, but can you give a concrete example?

I can't. And I promise not to mention this again until one is produced! :-)

Peter

> Perhaps I am mis-parsing this sentence. It sounds like you're saying:
>
>    'Api' is only going to want to use methods of 'Required', and
>     this is no good because 'Api' can only use methods of 'Required'.
>
> If that's what you're saying, I don't understand the problem. Api can
> only call the methods it's interested in. Seems fine to me. I'm probably
> misunderstanding.


It _is_ fine :-) However, this scenario is not possible without
bounding the type.

I think you are misunderstanding because what I am saying is quite
obvious, and maybe you are expecting that I am saying something
profound...

Dave Herman has covered all I had to say - and a lot more eloquently -
so I will leave it at that.


> I hate to sound like the broken record here, but can you give a concrete
> example?

I can't. And I promise not to mention this again until one is produced! :-)


Peter

# Peter Hall (19 years ago)

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.

Yes, this is something that I didn't know. Can I find somewhere the references for these ?

I think all relevent specs and proposals are linked from here: developer.mozilla.org/es4/spec/chapter_6_types.html

Peter

> > 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.
>
> Yes, this is something that I didn't know.
> Can I find somewhere the references for these ?

I think all relevent specs and proposals are linked from here:
http://developer.mozilla.org/es4/spec/chapter_6_types.html

Peter

# Burak Emir (19 years ago)

Nicolas Cannasse 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?

I don't have any link there, but I assume that the appropriate work has been done before (and completed after) integration of bounded type parameters in Java.

+1 for bounded type parameters, but one has to take case of some undecidability results (Fsub) lurking in this area.

I would not say that research is finished on this topic. See the following paper and its references for some examples on why bounds matter

doc icon Burak Emir, Andrew Kennedy, Claudio Russo and Dachuan Yu. * Variance and Generalized Constraints for C# Generics* In Proceedings of the 20th European Conference on Object-Oriented Programming (ECOOP), Nantes, France, July 2006.

research.microsoft.com/~akenn/generics/ECOOP06.pdf

Of course, there is a rich, established type theory for lambda calculus, a nice-to-read entry point is Cardelli and Wegner "On understanding data types, abstraction and polymorphism" citeseer.ist.psu.edu/cardelli85understanding.html

Nicolas Cannasse 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?
>>    
>>
>
>I don't have any link there, but I assume that the appropriate work has
>been done before (and completed after) integration of bounded type
>parameters in Java.
>  
>
+1 for bounded type parameters, but one has to take case of some 
undecidability results (Fsub) lurking in this area.

I would not say that research is finished on this topic. See the 
following paper and its references for some examples on why bounds matter

doc icon Burak Emir, Andrew Kennedy, Claudio Russo and Dachuan Yu. * 
Variance and Generalized Constraints for C# Generics*
In Proceedings of the 20th European Conference on Object-Oriented 
Programming (ECOOP), Nantes, France, July 2006.

http://research.microsoft.com/~akenn/generics/ECOOP06.pdf

Of course, there is a rich, established type theory for lambda calculus, 
a nice-to-read entry point is Cardelli and Wegner "On understanding data 
types, abstraction and polymorphism" 
http://citeseer.ist.psu.edu/cardelli85understanding.html

cheers,
Burak

-- 
Burak Emir

http://lamp.epfl.ch/~emir

# P T Withington (19 years ago)

On 2006-09-06, at 10:24 EDT, Dave Herman wrote:

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());

[...]

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.

It seems to me that the compiler has to do a fair bit of inferencing
to avoid runtime type-checks or casts in either case. It has to
infer the actual type of the expression new List and make sure it
is a subtype the declared type of ls, it has to determine if that
inferred type is sealed, so that it can choose the appropriate method
that ls.head will actually bind to, and it has to determine the
return type of that method and make sure it is a subtype of the
declared type of x.

What the parametric case does for the compiler is that the programmer
explicitly declares that the collection is going to have elements of
a uniform type, which would be pretty difficult to infer.

A question I always like to ask is: does this language construct
make the programmer's job easier, or does it make the compiler- writer's job easier? (Given the hope that there will be many more
programs than compilers, I favor the former.) Presumably the non- parametric case can also be written:

var ls = new List(...); var x = ls.head();

which sure makes the programmer's job easier.

Does it make the compiler-writer's job harder? I'm not sure. The
compiler can still infer the type of ls, figure out if it is sealed,
and determine the return type of the applicable method. But
depending on how x is used later in the program, the compiler may
actually not have to do any of this work, since it does not have to
determine if the actual types of the rhs expressions match the
declared types of the lhs, since there are none. (I realize that
work might be worthwhile to enable optimizations.)

On 2006-09-06, at 10:24 EDT, Dave Herman wrote:

> 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());

[...]

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

It seems to me that the compiler has to do a fair bit of inferencing  
to avoid runtime type-checks or casts in either case.  It has to  
infer the actual type of the expression `new List` and make sure it  
is a subtype the declared type of `ls`, it has to determine if that  
inferred type is sealed, so that it can choose the appropriate method  
that `ls.head` will actually bind to, and it has to determine the  
return type of that method and make sure it is a subtype of the  
declared type of `x`.

What the parametric case does for the compiler is that the programmer  
explicitly declares that the collection is going to have elements of  
a uniform type, which would be pretty difficult to infer.

A question I always like to ask is:  does this language construct  
make the programmer's job easier, or does it make the compiler- 
writer's job easier?  (Given the hope that there will be many more  
programs than compilers, I favor the former.)  Presumably the non- 
parametric case can also be written:

   var ls = new List(...);
   var x = ls.head();

which sure makes the programmer's job easier.

Does it make the compiler-writer's job harder?  I'm not sure.  The  
compiler can still infer the type of ls, figure out if it is sealed,  
and determine the return type of the applicable method.  But  
depending on how x is used later in the program, the compiler may  
actually not have to do any of this work, since it does not have to  
determine if the actual types of the rhs expressions match the  
declared types of the lhs, since there are none.  (I realize that  
work might be worthwhile to enable optimizations.)

# Graydon Hoare (19 years ago)

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?

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

# Peter Hall (19 years ago)

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

Not true. When you create an instance of the parametric container class, you will choose either Ducks or Artichokes to be the type of objects stored in the list. This means you will never be comparing Ducks to Artichokes unless one happens to extend the other...

var duckList:SortableList.<Duck> = new SortableList.<Duck>();

Peter

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

Not true. When you create an instance of the parametric container
class, you will choose either Ducks or Artichokes to be the type of
objects stored in the list. This means you will never be comparing
Ducks to Artichokes unless one happens to extend the other...

var duckList:SortableList.<Duck> = new SortableList.<Duck>();


Peter

# Graydon Hoare (19 years ago)

Peter Hall wrote:

Not true. When you create an instance of the parametric container class, you will choose either Ducks or Artichokes to be the type of objects stored in the list. This means you will never be comparing Ducks to Artichokes unless one happens to extend the other...

Oh sure, but the compiler can't prove any of that. You still have to implement Duck.lessThan using a dynamic type check on the argument. The implementation of SortedList.<Duck> may, in fact, apply Duck.lessThan to

an Artichoke. You have no way of knowing, it's statically unchecked.

Anyways, that just gives way to the second implementation -- that the compiler can prove some stuff about -- and in that case it has its own problems, as I pointed out.

Peter Hall wrote:

> Not true. When you create an instance of the parametric container
> class, you will choose either Ducks or Artichokes to be the type of
> objects stored in the list. This means you will never be comparing
> Ducks to Artichokes unless one happens to extend the other...

Oh sure, but the compiler can't prove any of that. You still have to 
implement Duck.lessThan using a dynamic type check on the argument. The 
implementation of SortedList.<Duck> may, in fact, apply Duck.lessThan to 
an Artichoke. You have no way of knowing, it's statically unchecked.

Anyways, that just gives way to the second implementation -- that the 
compiler *can* prove some stuff about -- and in that case it has its own 
problems, as I pointed out.

-graydon

# Nicolas Cannasse (19 years ago)

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.

Yes, I agree with your point. But this is somehow an expected behavior since overriding a method is intended to redefine a behavior.

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.

Again, i'm not such a fan of interfaces, and in a functional world you would tell the "right way" of doing things. I'm also convinced that the functional approach is more flexible and powerful, my original thoughts where based on the fact that I didn't know that ES4 will have structural functional types, which would have make things harder. BTW updating the wiki with more up-to-date material would be nice ;)

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?

Not easy one. I've been using the feature a few times in the haXe standard library, but more often to express architecture constraints than to provide an API. But the library is quite small and does not try to be a "framework".

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

Yes, I agree with your point. But this is somehow an expected behavior
since overriding a method is intended to redefine a behavior.

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

Again, i'm not such a fan of interfaces, and in a functional world you
would tell the "right way" of doing things. I'm also convinced that the
functional approach is more flexible and powerful, my original thoughts
where based on the fact that I didn't know that ES4 will have structural
functional types, which would have make things harder. BTW updating the
wiki with more up-to-date material would be nice ;)

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

Not easy one. I've been using the feature a few times in the haXe
standard library, but more often to express architecture constraints
than to provide an API. But the library is quite small and does not try
to be a "framework".

Nicolas