Stratego/XT 0.16M1

Stratego/XT 0.16M1 -- released August 30th, 2005

Download

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

Source tar.gz

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

Source RPM

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

Redhat Linux RPM

Redhat 9.0:

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

SuSE Linux RPM

SuSE 9.0:

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

Fedora Core RPM

Fedora Core 2:

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

Fedora Core 3:

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

Mac OS X binaries

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

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

Nix Packages

Open nixpkg files with nix-install-package. Installation of a Nix package is a one-click installation of package and all its dependencies.

i686-linux:

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

powerpc-darwin:

• aterm-2.4
• sdf2-bundle-2.3.2
• strategoxt-0.16M1

License

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.

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

Versioning

The refactoring is being released in a number of milestone releases. The first was 0.15, subsequent releases are 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.)

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 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()}

(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.

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.

TODO: overlays

(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. 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.

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)

Run-Time System

Refactoring to support `represent failure by NULL' model.

(Eelco Visser)

Stratego Library

Native code

Refactoring to support `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)

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)

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)

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.2). 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 specifiy 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.

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. The value of pkg_STRCFLAGS 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/StrategoRelease016M1Issues

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/StrategoRelease016M1

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 improvements, bug reports, and beta tests carried out by

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

Thanks!