Monday, June 21, 2010

my turn to explain type covariance and contravariance

The Web has a wealth of resources about type covariance and contravariance, but I often find the approach unsatisfying: either code snippets or abstract-ish theoretical axioms. I prefer an additional, intermediate level of understanding that may be called pragmatic. Pragmatically understood, any pattern or concept isn't solely "standalone" snippets or logical axioms. A learner should be able to connect the concept to his or her prior knowledge and also to the question "When would I use this?" I'll attempt to remedy this shortcoming.

For code reuse, a pivotal issue is which data type substitutions in the code will work. Can code written for type Y also function properly for data of type Z? Well, if the definition of data type Z is strictly "Y's definition plus some other stuff", then yes, since the code can treat Z data as if it were Y data. Z is said to be derived from Y. Z is a stricter data type relative to Y. We then say that Z is covariant to Y but Y is contravariant to Z. Code that acts on Y can also act on Z because Z encompasses Y, but code that acts on Z may not be able to act on Y because the code may rely on the "other stuff" in Z beyond Y's definition. In languages that support it, the creation of a data type that's covariant to an existing type can be easily accomplished through inheritance of the existing type's language artifacts. (When someone uses the language feature of inheritance to create a type whose data can't be treated by code as if it were of the original type, confident code reuse is lost, which is the goal behind type covariance/contravariance!)

Thus far I've only mentioned the reuse of one piece of code over any data type covariant to the code's original type. The data varies but the code doesn't. A different yet still eminently practical situation is the need for the code to vary and nevertheless join up with other pieces of code without any of the code failing to work (e.g. a callback). What relationship must there be between the data types of the code pieces in order for the whole to work?

All that's necessary to approach this question is to reapply the same principle: a piece of code that works with data type Y will also work with data type Z provided that Z is covariant to Y. Assume an example gap to be filled by varying candidates of code. In this gap, the incoming data is of original type G and the outgoing data is of original type P.

Consider the code that receives the outgoing data. If the candidate code sends data of type P, the receiving code will work simply because it's written for that original type. If the candidate code sends data of a type covariant to (derived or inherited from) P, the receiving code will work because, as stated before, covariant types can "stand in" for the original type. If the candidate code sends data of a type contravariant to P, the receiving code won't work because it may rely on the parts of P's definition that are included in P alone. (In fact, this should always be true. Whenever it isn't, the receiving code should have instead targeted either a less-strict type or even just an interface. A "snug" data-type yields greater flexibility.) So the rule for the candidate code is that it must be written to send data of type P or covariant to P.

Meanwhile, the code that sends the gap's incoming data has committed to sending it as type G. If G is the original type that the candidate code is written to receive, it will work simply because it's written for that type. If a type covariant to G is the original type that the candidate code is written to receive, it won't work because it may rely on the parts of that type that aren't in G. If a type contravariant to G is the original type that the candidate code is written to receive, it will work because G is covariant to it, and once again covariant types are substitutable. So the rule for the candidate code is that it must be written to receive data of type G or contravariant to G.

Hence, the rules for covariance and contravariance in various programming languages (delegates in C#, generics in Java or C#) are neither arbitrarily set nor needlessly complex. The point is to pursue greater code generality through careful variance among related data types. Static data types are "promises" that quite literally bind code together. Pieces of code may exceed those promises (legal covariance of return); however, the code may not violate those promises (illegal contravariance of return). Pieces of code may gladly accept what is seen as excessively-generous promises (legal contravariance of paramaters); however, no code should expect anything that hasn't been promised (illegal covariance of parameters).

No comments:

Post a Comment