Edoardo Vacchi on attribute grammars

I previously wrote that predictable performance is a practical challenge for using attribute grammars on real work. It does little good to quickly write the first version of a compiler pass if you then spend hours debugging oddball performance problems.

Edoardo Vacchi wrote me the following in response. I agree with him: having an explicit evaluation construct, rather than triggering attribute contributions automatically, is likely to make performance more predictable. UPDATED: edited the first paragraph as suggested by Edoardo.

Hi,

This is Edoardo Vacchi from Università degli Studi di Milano (Italy). For my PhD thesis I’m working on a language development framework called “Neverlang”[1,2]. Neverlang is an ongoing project of Walter Cazzola's ADAPT Lab; I am involved with its latest incarnation "Neverlang 2".

I stumbled upon an (old) blog post of yours about Attribute Grammars [3] and I would be interested to know if you knew some “authoritative” references that I could cite with respect to the points that you raise, with particular attention to point (3) “unpredictable performances” and, in part, to (2) caching.

The Neverlang model resembles that of simple “compiler-compilers” like Yacc, where attributes behave more like variables than functions; thus they are generally computed only once; in Neverlang attributes can also be re-computed using the `eval` construct, which descends into a child and re-evaluates the corresponding semantic action.

On the one hand, the need for an explicit `eval` make it less “convenient” than regular AG-based frameworks; on the other hand, I believe this gives better predictability, and, although the focus for the framework are not performances, but rather modularity, I think that “predictability” would better motivate the reasons for this choice.

Thanks in advance,

[1] http://link.springer.com/chapter/10.1007%2F978-3-642-39614-4_2#page-1
[2] http://dl.acm.org/citation.cfm?id=2584478
[3] http://blog.lexspoon.org/2011/04/practical-challenges-for-attribute.html

Edoardo Vacchi is PhD Student at Walter Cazzola's ADAPT-Lab, a research lab at Università degli Studi di Milano that investigates methods and techniques for programming language development and software adaptation and evolution. Walter Cazzola is associate professor at UniMi and his research is concerned with software and language engineering. More info about Neverlang can be found at the website http://neverlang.di.unimi.it.

Practical challenges for attribute grammars

I've had occasion recently to work on a compiler implemented with an attribute grammar framework. Such frameworks let you declare attributes on AST nodes that are computed in terms of other attributes. In general, it's a powerful and convenient way to compute information about an AST, and I expect they make a lot of sense in tools that only analyze ASTs and don't generate or rewrite them. They save you from working out a specific computation order, because the tool can look at which attributes refer to which other ones and compute them all on demand.

For compilers, however, I no longer think attribute grammars work well. Let me describe three fundamental problems with attribute grammars for use in compilers.

1. Attributes can be inherited, meaning they look up in the AST to for information. Examples are the expected type of an expression, the enclosing module for any node, and the set of free variables available in some context. These computations cannot be computed unless the node in question really is attached to an AST. However, compilers create new AST nodes all the time, and while those new nodes are being set up, they can't possibly be attached yet. Thus, unattached nodes are inconsistent with inherited attributes.
   
   
2. Compilers change the AST. They desugar syntax into lower-level syntax, they optimize, they reorder parts of the program, and so on. Every time the AST changes, some cached attribute values become invalid. At that point, how do you flush the caches that are now invalid? To some extent you can get by by flushing all caches after every compiler phase. However, this means that later parts of a phase will see stale data compared to earlier parts. This situation results in bugs where, to fix them, you have to reason about the exact order that the traversal happens and the relationship of the stale data to the current version of the AST.
   
   
3. Attributes have unpredictable performance characteristics. When you see a reference to an attribute, it might be cached and take constant time. On the other hand, it might trigger a chain of attribute computations that chain across the whole program. It's much harder to convince yourself that a particular AST traversal will operate in linear time, because you don't know how expensive all the attribute computations are.
   

These are all potentially addressable, but they are serious challenges that any practical tool will need to face. As things stand, I haven't seen an attribute grammar framework that is there yet. They don't really achieve their main benefit, which is to save you from reasoning about order of evaluation of and dependencies between different attributes. You end up reasoning about them anyway to get the bugs out and the performance up.

Instead of storing attributes on the AST nodes and computing them with an attribute grammars framework, a more traditional approach is as follows. Store a few, carefully selected bits of information on nodes, such as the types of expressions. These things must be carefully maintained across all AST rewrites, and the compiler will be buggy if you get it wrong, so don't store too much this way. For most information, have each compiler phase compute and maintain whatever information it needs. This results in some amount of computation, but you can usually find a way to calculate whatever you need in linear time. Since any one phase will usually require at least linear time, anyway, this is sufficient for getting the compiler reasonably performant before you do your first profile run.