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

oopsla2015
10:30 - 12:00: OOPSLA - 2. Domain Specific Languages at Grand Station 2
Chair(s): Eelco VisserDelft University of Technology
oopsla2015144602460000010:30 - 10:52
Talk
Thibaud HottelierGraphistry, Inc, Rastislav BodikUniversity of Washington, USA
Link to publication Media Attached
oopsla2015144602595000010:52 - 11:15
Talk
Sebastian ErdwegTU Darmstadt, Germany, Moritz LichterTU Darmstadt, Germany, Manuel WeielTU Darmstadt, Germany
Link to publication Media Attached
oopsla2015144602730000011:15 - 11:37
Talk
Alex PolozovUniversity of Washington, USA, Sumit GulwaniMicrosoft Research, USA
Link to publication DOI Media Attached
oopsla2015144602865000011:37 - 12:00
Talk
Haoyuan ZhangUniversity of Hong Kong, China, Zewei ChuUniversity of Hong Kong, China, Bruno C. d. S. OliveiraUniversity of Hong Kong, China, Tijs van der StormCWI
Link to publication Media Attached