License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2023.44
URN: urn:nbn:de:0030-drops-182372
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18237/
Go to the corresponding LIPIcs Volume Portal

Roth, Ori

Python Type Hints Are Turing Complete (Pearl/Brave New Idea)

pdf-format:
LIPIcs-ECOOP-2023-44.pdf (0.9 MB)

Abstract

Grigore proved that Java generics are Turing complete by describing a reduction from Turing machines to Java subtyping. Furthermore, he demonstrated that his "subtyping machines" could have metaprogramming applications if not for their extremely high compilation times. The current work reexamines Grigore’s study in the context of another prominent programming language - Python. We show that the undecidable Java fragment used in Grigore’s construction is included in Python’s type system, making it Turing complete. In contrast to Java, Python type hints are checked by third-party static analyzers and run-time type checkers. The new undecidability result means that both kinds of type checkers cannot fully incorporate Python’s type system and guarantee termination. The paper includes a survey of infinite subtyping cycles in various type checkers and type reification in different Python distributions. In addition, we present an alternative reduction in which the Turing machines are simulated in real time, resulting in a significantly faster compilation. Our work is accompanied by a Python implementation of both reductions that compiles Turing machines into Python subtyping machines.

BibTeX - Entry

@InProceedings{roth:LIPIcs.ECOOP.2023.44,
  author =	{Roth, Ori},
  title =	{{Python Type Hints Are Turing Complete}},
  booktitle =	{37th European Conference on Object-Oriented Programming (ECOOP 2023)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-281-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{263},
  editor =	{Ali, Karim and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18237},
  URN =		{urn:nbn:de:0030-drops-182372},
  doi =		{10.4230/LIPIcs.ECOOP.2023.44},
  annote =	{Keywords: nominal Subtyping with Variance, Python}
}

Keywords: nominal Subtyping with Variance, Python
Collection: 37th European Conference on Object-Oriented Programming (ECOOP 2023)
Issue Date: 2023
Date of publication: 11.07.2023
Supplementary Material: Software (ECOOP 2023 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.9.2.1

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI