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
Source RPM
Redhat Linux RPM
Redhat 9.0:
SuSE Linux RPM
SuSE 9.0:
Fedora Core RPM
Fedora Core 2:
Fedora Core 3:
Mac OS X binaries
The *-macosx.tar.gz files contain a file
README with installation instructions.
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:
powerpc-darwin:
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)
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.
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:
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.
Contributions
The Stratego Core refactoring was carried out by
Other improvements, bug reports, and beta tests carried out by
- Martin Bravenboer
- Ron de Bruijn
- Rob Vermaas
- Daniel Waddington
Thanks!