Stratego/XT 0.15

Stratego -- Strategies for Program Transformation
Stratego/XT 0.15 -- released July 5, 2005

This is an experimental release featuring a refactoring of the internals of the language definition and compiler. Please report problems to


See the installation instructions if you are not familiar with the standard installation procedure of tarballs or RPMs.

Source tar.gz

Source RPM

Redhat Linux RPM

Redhat 9.0:

SuSE Linux RPM

SuSE 9.0:

Fedora Core RPM

Fedora Core 2:

Fedora Core 3:

  • Build of rpm on FC3 failed because of a bug in GCC

Microsoft Windows Cygwin binaries

Sorry, no Cygwin binaries for this release.

Mac OS X binaries

Sorry, no OS X binaries for this release.



StrategoXT is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.


Despite the disclaimer above we do our best to help users of Stratego/XT. Subscribe to the Stratego mailing lists, in particular the stratego-announce and stratego mailing lists to get announcements of new releases and ask questions about usage of the languages and tools. Also we're interested to know what people are using Stratego/XT for and how it might be improved, so feel free to drop us a line.

Summary of Changes

This is a release of a major milestone in the Stratego Core refactoring project. It is not considered to be a production release to be used by average users. Use of the release for testing by seasoned Stratego developers who maintain applications in the Stratego/XT environment, would be appreciated, however.

This release will be followed by a number of minor releases, introducing improvements in the areas of the compiler back-end, dynamic rules, the module system, and the optimizer. This should result in a stable and much improved Stratego compiler in release 0.16.

Since the distributions before 0.16 are experimental, distributions are only provided through the Nix release management system. No binaries for Windows and MacOSX? will be available. RPMs for Fedora Core 3 are not provided due to a bug in GCC in that distribution.

Stratego Language

Stratego Core Language

The Stratego Core language project constitutes a major refactoring of the syntax definition of the language, also requiring a refactoring of all tools and components processing Stratego programs (in particular the compiler).

The project was prompted by the problems encountered in building the first version of the Stratego Optimizer in 2003. In particular, with the representation of term annotations in the abstract syntax. In addition the language design had eroded somewhat over the years through the addition of new features.

Thus, the aims of the project are threefold:

(1) Clearly distinguish a core language to be used as intermediate language in the compiler.

(2) Explicitly represent term annotations in the abstract syntax of the core language.

(3) Cleaning up the language, removing constructs that have not proven to be useful, or have been subsumed by more more general constructs.


Despite the changes in the structure of the language, the syntax is backwards compatible. This entails that existing applications should still work. Except of course for applications using constructs that have been removed. However, the decision to remove constructs was based on the fact that these were not used (some not even document), so this shouldn't pose a big problem. The only change with potential impact is discontinuation of support for old style dynamic rules. New style dynamic rules are the default in StrategoXT 0.14 and should be a good platform for preparing migration.

Core vs Sugar

The syntax definition is now divided into a Stratego-Core language that is extended to the full language in Stratego-Sugar, adding syntactic abstractions to the Core. The Core is a strict subset of the full language. In addition, a number of regular tree grammars has been defined that denote a number of intermediate languages between Stratego-Sugar and Stratego-Core. These RTGs are used by the compiler to verify the sanity of the compiler components.

Term Annotations

Term annotations were not originally supported in Stratego. The addition was handled by desugaring the matching and building of terms with annotions to calls to ATerm library functions using primitives in an early stage of compilation. The implicit presence of annotations made transformations within the compiler very fragile, and entailed that certain optimizations could not be defined properly.

In the new core syntax, terms always have an annotation. A pre-term (pt) has the form

pt := i | r | x | c(t1,...,tn)

and denotes a term without annotation. A term (t) is a pre-term with an annotation (which is itself a pre-term):

t  := pt{^pt}

This is the explicit representation of term annotations; every term always has a list of annotations. That is, the annotation pre-term should always be a list of the form

Cons(t1,...,Cons(tn, Nil())
Since most terms do not have annotations, or we're not interested in them, in the sugared extension of the core language, term annotations are optional. Thus, in Stratego-Sugar, the syntax of terms is extended with:
t := pt | pt{t1,...,tn}
The interpretation of this syntax depends on the use of the term in a match or build position. That is, the following desugaring rules apply:
|[ !pt ]| -> |[ !pt{^Nil()} ]|
|[ !pt{t1,...,tn} ]| -> |[ !pt{^Cons(t1,...,Cons(tn,Nil()))} ]|

|[ ?pt ]| -> |[ ?pt{^_} ]|
|[ ?pt{t1,...,tn} ]| -> |[ ?pt{^Cons(t1,...,Cons(tn,Nil()))} ]|
(Note that this is a bit simplified, as the Conses and Nils in the right-hand side have annotations themselves, except for the outermost ones.)

So a rewrite rule

A : Plus(x, y) -> Plus(y, x)
is desugared to
A : Plus(x, y){^_} -> Plus(y, x){^Nil()}

(Eelco Visser)


The syntax of types of higher-order arguments of strategy definitions was ambiguous. Thus, the type of the skip argument in

topdownS(s : ATerm() -> ATerm() , skip : a -> a * a -> a) = ...
could be parsed as
a -> (a * a -> a)   or ((a -> a) * a) -> a
This has been solved by only allowing function types as argument types when between parentheses. Thus, the above is not syntactically valid, but should now be written as
topdownS(s : ATerm() -> ATerm() , skip : (a -> a) * a -> a) = ...

It is better to require explicit disambiguation since it is easy to have the wrong expectation from implicit disambiguation in this case.

There was no priority definition between guarded left-choice and non-deterministic choice, such that the expression

s1 < s2 + s3 + s4
could be parsed in two ways, i.e.,
s1 < (s2 + s3) + s4   or   s1 < s2 + (s3 + s4) 
This has been resolved by giving the + operator higher priority than guarded choice to prefer the latter over the former. The first variant can be selected by using explicit parentheses.

(Eelco Visser)

Rules in let

Let bindings can now introduce new rules. For example,

main =
  let Foo : 1 -> 2
   in <Foo> 1 => 2

Local rules shadow rules with the same name (and arity) at top-level. The scope of the rule variables is the enclosing definition, not just the rule itself! This is in line with the semantics of local definitions, but the practicality of this design choice should be reviewed.

(Martin Bravenboer)

Outdated constructs no longer supported

A number of language constructs have been subsumed by more general constructs, or were simply never used. These constructs have been removed from the language definition starting with this release.

Old style dynamic rules are no longer supported. Everything expressible with old style rules can also be expressed with new style dynamic rules. See the paper 'Program Transformation with Scoped Dynamic Rewrite Rules' for definition and examples of new style dynamic rules.

Contextual rules can now better be expressed using dynamic rules. Local uses of contextual rules can also be defined using a local traversal. See the paper 'Strategic Pattern Matching' for a discussion of translation of contextual rules that can be applied by hand.

Literate programming comments such as

  foo = ...
are no longer supported. Use standard comment delimiters instead.

Other constructs that are discontinued are strategy rules of the form

L :: s1 --> s2
The thread traversal operator (can be expressed in the library), and threading and distributing congruence operators.

(Eelco Visser)

Stratego Core Compiler

The Stratego compiler now compiles programs according to the Stratego-Sugar syntax definition. The front-end of the compiler is drastically refactored and simplified. The optimizer has been disabled in this release. Migration and improvement of the optimizer has been planned for release 0.15.4.

Format Checking

The compiler monitors its own integrity by checking the format of intermediate results against subsets of the Regular Tree Grammar of the complete syntax definition. By default checks are only carried out at a few places, to save compile time. In case an error occurs, the level of checking can be increased using the --format-check option of strc.

(Eelco Visser)

List Variables

The treatment of list variables is cleaned up by improving their assimilation in meta-explode. This has made it possible to have fewer compiler components be aware of list variables. If list variables in concrete syntax quotations should be used as list variables outside those quotations as well, they should have a * suffix. See issue STR-321.

Realization of this clean-up required a bugfix in implode-asfix and a change in the assimilation of concrete syntax, which entails that Conc(ts1,ts2) is now used as a special constructor to denote the concatenation of two lists. In particular, if Conc(ts1,ts2) is used in a build, this is interpreted as (ts1, ts2). In other words Conc, cannot be used as a normal constructor.

(Eelco Visser)

Stratego Library

The definition of collect-all with a skip has been adapted to recurse to the current term instead of the children of current term in the case of application of the skip strategy.

(Report by Ron de Bruijn, Fix by Martin Bravenboer)

The string concatenation strategy conc-strings now supports tuples of more than 2 strings.

(Rob Vermaas)



pptable-diff now takes the arity of constructors into account.

(Martin Bravenboer)


The implementation of sig2rtg was not compatible with the new Stratego syntax. Since the tool does not seem to be used, migration has been deferred.

(Eelco Visser)

StrategoXT Deployment and Build System

Build order of stratego-front and stratego-lib

The build order of stratego-front and stratego-lib has been swapped in case of a baseline build. The modules in the library should be parsed with the local syntax definition of Stratego, instead of the syntax definition of the baseline. Since the library should be used with the compiler in the current package, it should be compatible with that compiler and use the same syntax definition. When bootstrapping (building from a pre-compiled source tarball), the build-order is reversed since the library is needed for the compilation of the components in stratego-front. Also in the case of a bootstrap build, xtc is built before stratego-front.

(Eelco Visser)

Detailed List of Issues

The full list of issues closed in this release is available at:

Download and Installation

The release page contains the source distributions, binary RPMs, and detailed instructions on how to install the distributions:

Bugs and Known Problems

See our issue tracking systems for reports about (open) bugs:

Please report any problems with installation or bugs in the implementation to our issue tracking system. Please check the existing issues to see if a report about the problem was already submitted.


The Stratego Core refactoring was carried out by

  • Eelco Visser

Other improvements, bug reports, and beta tests carried out by

  • Martin Bravenboer
  • Ron de Bruijn
  • Rob Vermaas
  • Daniel Waddington