Stratego/XT 0.10
Stratego -- Strategies for Program Transformation
Released May 10, 2004
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 8.0:
Redhat 9.0:
SuSE Linux RPM
SuSE 8.2:
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.
Summary of Changes
- Language
- Major redesign of dynamic rules
- If then else and switch operators
- Tools
- Update of XT
- Introduction of Stratego Regular
- Deployment
- Daily verified support for Cygwin
- Support for Mac OS X
- Miscellaneous
- Many bug fixes and minor improvements
- Issue tracking is paying off
Dynamic Rules
For StrategoXT 0.10 we have completely redesigned and reimplemented
dynamic rules. Scoped dynamic rewrite rules have been introduced in
Stratego 0.6 (August 2001). Dynamic rules have been applied
extensively since then. In particular they have proved to be very
useful for implementing context-sensitive transformations. However,
these applications also revealed some missing features in scoped
dynamic rewrite rules.
Motivation for Redesign
First, there is a need for forking and merging sets of dynamic rules
in data-flow optimizations and probably many other application
areas. At first we have implemented this at the implementation level
of dynamic rules. In StrategoXT 0.10 this functionality has been lifted
to the language level by allowing intersection and union operations on
sets of rules.
Second, many applications need to define more than one possible rewrite
rules that can all be applied, possibly all at once to retrieve a list
of possible rewrites. A first implementation of this idea was already
available in StrategoXT 0.9.4 (extend rules).
Third, the 'override rules' facility for defining dynamic in rules in
outer scopes proved to be insufficient. To this end we have added
labeled scopes. Rules can be tied to specifically labeled scopes. Labeled
scopes are based on an idea raised by Ganesh Sittampalam in a discussion
at the Stratego User Days 2004.
New Syntax and Semantics
The new abstract syntax is introduced by comparing to the old syntax and
and semantics, and is presented in BNF below. Some basic entities are:
s strategy,
f rule/strategy identifier, e.g. 'EvalBinOp', or 'innermost',
dsig definition signature, identifier with optional strategy and term
arguments: f(sd*|vd*).
Generation of new rules always occurred within
override/extend rules(..)
constructs. Now, just one
rules(..)
construct is available. The dynamic
rule definitions within determine the semantics.
s ::= rules(drd*) rule definition block
Labeling of Scopes
To prevent rules from being undefined too early at the end of the current
scope, the
override rules(..)
could be used in the past. Rules were tied
to some outer scope, instead of the current innermost.
The new dynamic rules still support the same scoping syntax, but now
optional labels maybe attached. These labels are term-patterns, and thus
result in runtime scope-labeling.
s ::= {| f1(.p1)?, ... fn(.pn)? : s |} dynamic rule scope
Within a
rules(..)
block, the current scope may be assigned additional
labels.
drd ::= f+p label current scope
Dynamic Rule Definitions
Besides the mandatory rule name, dynamic rule definitions now may also
contain a label, specifying in which scope this rule should be placed.
No label naturally means generation within the current inner scope.
drsig ::= sig relative to current scope
sig.p relative to labeled scope
sig+p relative to current scope, but add a
label to current scope simultaneously
drd ::= drsig : p1 -> p2 (where s)? dynamic rule definition
Instead of
extend rules
blocks, now the rule definitions specify themselves
whether 'extend-behavior' is intended:
drd ::= drsig :+ p1 -> p2 (where s)? dynamic rule extension
Undefining rules no longer uses the
Undefined
keyword, again it's the
rule definition itself.
drd ::= drsig :- p dynamic rule undefining
A new form of dynamic rule is the dynamic identity rule, that -when applied-
tries to match against the left-hand side and leaves the current term
untouched.
drd ::= drsig : p dynamic identity rule definition
Within a nested scope-structure, multiple scopes may have identical labels.
When (un-)defining dynamic rules in a labeled scope, the innermost scope with
that label is selected.
Dynamic Rule Calling
Dynamic rules are basically just runtime generated rewriting rules, so for a
definition:
UsedInExp :+ |[ x ]| -> |[ e ]|
the basic call is:
<UsedInExp> |[ y ]| => |[ e' ]| // Normal rewriting
It tries to rewrite with the most recently generated instance of
UsedInExp
,
and repeatedly tries older instances until rewriting succeeds or no more
instances exist in the same generation scope (i.e. no inheritance from higher
scopes than the one of latest generation).
Note that the semantics of this simple rewriting has changed: in the old model,
no older instances were available for rewriting if the youngest instance failed)
Two special rules are automatically available for each dynamic rule:
the
bagof-
and
once-
rule.
<bagof-UsedInExp> |[ y ]| => |[ e* ]| // Multiple rewritings
bagof-RuleName
applies all available instances of
RuleName
(from one scope)
and returns a list of succeeded result terms.
<once-UsedInExp> |[ y ]| => |[ e' ]| // Rewriting once
once-RuleName
rewrites just like
RuleName
would do, but upon successful
rewriting that rule instance is removed. A generated rule thus is used for
rewriting only once.
Branching and Meeting Rule Sets
When performing control-flow optimizations, rule sets had to be explicitly
saved, intersected and restored. The new model now provides some variants for
this at the language level (with generic functionality available in the API).
The best-known branch-meet operation is the intersection of rule sets after
constant propagation through the then- and else-branch of an if-then-else.
The general syntax allows two strategies to be performed, followed by an
automatic intersection of one or more named rule sets:
s1 / f1, ..., fn \ s2 dynamic rule intersection
Example:
If(id,s,id)/PropConst\If(id,id,s)
The same is possible for union, instead of intersection:
s1 \ f1, ..., fn / s2 dynamic rule union
Control structures that involve repetition (e.g. for-loops) often need
repeated traversal until a fixed point in the rule set is reached.
Two fixpoint traversals are available that meet the dynamic rule set with
the one from the previous iteration until the rule set is free of changes.
/ f1, ..., fn \* s2 dynamic rule fixpoint intersection
\ f1, ..., fn /* s2 dynamic rule fixpoint union
Example:
/PropConst\* While(s,s)
Dynamic Rules API
For in-depth specification of the underlying dynamic rules implementation,
please refer to the
dynamic-rules-refactored
module in the SSL.
At least the debug strategies are useful for end-users:
dr-debug-rule-set(|name) // Output dynamic rule set on stderr
dr-debug-rule-set(|name, msg) // Id. preceded by user's message
Compatibility and Compiler Flags
The new implementation of dynamic rules is not yet turned on by
default. To turn it on, you need to pass the option
--dr new
to the
Stratego compiler. Although the new implementation is not yet used by
default, all existing applications should work with the new
implementation. That is, if they do not rely on weird semantics in the
old dynamic rule implementation and do not manipulate the internal
representation of dynamic rules.
Parsing of stratego source always uses the new syntax, but for backward
compatibility
all old constructs are still available.
That is:
extend/override rules(..)
and
Rule: t -> Undefined
.
When the new dynamic rule implementation is selected (
--dr new
), the old
semantics are emulated for both constructs. All other old dynamic rules
constructs still fit within the new implementation.
Note however, that semantics for simple rule application within the new
dynamic rules implementation has changed (see 'Dynamic Rule Calling' above).
The other way around: the new syntax for dynamic rules is supported as much
as possible by the old dynamic rule implementation.
Dynamic rule extension (e.g.
Rule :+ t1 -> t2
), and dynamic rule undefining
(e.g.
Rule :- t
) are translated to their old equivalents.
When the input program contains scope-labels or identity rules, the compiler
warns and exits with an error.
But realize: when using new constructs in your program, there's no need to use
the old compiler implementation.
We advice to test compiling your programs with
--dr new
since future
releases of the Stratego compiler will have this flag switched on by default.
(Arthur van Dam, Eelco Visser, Karina Olmos and Martin Bravenboer)
If then else and switch operators
StrategoXT 0.10 introduces if-then-else and switch operators. Both
operators are defined in terms of the guarded left-choice. Thus, they
are just a more wordy syntax, which can be clearer in some case.
The if operator is translated into Stratego-Core by the following
rewrite rule:
|[ if s1 then s2 else s3 end ]| -> |[ where(s1) < s2 + s3 ]|
Note that the application of s1 does not change the subject
term. Therefore s2 and s3 are applied to the subject term of the
if-then-else operator. The translation of the switch statement is
somewhat more complex. It is best introduced by an example.
The following code fragment from pack-sdf:
( where(of-config => "txt") < xtc-asfix-yield
+ where(of-config => "ast") < xtc-implode-asfix
+ where(of-config => "asfix")
<+ <fatal-error> ["pack-sdf: ", <id>, " is not a valid output format."]
)
translates into the following code if the switch operator is used:
switch of-config
case "txt" : xtc-asfix-yield
case "ast" : xtc-implode-asfix
case "asfix" : id
otherwise :
<fatal-error> ["pack-sdf: ", <id>, " is not a valid output format."]
end
The case conditions (
"txt"
,
"ast"
and
"asfix"
) are not
restricted to term patterns: arbitrary strategies are allowed. They
are applied to the result of the subject of the switch, which is the
result of invoking
of-config
in this case.
The bodies (
xtc-asfix-yield
,
xtc-implode-asfix
,
id
and the
fatal-error
invocation) are applied to the subject term of the
switch strategy. That is, the switch subject and the conditions do not
modify the subject term, which is comparable to the behaviour of the
if operator.
The words used in these new operators (
if
,
then
,
else
,
end
,
switch
,
case
and
otherwise
) are not declared as
keywords. Therefore they are still allowed as identifiers.
(Arthur van Dam and Martin Bravenboer)
Stratego Regular
In StrategoXT 0.10 the Stratego Regular package has been added to the
packages of StrategoXT. Stratego Regular is a package of tools for
working with tree languages, which are defined by a tree
grammar. Stratego Regular contains two languages for defining regular
tree grammars: Regular Tree Grammar (RTG) and Regular Hedge Grammar
(RHG). RHG is only relevant to XML related tools, which are
implemented in the XML Tools package. Currently RTG is the only
relevant tree grammar language for StrategoXT applications.
The RTG language is of course accompanied by several tools, a few of
them are introduced here.
-
sdf2rtg
generates an RTG from an SDF syntax definition. If
sdf2rtg
cannot transform a concrete syntax production into
abstract syntax, then it will complain. This might then be caused
by a mistake in your syntax definition (a missing cons
attribute
for example), or it might be a limitation of sdf2rtg
, which we
would like to know about!
-
rtg2sig
generates a Stratego Signature from an RTG. This is a
rather straightforward translation, since signatures are closely
related to regular tree grammars. The tool tries to improve the
generated signature by using the parameterized sorts of Stratego
(List
and Option
).
-
format-check
checks if a term is an element of the tree language
defined by an RTG. Hence, format-check can be used to check if
your tools behave well, i.e. produce terms in the correct
format. Unfortunately, the error reporting of format-check is
currently very poor. This issue will be resolved for the next
release of StrategoXT, although it is still unclear which errors
should be reported to user.
Important: Stratego Signature Generation
Stratego Signature generation from an SDF syntax definition is in
StrategoXT 0.10 based on Stratego Regular. The old
sdf-to-sig
has
been removed because it was based on an old version of
SDF.
Makefile.xt
defines two new rules, one for generating an RTG
from an SDF definition, and one for generating a signature from an
RTG.
Existing packages that generate signatures must be updated because the
new tools generate only one file containing the full
signature. Fortunately, these changes are usually limited to
Makefile.am
. Two changes are needed in a typical
Makefile.am
that
generates a signature:
- Declare that only the
Language.str
module must be
generated. This means that you can just remove all other modules
that used to be generated.
- Declare the main module of the SDF syntax definition in a
variable
SDF2RTG_FLAGS
. If the main module has the same name as
the .def file, which is usually the case, then the value should
be -m $*
. The main module defaults to Main
, which is also the
default main module of sdf2table
.
Of course you can send an e-mail to
stratego@cs.uu.nl or
stratego-dev@cs.uu.nl if you have any problems with the conversion to
the new Stratego Signature generation tools.
(Martin Bravenboer)
Update of XT
For StrategoXT 0.10 we have updated many XT tools that are part of
StrategoXT. Unfortunately, many SDF Tools, but even the Stratego
Tools, have not been kept up-to-date with respect to the languages
they operate on in the last few years.
The SDF tools have all been updated to the most recent version of
SDF2, which is the one in in PGEN 2.0. There are quite some SDF tools
in StrategoXT, but the most relevant ones are
ppgen, the
pretty-print table generator,
pack-sdf, for collecting SDF modules
in a single definition, and
sdf-cons, for adding constructors to SDF
productions. The tool sdf-to-sig, for generating Stratego Signatures
from an SDF syntax definition is no longer available. It has been
replaced by tools available in Stratego Regular.
If you have yourself developed SDF tools based on StrategoXT, then you
might need to upgrade your tools. The previous versions of StrategoXT
used to ship with three versions of SDF.
SDF 2.1, which was named
Sdf2-Syntax
, an older version of SDF, which was named
sdf
or
sdf.cons
, and the most recent one, which is called
Sdf2
. This last
version is the only one that is left in StrategoXT 0.10. If your tools
use one of the older versions of SDF, then you need to update
them. Most SDF tools only have to change the top-level constructor
names, which are now completely lower-case. If you need more
information on upgrading issues, then just sent e-mail to the
stratego-dev mailing list.
(Martin Bravenboer and Valentin David)
AsFix Tools has been cleanup as well. The definition of AsFix in this
package was not very clear and the package used to contain signatures
for SDF modules, which have now been removed in StrategoXT 0.10. The
SDF signatures of the most recent SDF2 are part of the SDF Front
package. The signature for
asfix
has been replaced by a new
signature, now called
AsFix
. This module defines the AsFix language
in a single signature. If you import this module, then your program
can handle all AsFix constructs.
(Martin Bravenboer)
The Stratego Tools package has been updated to use the latest
definitions of Stratego in stratego-front. The existing tools in
Stratego Tools are not really heavily used, so you will probably never
have experienced any problems.
Stratego Tools in StrategoXT 0.10 contains a new tool,
pp-stratego-latex-alltt
. This tool is useful for including Stratego
code in publications and documentation written LaTeX. The tool adds
some macro invocations to a Stratego module, while preserving the
layout of the code. Currently it marks quotation symbols,
meta-variables, and dynamic rule scope. It escapes characters that
have a special meaning in the alltt environment. You can define the
macros yourself, so you can completely control the presentation of the
marked constructs. The source directory of the tool contains an
example LaTeX document.
(Martin Bravenboer)
Support for Cygwin and Mac OS X
In the meantime we have added a Cygwin machine to our buildfarm. In
this way we can make sure that StrategoXT is working on Cygwin. Since
no of our Stratego contributors is using Cygwin, signaling problems
with Cygwin used to be a problem in the past. Testing StrategoXT now
and then on Cygwin was not sufficient.
(Martin Bravenboer)
StrategoXT 0.10 also supports the most recent Mac OS X release. This
is mostly thanks to the updates of the development tools for Mac OS
X. We are looking forward to reports of Mac OS X users, especially
concerning the performance of StrategoXT. In particular, if someone
has access to a G5, then it would be great to hear some experiences.
Editor Support
Shishir Ramam contributed Vim syntax files for Stratego and SDF. These
files are available in the stratego-util package, which is part of
StrategoXT. Arthur van Dam has extended the SDF and Stratego syntax
highlighting patterns for NEdit. These are available in stratego-util
as well.
(Arthur van Dam and Shishir Ramam)
Many bug fixes and minor improvements
Just before the release of StrategoXT 0.9.5 we adopted the JIRA issue
tracking system. JIRA has been very helpful in keeping track of
problems. In particular many small problems have been fixed in this
release, which would typically have been forgotten before we adopted
JIRA. Please report any issues to JIRA, even if you think that it is
not that important, or if you have already found a workaround. Any
annoyance is welcome! Feedback of users is very important in adding
the finishing touch to our tools.
Some pointers to overviews of issues:
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
Not all bugs and known problems for StrategoXT have been solved in
this release, otherwise this would release 1.0 ;). 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
Developments, beta tests, and bug fixes were carried out by
- Martin Bravenboer
- Arthur van Dam
- Valentin David
- Shishir Ramam
- Rob Vermaas
- Eelco Visser