Stratego/XT 0.10

StrategoXT 0.10

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

• aterm-2.1 (located at CWI)
• sdf2-bundle-2.0.1
• strategoxt-0.10

Source RPM

• aterm-2.1
• sdf2-bundle-2.0.1
• strategoxt-0.10

Redhat Linux RPM

Redhat 8.0:

• aterm-2.1
• sdf2-bundle-2.0.1
• strategoxt-0.10

Redhat 9.0:

• aterm-2.1
• sdf2-bundle-2.0.1
• strategoxt-0.10

SuSE Linux RPM

SuSE 8.2:

• aterm-2.1
• sdf2-bundle-2.0.1
• strategoxt-0.10

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:

• list of all issues closed in StrategoXT 0.10
• StrategoXT roadmap

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

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:

• https://catamaran.labs.cs.uu.nl/jira/

For an overview of features planned for future releases:

• StrategoXT roadmap
• Release plan
• To do

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