Type parameters

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

Type parameters

Peter Hall-2
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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Peter Hall-2
> 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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Graydon Hoare-3
In reply to this post by Nicolas Cannasse
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


Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Peter Hall-2
> > 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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Graydon Hoare-3
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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Nicolas Cannasse
In reply to this post by Peter Hall-2
> 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


Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Nicolas Cannasse
In reply to this post by Graydon Hoare-3
>>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



Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Dave Herman-2
[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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Peter Hall-2
In reply to this post by Graydon Hoare-3
> 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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Peter Hall-2
In reply to this post by Nicolas Cannasse
> > 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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Burak Emir
In reply to this post by Nicolas Cannasse
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


Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

P T Withington
In reply to this post by Dave Herman-2
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.)


Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Graydon Hoare-3
In reply to this post by Nicolas Cannasse
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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Peter Hall-2
> 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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Graydon Hoare-3
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

Reply | Threaded
Open this post in threaded view
|

Re: Type parameters

Nicolas Cannasse
In reply to this post by Graydon Hoare-3
>    - 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