Search Results

Documents authored by Roth, Ori

Document
Pearl/Brave New Idea
DOI: 10.4230/LIPIcs.ECOOP.2023.44
Python Type Hints Are Turing Complete (Pearl/Brave New Idea)

Authors: Ori Roth

Published in: LIPIcs, Volume 263, 37th European Conference on Object-Oriented Programming (ECOOP 2023)

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.
Cite as

Ori Roth. Python Type Hints Are Turing Complete (Pearl/Brave New Idea). In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ECOOP.2023.44},
  URN =		{urn:nbn:de:0030-drops-182372},
  doi =		{10.4230/LIPIcs.ECOOP.2023.44},
  annote =	{Keywords: nominal Subtyping with Variance, Python}
}
Document
Artifact
DOI: 10.4230/DARTS.9.2.1
Python Type Hints Are Turing Complete (Artifact)

Authors: Ori Roth

Published in: DARTS, Volume 9, Issue 2, Special Issue of the 37th European Conference on Object-Oriented Programming (ECOOP 2023)

Abstract
The artifact comprises a Docker image (virtual environment) containing the source code and experiments setup mentioned in the paper. The artifact is available on Zenodo. The anonymous version submitted to the ECOOP Artifact Evaluation Committee (AEC) is also available on Zenodo. The project is maintained on GitHub.
Cite as

Ori Roth. Python Type Hints Are Turing Complete (Artifact). In Special Issue of the 37th European Conference on Object-Oriented Programming (ECOOP 2023). Dagstuhl Artifacts Series (DARTS), Volume 9, Issue 2, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{roth:DARTS.9.2.1,
  author =	{Roth, Ori},
  title =	{{Python Type Hints Are Turing Complete (Artifact)}},
  pages =	{1:1--1:4},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2023},
  volume =	{9},
  number =	{2},
  editor =	{Roth, Ori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.9.2.1},
  URN =		{urn:nbn:de:0030-drops-182418},
  doi =		{10.4230/DARTS.9.2.1},
  annote =	{Keywords: nominal Subtyping with Variance, Python}
}
Document
Artifact
DOI: 10.4230/DARTS.5.2.12
Fling - A Fluent API Generator (Artifact)

Authors: Ori Roth and Yossi Gil

Published in: DARTS, Volume 5, Issue 2, Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
The first general and practical solution of the fluent API problem is presented. We give an algorithm that given a deterministic context free language (equivalently, LR(k), k >= 0 language) encodes it in an unbounded parametric polymorphism type system employing only a polynomial number of types. The theoretical result is employed in an actual tool Fling - a fluent API compiler-compiler in the style of YACC, tailored for embedding DSLs in Java.
Cite as

Ori Roth and Yossi Gil. Fling - A Fluent API Generator (Artifact). In Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 2, pp. 12:1-12:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{roth_et_al:DARTS.5.2.12,
  author =	{Roth, Ori and Gil, Yossi},
  title =	{{Fling - A Fluent API Generator}},
  pages =	{12:1--12:9},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{2},
  editor =	{Roth, Ori and Gil, Yossi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.5.2.12},
  URN =		{urn:nbn:de:0030-drops-107897},
  doi =		{10.4230/DARTS.5.2.12},
  annote =	{Keywords: Fluent API, compilation, generics, code generation}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2019.13
Fling - A Fluent API Generator

Authors: Yossi Gil and Ori Roth

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
We present the first general and practical solution of the fluent API problem - an algorithm, that given a deterministic language (equivalently, LR(k), k >= 0 language) encodes it in an unbounded parametric polymorphism type system employing only a polynomial number of types. The theoretical result is accompanied by an actual tool Fling - a fluent API compiler-compiler in the venue of YACC, tailored for embedding DSLs in Java.
Cite as

Yossi Gil and Ori Roth. Fling - A Fluent API Generator. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 13:1-13:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gil_et_al:LIPIcs.ECOOP.2019.13,
  author =	{Gil, Yossi and Roth, Ori},
  title =	{{Fling - A Fluent API Generator}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{13:1--13:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.13},
  URN =		{urn:nbn:de:0030-drops-108053},
  doi =		{10.4230/LIPIcs.ECOOP.2019.13},
  annote =	{Keywords: fluent API, type system, compilation, code generation}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact