Wed 28 Oct 2015 10:30 - 10:52 at Grand Station 2 - 2. Domain Specific Languages Chair(s): Eelco Visser

We present an algorithm for synthesizing efficient document layout engines from compact relational specifications. These specifications are compact in that a single specification can produce multiple engines, each for a distinct layout situation, i.e., a different combination of known vs. unknown attributes. Technically, our specifications are relational attribute grammars, while our engines are functional attribute grammars. By synthesizing functions from relational constraints, we obviate the need for constraint solving at runtime, because functional attribute grammars can be easily evaluated according to a fixed schedule, sidestepping the backtracking search performed by constraint solvers. Our experiments show that we can generate layout engines for non-trivial data visualizations, and that our synthesized engines are between 39- and 200-times faster than general-purpose constraint solvers. Relational specifications of layout give rise to synthesis problems that have previously proved intractable. Our algorithm exploits the hierarchical, grammar-based structure of the specification, decomposing the specification into smaller subproblems, which can be tackled with off-the-shelf synthesis procedures. The new synthesis problem then becomes the composition of the functions thus generated into a correct attribute grammar, which might be recursive. We show how to solve this problem by efficient reduction to an SMT problem.

Wed 28 Oct

Displayed time zone: Eastern Time (US & Canada) change

10:30 - 12:00
2. Domain Specific LanguagesOOPSLA at Grand Station 2
Chair(s): Eelco Visser Delft University of Technology
10:30
22m
Talk
Synthesis of Layout Engines from Relational Constraints
OOPSLA
Thibaud Hottelier Graphistry, Inc, Rastislav Bodík University of Washington, USA
Link to publication Media Attached
10:52
22m
Talk
A Sound and Optimal Incremental Build System with Dynamic DependenciesOOPSLA Artifact
OOPSLA
Sebastian Erdweg TU Darmstadt, Germany, Moritz Lichter TU Darmstadt, Germany, Manuel Weiel TU Darmstadt, Germany
Link to publication Media Attached
11:15
22m
Talk
FlashMeta: A Framework for Inductive Program Synthesis
OOPSLA
Alex Polozov University of Washington, USA, Sumit Gulwani Microsoft Research, USA
Link to publication DOI Media Attached
11:37
22m
Talk
Scrap your Boilerplate with Object AlgebrasOOPSLA Artifact
OOPSLA
Haoyuan Zhang University of Hong Kong, China, Zewei Chu University of Hong Kong, China, Bruno C. d. S. Oliveira University of Hong Kong, China, Tijs van der Storm CWI
Link to publication Media Attached