Java Generics

In Java, generics refers to the implementation of parametric polymorphism. Introduced in Java 1.5 in 2004, generics enable making classes of containers parameterized in an arbitrary Java type, e.g. List<A> or Set<A>.

Models of Java generics

Java generics were initially specified carefully, but informally.

Early theoretical models of how they worked were more liberal than the actual implementation, and their subtype relation was undecidable Kennedy and Pierce 2007. In its appendix, the paper by Kennedy and Pierce contains a number of interesting Java programs that made Java 1.5 crash.

In a paper at POPL 2017, Grigore confirmed that subtype checking for Java generics is indeed undecidable. In fact, the paper shows that Java's type checker can recognise any recursive language Grigore 2017.

References

@inproceedings{kennedy_2007,
	title = {On Decidability of Nominal Subtyping with Variance},
	url = {https://www.cis.upenn.edu/~bcpierce/papers/variance.pdf},
	booktitle = {International Workshop on Foundations and Developments of Object-Oriented Languages ({FOOL}/{WOOD})},
	author = {Kennedy, Andrew J and Pierce, Benjamin C},
	date = {2007}
}

@inproceedings{grigore_2017,
	title = {Java generics are Turing complete},
	doi = {10.1145/3009837.3009871},
	pages = {73--85},
	booktitle = {Proceedings of the 44th {ACM} {SIGPLAN} Symposium on Principles of Programming Languages},
	publisher = {Association for Computing Machinery},
	author = {Grigore, Radu},
	date = {2017}
}