Home
Schedule
Abstract Template
Masters Attendance
Center
Home
Courses
People
Projects
Page
Edit Page
Rename Page
Attach File
Printable
Wiki Source
More ...
Web
Recent Changes
Notify Service
News
Page Index
Search
More ...
Wiki
About TWiki
Text Formatting
Registration
Change Password
Reset Password
Users
Groups
Log In
or
Register
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.