> > No mutability anywhere, yet if you let Function be
> > covariant (which Scala does not do, I hasten to add),
> > you get a runtime error. I claim this is relevant in
> > practice because otherwise all your higher-order
> functions
> > are potential type holes.
>
> I see my error. I said mutability but what I really mean
> is that as long as you are not calling methods with
> covariant parameters and only using return values or
> otherwise only doing pulls instead of pushes, there are no
> issues with covariance.

Correct. And in that case you would naturally make your type parameters covariant. But for function arguments it really goes the other way round. How would you find a language where immutable collections such as Scala's lists are contravariant? I.e you could assign a List[Object] to a List[String] but not the other way round? You would find that a crazy idea, right? Yet for function parameters contravariance exactly as natural and correct as covariance is natural and correct for immutable collections. Making function parameters covariant is just as crazy as making immutable collections contravariant.

Cheers

-- Martin

> So, please, for the love of all that is good, please stop
> trying to make things into academic vs real world debates.
> It's disgusting. You don't see electrical engineers
> s running around saying "we don't use Ohm's law here, it's
> too academic."

There's a big difference between a physical law that has been confirmed innumerable times and the recommendations of computer scientists to programmers.

"It's disgusting"? That's a bit over the top, don't you think?

My father is a mechanical engineer with a masters in thermodynamics and has been working with Phd engineers on a special project recently. He tells me many stories of the problems the Phds cause by not understanding how theory and practicality can differ.

Martin,

I think that most people here understand that covariance of generic types isn't sound. The question is, is fixing that worth the complexity involved?

GScript has a separate class of types for function types, where argument types are contravariant and return types are covariant. This eliminates one big class of ugly problems with covariant generics. Is that enough? I think so, but then I don't do particularly complicated programming.

It is, of course, a judgement call. I think that if you look at how collections are used in practice in java (and, in particular, note that there wasn't a scourge of ClassCastExceptions before generics came along) you can come to terms with covariance. It isn't correct, but it is useful.

It is definitely a worse-is-better, simplicity-over-correctness argument, though.

Cheers,
Carson

> Correct. And in that case you would naturally make your
> type parameters covariant. But for function arguments it
> really goes the other way round. How would you find a
> language where immutable collections such as Scala's lists
> are contravariant? I.e you could assign a List[Object] to
> a List[String] but not the other way round? You would find
> that a crazy idea, right? Yet for function parameters
> contravariance exactly as natural and correct as
> covariance is natural and correct for immutable
> collections. Making function parameters covariant is just
> as crazy as making immutable collections contravariant.

I see that. But I'm still not convinced it's worth the extra complications. That it's 'wrong' doesn't invalidate the fact that, in practice, it works just fine for a lot of people.

My real problem with generics is not that it's difficult to understand covariance and contravariance. It's that it's hard to imagine how these declarations will affect what you can do with your APIs later.

Here's an example of this that I ran into with Java: I had an observer interface defined for component types. I then declared that the component type were generic in terms of the observer type. That is, they could have a specialized observers. This worked well for a while because all the observers were created with full knowledge of the generic type of the component. But then I ran into a situation where I wanted to add an observer to all components based on the basic observer interface. I was stuck. I couldn't do that because the generic type of the component was not known. What I wanted was for the method to be covariant and in the case that the observer was not the generic type, allow it to receive the basic notifications. This is what I ended up doing but I had to add a new method. I could not use the generic one. So while you think this is 'crazy' this is actually perfectly fine for my needs. Even in the case where I wouldn't be able to handle the mismatch, a runtime error would be fine.

> > I assume Map takes 2, List 1, and Func a return type
> plus 0 to many parameter types.
>
> That is correct - each one uses a custom syntax. For
> example Fan's List parametrization looks like the Java
> array syntax. Because generics are used with only
> built-in types, it allows Fan to easily maintain the
> parametrization at runtime for reflection. For example
> given a list of Str, the type signature would be Str[],
> and you could reflect this type from the list at runtime.
> That becomes important for meta-programming and
> d serialization.
>
Is List mutable or immutable? Sorry I can't seem to find something like a FanDoc on the website. Is there a URL of something like the Java API JavaDoc? The reason I ask is that this looks like the syntax for Java's arrays. So I'm curious if it is implemented using Arrays underneath, and if not, how do I use Java arrays in Fan? (Like if I have to pass an array to a pre-existing Java method.)

> > First, are these type parameters on Map, List, and Func
> treated as nonvariant, covariant, contravariant? Or some
> combination? I see no mention of variance in their
> documentation.
>
> Technically they are covariant similar to Java arrays
> (although from the setter method perspective that allows
> contravariance). But it is sort of moot issue in Fan.
> Fan is mostly statically typed, however the compiler only
> y flags type errors which are guaranteed to be never be
> correct - for example passing a Str where an Int is
> expected. However any type check which could pass at
> runtime will generate a synthetic cast to keep the JVM/CLR
> happy. For example passing a Num where an Int is expected
> doesn't require an explicit cast.
>
Can you give an example of a "type check which could pass at runtime that generates a synthetic cast?

> It seems sort of crazy, but it turns out to be a great
> compromise. Almost all type errors still end up getting
> caught at compile time, we get Java-like performance, yet
> it avoids all the nasty syntax that clutters up Java code.
> So Fan's philosophy has been to use the type system as a
> a useful tool whenever it makes sense, but break out of it
> whenever it gets into the way.
>
> > Also, what do people usually do when they want to make
> some other collection besides List or Map? Do they cast,
> or perhaps use the -> to invoke mehods dynamically on
> objects pulled out of collections?
>
> I actually have seen it done very much - most all the code
> I've seen just uses the built-in types. But you would
> basically design it to work with Obj just like the
> pre-generics Java collections. The difference is you
> don't actually do the casting (it gets done for you).
> Although I use -> for duck typing things myself too.
>
Ah, you do a kind of cast inference on the Obj type. I see that now in the docs. That's interesting.

> There's a big difference between a physical law that has
> been confirmed innumerable times and the recommendations
> of computer scientists to programmers.
>
You mean, logic is a recommendation by computer scientists to programmers?

> "It's disgusting"? That's a bit over the top, don't you
> think?
>
Frankly I have to side with James there. These discussions of academic vs practical are silly and annoying (and particularly funny in the context of Scala, since people seem to just disregard who's behind the language and what their practical credentials are).

We are doing ourselves a disservice as a field with these allusions. Engineering is defined as the application of science to a technical problem. If we feel it's cool to disregard or doubt science in computing we put ourselves on the same level as simple technicians, and we should not complain if we will in the future be paid on this level.

> Is List mutable or immutable? Sorry I can't seem to find something like a FanDoc on the website.

Lists can be mutable, readonly (shallow copy-on-write), or immutable (guaranteed to store immutable items). Fan has a first-class notion of immutability using the const modifier, and doesn't allow threads (actors) to share mutable state.

The "ro" and "toImmutable" methods are used on List/Map to convert. You can see the Fandoc for List at http://fandev.org/doc/sys/List.html.

> So I'm curious if it is implemented using Arrays underneath, and if not, how do I use Java arrays in Fan?

List is a class backed by an array (like ArrayList in Java). True Java arrays are accessed with the Java FFI: http://fandev.org/doc/docLang/JavaFFI.html#arrays.

> Can you give an example of a "type check which could pass at runtime that generates a synthetic cast?

Take a look at: http://fandev.org/doc/docLang/TypeSystem.html#implicitCasts.

> > There's a big difference between a physical law that
> has
> > been confirmed innumerable times and the
> recommendations
> > of computer scientists to programmers.
> >
> You mean, logic is a recommendation by computer scientists
> to programmers?

No. I didn't say anything like that.

> > "It's disgusting"? That's a bit over the top, don't
> you
> > think?
> >
> Frankly I have to side with James there. These discussions
> of academic vs practical are silly and annoying (and
> particularly funny in the context of Scala, since people
> seem to just disregard who's behind the language and what
> their practical credentials are).

Since when are 'silly' and 'annoying' synonyms for 'disgusting'?

If you are saying that people must believe whatever those with the proper credentials say, then I reject that outright. The lack of a piece of paper is not the lack of intelligence, ability or knowledge.

> We are doing ourselves a disservice as a field with these
> allusions. Engineering is defined as the application of
> science to a technical problem. If we feel it's cool to
> disregard or doubt science in computing we put ourselves
> on the same level as simple technicians, and we should not
> complain if we will in the future be paid on this level.

Language design is not a science. I studied Physics before I studied computer science and computer science is more like mathematics than it is like a hard science. Science requires falsifiable hypothesis. Logic is not science. If you feel you can propose such a hypothesis I'm open to it.

As a side note, is anyone else shocked that Java doesn't have ImmutableCollection, ImmutableList, ImmutableSet and ImmutableMap interfaces? They could be easily added with no backwards compatability issues and would make loads of API's much, much more obvious.

Cheers,
Carson

Hi Andrew,

> > I'm curious what the implication of assuming covariance
> > for type parameter is in practice?
>
> Eiffel allows covariant input parameters for methods.
> This approach is often "beaten up" by academic
> c researchers, but it always seemed to be intuitive to
> me.
>
I looked up Bertrand Meyer's rationale in his book Object-Oriented Software Construction. I have the 2nd edition from 1997. The reason is I was reading some older posts on this subject on Artima and found an old blog by Bruce Eckel that quoted him:

http://www.artima.com/weblogs/viewpost.jsp?thread=132041

What Meyers shows is a hierarchy with a class Skier with two subclasses, Girl and Boy. (It's a high school ski team going to a meet.) Skier has a method share that takes another skier, and is used to model which skier will share a room with which other skier during the event. So in Java it might look like:

abstract class Skier {
    abstract void share(other: Skier);
}

Then he wants to model a rule that only girls can share a room with girls, and boys can share a room with boys. So he says what you want to do in the subclasses is:

class Boy extends Skier {
    void share(other: Boy) { ... }
}
 
class Girl extends Skier {
    void share(other: Girl) { ... }
}

In Eiffel I think the subclass share methods override (actually implement, since it is abstract) the share method in Skier, because this kind of covariance of parameter types is allowed. In Java, the subclass share methods would overload the superclass one, and you'd be told that you still need to implement share(Skier) in the subclasses.

Meyers then later says, in a section entitled "polymorphic perversity", that "a harmful scheme is easy to make up," and gives this example (again translated to Java):

Skier s;
Boy b = new Boy;
Girl g = new Girl;
s = b;
s.share(g);

Sorry about the the one-char names, but that's what Meyer used. Basically, you assign a Boy to a variable of type Skier. You can then call share on that variable and pass in any Skier, because that's the parameter type of share in class Skier. Well, a Girl is a Skier, so I could pass a Girl to share a room with a Boy. Now what Meyer could have concluded about all this is "Cats and dogs living together! Mass Hysteria!" However, his take was:

With contravariance one would not have these problems: as you specialize the target of a call (s in this example), you would generalize the argument. Contravariance, as a result, leads to simpler mathematical models of the inheritance-redefinition-polymorphism mechanism. For that reason a number of theoretical articles have advocated contravariance. But the argument is not very convincing, since, as we have seen and as the literature readily admits, contravariance is of essentially no practical use.

An argument often encountered in the programming literature is that one should strive for techniques that have simple mathematical models. Mathematical elegance, however, is one one of several design criteria; we should not forget to make our designs realistic and useful too. In computing science as in other disciplines, it is after all much easier to device drastically simple theories if we neglect to make them agree with reality.

So rather than trying to force a covariant body into a contravariant suit, we should accept the reality for what it is, covariant, and study ways to remove the unpleasant effects.

What I think Meyer means when talking about reality is that you want to actually model that two kinds of Skiers are Boys and Girls, and that Skiers can share rooms, but only Boys can share with other Boys, and Girls with other Girls. So he suggests that the "rare but serious possibility of type violations when [covariance is] combined with polymorphism," as he put it, are something that can be managed and are worth getting the benefit of being able to model this kind of reality. He never said it was about covariance being simpler or easier to understand, just that he want to be able to model things like making sure Girl and Boy skiers stay in separate rooms.

So fast forward 12 years, and here's how you could do this in Scala that keeps both the types and the high schoolers out of trouble. First, in Skier you add an abstract type as a member:

abstract class Skier {
  type SuitableRoommate <: Skier
  def share(other: SuitableRoommate)
}

The <: means that type SuitableRoommate must be a subtype of Skier. The SuitableRoommate type is abstract, because there's no equals sign specifying it to be some other type. The share method is also abstract, as in the Java example I showed previously, because it has no definition. In Scala, you don't need to put the keyword abstract on these as in Java.

OK, now in the subclasses, you define what the SuitableRoommate type is:

I edited this later, because I had some bugs in the code below. Fixed now.

class Boy extends Skier {
  type SuitableRoommate = Boy
  def share(other: Boy) {}
}

class Girl extends Skier {
  type SuitableRoommate = Girl
  def share(other: Girl) {}
}

For Boys, a suitable roommate is another Boy. And for Girls, a suitable roommate is another Girl. Now you can put Boy and Girl in the method signatures, and you get the behavior you want:

scala> :load skier.scala
Loading skier.scala...
defined class Skier
defined class Boy
defined class Girl

scala> val s: Skier = new Boy
s: Skier = Boy@101afe

scala> val g = new Girl
g: Girl = Girl@cf63bb

scala> s.share(g)
<console>:10: error: type mismatch;
 found   : Girl
 required: s.SuitableRoommate
       s.share(g)
               ^

> What I think Meyer means when talking about reality is
> that you want to actually model that two kinds of Skiers
> are Boys and Girls, and that Skiers can share rooms, but
> only Boys can share with other Boys, and Girls with other
> Girls.

The way I read it, he says what he means by that in the text you have quoted: "contravariance is of essentially no practical use."

> > What I think Meyer means when talking about reality is
> > that you want to actually model that two kinds of
> Skiers
> > are Boys and Girls, and that Skiers can share rooms,
> but
> > only Boys can share with other Boys, and Girls with
> other
> > Girls.
>
> The way I read it, he says what he means by that in the
> text you have quoted: "contravariance is of essentially no
> practical use."
>
Yes, I'm sure he meant that too. Remember this was 1997. What contravariance doesn't help you do is keep Girls and Boys in separate rooms. That was the practical benefit he saw in allowing covariant method parameters. What contravariance does do is exactly express the nature of overridden method parameters. It makes the types sound, which has some practical benefit I'd say. As Martin pointed out, once you have functions being passed around, it is handy that function parameter types are contravariant. Meyer may not have had that use case in mind back then.

But my main point with the skier post is that there are alternative ways to get at the benefit Meyer seemed to be after when he compromised and made the parameter types covariant even though their true nature was contravariant. It's also about as simple conceptually.

> Yes, I'm sure he meant that too. Remember this was 1997.
> What contravariance doesn't help you do is keep Girls and
> Boys in separate rooms.

I'm at a disadvantage here in that I don't have the full text but the first line in what you quote is:

"With contravariance one would not have these problems" which seems to suggest that it does solve the problem of keeping the boys and girls in separate rooms. Maybe I'm misunderstanding but I thought the boy and girl skier example was meant to show the problem with covariance and then the following text was meant to argue that despite these types of problems, covariance is still the right choice.

> What Meyers shows is a hierarchy with a class Skier with
> two subclasses, Girl and Boy.

haha. as an aside, i'm not a big fan of these types of scenarios as (1) they misuse inheritance, and (2) date very quickly. it kind of reminds me of the model in the sina composition filters paper that models Secretary as a subclass of Spouse (which is assumed to be female). Employees who have secretaries are assumed to be male of course!! http://trese.cs.utwente.nl/oldhtml/publications/reports/cf.pdf

> In Eiffel I think the subclass share methods override
> (actually implement, since it is abstract) the share
> method in Skier, because this kind of covariance of

yes, i believe these these override in eiffel. i can't even remember if eiffel has overloading.

> Meyers then later says, in a section entitled "polymorphic
> perversity", that "a harmful scheme is easy to make up,"
> and gives this example (again translated to Java):

yes, it's easy to make up a scenario where parameter covariance leads to runtime holes. whether it is a major problem in practice is another question.

> contravariance is of essentially no practical use.

I'd agree with bertrand here. I've found contravariance of input parameters to be useless. covariance is statically unsound, and therefore the java position of invariance seems sensible in a record type model. (Obviously contravariance of return types is a different story)

> In computing science as in other disciplines, it is after
> all much easier to device drastically simple theories if
> we neglect to make them agree with reality.

we just spend so much time trying to form the perfect type system that I wonder if it would be better to accept occasional holes for simplicity and clarity. It's the old 80/20 rule. To me Bertrand's crazy example sort of makes sense. You have a boy skier and a girl skier and they can't share a room. However, if you just tell someone you have 2 skiers and to put them in a room together, and you do it, someone's going to get in trouble ;-)

> So he suggests that the "rare but serious
> possibility of type violations when [covariance is]
> combined with polymorphism," as he put it, are something
> that can be managed and are worth getting the benefit of
> being able to model this kind of reality. He never said it
> was about covariance being simpler or easier to
> understand, just that he want to be able to model things
> like making sure Girl and Boy skiers stay in separate
> rooms.

fair enough. i find it simpler then to understand from a modeling perspective. for instance, if you have a Java class animal:

class Animal { void eat(Food f) {}}

and you want to subclass it to make Bear, you'd ideally want:

class Bear extends Animal { void eat (Honey h) {} }

where eat is overridden and Honey is a subclass of Food. To me this makes modeling sense, even though we can then ask the question as to what happens if we feed a bear weetabix...

> So fast forward 12 years, and here's how you could do this
> in Scala that keeps both the types and the high schoolers
> out of trouble. First, in Skier you add an abstract type
> as a member:
>
>

> abstract class Skier {
>   type SuitableRoommate <: Skier
>   def share(other: SuitableRoommate)
> }
> 

>
> The <: means that type SuitableRoommate must be a subtype
> of Skier. The SuitableRoommate type is abstract, because
> there's no equals sign specifying it to be some other
> type. The share method is also abstract, as in the Java
> example I showed previously, because it has no definition.
> In Scala, you don't need to put the keyword abstract on
> these as in Java.

yes, you do it the same sort of way in Beta with virtual patterns. In Beta you still have type holes because the Boy and Girl would still be subclasses of Skier.

So, in your scala example, does it mean that Boy and Girl are no longer subclasses of skier? if they are, what happens if you call Skier::share() on a boy as a Skier and pass in a girl as a Skier?

So, the idea of putting the share() function in the base class must be so that Boy and Girl can be treated polymorphically from the perspective of the share() method at some point, surely? otherwise, why wouldn't you just omit it from the Skier base and just place share(Girl) on the Girl class and vice versa?

And if Boy and Girl are no longer substitutable for Skier, then haven't we lost something major?

Alternatively, i'm not understanding how Scala handles this.

Cheers,
Andrew

> What I think Meyer means when talking about reality is
> that you want to actually model that two kinds of Skiers
> are Boys and Girls, and that Skiers can share rooms, but
> only Boys can share with other Boys, and Girls with other
> Girls. So he suggests that the "rare but serious
> possibility of type violations when [covariance is]
> combined with polymorphism," as he put it, are something
> that can be managed and are worth getting the benefit of
> being able to model this kind of reality. He never said it
> was about covariance being simpler or easier to
> understand, just that he want to be able to model things
> like making sure Girl and Boy skiers stay in separate
> rooms.

From what has been posted, I don't agree that this is what Meyer is saying at all. Unless I'm missing something he's saying that covariance doesn't work in this kind of situation but it's not worth including contravariance over. He saying he doesn't care about this situation much at all. That's what I read.