Java Subtyping as an Infinite Self-Similar Partial Graph Product
share
Due to supporting variance annotations, such as wildcard types, the subtyping relation in Java and other generic nominally-typed OO programming languages is both interesting and intricate. In these languages, the subtyping relation between ground object types (ones with no type variables) is the basis for defining the full OO subtyping relation (i.e., that includes type variables). In this paper we present how the subtyping relation between ground Java types can be precisely constructed using a binary operation on directed graphs. The binary operation we use, called a partial Cartesian graph product, is similar in its essence to standard graph products and group products. Its definition is based in particular on that of the standard Cartesian graph product. We believe the use of this graph operation in constructing the ground generic Java subtyping relation reveals some of the not-immediately-obvious structure of the subtyping relation in generic nominally-typed OO programming languages. Accordingly, we believe that describing precisely how this graph operation is used to construct the subtyping relation of these languages, as we do in this paper, may significantly improve our understanding of wildcard types and variance annotations in those languages.
READ FULL TEXT