Sunday, March 4, 2012

Modeling language experience report: synthesizing CSS's automatic table layout solver

Table rendered using an automatically synthesized layout solver.

Model-driven languages handle complexity in implementing a language. For example, after designing a language feature, you want it to work with the optimizer, parser, IDE, etc. As the language gets more complicated, such as we've seen with the increasing scope of the CSS layout language, the implementation burden gets so high that many seemingly small language extensions and tool improvements require understanding a lot of the eco-system. With modeling languages, we can use synthesizers and code generators to correctly write features, avoid duplication of work, and basically handle more code than you could manually. For example, we don't want to manually teach the Firebug debugger about CSS semantics nor, when parallelizing for multicore or SIMD hardware, do we want to manually look at every edge case in the layout specification.

We picked attribute grammars as the basic specification language for our parallel browser layout language work. However, this begs the question: are attribute grammars expressive enough to actually handle layout languages?** Previously, we wrote (and automatically parallelized) various visualizations, so we know attribute grammar can be used for
future languages. We're now going after the elephant in the room: CSS. As a fun start, Ras and I just put together an experience report about our successful experience with synthesizing an implementation of the 'automatic table layout' specification.

In short, it works. The table above was rendered using an automatically generated layout engine. Furthermore, our synthesizer found a multicore implementation for it. Neat :)

Stay tuned for more and we'll welcome any challenge problems :) Props to Ras, Matt, and Sam for help in revising that report!

**: More specifically, can we do this with statically scheduled attribute grammars? I'm distinguishing against 'demand-driven' and other approaches that essentially reduce to the Turing tar pit via general lazy functional programming.
Post a Comment