Why is Dart not supporting both covariant and contravariant

[Samuel Hapak]

The following article discuss covariance and contravariance in the Dart:

https://www.dartlang.org/articles/why-dart-types/#why-are-generics-covariant

My question is simple, why

List<String> is List<Object>

but not

List<Object> is List<String>

?

I mean, why don't make both of these expressions true? It would be pretty compatible with Dart types "optimistic" approach to types.

What do you think?

[Cogman]

Someone can correct me if I'm wrong, but I believe it has some limited support for contravariance.  The case of List<dynamic> is List<String> is true (and really about the only level of contravariance that you would want to support).

List<Subtype> is List<Type> should be false, IMO, after all, the next step is almost always (List<Type>)subTypeList, which would be bad if the subtype list wasn't made up completely of Type.

--
For other discussions, see https://groups.google.com/a/dartlang.org/
 
For HOWTO questions, visit http://stackoverflow.com/tags/dart
 
To file a bug report or feature request, go to http://www.dartbug.com/new

To unsubscribe from this group and stop receiving emails from it, send an email to misc+uns...@dartlang.org.

[Peter Ahé]

Having covariant (or contravariant) generic type arguments is not sound.

However, this doesn't seem natural to most programmers, instead, they
assume that generics are covariant.

So we chose to have semantics that match what we think most
programmers expect, but still try to maintain some form of type
system.

Cheers,
Peter

[Bob Nystrom]

On Thu, Nov 14, 2013 at 9:56 AM, <dangli...@gmail.com> wrote:

>> However, this doesn't seem natural to most programmers, instead, they assume that generics are covariant. 

Are you sure for the most programmers?

I'm sure. Look on StackOverflow and you'll find hundreds of questions from Java and C# developers confused that their generic types aren't naturally covariant. The set of people who actually understand variance is astonishingly small.

- bob

[Peter Ahé]

Both declaration site and use-site variance is sound (they proved
wildcards are sound in
http://homepages.inf.ed.ac.uk/wadler/fool/program/final/14/14_Paper.pdf).
If you need a gentler introduction to wildcards, look at this:
http://www.jot.fm/issues/issue_2004_12/article5/. Mads Torgersen was
instrumental in working out the theory behind wildcards, and he now
works for Microsoft on C#. If he hasn't already published a paper
demonstrating that C#'s declaration-site variance is sound, he is
either working on that paper in his free time, or it follows trivially
from another paper.

However, simply making type arguments covariant (or contravariant) is
not sound. This is why Java and C# impose additional restrictions.
Dart does not, and instead rely on checked mode for helping you find
bugs.

On Thu, Nov 14, 2013 at 6:56 PM, <dangli...@gmail.com> wrote:
>>> Having covariant (or contravariant) generic type arguments is not sound.
>

> You not take into account mainstream languages such as Java and C#.
> The variance of type constructors.
>
> Declaration-site variance annotations (C#): the programmer annotates the
> definition of a generic type with the intended variance of its type
> parameters.
> Site variance annotations (Java): the programmer instead annotates the
> places where a generic type is instantiated.
>
> Declaration-site variance annotations:
> C# (using the keywords out and in), and Scala using the keywords + and -).
>
> In C#, each type parameter of a generic interface can be marked covariant
> (out), contravariant (in), or invariant (no annotation).
>
> Site variance annotations:
> Java provides use-site variance annotations through wildcards.
> A parameterized type can be instantiated by a wildcard ? together with an
> upper or lower bound, e.g. List<? extends Animal>.
>
> A wildcard type like C<? extends T>, there are three ways to form a subtype:
> by specializing the class C, by specifying a tighter bound T, or by
> replacing the wildcard ? by a specific type.
>
> The Dart language specification states.
> The type system is unsound, due to the covariance of generic types.
>
> Where practical proof that this statement is true?

List<int> ints = <int>[];
List<Object> objects = ints;
objects.add("a string");
int i = ints[0]; // Problem i is a String, not an int.

This program doesn't give a type warning, and only fails in checked
mode. Consequently, (if you ignore checked mode) the static type
system is unsound. Just like Java's covariant arrays aren't sound:

Integer[] ints = new Integer[1];
Object[] objects = ints;
objects[0] = "a string";
Integer i = ints[0];

This program throws a runtime error (ArrayStoreException), precisely
because covariance is unsound.

In reality most mainstream programming languages have unsound type
systems, because casts aren't statically sound. Dart embraces this
fact and does not use the static type system for optimizations, and
offer checked mode to help you find bugs. This both makes Dart safer
than Java, and easier to use.

>>> However, this doesn't seem natural to most programmers, instead, they
>>> assume that generics are covariant.
>

> Are you sure for the most programmers?

My experience include implementing wildcards in javac, being tech-lead
of javac at Sun (now Oracle), engaging javac's users (through bug
reports, conferences, and online forums), and using this experience to
advice my colleagues on solving type problems in Java. Based on this,
I conjecture that most programmers find it natural to assume
covariance. I cannot back this up with research.

Cheers,
Peter

[Peter Ahé]

I'm not sure I understand your question.

Are you asking: "Why doesn't Dart have a form of variance notation?"

The answer is that we want to keep things simple. The goal of the Dart
type system is not to be statically sound. It is to document intent.
This is different from most static type systems that you know,
especially from Java and C#. This doesn't mean that Dart is unsafe, it
just means that you cannot make optimizations based on type
annotations.

As we're keeping things simple (and not adding any variance
annotations), we have to pick a default to answer this question:

What does "class G<T> {...}" mean?

Unconventionally, we have decided that this means some like this in
C#: "interface G<in T> {...}". In other words, all type parameters in
Dart are covariant.

However, we do not disallow methods like GetInput, SetOutput, etc.
This isn't a sound, so we say that. We're doing it this way because we
think it is easier for people to express their intent and then see
concrete examples of when it doesn't work (in checked mode).

We understand that there are different ways to do things, and we
understand that most people with a strong background in type theory
would like to see a more powerful type system. But we don't think the
majority of our intended audience would be comfortable with a more
powerful type system.

Cheers,
Peter

On Fri, Nov 15, 2013 at 10:28 AM, <dangli...@gmail.com> wrote:
> I found that this your main argument that "Dart does not, and instead rely
> on checked mode for helping you find bugs." is not a serious.
> It is very wrong conclusion.
>
> Why you cannot just say that you do not want or can not do this?
>
> Look at this example in C# that does not follow the Dart Team arguments and
> still helping not only finding the bugs but also helping to write code
> without bugs.
>
> +++++++++++++++++
> interface IVariant<out TOutput, in TInput> {
> // These methods works
> TOutput getOutput();
> void SetInput(TInput sampleArg);
> TOutput GetOutputSetInput(TInput sampleArg);
>
> // And these don’t.
> // TInput GetInput();
> // void SetOutput(TOutput sampleArg);
> // TInput GetInputSetOutput(TOutput sampleArg);
> }
> +++++++++++++++++
>
> I look forward to your response.

[Peter Ahé]

On Fri, Nov 15, 2013 at 1:49 PM, <dangli...@gmail.com> wrote:
>>> This doesn't mean that Dart is unsafe,
>

> I Dart all works fine.

>
>
>>> What does "class G<T> {...}" mean?
>>> Unconventionally, we have decided that this means some like this in C#:
>>> "interface G<in T> {...}". In other words, all type parameters in Dart are
>>> covariant.
>

> You not understand me. In C# you can apply generic modifier (in and out)
> only to interfaces but not to classes.
> This means not as you say but this means that "class G<T> {...}" is not the
> same as "interface G<in T> {...}".
> This means that in Dart "class G<T> {...}" is the same as in C# "class G<T>
> {...}".
> But in C# "interface G<in T> {...}" means that Dart does not have.
> In C# for generic type parameters, the "in" keyword specifies that the type
> parameter is contravariant.
> But you say "In other words, all type parameters in Dart are covariant like

> this in C#: "interface G<in T> {...}"

Yes. I got it wrong. What I should have said was:

What does "class G<T> {...}" mean? Unconventionally, we have decided

that this means something like this in C#: "interface G<out T> {...}"

It should have been "out" (covariance), not "in" (contravariance).

I didn't get class vs. interfaces wrong, this is because in Dart, each
class implies an interface (that you can implement), and when you're
discussing Dart types, only these interfaces matter. This is why a
class declaration in Dart is more similar to an interface declaration
in Java or C# when we are discussing types.

If, in C#, I have:

interface A {}
interface B {}
interface G<out T> {}

G<B> is a subtype of G<A>. This is because G.T is covariant (it is
explicitly declared covariant with the "out" annotation).

Similarly in Dart:

class A {}
class B {}
class G<T> {}

G<B> is a subtype of G<A>. This is because G.T is covariant (all type
parameters in Dart a covariant).

We could extend the Dart language with declaration-site variance
annotations (but the default is covariance):

class H<in T> {} // T is contravariant, similar to interface H<in T> {} in C#.
class I<T!> {} // T is invariant, similar to interface I<T> {} in C#.

In this case, we could say that H<A> is a subtype of H<B> and that
I<A> is not related to I<B> by subtyping. But as I mentioned before,
this is more complexity than we felt would be necessary.

Cheers,
Peter

>
> C#
>
> // Contravariant interface.
> interface IContravariant<in A> { }
>
> // Extending contravariant interface.
> interface IExtContravariant<in A> : IContravariant<A> { }
>
> // Implementing contravariant interface.
> class Sample<A> : IContravariant<A> { }
>
> class Program
> {
> static void Test()
> {
> IContravariant<Object> iobj = new Sample<Object>();
> IContravariant<String> istr = new Sample<String>();
>
> // You can assign iobj to istr because
> // the IContravariant interface is contravariant.
> istr = iobj;
> }
> }
>
>
> Also, in C# generic modifier means the following (because it specifies
> contravariance).
>
> You can declare a generic type parameter contravariant by using the in
> keyword. The contravariant type can be used only as a type of method
> arguments and not as a return type of interface methods. The contravariant
> type can also be used for generic constraints. The following code shows how
> to declare a contravariant interface and use a generic constraint for one of
> its methods.
>
> C#
> VB
>
> interface IContravariant<in A>
> {
> void SetSomething(A sampleArg);
> void DoSomething<T>() where T : A;
> // The following statement generates a compiler error.
> // A GetSomething();

[Peter Ahé]

On Sun, Nov 17, 2013 at 11:57 AM, <dangli...@gmail.com> wrote:
>>> We could extend the Dart language with declaration-site variance
> annotations (but the default is covariance):
>

> I think is more important to add support of generic type parameters in
> function.

I'm strongly opposed to that.

I understand that some people find generic methods useful, but I think
an overwhelming majority of developers find them quite complicated and
have a hard time using them correctly. Supporting generic methods well
would have a huge impact on the VM implementation and performance, and
personally I don't think generic methods are useful enough to warrant
this extra cost. I hardly think adding generic types to Dart in the
first place was worth the cost.

> As far as I know the "Function" interface currently in Dart not a generic
> type.
>
> That means that this is not compiled in Dart.
> Function<TRet>
> Function<T1, TRet>
>
> If you want add support into language type parameters in function then you
> must know that in C# delegates are contravariant in their argument types.

That is the sane approach from a pure type theoretical point of view.
Function types are fundamentally contravariant in their argument types
(and covariant in their return types).

In Dart we chose to make function types unsound by making them both
covariant and contravariant in their argument types and return types.
This is not sound, but again we felt it was better to leverage checked
mode than to bother developers with complex type theory.

Cheers,
Peter

> void takeHippopotamus(Hippopotamus h) {}
> void takeAnimal(Animal a) {}
>
> Action<Animal> action1 = takeHippopotamus; // illegal
> Action<Animal> action2 = takeAnimal; // legal
>
> Why is the first assignment illegal?
> Because the caller of "action1" can pass a "Leopard", but "takeHippopotamus"
> cannot take a "Leopard", only a "Hippopotamus"!
> The second assignment is legal because "takeAnimal" can take any "Animal".

[Gen]

<< Supporting generic methods well
<< would have a huge impact on the VM implementation and performance

What do you mean with "well supported" ?
What are the reasons for the complications at runtime ?
Generics and static types are static constraints.
They should be used to simplify and constrain the runtime and not to complicate it.

[Peter Ahé]

On Sun, Nov 17, 2013 at 12:38 PM, Gen <gp78...@gmail.com> wrote:
> << Supporting generic methods well
> << would have a huge impact on the VM implementation and performance
>
> What do you mean with "well supported" ?

I assume that most people are really asking for generic methods whose
type arguments are inferred.

For example, in Java you can write:

java.util.List<String> strings = java.util.Collections.emptyList();

You don't have to explicitly pass type arguments to the generic method
"java.util.Collections.emptyList", and most people don't know how to
do so:

java.util.List<String> strings = java.util.Collections.<String>emptyList();

> What are the reasons for the complications at runtime ?

First you have to pass the generic type arguments. They are real
arguments to a method.

Secondly, you'd have to infer the type arguments. At runtime in the
VM. Based on what? Static types? Then the VM has to include a full
type checker and be able to track types of non-local elements.

> Generics and static types are static constraints.

Generic type arguments are not only static constraints, they are also
available at runtime, and the VM cannot ignore them. For example,
generic type arguments are preserved and can be used in "is" and "as"
tests. They are also used by checked mode, and using dart:mirrors you
can directly read their values.

> They should be used to simplify and constrain the runtime and not to
> complicate it.

In practice, my experience is that generics only adds complexity.

Cheers,
Peter

[Peter Ahé]

I'm not sure I understand your point? Are you saying that "complexity
in implementation is not a reason to not provide features to users?"

Cheers,
Peter

On Sun, Nov 17, 2013 at 12:33 PM, <dangli...@gmail.com> wrote:
>>> I'm strongly opposed to that.
>

> These things I have always criticized and will continue to do so.
>
> Labour has made of the monkey man.
>
> Basically is no such problem that cannot be be solved if you know how to
> solve it, or you know for certain that it is not impossible and does not
> require a disproportionate cost to solve these problem.

[Peter Ahé]

On Sun, Nov 17, 2013 at 1:03 PM, <dangli...@gmail.com> wrote:
>>> I understand that some people find generic methods useful, but I think
> an overwhelming majority of developers find them quite complicated and
> have a hard time using them correctly. Supporting generic methods well
> would have a huge impact on the VM implementation and performance, and
> personally I don't think generic methods are useful enough to warrant
> this extra cost. I hardly think adding generic types to Dart in the
> first place was worth the cost.
>

> It is not required to big modifications in VM because generic already in
> Dart reified.

That is not correct. If you don't understand something, please ask for
more details.

> Disadvantage only in overhead of performing runtime checks of generic type
> parameters.

That is not correct. There is overhead in passing type arguments to
methods, but yes, that is a consequence of having to support runtime
checks ("is", "as", and checked mode).

> But want you want? This problem not related to Dart language only.
> This is not present as such only Java. Generic type information in Java
> erased at rumtime.

Yes. That is one solution. However, I believe this is a fundamentally
flawed approach to generics as it creates two type systems that the
programmer has to understand. In my experience, these two type systems
are a source of confusion to a vast majority of Java programmers.

> But in in C # also performed additional checks at runtime but not only on
> compile time.
> This is the cost of geneirics in worldwide.

As C# is a language that is compiled ahead-of-time by a compiler, some
complexities can be handled at compile time without affecting the CLR.

That is not the case in Dart. In Dart, your program is compiled
directly by the VM, and every feature we add must be implemented in
the VM.

> What hardest in that you to reverse type checking direction from covariance
> to contravariance if type will be Function?
>
> Pseudo C++ but in Dart
>
> var destType = someType;
> var obj = someObj.
> var srcType = obj.type.
> var parametersVariance = Variance.Covariance;
> if(obj is Function) {
> parametersVariance = Variance.Contravariance;
> }
>
> checkTypeParameter(destType.parameters, srcType.parameters,
> argumentsVariance);
>
> I not found this code hard.

I don't see how this is relevant to generic methods. Do you think
adding type parameters to the Function class is a generic method? In
that case, we're not talking about the same thing.

I'm talking about generic methods, for example, as they appear in Java:

public class Foo {
public static <T> T m(T argument) { ... }
}

In this case, the method Foo.m is generic because it has a type
parameter (T). We say that a class is generic when it has type
parameters, for example, class List<E> { ... } is a generic class
because it has a type parameter (E). In general, we say foo is generic
if it has type parameters. Sometimes, we also say "parameterized" or
"polymorphic". However using the words "polymorphic" or "polymorphism"
is a bit confusing as all methods and classes are polymorphic in a
more fundamental way.

At runtime, a type parameter to a method is like any other parameter
to a method, and it needs to have a value (in Java they avoid passing
this extra argument due to erasure). The big problem is that most
programmers don't want to specify this extra value explicitly. They
insist on the compiler inferring this value for them, for example,
using Java syntax:

Foo.m("a string"); // This is preferred (value for T inferred by
compiler to be String).

Foo.<String>m("a string"); // This is hated (value for T explicitly
passed by user).

This leads to very complex rules that users of a programming language
have a hard time understanding, and that implementors of a programming
language have a hard time understanding, specifying, and implementing.

So the fundamental question is: if we added generic methods to Dart,
would this be in the best interest of all our users? No, in my
opinion.

Cheers,
Peter

[Gen]

Thanks for the quick reply.

I think about generics more like templates in C++.
So no runtime overhead.
Just static constraints and a complicated static typecker.

As I understand, the design of Dart takes or would take all that complexity into the runtime for dynamic manipulation.

[Gen]

I am quite a Dart beginner and have much less experience than you have; at least with Dart.

 

As I have understood Peter's explanations and your intentions:

- "is" and "as" would have to take type parameters/arguments dynamically into account

- mirrors would have to take type parameters/arguments dynamically into account

All info should be available at runtime.

 

Are additional runtime type info and checks difficult and expensive for programmers and the VM ?

I have to trust the experts in the Dart team; the Dart VM it is not their first (world class) VM.

For now I have no use for (expensive) runtime type info.

 

Am Sonntag, 17. November 2013 15:14:46 UTC schrieb dangli...@gmail.com:

>> As I understand, the design of Dart takes or would take all that complexity into the runtime for dynamic manipulation.

Not.
The overhead only when check type parameters.
I am trying write example. In two hour possible to write all required type checks.
But i have problem for writing this in Dart  language 1.0.
:-()

I cannot continue to write in Dart because I have these troubles.
1.
This code can be compiled in Dart
action is _Function <int, int>

But this cannot be compiled
var action = _Function <int, int>;

Of course, this is a syntax error. But I have question to Gilad Bracha:
"Where in Dart 'typeof'"?

var type = typeof (_Function <int, int>);
typeCheck (type);

How to pass as parameters generic types in Dart?

2.
Another problem.
Mirrors not support generic type parameters and arguments.
I was not successful.

P.S.
Conclusion.
So not worry about complexity.
Not so complex and without big overhead.
If something as me (just a guy from vilage. humor) can write prototype in a few hours that means that the Dart VM can be refactored in few days.
Overhead not so significant judging by what I've managed to write in my unfinished prototype.

Some work only in requirements to refactor concept of functions in Dart.
Instead of just this "legacy" interface.

abstract class Function {}

Required that all "new" generic function implements these interfaces.


class Function1<TRet> implements Function {
}

class Function2<T1, TRet> implements Function {
}

And so on to "FunctionN", where N is natural number that specifies "maximun -1" number of parameters that generic functions can have. My be 25?
And also (by default, that I am trying wrote in my prototype) all arguments are contravariant and return type parameter covariant.

Also modifier "in" not required to be implemented in Dart before this work.
This is redundant because generic methods directly implements "Function".

abstract class Function2<in T1, TRet> implements Function {
}

This rule can be described in language specification.
If the type implements "Function" and defines type parameters then the last type parameter is covariant and the rest of all other are contravariant.

[Gen]

<< >> All info should be available at runtime.

I guess, this is what you want.

 

<< I urge you did the opposite opinion?

Maybe I do not understand what you mean by that.

Peter claims things become much more complicated and expensive.

You claim there is not much additional work and overhead for complete generic support. 

I can not judge because I have not the required knowledge and understanding.

 

<< >> For now I have no use for runtime type info related overhead.

I do not need runtime type information for my current purposes.

 

But as Dart seems to require so much type information and checks anyway,

I do not know what to say about full support of generic features.

 

Am Sonntag, 17. November 2013 17:16:58 UTC schrieb dangli...@gmail.com:

>> - "is" and "as" would have to take type parameters/arguments dynamically into account

The "type test" expression use the same unified runtime type check that used internally for all type check.
There is no difference who and where performed type check.

>> mirrors would have to take type parameters/arguments dynamically into account

Ask this question to Gilad Bracha. Dart has version 1.0 but mirrors still not fully implemented.
Also I can say that mirrors in Dart is not an externally implemented. They based on VM implementation.
Still the bridge to VM is not implemented carefully.

>> All info should be available at runtime.

Any information ALWAYS available at runtime if it not erased.
Another problem in that the not all information can be stored in ready for immediate use form.
A good example of this case is a operations of typecheck. They always required some computations.

>> Are additional runtime type info and checks difficult and expensive for programmers and the VM ?

No. Try this example. Also read comments in code

main() {
  // You will have exception when invoke this function.
  // Is this expensive for programmers and the VM?
  foo(1);
}

foo(String s) { // Breaking on exception: type 'int' is not a subtype of type 'String' of 's'.
}

Another example.

main() {
  int i  = 0;
  String s = "";
  // Is this expensive for programmers and the VM?
  // type 'String' is not a subtype of type 'int' of 'i'.
  i = s;

}

>> I have to trust the experts in the Dart team; the Dart VM it is not their first (world class) VM.

I urge you did the opposite opinion?

>> For now I have no use for runtime type info related overhead.

Not understand. Google language translator is not good here.
Please explain this problem in more detail.

P.S.

Runtime type check just a calculations.
Example based on "mirrors" but in practice this very fast because used native comparison of pointers in C++.

mov eax, [ebp+32] // current_type
mov edx, [ebp+36]  // base_type
cmp eax, edx
je return_true
lea edi, ebp+32+intrefaces
mov ecx, [ebp+32+intrefaces_count]
rep scasd

etc

static bool _testSupertype(ClassMirror fromClass, ClassMirror toClass, [Variance variance = Variance.COVARIANCE]) {
    if(variance == Variance.INVARIANCE && toClass != fromClass) {
      return false;
    }

    ClassMirror current = fromClass;
    if(variance == Variance.CONTRAVARIANCE) {
      var temp = toClass;
      toClass = fromClass;
      fromClass = temp;
      current = temp;
    }

    while(true) {
      if(current == toClass) {
        return true;
      }

      for(var interface in current.superinterfaces) {
        if(interface == toClass) {
          return true;
        }
      }

      current = toClass.superclass;
      if(current == OBJECT) {
        break;
      }
    }

    return false;
  }
}

[Peter Ahé]

On Sun, Nov 17, 2013 at 1:38 PM, Gen <gp78...@gmail.com> wrote:
> Thanks for the quick reply.
>
> I think about generics more like templates in C++.
> So no runtime overhead.

I guess there is a caveat: Templates can blow up the size of your
binary as each template must be compiled separately for each
parameterization. I'm sure it is possible to construct scenarios where
that impacts runtime performance. But if you're careful, templates add

no runtime overhead.

> Just static constraints and a complicated static typecker.
>
> As I understand, the design of Dart takes or would take all that complexity
> into the runtime for dynamic manipulation.

Yes. And that often leads to poor start-up performance. For example,
consider Java Applets. Each time an applet starts, its code must be
run through the byte code verifier (which essentially is a static type
checker). During this step, the application is unresponsive.

For this reason, we are very careful about what we ask the VM to do
during startup and when it is compiling methods. The faster the VM can
start executing main, the faster you get in control and can make fast
awesome applications.

[Thomas Stephenson]

Sometimes I'd prefer generic methods, purely for documentation purposes when you'd like a bound on the type

For instance, on the Iterable interface, I'd prefer to write

T fold<T>(T initialValue, T combine(T current, E element)

rather than
dynamic fold(dynamic initialValue,
                        dynamic combine(dynamic current, E element))

(in real code, dropping the dynamic annotation, since inferred) because it makes it clear that the return type is determined by the initialvalue and combine arguments and makes it clear that they expect the same type.

It's only a marginal improvement over the current type signature though. Fold is a bad example, because you should have an intuitive notion of what it does, but in my own code, but I think generic methods are an improvement in the presence of higher order function arguments.

Also, generic methods play nicely with top level functions. At the moment, the only way to write

listExtensionMethod(List<E> list, E arg)
is to ignore both the list generic and argument type.

At the call site, I wouldn't bother actually calling the method with the generic type, so generic methods in dart would be a documentation only feature (even checked mode could only check if the argument types had a common base type -- which is always true).

But again, not a real improvement. As for variance, I like the implicit covariance. It makes sense considering the spirit of the type system in dart.

[Thomas Stephenson]

tl;dr provide generic method type signatures but no way of calling a generic method with a specific type argument

[Kevin Moore]

Can't hurt to start this issue: https://code.google.com/p/dart/issues/detail?id=254

Support declaration of generic type for methods

[Kevin Moore]

I'd love someone to start this issue. In the mean time, star it. :-)

[Thomas Stephenson]

>> This function always return T or null.

>> >> T fold<T>(T initialValue, T combine(T current, E element)

No, that's a misunderstanding of the point of optional types. That declaration makes it clear that the initialValue is supposed to be of type T and the function is supposed to take a value of type T and one of the elements of the iterable and return a type T. Whether it actually does what it says or not is dependent on the implementation. 

>> But return type of this function not depends on the initialvalue.
>> >> fold(initialValue, combine(current, element);

Again, yes it does depend on it, because (hopefully) the implementation of the method in the built-in Iterable class will always return a value of the type T (or null). If the method is overriden with another implementation, then it could return anything, just like the (generic) function could. The difference is that in the second case the type signature gives you no indication that this will be the case.

Also @Kevin Moore:

I've starred it and will add a comment with my own opinions on the issue when I'm finished this.

On 18 November 2013 16:10, <dangli...@gmail.com> wrote:

>> Sometimes I'd prefer generic methods, purely for documentation purposes when you'd like a bound on the type

Not only you.

>> (in real code, dropping the dynamic annotation, since inferred) because it makes it clear that the return type is determined
by the initialvalue and combine arguments and makes it clear that they expect the same type.

Your statement "return type is determined by the initialvalue" is not true.

1.
This function always return T or null.

T fold<T>(T initialValue, T combine(T current, E element)

2.
But return type of this function not depends on the initialvalue.
fold(initialValue, combine(current, element);

In first case it is guaranteed by the programming language.
In first case you may only rely on the documentation or on the correctness of the algorithm that result will that you expect.

That's the beauty generic functions. They are predictable.

понедельник, 18 ноября 2013 г., 10:35:39 UTC+6 пользователь Thomas Stephenson написал:

[Gen]

I want more than just intentions.
I want a type system that enforces constraints.

I would like to choose one of 3 "type cases" per variable and parameter:
- untyped: Untyped like in real dynamic languages Javascript or Ruby.
- some static type
- some static type and immutable
Maybe a 4th case too: some static type and not nullable.

The typesystem forbids to pass untyped arguments to typed parameters of (maybe compiled) functions.
No way to dynamically cast and smuggle untyped objects into typed code.

I can imagine 2 ways how to handle the passing of typed arguments to untyped parameters:
- Either do dynamic type checks and throw dynamic errors.
- Or forbid it statically.

I prefer to forbid it statically:
- Static typesafety is want I want when I use static types.
- It allows better code optimizations.
- It allows typesafe interaction with (maybe compiled) code written in other languages.
- It could enable method overloading.

Untyped objects can have statically typed members.
The VM tracks dynamically the type of objects if required by the program or function.
Then "is" checks allow to detect such typed members and use them as arguments for typed parameters.

I guess, another "checked mode" for the above type system could be added to Dart.

[Jeremy Bell]

I'm somewhat late to the discussion, so I apologize for resurrecting an old thread. 

I'm not an expert in type theory, or language design, by any means. But I've been at this whole programming thing for a while now (gosh, has it really been 15+ years?), and thought I'd chime in.

To be perfectly honest, I just plain disagree with the arguments made by the Dart team with regards to generics, and unsoundness in general:

1) Most programmers don't understand co/contravariant type arguments. So we'll just make them work the way most people expect them to work, even when that is not sound.

My response: So what if most programmers don't understand variance? One in four people in America think the sun rotates around the earth. That doesn't make it true. Also, I sometimes tutor students from my old high school who are interested in computer science. I haven't yet met a student who wasn't able to properly grasp the concepts of variance after some explanation. Why is variance different than any other particularly tricky aspect of programming that everyone just needs to learn and move on? It's not actually that difficult. The kids I've tutored had more trouble with basic boolean algebra and algorithmic complexity than with variance. 

2) Dart's type system is unsound, and we are unapologetic about this. Types in Dart are meant for documentation. Of course we have this checked-mode thing that will throw an error at runtime.

My response: With all due respect, this is nonsense. Types are constraints. They are meant to be enforced, one way or the other. There is no real point to them otherwise. In fact, if they are not enforced, or especially if they are too loosely enforced, then types are counterproductive. They make the programmer (ESPECIALLY the inexperienced kinds of programmers that Dart seems to be targeted towards) believe things that are not true, such as that Dog object arguments are actually Dogs and not Cats or Insects. Also, a type check is a type check, and you've gained nothing by moving the type check to the runtime. If you can detect an error before it happens, how does it serve the programmer to ignore the error until the code runs? It doesn't.

3) Type arguments on methods increases overhead as you have to pass the type argument as an actual argument to the function.

My response: Ok, this is getting into the details of VM implementation, which is beyond my expertise, but is this really necessary? I would have thought it was only necessary for cases where you don't already have an instance of the type argument before you need the metadata. If you have an instance of T, then you can get any information you want by reflecting over the object instance. If you don't have an instance of T, then of course you would have to pass the type argument in. But, maybe have something that would trigger this to happen - for instance in Scala, you can't get runtime type information without an instance, unless you annotate your type like so: Foo[A: Manifest](var x: Int), which causes the compiler to add an implicit argument to the constructor (or method, or whatever) to pass along A's manifest. You don't pay that penalty unless you need it.

To be clear, I'm not saying Dart has to give up optional typing. I just think that, where and when typing is used, I think it should work correctly to help programmers not just with documentation, but in validating code against constraints as early as possible (in other words, not just at runtime when you have checked mode turned on). 

Cheers,

Jeremy Bell

Sleepy Daddy Software™

[Gen]

I think that variance is a very complicated topic. You might know about Liskov Substitution Principle.
The right implementation of classes, according to the typesystem, is neither easy nor obvious and can not be checked by tools.
How type safe is code that is not checked by tools ?

There is no universally perfect typesystem.
Almost all typed language have their own peculiar type system for peculiar reasons.

I think everyone agrees that static checks should be made where possible.
What can and should be statically enforced in Dart in addition to what is now ?
I do not know.
 
PS.
My opinion has changed since my last post.
I do not know anymore what I want and expect from Dart with regard to types.

[Anders Holmgren]

I agree this is a complex issue. I'm in two minds about the covariance issue. I can understand the desire to keep it simple and agree intuition is often right. But on the other hand I never like deferring till runtime things that can be caught earlier.

But, as I mentioned on another thread, by far the bigger issue for me is the loss of refactoring due to lack of generic methods. Particularly on absolutely core methods like Iterable.map

That's going to hurt a lot as codebases grow.

A

[Quildreen Motta]

On 17 February 2014 04:28, Jeremy Bell <bell....@gmail.com> wrote:

1) Most programmers don't understand co/contravariant type arguments. So we'll just make them work the way most people expect them to work, even when that is not sound.

My response: So what if most programmers don't understand variance? One in four people in America think the sun rotates around the earth. That doesn't make it true. Also, I sometimes tutor students from my old high school who are interested in computer science. I haven't yet met a student who wasn't able to properly grasp the concepts of variance after some explanation. Why is variance different than any other particularly tricky aspect of programming that everyone just needs to learn and move on? It's not actually that difficult. The kids I've tutored had more trouble with basic boolean algebra and algorithmic complexity than with variance. 

Well, Dart's type system is unsound by design, so whether variant type arguments make them unsound is not quite relevant :)

I'm particularly against subtyping polymorphism and variance in general, because they're too complicated. I much prefer the simplicity of invariant type arguments coupled with row polymorphism for structural types. But this is not the path the Dart team has followed (and if I remember correctly, Bob said Bracha's experience with structural types led to intractable error messages, which are not quite what one wants when writing a compiler).

Dart's design, as I understand, is catered for JavaScript and Java programmers, most of which are not overtly concerned with type soundness.

 

2) Dart's type system is unsound, and we are unapologetic about this. Types in Dart are meant for documentation. Of course we have this checked-mode thing that will throw an error at runtime.

My response: With all due respect, this is nonsense. Types are constraints. They are meant to be enforced, one way or the other. There is no real point to them otherwise. In fact, if they are not enforced, or especially if they are too loosely enforced, then types are counterproductive. They make the programmer (ESPECIALLY the inexperienced kinds of programmers that Dart seems to be targeted towards) believe things that are not true, such as that Dog object arguments are actually Dogs and not Cats or Insects. Also, a type check is a type check, and you've gained nothing by moving the type check to the runtime. If you can detect an error before it happens, how does it serve the programmer to ignore the error until the code runs? It doesn't.

I do agree that unsound type systems are less than ideal for people who are concerned about correctness, and can be misleading to people who are relying on it to enforce compositional constraints.