Towards an Order and Category Theoretic Model of Java Generics (extended version)

EasyChair Preprint 3631, version 2

Abstract

The mathematical modeling of generic type systems of mainstream object-oriented programming languages such as Java, C#, C++, Scala and Kotlin is a challenge. This is mainly due to these languages supporting features such as ‘variance annotations,’ ‘F-bounded type parameters,’ and ‘type erasure.’

In this paper we present an order-theoretic and lattice-theoretic approach to modeling generics in nominally-typed OOP type systems that aims to build a simpler and more intuitive model than the extant “existentials-based” model. The approach also uses some elementary notions in category theory, as a generalization of order and lattice theory.

Our model, as constructed so far, reveals characteristics and relations underlying type systems of generic mainstream OOP languages—such as a Galois connection between subclassing and subtyping—that seem to have not been formalized and made explicit before. The model also suggests how support for generics in these languages may be simultaneously extended and simplified, including proposing features such as ‘interval types,’ ‘doubly F-bounded generics,’ ‘default type arguments,’ and ‘cofree types.’

Keyphrases: Bounded existential types, Coinductive F-bounded existential types, F-algebras, F-bounded existential types, F-bounded polymorphism, F-coalgebras, Free Type, Free and cofree types, Galois connections, Interval Type, Java Wildcards, Java type erasure, Nominal Typing, OO Inheritance, OO Subtyping, Ordered sets and lattices, Structural-Typing, Subclassing, Variance Annotations, adjunctions, category theory, cofree type, default type, default type argument, existential type, fixed point, generic class, generic oop, generic oop type system, generics, interval type argument, mathematical modeling, object-oriented programming, oo type system, oop language, order theory, parameterized type, partial products, post fixed point, pre fixed point, subtyping relation, valid type argument, wildcard type argument

@booklet{EasyChair:3631,
  author    = {Moez Abdelgawad},
  title     = {Towards an Order and Category Theoretic Model of Java Generics (extended version)},
  howpublished = {EasyChair Preprint 3631},
  year      = {EasyChair, 2020}}