Covariance and Contravariance:Conflict without a CauseGIUSEPPE CASTAGNAC. N.R.S.In type-theoretic research on object-oriented programming, the issue of “covarianceversus con-travariance” is atopicof continuing debate. In this short notewe argue that covariance and con-travariance appropriately characterize two distinct and independent mechanisme. The so-calledcontravariance rule correctly captures the subtyping relation (that relation which establishes whichsets of functions can replace another given set m eve~contezt). A covariant relation, instead,characterizes the speczalizatzon of code (i.e., the definition of new code which replaces old def-initions in some particular cases). Therefore, covariance and contravariance are not opposingviews, but distinct concepts that each have their place inobject-oriented systems. Both can (andshould) be integrated in a type-safe manner in object-oriented languages. We also show thatthe independence of the two mechanisms is not characteristic of aparticular model but is valid ingeneral, since covariant specialization is present in record-based models, although it is hidden by adeficiency ofallexisting calculi that realize this model. Asanaside, weshowthat the A&-calculuscan betaken asthebmic calculus for both anoverloading-bmed and arecord-based model, Usingthis approach, onenotonly obtains amoreuniform vision ofobject-oriented type theories, but inthe case of the record-based approach, one also gains multiple dispatching, a feature that existingrecord-based models do not capture.Categories and Subject Descriptors: D.3.2 [Programming Languages]: Language Classifica-tions—object-otiented languages; F.3.3 [Logics and Meanings of Programs]: Studies of Pro-gram Constructs—typestructureGeneral Terms: Theory, LanguagesAdditional Key Words and Phraaes: Object-oriented languages, type theory1. INTRODUCTIONIn type-theoretic research on object-oriented programming, the issue of “covarianceversus contravariance” has been, and still is, the core of a heated debate. The dis-cussion goes back, in our ken, to at least 1988, when L6cluse, Richard, and V61ezused “covariant specialization” for the methods in the 02 data model [L6cluseet al. 1988]. Since then, it has been disputed whether one should use covari-ant or contravariant specialization for the methods in an object-oriented language.The fact that this debate is still heated is witnessed by the excellent tutorial onobject-oriented type systems given by Michael Schwartzbach at the last POPL con-ference [Schwartzbach 1994]: in the abstract of his tutorial Schwartzbach fingersThis work was partially supported by grant no. 203.01.56 of the Consiglio Nazionale delle Rlcerche,Comitato Nazionale delle Scienze Matematiche, Italy, to work at LIENS.Author’s address: LIENS, 45 rue d’Ulm 75005 Paris, Ih-ante; email: castagna(@dmi.ens. fr.Permission to make digital/hard copy of part or all of this work for personal or classroom use isgranted without fee provided that copies are not made or distributed for profit or commercialadvantage, the copyright notice, the title of the publication, and its date appear, and notice isgiven that copying is by permission of ACM, Inc. To copy otherwise, to republish, to post onservers, or to redistribute to lists, requires prior specific permission and\or a fee.@ 1995 ACM 0164-0925/95/0500-0431 $03.50ACM l’ransactlons on Programnung Languages and Systems, Vol 17, No 3, May 1995, Pages 431–447432 . Gluseppe Castagnathe “covarianceversus contravariance” issue as akeyexample of the specificity ofobject-oriented type systems.In this short note we argue that the choice between covariance and contravari-anceis a false problem. Covariance and contravariance characterize two completelydistinct mechanisms: subtyping and specialization. The confusion of the two madethem appear mutually exclusive.In fact, covariance and contravariance are notconflicting views but distinct concepts that can be integrated in a type-safe formal-ism. Finally, we argue that it would be an error to exclude either of them, sincethen the corresponding mechanism could not be properly implemented.This result is clear in the model of object-oriented programming defined byGiuseppe Longo, Giorgio Ghelli, and the author in Castagna et al. [1995]; it isalready present in Ghelli’s seminal work [Ghelli 1991], and it is somehow hidden inthe work on OBJ [Goguen and Meseguer 1989; Jouannaud et al. 1992; Marti-Olietand Meseguer 1990]. In these notes we want to stress that this result is indepen-dent of the particular model of object-oriented programming one chooses, and thatcovariance and contravariance already coexist in the record-based model proposedby Luca Cardelli in Cardelli [1988], and further developed by many other authors(see the collection [Gunter and Mitchell 1994] for a wide review of the record-basedmodel).The article is organized as follows. In Section 2, we recall the terms of the problemand we hint at its solution. In Section 3, we introduce the overloading-based modelfor object-oriented programming and give a precise explanation ofsubtyptng andspectalazatzon. We then show how and why covariance and contravariance cancoexist within a type-safe calculus. We use this analysis to determine the preciserole of each mechanism and to show that there is no conflict between them. Section4 provides evidence that this analysis is independent of the particular model byrevealing the (type-safe) covariance in the record-based model. Section 5 containsour conclusions and the golden rules for the typesafe usage of covariance andcent ravariance.We assume that the reader is familiar with the objects-as-records model of object-oriented programming and is aware of the typing issues it raises.The presentation is intentionally kept informal: no definitions, no theorems. Itis not a matter of defining a new system but of explaining and comparing existingones: indeed, all the technical results have already been widely published.2. THE CONTROVERSYThe controversy concerning the use of either covariance or contra~-ariance can bedescribed as follows. In the record-based model. proposed b>- Luca Cardelli in1984 [Cardelli 1988], an object is modeled by a record,w-hose fields contain allthe methods of the object and whose labels are the corresponding messages thatinvoke the methods. An object can be specialized to create a new object in twodifferent ways: either by adding new methods —i.e., new fields— or by