Part III. The Stratego Language


Stratego Version

This manual is being written for and with Stratego 0.16; You are advised to install the latest milestone for this release. See the download page at

Program transformation is the mechanical manipulation of a program in order to improve it relative to some cost function C such that C(P) > C(tr(P)), i.e. the cost decreases as a result of applying the transformation. The cost of a program can be measured in different dimensions such as performance, memory usage, understandability, flexibility, maintainability, portability, correctness, or satisfaction of requirements. Related to these goals, program transformations are applied in different settings; e.g. compiler optimizations improve performance and refactoring tools aim at improving understandability. While transformations can be achieved by manual manipulation of programs, in general, the aim of program transformation is to increase programmer productivity by automating programming tasks, thus enabling programming at a higher-level of abstraction, and increasing maintainability and re-usability of programs. Automatic application of program transformations requires their implementation in a programming language. In order to make the implementation of transformations productive such a programming language should support abstractions for the domain of program transformation.

Stratego is a language designed for this purpose. It is a language based on the paradigm of rewriting with programmable rewriting strategies and dynamic rules.

Transformation by Rewriting.  Term rewriting is an attractive formalism for expressing basic program transformations. A rewrite rule p1 -> p2 expresses that a program fragment matching the left-hand side pattern p1 can be replaced by the instantiation of the right-hand side pattern p2. For instance, the rewrite rule

|[ i + j ]| -> |[ k ]| where <add>(i, j) => k 

expresses constant folding for addition, i.e. replacing an addition of two constants by their sum. Similarly, the rule

|[ if 0 then e1 else e2 ]| -> |[ e2 ]| 

defines unreachable code elimination by reducing a conditional statement to its right branch since the left branch can never be executed. Thus, rewrite rules can directly express laws derived from the semantics of the programming language, making the verification of their correctness straightforward. A correct rule can be safely applied anywhere in a program. A set of rewrite rules can be directly operationalized by rewriting to normal form, i.e. exhaustive application of the rules to a term representing a program. If the rules are confluent and terminating, the order in which they are applied is irrelevant.

Limitations of Pure Rewriting.  However, there are two limitations to the application of standard term rewriting techniques to program transformation: the need to intertwine rules and strategies in order to control the application of rewrite rules and the context-free nature of rewrite rules.

Transformation Strategies.  Exhaustive application of all rules to the entire abstract syntax tree of a program is not adequate for most transformation problems. The system of rewrite rules expressing basic transformations is often non-confluent and/or non-terminating. An ad hoc solution that is often used is to encode control over the application of rules into the rules themselves by introducing additional function symbols. This intertwining of rules and strategies obscures the underlying program equalities, incurs a programming penalty in the form of rules that define a traversal through the abstract syntax tree, and disables the reuse of rules in different transformations.

Stratego solves the problem of control over the application of rules while maintaining the separation of rules and strategies. A strategy is a little program that makes a selection from the available rules and defines the order and position in the tree for applying the rules. Thus rules remain pure, are not intertwined with the strategy, and can be reused in multiple transformations. schemas.

Context-Senstive Transformation.  The second problem of rewriting is the context-free nature of rewrite rules. A rule has access only to the term it is transforming. However, transformation problems are often context-sensitive. For example, when inlining a function at a call site, the call is replaced by the body of the function in which the actual parameters have been substituted for the formal parameters. This requires that the formal parameters and the body of the function are known at the call site, but these are only available higher-up in the syntax tree. There are many similar problems in program transformation, including bound variable renaming, typechecking, data flow transformations such as constant propagation, common-subexpression elimination, and dead code elimination. Although the basic transformations in all these applications can be expressed by means of rewrite rules, these require contextual information.

Outline.  The following chapters give a tutorial for the Stratego language in which these ideas are explained and illustrated. The first three chapters outline the basic ideas of Stratego programming in bold strokes. Chapter 10 introduces the term notation used to represent source programs in Stratego. Chapter 11 shows how to set up, compile, and use a Stratego program. Chapter 12 introduces term rewrite rules and term rewriting. Chapter 13 argues the need for control over the application of rewrite rules and introduces strategies for achieving this.

The rest of the chapters in this tutorial explain the language in more detail. Chapter 14 examines the named rewrite rules, defines the notion of a rewriting strategy, and explains how to create reusable strategy expressions using definitions. Chapter 15 introduces combinators for the combination of simple transformations into more complex transformations. Chapter 16 re-examines the notion of a rule, and introduces the notions of building and matching terms, which provide the core to all manipulations of terms. It then goes on to show how these actions can be used to define higher-level constructs for expressing transformations, such as rewrite rules. Chapter 17 introduces the notion of data-type specific and generic traversal combinators. Chapter 18 shows how to generically define program analyses using type-unifying strategies. Chapter 19 shows ho to use the syntax of the source language in the patterns of transformation rules. Finally, Chapter 20 introduces the notion of dynamic rules for expressing context-sensitive transformations.

Table of Contents

10. Terms
10.1. Annotated Term Format
10.2. Exchanging Terms
10.3. Inspecting Terms
10.4. Signatures
11. Running Stratego Programs
11.1. Compiling Stratego Programs
11.2. Basic Input and Output
11.3. Combining Transformations
11.4. Running Programs Interactively with the Stratego Shell
11.5. Summary
12. Term Rewriting
12.1. Transformation with Rewrite Rules
12.2. Adding Rules to a Rewrite System
12.3. Summary
13. Rewriting Strategies
13.1. Limitations of Term Rewriting
13.2. Attempt 1: Remodularization
13.3. Attempt 2: Functionalization
13.4. Programmable Rewriting Strategies
13.5. Idioms of Strategic Rewriting
13.5.1. Cascading Transformations
13.5.2. One-pass Traversals
13.5.3. Staged Transformations
13.5.4. Local Transformations
13.6. Summary
14. Rules and Strategies
14.1. What is a Rule?
14.2. What is a Strategy?
14.3. Strategy Definitions
14.3.1. Simple Strategy Definition and Call
14.3.2. Parameterized Definitions
14.3.3. Local Definitions
14.3.4. Extending Definitions
14.4. Calling Primitives
14.5. External Definitions
14.6. Dynamic Calls
14.7. Summary
15. Strategy Combinators
15.1. Identity and Failure
15.2. Sequential composition
15.3. Choice
15.3.1. Deterministic Choice (Left Choice)
15.3.2. Guarded Choice
15.3.3. If Then Else
15.3.4. Switch
15.3.5. Non-deterministic Choice
15.4. Recursion
15.5. Summary
16. Creating and Analyzing Terms
16.1. Building terms
16.2. Matching terms
16.3. Implementing Rewrite Rules
16.3.1. Anonymous Rewrite Rule
16.3.2. Term variable scope
16.3.3. Implicit Variable Scope
16.3.4. Where
16.3.5. Conditional rewrite rule
16.3.6. Lambda Rules
16.4. Apply and Match
16.5. Wrap and Project
16.5.1. Term Wrap
16.5.2. Term Project
16.6. Summary
17. Traversal Strategies
17.1. Traversal Rules
17.2. Congruence Operators
17.3. Generic Traversal
17.3.1. Visiting All Subterms
17.3.2. Visiting One Subterm
17.3.3. Visiting Some Subterms
17.4. Idioms and Library Strategies for Traversal
17.4.1. Full Traversals
17.4.2. Cascading Transformations
17.4.3. Mixing Generic and Specific Traversals
17.4.4. Partial Traversals
17.4.5. Path (*)
17.4.6. Recursive Patterns (*)
17.4.7. Dynamic programming (*)
17.5. Summary
18. Type Unifying Strategies
18.1. Type Unifying List Transformations
18.2. Extending Fold to Expressions
18.3. Generic Term Deconstruction
18.4. Generic Term Construction
18.5. Summary
19. Concrete Object Syntax
19.1. Instrumenting Programs
19.2. Observations about Concrete Syntax Specifications
19.3. Implementation
19.3.1. Extending the Meta Language
19.3.2. Meta-Variables
19.3.3. Meta-Explode
19.4. Discussion
19.5. Summary
20. Dynamic Rules