VB » Variance

Co- and Contravariance
How do I convert a List(Of Apple) into a List(Of Fruit) ?

This is the first in a series of posts exploring how we might implement generic co- and contra-variance in a hypothetical future version of VB. This is not a promise about the next version of VB; it's just one possible proposal, written up here to get early feedback from potential users.

Sub EatFruit(ByVal x as IEnumerable(Of Fruit))

Dim x as New List(Of Apple)
x.Add(GrannySmith)
x.Add(GoldenDelicious)
EatFruit(x)
' ERROR: cannot convert List(Of Apple) to IEnumerable(Of Fruit)

Look at the above code. You'd think it should work. It's a common enough scenario: there's a library function which handles some kind of data type, but you've inherited from that type for your own purposes. How can you pass a collection of your own inherited type into the library function?

We're considering a VB language feature to support this kind of conversion. The topic is called "Co- and contra-variance", or just "variance" for short. Variance has actually been in the CLR since 2005 or so, but no one's yet released a .net language that uses it. There are other languages with it, though. Here are some links to what people have written on the topic.

Wikipedia article on co- and contravariance
Eric Lippert's blog about how one might add variance to C#
[PDF] Contravariance for the rest of us, a technical report from HP
[PDF] Conflict without a cause, a pivotal 1995 theory paper on it
Rick Byers about variance in the CLR
Bruce Eckel's thoughts on contravariance
Co- and contravariance in java, through "wildcard generics"

I'll talk about how you could use variance practically in VB, where it could make your code easier or cleaner, and what problems it might solve if we implement it. There's much more to variance than just converting apples into fruit, and it gets trickier as the above articles show, but I think the practical syntax and examples that we're proposing for VB could demystify it.

Here's a practical problem I had just yesterday that could have been solved by variance:

Function Call(instance As Expression, method As MethodInfo, arguments As IEnumerable(Of Expression)) As MethodCallExpression
...

' Create a new callsite that takes two arguments:
Dim args As New List(Of ConstantExpression)
args.Add(Expression.Constant("x"))
args.Add(Expression.Constant("y"))
'
Dim call1 = Expression.Call(instance, method, args)

' args inherits from IEnumerable(Of ConstantExpression), which
' variance-converts to IEnumerable(Of Expression)

For this first article, though, we'll stick to just fruit.

' some example classes to get us started
Class Food : End Class
Class Fruit : Inherits Food : End Class
Class Apple : Inherits Fruit : End Class
Class GoldenDelicious : Inherits Apple : End Class

' GoldenDelicious < Apple < Fruit < Food
' using < in the mathematical sense of "is smaller than",
' and in the VB sense of "can be converted to"

Class AppleBasket
  Implements IReadOnly(Of Apple)
  Implements IWriteOnly(Of Apple)
End Class

"Out" parameters

We're thinking of using contextual keywords "Out" and "In" to introduce variance:

Interface IReadOnly(Of Out T)
   Function Read() As T
End Interface
' "Out" declares that T will only ever be used
' as return type of functions *

Dim x As IReadOnly(Of Apple) = New AppleBasket
Dim y as IReadOnly(Of Fruit) = x

Dim f as Fruit = y.Read()
' This is guaranteed not to throw InvalidCastException

When the interface declares its type parameter as "Out", it makes a promise to only ever use that type for function returns (* or other places where it outputs data). The interface will be held to that promise: if it tries to do "Sub f(ByVal x As T)" then it's a compile-time error. (A lot of the design is constrained by how the CLR uses and represents variance; we want compatibility with other .Net languages.)

It's this "Out" promise that lets the CLR convert the interface:

' GoldenDelicions < Apple < Fruit < Food < Object

Dim apples as IReadOnly(Of Apple) = New AppleBasket

' It is allowed to change to an IReadOnly of something bigger:
Dim fruits IReadOnly(Of Fruit) = apples
Dim foods as IReadOnly(Of Food) = apples
Dim things as IReadOnly(Of Object) = fruits

' It is an ERROR to change to an IReadOnly that is smaller: 
Dim golds as IReadOnly(Of GoldenDelicious) = apples

' Also an ERROR to change to something unrelated
Dim cars  as IReadOnly(Of Car) = apples

In general, if you have a generic interface IReadOnly(Of Out T), then you can cast from it from "Of T" to something that T converts to. And it's typesafe, for obvious reasons.

Variance conversions are typesafe and efficient. It takes only a single IL instruction to do a variance conversion. There are NO runtime checks required. (This differs from arrays, which have to do a runtime type-check every time you put something into the array.)

Interfaces with "Out" parameters are called covariant in the literature.

"In" parameters

Interface IWriteOnly(Of In T)
  Sub Write(ByVal x As T)
End Interface
' "In" declares that T will only ever be used
' as ByVal arguments to functions.

Dim x As IWriteOnly(Of Apple) = New AppleBasket
Dim z As IWriteOnly(Of GoldenDelicious) = x

z.Write(New GoldenDelicious)

"In" parameters are the opposite. When an interface declares one of its type parameter T as "In", it's promising only ever to use T for ByVal arguments (* or other places where the interface takes data in). Again the interface will be held to that promise: if it tries to do "Function f() as T" then it's a compile-time error.

And "In" parameters let you do the opposite kinds of conversion:

' GoldenDelcious < Apple < Fruit < Food < Object

Dim apples As IWriteOnly(Of Apple) = new AppleBaset

' It is allowed to convert to an IWriteOnly of something smaller:
Dim golds As IWriteOnly(Of GoldenDelicious) = apples

' It is an ERROR to convert to something bigger, or unrelated:
Dim foods as IWriteOnly(Of Food) = apples
Dim cars as IWriteOnly(Of Car) = apples

Interfaces with "In" parameters are called contravariant in the literature.

"In" and "Out" together

Up until the early 1990s, people used to argue about whether "In" or "Out" parameters were the right thing to have. We now know that they're both right! The first convincing argument for this was in 1995 in Giuseppe Castagna's 1995 research paper "Conflict Without A Cause" [PDF].

Here are two examples for why they're both right, and how they both work together:

Class AppleBasket
   Implements IReadOnly(Of Apple)
   Implements IWriteOnly(Of Apple)

   Private m_value As Apple

   Public Function Read() As Apple Implements IReadOnly(Of Apple).Read
      Return m_value
   End Function

   Public Sub Write(ByVal x As Apple) Implements IWriteOnly(Of Apple).Write
      m_value = x
   End Sub
End Class

Pipes: using "In" and "Out" for internal and external contracts

' Here we implement a Pipe. Each element in the pipe is an ICollection.
'    IList <  ICollection  <  IEnumerable
'
' When we give out reader ("Out") access to the public, we force it so
' readers can only ever assume that elements are IEnumerable.
' And when we give out writer ("In") access, we force it so
' that writers must always put in IList
'
' This future-proofs our code in TWO directions: it forces the
' implementation to provide IList in case in the future we want
' to expose more to the clients; but it does so without making
' a public commitment to the clients that future implementations
' would have to uphold.

Class MyPipe(Of T)
   Implements IWriteOnly(Of T)
   Implements IReadOnly(Of T)

   Private contents As New Stack(Of T)

   Public Sub Write(ByVal x As T) Implements IWriteOnly(Of T).Write
      contents.Push(x)
   End Sub

   Public Function Read() As T Implements IReadOnly(Of T).Read
      Return contents.Pop()
   End Function
End Class

We are eager for customer feedback as we consider whether to add this feature to the VB language, and think about how it might work. Please add your comments.

I'll be writing more on variance (a lot more) in the weeks to come.

PS. As for the title of this article, here's what we envisage...

Dim x As New List(Of Apple)
Dim y As List(Of Fruit) = x
'
' ERROR: List(Of Fruit) cannot be converted to List(Of Apple)
' Consider using IEnumerable(Of Fruit) instead.

Comments:

[Lucian Wischik] Please add comments either here or at the VB Team Blog

It seems to me you only need to have one key work Like x as CLONE List(Of T) on function call. Then in the scope of the method x will reference clone of List(Of T). Everything works as normal. Modifications of list are bound into scope of the method or object and will not have effect callers list. Furthermore modifications to objects in the list will persist out of scope which is porsumably is a desired result. This would allow stuff like is.

Class Fruits
Public Property Washed() As Boolean
Public Property Eaten() As Boolean
End Class

Class WashedFruitList
Private mList As List(Of Fruits)
Public Sub New(ByVal NewList As List(Of Fruits))
For Each Fruit As Fruits In NewList
Fruit.Washed = True
Next
mList = NewList
End Sub
Public Sub EatList()
For Each Fruit As Fruits In mList
Fruit.Eaten = True
Next
mList=New List(Of Fruits)
End Sub
Public Sub Add(ByVal itm As Fruits)
itm.Washed = True
mList.Add(itm)
End Sub

End Class
.
.
.
Dim lApples As New List (Of Apples)
Dim CartFriut as WashedFruitList
.
.
.

CartFriut = New WashedFruitList(lApples)
' All apples in lApples would be washed
CartFriut.Add(BobsBanana)
' lApples would only still have Apples
lApples.Add(NewApple1)
lApples.Add(NewApple2)
CartFriut.EatList
' LApples Still Exist Members and all members of LApples would be eaten except NewApple1, and NewApple2
.
.
.
If you want further clarification email me @ btcheng@yahoo.com

It seems to me that declaration-site variance (as implemented in the CLR, and now proposed for C# and VB.NET) is less useful than call-site variance (as implemented in Java using wildcards). Here's why: stop for a moment and think, how many of BCL generic classes could actually be converted to use this feature? There's IEnumerable<T>, alright - but what else? ICollection<T> is right out, because it is IEnumerable<T> (and hence covariant), but it also takes T as an argument for Add() (which is contravariant) - the intersection of those is invariant. The same goes for all interfaces further extending ICollection<T>, such as IList<T>.

On the other hand, with wildcards, I can deal with ICollection<T> either in covariant or contravariant fashion: for example, only using GetEnumerator() and Count - a typical real-world scenario - is covariant; only using Add() is contravariant. You can do this with declaration-site variance too, but you have to split every interface into its covariant and contravariant parts, and I doubt the BCL team would do it at this point; besides, it relies upon interface designers to do the right thing, and gives the user no recourse if they don't.

add comment edit comment