Thibaud Hottelier and Ras Bodik

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2014-181

November 19, 2014

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-181.pdf

We present an algorithm for synthesizing efficient document layout engines from relational specifications. These specifications are high level in that a single specification can produce engines for distinct layout situations. Specifically, our engines are functional attribute grammars, while the specifications are relational attribute grammars. By synthesizing functions from relations (constraints), we obviate the need for constraint solving at runtime, shifting this cost to compilation time. Intuitively, the synthesized functions execute only value propagations and bypass the backtracking search performed by constraint solvers. By working on hierarchical, grammar-induced specifications, we make synthesis applicable to previously intractable relational specifications. We decompose them into smaller subproblems which are tackled in isolation by off-the-shelf synthesis procedures. The functions thus generated are subsequently composed into an attribute grammar which satisfies the relational specification. Our experiments show that we can generate layout engines for non-trivial data visualizations, and that our synthesized engines are between 39- to 200-times faster than general-purpose constraint solvers.

---

BibTeX citation:

@techreport{Hottelier:EECS-2014-181,
    Author= {Hottelier, Thibaud and Bodik, Ras},
    Title= {Synthesis of Layout Engines from Relational Constraints},
    Year= {2014},
    Month= {Nov},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-181.html},
    Number= {UCB/EECS-2014-181},
    Abstract= {We present an algorithm for synthesizing efficient document layout engines from relational specifications.  
These specifications are high level in that a single specification can produce engines for distinct layout situations. Specifically, our engines are functional attribute grammars, while the specifications are relational attribute grammars. By synthesizing functions from relations (constraints), we obviate the need for constraint solving at runtime, shifting this cost to compilation time. Intuitively, the synthesized functions execute only value propagations and bypass the backtracking search performed by constraint solvers. By working on hierarchical, grammar-induced specifications, we make synthesis applicable to previously intractable relational specifications. We decompose them into smaller subproblems which are tackled in isolation by off-the-shelf synthesis procedures. The functions thus generated are subsequently composed into an attribute grammar which satisfies the relational specification. Our experiments show that we can generate layout engines for non-trivial data visualizations, and that our synthesized engines are between 39- to 200-times faster than general-purpose constraint solvers.},
}

EndNote citation:

%0 Report
%A Hottelier, Thibaud 
%A Bodik, Ras 
%T Synthesis of Layout Engines from Relational Constraints
%I EECS Department, University of California, Berkeley
%D 2014
%8 November 19
%@ UCB/EECS-2014-181
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-181.html
%F Hottelier:EECS-2014-181