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 OctDisplayed 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 22mTalk | Synthesis of Layout Engines from Relational Constraints OOPSLA Link to publication Media Attached | ||
10:52 22mTalk | A Sound and Optimal Incremental Build System with Dynamic Dependencies OOPSLA Sebastian Erdweg TU Darmstadt, Germany, Moritz Lichter TU Darmstadt, Germany, Manuel Weiel TU Darmstadt, Germany Link to publication Media Attached | ||
11:15 22mTalk | FlashMeta: A Framework for Inductive Program Synthesis OOPSLA Link to publication DOI Media Attached | ||
11:37 22mTalk | Scrap your Boilerplate with Object Algebras 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 |