Grigore, Radu (2017) Java Generics are Turing Complete. In: POPL 2017 Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. POPL Principles of Programming Languages . pp. 73-85. ACM, New York, USA ISBN 978-1-4503-4660-3. (doi:10.1145/3009837.3009871) (KAR id:58183)
|
PDF
Author's Accepted Manuscript
Language: English |
|
|
Download (348kB)
Preview
|
Preview |
|
This file may not be suitable for users of assistive technology.
Request an accessible format
|
|
| Official URL https://dx.doi.org/10.1145/3009837.3009871 |
|
Abstract
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 Gill and Levy from 2016. The latter point is illustrated by a parser generator for fluent interfaces.
| Item Type: | Conference or workshop item (Paper) |
|---|---|
| DOI/Identification number: | 10.1145/3009837.3009871 |
| Uncontrolled keywords: | Java, subtype checking, decidability, fluent interface, parser generator, Turing machine |
| Subjects: | Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, > QA76.76 Computer software |
| Divisions: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing |
| Depositing User: | Radu Grigore |
| Date Deposited: | 28 Oct 2016 11:29 UTC |
| Last Modified: | 10 Mar 2021 17:13 UTC |
| Resource URI: | https://kar.kent.ac.uk/id/eprint/58183 (The current URI for this page, for reference purposes) |
| Grigore, Radu: |  https://orcid.org/0000-0003-1128-0311 |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):
Altmetric
Altmetric
