Stratego/XT Tutorial

Martin Bravenboer

Delft University of Technology

Karl Trygve Kalleberg

Universitetet i Bergen

Eelco Visser

Delft University of Technology

Table of Contents

I. Introduction
1. Software Transformation Systems
1.1. What is Software Transformation?
1.2. What is Stratego/XT?
1.3. Outline
2. Installation
2.1. What do I Need?
2.2. Instructions
II. The XT Transformation Tools
3. Architecture
3.1. Tools as Transformation Components
3.2. Grammar Oriented
3.3. Being on Good Terms with Trees
4. Annotated Terms
4.1. Annotated Term Format
4.2. Inspecting Terms
4.3. Maximal Sharing (*)
4.4. Exchange Format
4.5. ATerm Library
5. Syntax Definition and Parsing
5.1. Concepts: Grammars, Parse Trees, and Abstract Syntax Trees
5.2. From Concepts to Practice: Generating a Parser
6. Syntax Definition in SDF
6.1. SDF: The Basics
6.2. Syntax
6.3. Examples: Defining Lexical Syntax
6.4. Examples: Defining Context-Free Syntax
6.5. Unit Testing of Syntax Definitions
7. Advanced Topics in Syntax Definition (*)
7.1. Combining Languages
7.2. Advanced Module Features
7.3. Context-sensitive Lexical Syntax
7.4. Explicit versus Implicit Ambiguities
7.5. Performance Tips and Tricks
8. Trees, Terms, and Tree Grammars (*)
8.1. Regular Tree Grammars
8.2. Generating Code from an RTG
8.3. Creating a Subset of a Regular Tree Grammar
8.4. Format Checking
8.5. Signatures (todo: imported)
8.6. Signature Tools (todo: imported)
9. Pretty Printing with GPP (*)
9.1. Box Text Formatting Language
9.2. Pretty Print Tables
9.3. Restoring Parenthesis
9.4. Pretty Printing using Stratego
9.5. Pretty-Printing (todo: imported)
9.6. Pretty-Printing and Term Visualization Tools (todo: imported)
III. The Stratego Language
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.6. Summary
14. Rules and Strategies
14.1. What is a Rule?
14.2. What is a Strategy?
14.3. Strategy 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.4. Recursion
15.5. Summary
16. Creating and Analyzing Terms
16.1. Building terms
16.2. Matching terms
16.3. Implementing Rewrite Rules
16.4. Apply and Match
16.5. Wrap and Project
16.6. Summary
17. Traversal Strategies
17.1. Traversal Rules
17.2. Congruence Operators
17.3. Generic Traversal
17.4. Idioms and Library Strategies for Traversal
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.4. Discussion
19.5. Summary
20. Dynamic Rules
IV. The Stratego Library
21. Arithmetic Operations
21.1. Basic Operations
21.2. Number comparisons
21.3. Other Operations
21.4. Random Numbers
21.5. Summary
22. Lists
22.1. Making heads and tails of it
22.2. Sorting
22.3. Associative Lists
22.4. Pairing Lists
22.5. Lightweight Sets
22.6. Transforming Lists
22.7. Folding from the Left and Right
22.8. Summary
23. Strings
23.1. Basic String Operations
23.2. Sorting Strings
23.3. Strings and Terms
23.4. Strings and Numbers
24. Hashtables and Sets
24.1. Hashtables
24.2. Indexed Sets
25. I/O
25.1. Console I/O
25.2. Path and Directory Operations
25.3. File and Text I/O
25.4. Term I/O
25.5. Logging
26. Command-line Options
26.1. Parsing Command-line Options
26.2. Adding Custom Options
26.3. Setting Description and About
26.4. I/O-less Programs
27. Unit Testing with SUnit
27.1. Setting up a test suite
27.2. Compare expected and actual output
27.3. Check for failure
27.4. Check arbitrary conditions on output
27.5. Unit testing with XTC
28. Transformation Tool Composition with XTC
28.1. Basic Mechanisms of XTC
28.2. Composing Tools in Stratego
28.3. Summary
29. Building and Deploying Stratego Programs
29.1. Building stand-alone artifacts
29.2. Setting up your Project
29.3. Building Stand-alone Stratego Applications
29.4. Building Parse Tables, Tree Grammars and Stratego Signatures
29.5. Building Your Own Stratego Library
29.6. Package Config Support
29.7. RPM Support
29.8. Summary
30. Debugging Techniques for Stratego/XT
30.1. Debugging Stratego
30.2. Debugging XT compositions
30.3. Debugging SDF definitions

List of Figures

1.1. Applications of Software Transformation.
1.2. Pipeline of a software transformation system.
1.3. file: sample-rules.str
3.1. Pipeline of a software transformation system.
3.2. Syntax definitions play a central role in a transformation system.
4.1. Tree and dag for the string (a + b) * c + (a + b)
5.1. Context-free productions and a reduction sequence.
5.2. Parse tree
5.3. Context-free productions with constructor annotations and an abstract syntax tree.
5.4. SDF modules for a small language of arithmetic expressions.
6.1. Syntax definition with regular expressions.
8.1. Signature for statement and expression constructors, automatically derived from a syntax definition.
9.1. Unparsing an abstract syntax tree.
9.2. Unparsing table
9.3. Pretty-printing with Box markup
9.4. Pretty-print table with Box markup
9.5. Pretty-printing of if-then-else statement

List of Examples

6.1. Basic constructs of SDF
6.2. Examples of Character Classes
6.3. Syntax of Small Expression Language in SDF
6.4. Ambiguous Syntax Definition for Expressions
6.5. Non-Ambiguous Syntax Definition for Expressions
7.1. Parameterized Module for Regular Expressions