Positive Subtyping

AbstractThe statementS⩽Tin aλ-calculus with subtyping is traditionally interpreted by a semantic coercion function of type [[S]]→[lsqb;T]] that extracts the “Tpart” of an element ofS. If the subtyping relation is restricted to covariant positions, this interpretation may be enriched to include both the implicit coercion and an overwriting functionput[S, T]∈[[S]]→[[T]]→[[S]] that updates theTpart of an element ofS. We give a realizability model and a sound equational theory for a second-order calculus of positive subtyping. Though weaker than familiar calculi of bounded quantification, positive subtyping retains 1?sufficient power to model objects, encapsulation, and message passing, and inheritance. The equational laws relating the behavior of coercions andputfunctions can be used to prove simple properties of the resulting ?classes in such a way that proofs for superclasses are “inherited” by subclasses