Stratego/XT 0.16

Stratego -- Strategies for Program Transformation

Stratego/XT 0.16 -- released November 4th, 2005

Warning: This release has known issues with recent GCC 4.x, GNU Make 3.81, Mac OS X, and operating systems that have a non-executable stack (e.g. some recent Linux distributions). We advice to install the latest successful integration build.

Download

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:

Fedora Core 5:

Gentoo

Stratego/XT is available as dev-lang/stratego-0.16
Run ACCEPT_KEYWORDS="~x86" emerge \=dev-lang/stratego-0.16 (or ~ppc) to install it.

Microsoft Windows Cygwin binaries

The *-cygwin.tar.gz files contain a file README with installation instructions.

Mac OS X binaries

The *-macosx.tar.gz files contain a file README with installation instructions.
Warning: Stratego/XT 0.16 only supports PowerPC Macs. If you have an Intel Mac, then please use the latest unstable release, which fully supports Mac/Intel machines. See also the topic on Max OS X support

Nix Package

One-click installation using Nix, open with /nix/bin/nix-install-package

i686-linux:

powerpc-darwin (MacOS X)

Documentation

Stratego/XT Manual

The Stratego/XT Manual is a series of three books: a tutorial, a series of examples, and a reference manual with the finer details of the language and tools. The manual is available online and can be downloaded for offline use.

Online version:

Stratego/XT 0.16 Manual

Download for local and offline use:

Warning: this manual is specific for Stratego/XT 0.16 and will not be extended. The latest version of the manual, available at at the documentation page, might be more extensive, but might also cover features that were not yet available in Stratego/XT 0.16.

Stratego/XT API Documentation

Online API documentation:

Download API documentation for local and offline use:

Stratego Library: stratego-lib-docs-0.16.tar.gz
XTC Library: xtc-docs-0.16.tar.gz

License

Stratego/XT 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.

Support

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

Stratego/XT 0.16 introduces a major refactoring of the Stratego Language, resulting from the Stratego Core project.

The project comprises a cleanup of the language, removing obsolete language constructs, and a refactoring of the internal representation of Stratego programs. In particular the abstract syntax of terms has been refactored in order to treat term annotations explicitly within the compiler.

In addition, a large number of outstanding issues have been addressed.

Last, but not least, we have been working on an extensive manual for Stratego/XT, covering all the aspects of the Stratego language, giving an overview of the Stratego Library, and the introducing the XT Transformation Tools. This new manual will be a very valuable resource for new and existing users.

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.

Impact

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 Stratego/XT 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 annotations 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()}

(STR-58)

Disambiguation

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
    end

Local rules shadow rules with the same name (and arity) at top-lovel. 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

\begin{code}
  foo = ...
\end{code}

are no longer supported. Use standard comment delimiters instead. In the future, we we also remove the ML-style comments (* *), which is deprecated in Stratego/XT 0.16.

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.

Overlays are no longer allowed to contain strategy applications. For example,

overlays
  Foo(x) = Bar(<s> x)

is no longer supported.

(Eelco Visser)

Calling strategies by their name

Strategies can now be called dynamically by name.

  !"do-it-now" => f ; call(f | s | t )

Above dynamic call calls the do-it-now strategy with s as strategy argument and t as term argument. If the strategy does not exist (given the name, and arities) the dynamic call will fail without warning.

At the moment it is necessary to 'register' a strategy to be able to call it dynamically. Make a dummy strategy DYNAMIC-CALLS with static calls to the strategies you want to call dynamically.

  DYNAMICAL-CALLS = do-it-now(!1 | 1)

This is only temporary until we find a good syntax for specifying this.

(Rob Vermaas)

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. Some of the optimizer components have been disabled in this release and the default optimization level is -O 2. Migration and improvement of the remaining optimizer components has been planned for release 0.17M3.

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.

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)

Translation Scheme I: Represent Failure by NULL

The back-end of the compiler uses a new translation scheme. The old scheme used the C feature of setjmp/longjmp to deal with failing transformations. This provided the opportunity to go from using C as an assembly language, where an entire Stratego program was compiled to a single C function using gotos for control-flow, to a more idiomatic style of C programs in which each strategy definition was compiled to a C function. The setjmp/longjmp feature elegantly dealt with the notion of a failure by declaring a choice point (with setjmp) and jumping to it from anywhere (with longjmp). However, since choice points are the control-flow mechanism in Stratego, the speed of programs depends heavily on the cost of this feature. On Intel machinery (running Linux) this is not a big issue, but on Apples and Suns (RISC machines) the number of registers saved at each choicepoint is quite expensive; at least that is a theory about possibilities for improving the performance of Stratego programs.

Eelco Dolstra suggested a long time ago to return NULL to indicate failure of a strategy. Indeed, this representation closely matches the formal operational semantics of the language, in which the set of terms is extended with a failure value; exactly the ATerm data-type extended with an extra value (NULL).

The new translation scheme is pretty standard fair. Noteworthy about the new version is the use of concrete syntax of Stratego and C almost everywhere. For example, the following rule defines the translation of the crucial guarded choice construct:

  TranslateStrat(|S,F) :
    |[ s1 < s2 + s3 ]| ->
    stm|[
      {
        ATerm ~id:x = t;
        ~stm:<translate-strat(|Next,F')>s1
        ~stm:<translate-strat(|S,F)>s2
        ~id:F' : t = ~id:x; 
        ~stm:<translate-strat(|S,F)>s3
      }
    ]|
    where <not(Next)> S; new => x; new => F'

An interesting feature of the implementation is the collection of code fragments using dynamic rules, and the synthesis of the target program from these fragments afterwards; in contrast to the old method in which the source program was traversed for each type of fragment `driven by' the target program.

The new translation scheme is accompanied by a refactoring of the C code of the run-time system and the native part of the Stratego Library.

(Eelco Visser)

Versioning

The refactoring has been being released in a number of milestone releases. The first was 0.15, subsequent releases were numbered 0.16M1, 0.16M2, etc.

We have introduced a new versioning scheme for unstable releases. Intermediate versions on the way to a new major release get an M n suffix indicating that the release is the n-th milestone towards the major release.

This NEWS file presents the result of the entire operation, i.e., it discusses the integral set of changes since the previous major release (0.14).

The release notes at the end of this file show the issues addressed in each milestone. (Although issues from later milestones may be included in earlier releases.)

Run-Time System

The Stratego Run-Time System has been refactord to support `represent failure by NULL' model.

(Eelco Visser)

Stratego Library

Native code

The native code of the Stratego Library has been refactored to support the new `represent failure by NULL' model.

(Eelco Visser)

Refactored native code of stratego-lib to reflect the structure and order of the hierarchy of the Stratego part of the library. Removed unused definitions.

(Rob Vermaas)

Stratego code

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)

SUnit

If the environment variable "ENABLE_COLORS" is set to "true", the sunit now prints error reports in red. This makes it much easier to find failing tests in a terminal.

Add: export ENABLE_COLORS="true" to your .bashrc to make this work by default.

(Martin Bravenboer)

ATerm command-line flags

Added -at-* flags to general-options. All flags starting with '-at' are being ignored by option handling. -at flags are meant to be dealt by the ATerm library itself. See ATerm User manual for further details.

(Rob Vermaas)

Tools

Man Pages

All Stratego/XT tools now have a manpage, which are installed on the system of the user. The manpages are maintained in DocBook as part of the Stratego/XT Manual, so they are also available online.

(Karl Trygve Kalleberg)

GPP

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

(Martin Bravenboer)

Stratego-regular

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)

Manually Built Pretty-Printer in pp-stratego

The Stratego pretty printer is now a manually built pretty-printer (using Stratego-Box language). The new pretty-printer should give a much nicer output than the old pp-table approach.

(Rob Vermaas)

Heuristic Filters Disabled in sglri

The default behaviour of sglri has been changed to disable the heuristic disambiguation filters of sglr: eagerness and injection count. Disabling the heuristic filters of sglr makes it much clearer when, why, and how ambiguities arise in a syntax definition. These ambiguities can then be solved by using one of the non-heuristic mechanism for disambiguation in SDF.

If the disabling of heuristic filters causes new ambiguities in your syntax definition, then we advice you to fix the syntax definition, or alternatively you can invoke slgri with an option to enable the heuristic filters. To this end, we have added the option --heuristic-filters , as a more general variant of --no-heuristic-filters. Please use the new --heuristic-filters option instead of --no-heuristic-filters.

(Martin Bravenboer)

parse-stratego

Related to the new behaviour of sglri, Stratego programs are now parsed without the heuristic filters of sglr. For plain Stratego programs this is not a problem, but for Stratego programs that use concrete object syntax more often rely on these heuristic filters. For this reason, we enable the heuristic filters if there is a .meta file.

So we have the following behaviour for parse-stratego:

In case of no .meta file (no concrete syntax), heuristic filters are disabled: 'off'.
If there is a .meta file,
- If the .meta file does not specify the HeursiticFilters option, then default to 'On', i.e. heuristic filters are enabled.
- If the .meta file specifies the HeuristicFilters option, then parse-stratego uses that value.

(Martin Bravenboer)

Stratego/XT Deployment and Build System

New versions of ATerm Library and SDF Packages

Stratego/XT 0.16 requires new versions of the ATerm library (2.4) and sdf2-bundle (2.3.3). Downloads for these packages are available from the Stratego/XT 0.16 release page.

It is no longer necessary to configure the ATerm library with the option --with-gcc.

Also, it is no longer necessary to specify the locations of the ATerm Library and sdf2-bundle to Stratego/XT. Stratego/XT will locate the packages using pkg-config if you do not explicitly specify locations for these packages.

If you install packages in non-standard locations, then pkg-config will only be able to find them if you add these locations to the PKG_CONFIG_PATH. For example, set PKG_CONFIG_PATH to

export PKG_CONFIG_PATH=/opt/aterm/lib/pkgconfig:/opt/sdf2-bundle/lib/pkgconfig

where the ATerm Library and the SDF2 Bundle are installed in /opt/aterm and /opt/sdf2-bundle. For more information see man pkg-config.

This method of configuration can also be used for packages that use Stratego/XT. So, you don't have to specify the location of Stratego/XT to these packages.

AutoXT

Makefile.xt now supports the STRCFLAGS variable. The old SCFLAGS variable is still supported.

The Autoconf macro XT_USE_XT_PACKAGES now supports a mixture of explicit configuration and searching for packages with pkg-config. If the user specifies a location of a package, then pkg-config will not be used to search for the package.

The AutoXT macros now set variables pkg_STRCFLAGS, where pkg is the name of the package. This variable contains the include paths that have to be passed to the Stratego compiler to be able to use that package. Packages can also pass other arguments to strc using this variable, if necessary. This feature allows dependent packages to abstract more of the way they need to use a package. Hence, making the dependent packages more stable.

In addition to pkg_STRCFLAGS, AutoXT now also supports pkg_XTC, for example STRATEGOXT_XTC. In this way, dependent packages no longer need to know where the XTC repositories of the packages they use are locatied.

The values of pkg_STRCFLAGS and pkg_XTC can be specified in the strcflags pkg-config variable. It is inspired by the pkg_CFLAGS and pkg_LIBS feature of pkg-config.

The Autoconf macro XT_CHECK_STRATEGOXT_UTILS now supports pkg-config as well as explicit configuration.

(Martin Bravenboer)

Linking Stratego Libraries

For Stratego/XT 0.16, we have solved various linking issues on Mac OS X and Cygwin.

First, the latest version of the ATerm Library (2.4) now creates a dynamic library. Indirectly, this allows us to use dynamic linking of the Stratego Library at Cygwin. This makes the executables, memory consumption and the binary distribution for Cygwin much smaller.

Second, the dynamic ATerm Library solves a linking problem at Mac OS X for very small Stratego programs.

Also, Stratego libraries now declare inter-library dependencies. This means that all the indirectly required libraries are automatically added as arguments to the linker. This is required for building dynamic libraries at Cygwin and it might be useful for users that don't use Makefile.xt or the stand-alone Stratego compiler.

Mac OS X support checked in buildfarm

The improved performance of Stratego/XT on Mac OS X allows us to run a full check of the Stratego/XT distribution on the Darwin machine in our buildfarm. This will further improve the support of Stratego/XT for Mac OS X.

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:

http://www.stratego-language.org/Stratego/StrategoRelease016Issues

Download and Installation

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

http://www.stratego-language.org/Stratego/StrategoRelease016

Bugs and Known Problems

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

https://bugs.cs.uu.nl/browse/STR

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.

Contributions

The Stratego Core refactoring was carried out by

Eelco Visser

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

Martin Bravenboer
Ron de Bruijn
Valentin David
Eelco Dolstra
Karl Trygve Kalleberg
Rob Vermaas
Eelco Visser
Daniel Waddington

Thanks!