Home
Schedule
Abstract Template
Masters Attendance
First Class Tree Traversal Idioms With Nested Attribute Grammars

Stc
Date: 2010-04-15

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: First Class Tree Traversal Idioms with Nested Attribute Grammars

----+++++  Abstract

Software components for almost any aspect of a compiler are available in surplus amounts. Parsers, pretty printers, environment dictionaries, unification libraries, graph libraries, constraint solver frameworks, some standard bottom up/top down tree traversals, etc. The list goes on and on. You may, however, be surprised that you cannot find off-the-shelf components for typical tasks, such as name analysis and type checking.

For example, suppose you want to use the UHC compiler as basis for an OCaml compiler. UHC ships with about all of the libraries above. You'll then notice that you can reuse many of these libraries verbatim. However, you'll also notice that the attribute grammar description of the type checker has to be rewritten entirely (due to different abstract syntax), although there will be a strong similarity between the two descriptions.

These similarities correspond to tree traversal idioms ("design patterns for AG code"). One of these idiomatic traversals is name analysis. With name analysis, bottom up an environment is collected, containing the name and e.g. a type introduced at binding-sites in the AST. At a diversity of places in the AST, this collected environment is combined with the environment from the parent, and passed topdown, with a lookup of the value at use-sites. During the process, duplication errors and missing-definition errors are discovered. In the type checking code of UHC, we can find occurrences of this idiom already more than ten times. Many more idioms can be found in the UHC code base.

In this talk, we show how to abstract from these idioms, and turn them into reusable and extensible software components. Instantiation of such a component gives us the actual traversal that we desire. We will see that instantiation of a component corresponds to a runtime construction of the traversal itself (hence, the traversals will be first class). Furthermore, we need to extend the AG formalism to handle extension of components and interfacing with them. Nested Attribute Grammars, where the rules for attributes of a tree are defined in the scope of attributes of nodes of a different tree, provide the expressive power that we need.