Ori Roth

Selected Publications

1. OOPSLA

   Fluent APIs in Functional Languages

   Ori Roth, and Yossi Gil

   Proc. ACM Program. Lang. Apr 2023

   Abs DOI PDF

   Fluent API is an object-oriented pattern for elegant APIs and embedded DSLs. A smart fluent API can enforce the API protocol or DSL syntax at compile time. Since fluent API implementations typically rely on overloading function names, they are hard to realize in functional programming languages. This work shows how functional fluent APIs can be implemented in the absence of name overloading, by relying on parametric polymorphism and Hindley-Milner type inference. The implementation supports fluent API protocols in the regular- and deterministic context-free language classes, and even beyond.

2. arXiv

   Python Type Hints are Turing Complete

   Ori Roth

   Apr 2022

   Abs DOI PDF

   Grigore showed that Java generics are Turing complete by describing a reduction from Turing machines to Java subtyping. We apply Grigore’s algorithm to Python type hints and deduce that they are Turing complete. In addition, we present an alternative reduction in which the Turing machines are simulated in real time, resulting in significantly lower compilation times. Our work is accompanied by a Python implementation of both reductions that compiles Turing machines into Python subtyping machines.

3. OOPSLA

   Study of the Subtyping Machine of Nominal Subtyping with Variance

   Ori Roth

   Proc. ACM Program. Lang. Oct 2021

   Abs DOI PDF

   This is a study of the computing power of the subtyping machine behind Kennedy and Pierce’s nominal subtyping with variance. We depict the lattice of fragments of Kennedy and Pierce’s type system and characterize their computing power in terms of regular, context-free, deterministic, and non-deterministic tree languages. Based on the theory, we present Treetop—a generator of C# implementations of subtyping machines. The software artifact constitutes the first feasible (yet POC) fluent API generator to support context-free API protocols in a decidable type system fragment.

4. ECOOP

   Fling - A Fluent API Generator

   Yossi Gil, and Ori Roth

   In 33rd European Conference on Object-Oriented Programming (ECOOP 2019) Oct 2019

   Abs DOI PDF

   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.

Honors and Awards

• 2022

  Jacobs Excellence Certificate (Technion)

  For academic excellence and research achievements.

  
  
• 2021

  ACM SIGPLAN Distinguished Paper Award (OOPSLA 2021)

  
  

  Shimon Even Award (Technion)

  Outstanding publication award

  
  
• 2019

  ECOOP Distinguished Paper Award (ECOOP 2019)

  
  
• 2018

  Amdocs Prize (Technion)

  Best undergraduate research project

Service

• 2023

  Artifact Evaluation Committee member (PLDI 2023)

  
  
• 2021

  Artifact Evaluation Committee member (ISSTA 2021)