Attribute Grammars in Stratego

March 11, 2008

This morning I gave my very first lecture on attribute grammars, featuring Knuth’s binary numbers AG (ripped from the jastadd.org site), and my own implementation of WebDSL data models in JastAdd. In the slides I explored the implementation of model of JastAdd by including the code it generates. While I had not added any JastAdd code since last week, the presentation further improved my understanding what is going in JastAdd. At the same time, I’m realizing I do not fully understand the design space we are considering, and the distinction between notational and essential differences between the various approaches.

In the afternoon, Nicolas Pierron, a student from the Transformers group at Epita who is doing an internship in Delft, showed the code of his implementation of WebDSL typechecking in the Transformers SDF attribute grammar extension, which is implemented by generating Stratego code with some native code hacks. The hacks basically implement thunks of deferred attribute evaluations for nodes in the tree with pointers to dependent attribute value thunks. Attributes are then evaluated on demand, and thus no static scheduling is done. This approach is essentially the same as that of the encoding of attribute grammars in a lazy functional language such as Haskell (a hobby of my former colleagues in Utrecht). If we would just add heap-bound closures to Stratego, implementing this pattern would become that much easier.

The Transformers AG code operates on ATerms without sharing. Again, I’m not sure about the implications of this design choice. Are the Stratego libraries at all usable without maximal sharing? I guess I should ask Nicolas tomorrow.

To be continued.