2016/05/17 by Radu Grigore, Grigore, Radu · 6 voices · 2 citations
#cs.PL
paper · pdf · doi:10.48550/arxiv.1605.05274
This paper describes a reduction from the halting problem of Turing machines to subtype checking in Java. It follows that subtype checking in Java is undecidable, which answers a question posed by Kennedy and Pierce in 2007. It also follows that Java's type checker can recognize any recursive language, which improves a result of Gil and Levy from 2016. The latter point is illustrated by a parser generator for fluent interfaces.