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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.

Original languageEnglish
Title of host publicationICBTA 2021 - 2021 4th International Conference on Blockchain Technology and Applications
PublisherAssociation for Computing Machinery
Number of pages7
ISBN (Electronic)9781450387460
Publication statusPublished - 17 Dec 2021
Event4th International Conference on Blockchain Technology and Applications, ICBTA 2021 - Virtual, Online, China
Duration: 17 Dec 202119 Dec 2021

Publication series

NameACM International Conference Proceeding Series


Conference4th International Conference on Blockchain Technology and Applications, ICBTA 2021
CityVirtual, Online


  • class graph
  • distributed programming
  • intersection type
  • multiple inheritance
  • nominal subtyping
  • object-oriented language
  • recursive type
  • structural subtyping
  • subtyping
  • type equivalence
  • union type


Dive into the research topics of 'A Subtyping Scheme for Nominal and Structural Types Based on Class Graph Equivalence'. Together they form a unique fingerprint.

Cite this