This program is tentative and subject to change.
We transport multi-stage programming from functional to relational programming, with novel constructs to give programmers control over staging and non-determinism. We stage interpreters written as relations, in which the programs under interpretation can contain holes representing unknown expressions or values. By compiling the known parts without interpretive overhead and deferring interpretation to run time only for the unknown parts, we compound the benefits of staging (e.g., turning interpreters into compilers) and relational interpretation (e.g., turning functions into relations and synthesizing from sketches). We extend miniKanren with staging constructs and apply the resulting multi-stage language to relational interpreters for subsets of Racket and miniKanren as well as a relational recognizer for context-free grammars. We demonstrate significant performance gains across multiple synthesis problems, systematically comparing unstaged and staged computation,
as well as indicatively comparing with an existing hand-tuned relational interpreter.
This program is tentative and subject to change.
Wed 18 JunDisplayed time zone: Seoul change
10:30 - 12:10 | |||
10:30 20mTalk | Programming by Navigation PLDI Research Papers Justin Lubin University of California at Berkeley, Parker Ziegler University of California at Berkeley, Sarah E. Chasins University of California at Berkeley DOI Pre-print | ||
10:50 20mTalk | A Concurrent Approach to String Transformation Synthesis PLDI Research Papers DOI | ||
11:10 20mTalk | Exact Loop Bound Analysis PLDI Research Papers DOI | ||
11:30 20mTalk | Multi-stage Relational Programming PLDI Research Papers Michael Ballantyne Northeastern University, Rafaello Sanna Harvard University, Jason Hemann Seton Hall University, William E. Byrd University of Alabama at Birmingham, Nada Amin Harvard University DOI | ||
11:50 20mTalk | Program Synthesis From Partial Traces PLDI Research Papers Margarida Ferreira Carnegie Mellon University; INESC-ID; Instituto Superior Técnico - University of Lisbon, Victor Nicolet Amazon, Joey Dodds Amazon, Daniel Kroening Amazon DOI |