3 Search Results for "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.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}
}
  • Refine by Author
  • 3 Roth, Ori
  • 2 Gil, Yossi

  • Refine by Classification
  • 3 Software and its engineering → General programming languages
  • 2 Software and its engineering → Domain specific languages

  • Refine by Keyword
  • 2 code generation
  • 2 compilation
  • 1 Fluent API
  • 1 Python
  • 1 fluent API
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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