Okay, so after having applied attribute grammars to one or two things now, I think this is one of the Great Tree Transformation Tools the design team has been looking for. Of course, Allison has known this for a long time, but I guess she failed to convince me.
Anyway, I went to have a chat with Prof. William Waite here at the University of Colorado. He's done extensive research on compiler tools in general and attribute grammars in particular. I told him about my implementation in Language::AttributeGrammar, and he told me that that's about the worst way to do it. Sure, the time complexity is no worse than that of any other algorithm, but the memory complexity is horrific. Both are O(na), for n the number of nodes in the tree and a the number of attributes. A serious implementation in terms of attribute grammars is going to have hundreds of attributes, so linear space in the number of attributes is unacceptable.
He pointed me to some literature, in particular "Lecture Notes in Computer Science #545". I read up, and it turns out that the algorithms for preprocessing the grammar statically to remove laziness (resulting in a linear speed boost) and deallocate attributes when you're done with them (resulting in potentially massive space boosts) are not terribly difficult to implement. A little graph theory here, a little lifetime analysis there.
So I'm going to rewrite my module to incorporate static analysis. Also, as you saw in the design meeting notes, Patrick and chromatic want it for Parrot. So I'm going to design it pluggably (syntactically and code-generatively), but I personally dislike programming in assembly (even if it is high-level parrot assembly), so I'll let them do the dirty work.
