Fun With Attribute Grammars
Stc
Date: 2010-04-08
Time: 11:45
Room:
BBL 023
Speaker: Arie Middelkoop
Title: Fun With Attribute Grammars
Abstract
We use attribute grammars extensively to program traversals over trees. The programming model in terms of attributes of trees is convenient: the order of appearance of code for attributes in source files is irrelevant (allowing separate specification), and code for attributes related to a topdown, bottom up, or inorder traversal can be left out (saving the programmer from a lot of boilerplate).
The formalism comes with a price: attribute grammars can only be applied to those functions that you can write as a fold (e.g. in Haskell). However, there are many tree-like traversals that we cannot write as a fold. For example, unification (simultaneous traversal of two type trees), constraint solving (dynamic construction of derivation tree), and graph traversal (node may have multiple parents). Such traversals typically resemble tree traversals and we would like to program these with attribute grammars as well.
In this talk, I show you how to write any Haskell function as an attribute grammar in a straight-forward way. The idea is that the programmer specifies with some additional notation how to construct and decorate a virtual attributed tree during attribute evaluation. This virtual tree is a representation of the traversal, similar to a call graph being a representation of function calls. The programmer can consequently program any function in terms of attributes, with a small tradeoff due to the extra work of specifying the virtual traversal.
