Third Sud Report

Stratego -- Strategies for Program Transformation

On May 3, 2002 the ThirdStrategoUsersDay was held at Utrecht University. During the day seven presentations about features or applications of Stratego were given. In the opening session an overview of activities in the Stratego community was given. The day was concluded with a discussion about needed extensions and improvements of Stratego and it implementation. The day was attended by:

Below you can find a short characterization of each of the presentations and the slides. At the bottom a few pictures taken by Niels Jannsen.

Past and Present of Stratego (slides)

Eelco Visser gave an overview of the achievements of the past year, the groups and people involved in Stratego and XT, and a list of ongoing projects. Among the features introduced over the last year are dynamic rules, global backtracking^?, term project, term wrap, term annotations, and concrete syntax. On the implementation side a number of innovations were introduced including the new compilation scheme^? introduced in StrategoRelease06, the division of the distribution in smaller packages, support for native lists and tuples, constant term caching, definition of the Stratego syntax in SDF and, innermost fusion. The XT distribution has matured and installs smoothly at many platforms.

Stratego is now used, mainly in research contexts, at Utrecht University, CWI, University of Bergen, and OGI. Projects include the StrategoCompiler itself, the XT tool bundle, AutoBundle, TigerInStratego^?, RhoStratego, CodeBoost, CobolX, Similix, HsOpt, and MatLabCompiler^?.

Although several people from other places report interest in using Stratego and XT, starting to use the tools seems to be hampered by a lack of documentation and examples. This should be a concern in the next period.

Meta Programming with Concrete Object Syntax (slides)

Eelco Visser gave a presentation about the extension of Stratego with concrete object syntax^?. This features allows the specification of terms using the concrete syntax of the object language, instead of abstract syntax terms. For example,

  PlusZero :  [[ x + 0 ]] -> [[ x ]]

instead of

   PlusZero : Plus(x, Int(0)) -> x

Especially for larger patterns and/or languages with a complex syntax (e.g., COBOL) this makes it much easier to write and read specifications.

The use of concrete syntax also introduces possibilities for confusion, such as the confusion between object identifiers and meta-variables. Instead of using identifier-like syntax for meta-variables, a convention is to start meta-variables with a $ or some such symbol. In the extension of Stratego the programmer can decide on such conventions, since the syntax of injections of object expressions into meta-expressions and the syntax of meta-variables is completely programmable.

Term Annotations (slides)

Martin Bravenboer presented the extension of Stratego with term annotations. This extension allows the programmer to access and manipulate annotations that can be attached to ATerms^?. Annotations can be used to add all kinds of semantics information such types and scope indicators, to programs. Annotations could also be useful in modeling attributes in XML. Martin's experiments with the implementation of annotations in StrategoRelease07 revealed a number of bugs that should be repaired in the next release.

There was much discussion about the merits of annotations. The advantage of annotations is the possibility of attaching more information to a term than the signature supports, i.e., without extending the basic representation of an abstract syntax additional information can be attached to identifiers, expressions, declarations, etc. This is also the weakness of annotations. Inherent in the idea of annotations is the fact that they are very fragile; when transforming a term, its annotations tend to get lost. The programmer has to be aware of the possible annotations of a term and consider whether and how to preserve them.

Experience will have to show whether or not annotations are useful in practice.

Reflection and Interprocess Communication

Hedzer Westra talked about two extensions of the StrategoStandardLibrary^?. The reflection library supports dynamic checking ot terms against the signature. The API provides operations for registering a signature, for checking the sort of a term, and completely checking the structure of a term.

The interprocess communication^? library supports the connection of Stratego (and other) components via sockets. Communication takes place by exchanging ATerms^?. One possible application is connecting to components written in another language (e.g., Java), for example, to connect to a database or webserver. Another application is the implementation of compiler plugins^? that provide an application or domain-specific transformation service to a compiler. A first experiment by Martin showed that connecting to Java programs does not work yet.

Dynamic Rules: A Tutorial (slides)

Eelco Visser gave a short overview of the basic features of dynamic rules. Dynamic rules allow the run-time generation of rewrite rules that inherit information from their context. This solves the limitations posed by the context-free nature of rewrite rules. Applications of dynamic rules include bound variable renaming, function inlining, dead function elimination, type checking, data-flow optimizations (the subject of the next talk).

Data-flow Optimizations (slides)

Karina Olmos illustrated the specification of data flow optimizations^? using dynamic rules by means of constant propagation. A specification of constant folding is gradually refined to include propagation through straight-line code, and structured control-flow constructs. This application required the extension of dynamic rules with operations for saving, restoring and intersecting sets of dynamic rules.

Partial Evaluation (slides)

Lennart Swart explained how partial evaluation for Similix works and how it can be implemented in Stratego.

Transforming Haskell Programs (slides)

Alan van Dam described his first steps on the path to implementing HsOpt, a transformation environment for Haskell programs (or rather Helium programs --- a subset of Haskell). HsOpt now consists of a parser and pretty-printer written in Haskell (by Rijk-Jan van Haaften), an ATerm reader and writer (based on the HATermLibrary^?), and a small set of simplification rules in Stratego.

Discussion: Future of Stratego

Joost Visser moderated a lively discussion about the future of Stratego. The following questions were the basis for the discussion:

Which improvements to Stratego and the Stratego tools are needed most?
How to teach Stratego?
How to improve communication within the Stratego community?

The first question took most of the time and yielded a long list of requests, mainly having to do with programmer productivity:

Separate compilation
- Compilation time should be reduced. The obvious way to achieve this is by a separate compilation scheme. The obstacle to a straightforward implementation of separate compilation is the extensibility of strategy operators. A less straightforward solution is possible in C. Addition of a final modifier that indicates that a definition cannot be extended is probably useful.

Stratego documentation
- The documentation needs updating and expansion. Documentation at several levels is needed:
- ExtendibleDocumentationGenerator: documentation generation for the library and user programs
- A Quick Introduction to Stratego^?
- Reference Manual^?: should be updated and completed
- A collection of examples
- Proposal: start adding material to this twiki first

Type system
- More static checking to catch programming errors
  - Format checker generator^?
  - Arity checker^?
  - Term type checker^?
- A notation for types of strategy operators for documentation purposes
- Possibility to add static analysis engines to the compiler

Name space^?
- A mechanism for name space management in the style of packages in Java and C# or modules in Haskell
- There seemed to be general agreement that modifiers (public, private) per definition are to be prefferred over lists of exported operators

Facilities for detecting where an unexpected failure originates
- Tracing
- Effects analysis

Miscelleneous
- list matching: syntactic sugar for extracting elements from a list would be useful for term annotation manipulation
- Stratego Script^?: What happened to the interpreter? It has not been included in the distribution since StrategoRelease06. Should it be reintroduced?
- Emacs mode^?: don't escape \
- Distribution of compiled Stratego programs (without the Stratego compiler)

This was followed by a short discussion about teaching Stratego. Some remarks:

Some people observed that it was very confusing at first to program without reference to the term being transformed. The lifted style of programming is typical for Stratego (define topdown without mentioning the thing that is being traversed), but not unique. For example, combinator programming in Haskell has the same properties. But this idiomatic shift should be addressed explicitly when first explaining the language. For example, by showing a eta-expanded versions of definitions and arguing that leaving out the redundant parameters and arguments leads to much more concise definitions.

Another observation is that there is some confusion in terminology: topdown is called a strategy, while purists would call an instance of topdown, e.g., topdown(try(Desugar)), a strategy and topdown a strategy combinator.

We didn't have time to address the final issue: improving information exchange, discussion in the Stratego community. Something should be done to extend the usage of the mailinglists and the wiki. Or are there othe r media to use?

Dinner

The dinner in restaurant Sardegna was quite good even though the food was served on some mysterious interleaving scheme such that we never had our food at the same time.

Pictures

NIels Jannsen took several pictures. Here are some:

-- EelcoVisser - 05 May 2002