5 Search Results for "Roth, Ori"

Document
DOI: 10.4230/LIPIcs.FUN.2026.15
Spells for Quantum Programmers: Expressive High-Level Commands in Qutes

Authors: Simone Faro, Francesco Pio Marino, and Gabriele Messina

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Classical computers are powerful but fundamentally mundane: they operate through explicit, step-by-step instructions that force programmers to think locally and procedurally. Quantum technologies, by contrast, resemble magical instruments, capable of acting on superpositions, correlations, and entire collections of states at once. Yet, despite their magical nature, quantum computers are still programmed as if they were ordinary machines, relying on long sequences of low-level operations that obscure the underlying algorithmic ideas. Magic, however, is not performed by improvisation alone: it requires a spellbook. In this paper we position Qutes as a book of spells for quantum programmers, providing high-level commands that capture complex quantum behaviour behind concise and expressive syntax. We focus on the manipulation of quantum arrays, which naturally arise in many algorithms but are notoriously cumbersome to manage at the circuit level. We introduce three new array-oriented spells in Qutes: global initialization, parallel pairwise comparison, and parallel (optionally controlled) swap. Individually, these spells encapsulate non-trivial quantum procedures; when combined, they enable programmers to express algorithms in a way that is immediate, readable, and surprisingly elegant. As a final demonstration, we show how these spells can be assembled to produce a remarkably compact implementation of Bubble Sort. While algorithmically simple, this example illustrates a broader message: when the right abstractions are available, quantum programming can feel less like engineering machinery and more like magic.
Cite as

Simone Faro, Francesco Pio Marino, and Gabriele Messina. Spells for Quantum Programmers: Expressive High-Level Commands in Qutes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{faro_et_al:LIPIcs.FUN.2026.15,
  author =	{Faro, Simone and Marino, Francesco Pio and Messina, Gabriele},
  title =	{{Spells for Quantum Programmers: Expressive High-Level Commands in Qutes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.15},
  URN =		{urn:nbn:de:0030-drops-257349},
  doi =		{10.4230/LIPIcs.FUN.2026.15},
  annote =	{Keywords: Quantum programming languages, High-level abstractions, Quantum arrays}
}
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}
}
  • Refine by Type
  • 5 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2023
  • 2 2019

  • Refine by Author
  • 4 Roth, Ori
  • 2 Gil, Yossi
  • 1 Faro, Simone
  • 1 Marino, Francesco Pio
  • 1 Messina, Gabriele

  • Refine by Series/Journal
  • 3 LIPIcs
  • 2 DARTS

  • Refine by Classification
  • 4 Software and its engineering → General programming languages
  • 2 Software and its engineering → Domain specific languages
  • 1 Software and its engineering
  • 1 Theory of computation

  • Refine by Keyword
  • 2 Python
  • 2 code generation
  • 2 compilation
  • 2 nominal Subtyping with Variance
  • 1 Fluent API
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact