Wed 10 Jan 2018 13:40 - 14:05 at Watercourt - Interpretation and Evaluation Chair(s): Atsushi Igarashi

Metaprograms are programs that manipulate (generate, analyze and evaluate) other programs. These tasks are greatly facilitated by quasiquotation, a technique to construct and deconstruct program fragments using quoted code templates expressed in the syntax of the manipulated language. We argue that two main flavors of quasiquotes have existed so far: Lisp-style quasiquotes, which can both construct and deconstruct programs but may produce code that contains type mismatches and unbound variables; and MetaML-style quasiquotes, which rely on static typing to prevent these errors, but can only construct programs. In this paper, we show how to combine the advantages of both flavors into a unified framework: we allow the construction, deconstruction and evaluation of program fragments while ensuring that generated programs are well-typed and well-scoped, a combination unseen in previous work. We formalize our approach as λ{}, a multi-stage calculus with code pattern matching and rewriting, and prove its type safety. We also present its realization in Squid, a metaprogramming framework for Scala, leveraging Scala’s expressive type system. To demonstrate the usefulness of our approach, we introduce speculative rewrite rules, a novel code transformation technique that makes decisive use of these capabilities, and we outline how it simplifies the design of some crucial query compiler optimizations.

Squid is open source, available online at

Wed 10 Jan
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

13:40 - 15:20: Research Papers - Interpretation and Evaluation at Watercourt
Chair(s): Atsushi IgarashiKyoto University, Japan
POPL-2018-papers13:40 - 14:05
Lionel ParreauxEPFL, Antoine VoizardUniversity of Pennsylvannia, Amir ShaikhhaEPFL, Christoph E. KochEPFL
POPL-2018-papers14:05 - 14:30
Matt BrownUCLA, Jens PalsbergUniversity of California, Los Angeles (UCLA)
POPL-2018-papers14:30 - 14:55
John Peter Campora IIIULL Lafayette, Sheng ChenUniversity of Louisiana at Lafayette, Martin ErwigOregon State University, Eric WalkingshawOregon State University
POPL-2018-papers14:55 - 15:20
Casper Bach PoulsenDelft University of Technology, Arjen RouvoetDelft University of Technology, Andrew TolmachPortland State University, Robbert KrebbersDelft University of Technology, Eelco VisserDelft University of Technology
DOI Pre-print