A Subtyping Scheme for Nominal and Structural Types Based on Class Graph Equivalence

Subtyping and multiple inheritance are the essential features of oo and component-based programming languages, in particular with the presence of interfaces and contracts. More general, the composability of these constructs admitting the subtype relation powers the reusability, modular, flexibility and reliability of oo-based systems. While nominal classes allow annotation of user intention to the types, operations on interfaces and contracts naturally result structural constructs. Structural types are also necessary if we need the types to have value-semantics, so that they can be transferred around in distributed systems. Building a type system that allows the coexistence of nominal and structural classes, while maintaining the usual subtype relation is critical and challenging. We present a subtyping scheme that encodes a class to a directed and edge-labeled graph, which has the convenience to handle recursive types. The names of a class and its superclasses are encoded as tags to label the edges of the graph, turning the nominal construct into a structural one. This encoding allows us to unify the handling of class relations into graph relations. We define the class representation, canonical form, value-identity and subtype relation in the notion of graphs, and justify our subtyping scheme in the cases of multiple inheritance, class intersection and union. Our scheme is general, easy to implement and compatible with most of the existing oo type systems, providing a solid base for further oo language and tool development.