Containers and Inheritance

I had a request to implement something similar to the following:

If B inherits from A, then B can be passed to a function which takes an A as a parameter just like in any language with inheritance. Make it so that a function taking a list of B can be passed to a function accepting a list of A without conversion beforehand. (And no one cares if it's slow; externally it should require no conversions.)

My reasoning against doing this was that this was that it is really equivalent to saying that a list of B inherits from list of A. And if I add a new type of container (mycontainer) which inherits from list, then a mycontainer of B would inherit from all of a mycontainer of A and list of B and a list of A, and that get's really messy. Not a great argument in this particular case as there's no intention to ever support a mycontainer that inherits from list.

It got me thinking though, no major languages I know of support this. I can kind of see why for low-level languages like C++ when I think of how object orientation is implemented and speed requirements. However, there must be some deeper theoretical reasoning behind why it's not found in higher level languages than it's just messy. Is it found in languages I don't know, or research languages? If not, why not? Does this type of language feature have a name? The feature request has died, but it's got me curious.

Covariance

What you are talking about is covariance - more specifically, a type constructor (your "mycontainer") that is covariant in its type parameter.

Covariance (and its cousin, contravariance) are available in Scala (on the JVM) and in C# and F# (on the .NET CLR), as well as a number of less "mainstream" languages.

By Tess Foley at Fri, 2010-07-23 21:12 | login or register to post comments

Wow.

Thanks for that. C# is actually the language I've found myself using most at work over the past couple years. This will come in useful.

By bfraser at Sat, 2010-07-24 01:28 | login or register to post comments

C# versions

Be aware that generic co/contravariance is only available as of C#4. An overview is available at http://msdn.microsoft.com/en-us/magazine/ff796223.aspx.

By Wolf Logan at Wed, 2010-07-28 19:53 | login or register to post comments

Java's covariant arrays

Java has covariant arrays. However, since arrays are mutable this turns out to be unsafe, which Java rectifies with dynamic checks for all object array stores (good Java JITs do type analysis to remove most of these).

Java also allows constraints on type parameters (i.e. you specify either a subtype or supertype relation), but it does not have variance in type constructors.

It's arguable whether variance for type parameters to classes is particularly useful. Scala people seem to think so.

Definitely if you have Tuple, ImmutableArray, and Function as type constructors in your language, variance is important.

By Ben L. Titzer at Fri, 2010-07-23 21:21 | login or register to post comments

Java Wildcards

Java's Wildcard types would allow you to meet your goals.

'foo(List<? extends A> L)' if foo reads elements of type A from the list.

'foo(List<? super A> L)' if foo writes elements of type A into the list.

If you need a temporary variable of type S inside definition of foo, you might use '<S> foo(List<S super A> L)'

C++ is also capable of such, albeit using templates. And I would suspect that Scala is capable of it. The main concern is that 'foo' cannot both read and write to the list if you wish for it to safely be generic.

By dmbarbour at Fri, 2010-07-23 22:12 | login or register to post comments

C++ more like duck typing

C++ templates is more of a duck typing situation. It'll do something similar to this, but not without also allowing much more... unless you really go out of your way.

I didn't know Java had this though. It sure didn't last time I had to use Java. Cool.

By bfraser at Sat, 2010-07-24 01:26 | login or register to post comments

C++ Concepts

Concepts would have provided the greater precision you're demanding. However, they were dropped for C++0x.

These Java features were new to me, as well. I haven't used Java since 1.4, and most of my experience was with 1.2. I was not happy with Java at the time. (Generics and anonymous functors weren't introduced until 1.5.)

By dmbarbour at Sat, 2010-07-24 01:37 | login or register to post comments

Bounded Existentials

Scala allows variance to be defined at the definition site as others have commented but it also allows Java style usage variance using bounded existentials

Java's void foo(List<? extends A> L) becomes def foo(l : List[_ <: A]) : Unit

In Scala you can give the existential a name

def foo(l : List[S <: A] forSome {type S}) : Unit

For this example the named form is synonymous with the underscore version, but naming the existential allows access to the type variable S over a very small scope for more sophisticated types. E.g.

def foo(m : Map[S, S] forSome {type S <: A}) : Unit = {}

Says we expect a map from one type to the same type and we don't care what the type is as long as it's upper bounded by A.

void foo(List<S extends A> L) isn't valid Java, you can however universally quantify S in Java

<S extends A> void foo(List<S> L)

Which in Scala looks like

def foo[S <: A](l : List[S]) : Unit

By James Iry at Mon, 2010-07-26 15:36 | login or register to post comments

Scala Variance

Scala has explicit variance annotations. The standard library Function1 class exhibits both:

class Function1[-A, +R] { def apply(arg: A): R }

Function1 (as with all non-zero arity FunctionN) is contravariant in its argument type(s) and covariant in its result type.

And, also as expected and consistent with bfraser's remarks, similar variance patterns can be seen in Scala's immutable collections while its mutable collections are invariant.

By Randall Schulz at Fri, 2010-07-23 22:34 | login or register to post comments

Lambda the Ultimate

User login

Navigation