Stratego (back) in Portland

On 15 October 1997 I arrived in Portland, Oregon to do a postdoc at the Oregon Graduate Institute. During the year I lived in pretty Portland NW (picture).

Before arriving in Portland I had defended my thesis on Syntax Definition for Language Prototyping in which I introduced scannerless generalized-LR parsing and a syntax definition formalism (SDF2) supporting that parsing algorithm.

As a side project during writing my thesis I had started experimenting with rewriting strategies together with Bas Luttik. When I left OGI a year later I had designed (with Zino Benaissa and Andrew Tolmach) a programming language based on rewriting with programmable strategies, developed the first bootstrapping compiler for the language, presented it at ICFP’98, and decided that it could have no other name than Stratego. Since then, I and many others have worked on and with Stratego and the transformation toolset XT that connects SDF and Stratego.

Nine years later I was in Portland again to attend OOPSLA/GPCE 2006.To see how SDF and Stratego have fared in those years, it is instructive to see their manifestation at this conference (which was held in the convention center on the southside of the Willamette river with a view on downtown Portland to the north).

At any conference I’d be happy with one or a couple of papers/presentations from my group. There were several here. At the Software Transformation Systems Workshop I gave a presentation about the projects we’re starting up in Delft on the integration of domain-specific languages in the software development process. (We have four open positions.) Martin Bravenboer gave a presentation about the lack of impact of the STS community (more about that later). We also gave a tutorial on Building Java Transformations with Stratego/XT, which amounted to a basic introduction to Stratego.

But our main contribution this year was the OOPSLA paper about a declarative syntax definition for AspectJ, which is a case study in the application of SGLR/SDF to the definition of language ‘conglomerates’, for which traditional parsing techniques break down.

While in itself already a decent contribution to a conference, I was delighted by the contributions from other groups that were directly or indirectly related to the Stratego/XT project.

The group of Magne Haveraaen at Bergen University can be considered as fairly directly associated with the Stratego project. He adopted Stratego early on for the implementation of the CodeBoost domain-specific optimization tool, and sent Anya Bagge to Utrecht to become one of the first users. She gave a talk at the Domain-Specific Aspect Languages Workshop (DSAL) about an experimental extension for exceptions implemented with Stratego using the approach from the Transformations for Abstractions paper. After his master’s thesis on domain-specific optimization, Karl Trygve Kalleberg has been working on several extensions of Stratego (e.g. aspects, graph rewriting); he talked at STS about the needs for reusable front-ends. At GPCE Magne talked about moulding failure and exceptions to your needs, a mechanism for allowing users to adapt the ways exceptions from libraries are handled to the needs of an application. The mechanism was implemented as an extension of C using the Transformers infrastructure.

At GPCE, Jonathan Riehl presented his ideas forAssimilating MetaBorg. MetaBorg is a method for embedding domain-specific languages (DSLs) in a general-purpose language (GPL). The method is supported by DSLs; SDF for syntax definition and Stratego for assimilation (translating the embedded language to the host language). John proposes in his paper to embed these DSLs in a GPL themselves such that language embeddings can be defined within a program, rather than in a preprocessor or extension of the compiler. While the idea is interesting, its realization is not trivial. In particular, it requires a solution for dynamic extension of the parser (during parsing). There are also questions about the design of an extensible GPL; for instance, are the definitions of an extension static constructs or are they subject of computation as well. At least one effect of the paper has been that we are now seriously considering dynamic language extension; something we had decided not to support in the original (OOPSLA’04) MetaBorg paper.

Other interesting contributions are those that are plain uses of Stratego/XT to support research in other areas.

For example, the following quote is from the paper “A Commensalistic Software System” by Sebastian Fleissner and Elisa Baniassad, which was presented in the Onward! track at OOPSLA.

Since the prototype is based on Java, all Comm-L programs are translated intoJava class files in two steps. The first step uses the Stratego/XT toolkit described in [2] to transform the Comm-L code into Java source code. The second step uses the JDK compiler to generate translate the Java source code into class files. The Stratego/XT toolkit is used in this prototype, because of its ease of use and flexibility.

And they did this without any interaction with anyone of the Stratego/XT team, a sign that the documentation is in a good state these days.

Also at OOPSLA was a poster from <a href=”http://web.comlab.ox.ac.uk/oucl/people/oege.de.moor.html”Oege de Moor</a>’s group in Oxford, which included work using Stratego to define a mapping from AspectJ pointcut expressions to datalog queries (POPL’07 paper).

I also talked to Dan Quinlan from the Lawrence Livermore National Laboratory who told me that Stratego was being used in a project in the Rose transformation system for domain-specific optimization.

Another category of work are approaches that reuse ideas from Stratego. At STS Pierre-Etienne Moreau gave a presentation about strategies in Tom. Tom is an extension of Java providing an algebraic term view of objects. The extension supports pattern matching and rewrite rules. Tom adopts Stratego’s strategies with a reflexive twist; Strategies are objects and can thus be computed at run-time.

So, while Stratego/XT is not yet on every (software developer’s) desktop, the use in academia is growing, which makes me optimistic about the future.

For more photos from the trip see the photosets Portland 2006 and Eugene; the latter has photos of our visit to Yannis Smaragdakis and Shan Shan Huan in Eugene.