Home
Schedule
Abstract Template
Masters Attendance
Fun With Attribute Grammars

Stc
Date: 2010-04-08

Time: 11:45

Room: [[http://www.cs.uu.nl/docs/reach/bbl.php][BBL]] [[http://www.cs.uu.nl/info/plan/bbl.php][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.