Stratego Language

Stratego is a language for program transformation based on the paradigm of programmable rewriting strategies.

Terms

In Stratego, programs are represented by means of terms. The abstract syntax of a programming language is described by means of a signature.

Conditional Rewrite Rules

Basic transformation steps are specified by means of conditional rewrite rules. A rule recognizes a subterm to be transformed by pattern matching and replaces it with a pattern instance.

Rewriting Strategies

Rewrite rules are a natural formalism for expressing single program transformations. However, using a standard strategy for normalizing a program with a set of rewrite rules is not adequate for implementing program transformation systems. It may be necessary to apply a rule only in some phase of a transformation, to apply rules in some order, or to apply a rule only to part of a program. These restrictions may be necessary to avoid non-termination or to choose a specific path in a non-confluent rewrite system.

Stratego supports the separation of strategies from transformation rules, thus allowing careful control over the application of these rules. As a result of this separation, transformation rules are reusable in multiple different transformations and generic strategies capturing patterns of control can be described independently of the transformation rules they apply.

Generic Traversal

Instead of spelling out the details of traversals over trees for a specific abstract syntax, Stratego supports generic traversal by means of a few traversal primitives. These primitives can be combined to define a wide range of generic traversals, such as topdown, bottomup, once topdown, and innermost.

Dynamic Rules

Normal rewrite rules are context-free, that is, they use information only from the pattern that is matched, and possibly from subterms. The dynamic rules of Stratego allow the run-time generation of rewrite rules that inherit context information. For example, generation of an inlining rule at the declaration site.

Concrete Syntax

Specification of transformations in abstract syntax becomes cumbersome when the patterns become large. Therefore, Stratego supports specification of patterns in the concrete syntax of the object language. This is especially useful in template-based program generation, where large fragments of object language programs are instantiated.

Annotations

The signature of an abstract syntax corresponds to the syntax of the object language. When performing transformations or analyses it is sometimes necessary to attach additional information to nodes. This is supported in Stratego by means of term annotations.

Overlays

Transformations are usually specified in terms of the abstract syntax constructors of the object language. Stratego overlays allow the specification of pattern abstractions. This can be used, for example, in defining application specific transformations.

Stratego Library

The Stratego Library is a collection of modules with reusable rules and strategies. Included in the library are strategies for sequential control, generic traversal, built-in data type manipulation (numbers and strings), standard data type manipulation (lists, tuples, optionals), generic language processing, and system interfacing (I/O, process control, association tables).

Stratego Compiler

The Stratego Compiler translates Stratego specifications to high-level C code. The run-time system is based on the ATerm library, which supports the ATerm Format, a representation for first-order terms with prefix application syntax.

Applications

Stratego is being applied in a wide variety of program transformation projects including a software improvement tool for Cobol programs (CobolX), a compiler for Tiger (Tiger Compiler), a documentation generation tool for SDL, tools for grammar transformation (GrammarTools), a tool for deforestation of functional programs through the warm fusion algorithm (HSX), and a tool for domain-specific optimization of C++ programs in the domain of numeric (coordinate-free) programming (CodeBoost). The StrategoCompiler is bootstrapped, i.e., implemented in Stratego itself.

Distribution

Stratego is also distributed as part of Stratego/XT. This package combines the Stratego language with a collection free transformation tools to support the implementation of program transformations. The package includes a collection of syntax definitions for programming languages and tools for generating tools such as pretty-printers from syntax definitions. Stratego/XT is distributed under the GNU Lesser General Public License. The distribution of and publications about Stratego are available from http://www.stratego-language.org.