Subtyping in Java with Generics and Wildcards is a Fractal

Abstract

For helping themselves in writing, debugging and maintaining their software, professional OO software developers keep in their minds an image of the subtyping relation between types in their software while they are developing their software. In pre-generics Java, the structure of the subtyping mental image was simple: the graph of the subtyping relation between classes and interfaces was a directed-acyclic graph, and the graph of the subtyping relation between classes alone was simply a tree. This fact about the graph of the subtyping relation applied not only to Java but, more generally, also to the non-generic sublanguage of nominally-typed OO languages similar to Java, such as C#, C++, and Scala. The goal of this casual essay is to present and defend, even if incompletely and not quite rigorously, a hunch and intuition the author had years ago about the graph of the subtyping relation in Java after generics were added to it. The author observed that: after the addition of generics---and of wildcards in particular---to Java, the graph of the subtyping relation is still a DAG, but no longer a simple DAG but rather one whose structure can be better understood as a /fractal/. Today, generics and wildcards (or some other form of `variance annotations') are a standard feature of mainstream nominally-typed OO languages. Accordingly, the shape of the subtyping relation in nominally-typed OO languages is more complex than a tree or a simple DAG. Given the popularity of fractals, the fractals observation may help OO software developers keep a useful and intuitive mental image of their software's subtyping relation, even if it is one a little more frightening, and amazing, than before.