Stratego/XT Examples

Eelco Visser

Delft University of Technology

Karl Trygve Kalleberg

Universitetet i Bergen

Table of Contents

1. Introduction
1.1. Software Transformations
1.2. Introducing Stratego/XT
1.3. Software
1.4. Overview
1.4.1. TIL: A Tiny Imperative Language
1.4.2. BibTeX Transformations
1.4.3. Tiger
1.4.4. Other Applications
I. A Tiny Imperative Language
2. Syntax Definition and Pretty-Printing
2.1. TIL: a Tiny Imperative Language
2.2. Syntax Definition
2.3. Term Format
2.4. Pretty-Printing
2.5. A Complete Pipeline
3. Simplification and Desugaring
3.1. Constant Folding Rules
3.2. Desugaring Rules
3.3. Simplying by Term Rewriting
3.4. Compiling the Simplifier
3.5. Applying the Simplifier
4. Bound Variable Renaming (*)
4.1. Renaming Bound Variables
4.2. Example
5. Typechecking (*)
5.1. Typechecking
5.2. Example
6. Interpretation
6.1. Evaluating Expressions
6.2. Evaluating Variable Accesses
6.3. Evaluating Statements
6.4. The Complete Interpreter
6.5. Running TIL Programs
7. Data-flow Transformation (*)
7.1. Preliminaries
7.2. Constant Propagation
7.3. Copy Propagation
7.4. Reverse Copy Propagation
7.5. Common-subexpression Elimination
7.6. Forward Substitution
7.7. Dead Code Elimination
7.8. Compiling the Transformations
8. Typestate Checking
9. Expression Blocks (*)
9.1. Syntax of Expression Blocks
9.2. Desugaring Expression Blocks
9.3. Example
II. Example Packages (*)
10. Tiger Base (*)
11. BibTeX Tools (*)

List of Figures

2.1. file: til/xmpl/test1.til
2.2. file: til/syn/TIL-layout.sdf
2.3. file: til/syn/TIL-literals.sdf
2.4. file: til/syn/TIL-expressions.sdf
2.5. file: til/syn/TIL-statements.sdf
2.6. file: til/syn/TIL-calls.sdf
2.7. file: til/syn/TIL.sdf
2.8. file: til/syn/maak
2.9. file: til/syn/TIL.def
2.10. file: til/xmpl/parse-test
2.11. file: til/xmpl/test1.atil
2.12. file: til/sig/maak
2.13. file: til/sig/TIL.rtg
2.14. file: til/sig/TIL.str
2.15. file: til/xmpl/fc-test1
2.16. file: til/xmpl/test1.atil.fc
2.17. file: til/xmpl/test1-wrong.atil
2.18. file: til/xmpl/fc-test2
2.19. file: til/xmpl/test1-wrong.atil.fc
2.20. file: til/pp/maak
2.21. file: til/pp/TIL.pp
2.22. file: til/xmpl/pp-test1
2.23. file: til/xmpl/test1.txt1
2.24. file: til/pp/TIL-pretty.pp
2.25. file: til/xmpl/test1.txt2
2.26. file: til/xmpl/pp-test3
2.27. file: til/xmpl/test2.atil
2.28. file: til/xmpl/test2.txt1
2.29. file: til/xmpl/test2.atil.par
2.30. file: til/xmpl/test2.txt2
2.31. file: til/xmpl/til-process
3.1. file: til/sim/til-eval.str
3.2. file: til/sim/til-desugar.str
3.3. file: til/sim/til-simplify.str
3.4. file: til/sim/maak
3.5. file: til/xmpl/simplify-test
4.1. file: til/renaming/til-rename-vars.str
4.2. file: til/xmpl/rename-test
5.1. file: til/tc/til-typecheck.str
5.2. file: til/tc/til-typecheck-exp.str
5.3. file: til/tc/til-typecheck-stats.str
5.4. file: til/tc/til-typecheck-var.str
5.5. file: til/xmpl/typecheck-test1
6.1. file: til/run/til-eval-exp.str
6.2. file: til/run/til-eval-var.str
6.3. file: til/run/til-eval-stats.str
6.4. file: til/run/til-run.str
6.5. file: til/run/maak
6.6. file: til/xmpl/run-test1
6.7. file: til/xmpl/
7.1. file: til/opt/til-opt-lib.str
7.2. file: til/xmpl/propconst-test2
7.3. file: til/opt/til-propconst.str
7.4. file: til/xmpl/copyprop-test2
7.5. file: til/opt/til-copyprop.str
7.6. file: til/opt/til-copyprop-rev.str
7.7. file: til/xmpl/cse-test2
7.8. file: til/opt/til-cse.str
7.9. file: til/opt/til-forward-subst.str
7.10. file: til/xmpl/dce-test2
7.11. file: til/opt/til-dce.str
7.12. file: til/opt/maak
9.1. file: til/til-eblock/TIL-eblocks.sdf
9.2. file: til/til-eblock/til-eblock-desugar.str
9.3. file: til/xmpl/eblock-desugar-test2

List of Tables

3.1. files: til/xmpl/test1.til, til/xmpl/test1.sim.txt
4.1. files: til/xmpl/test1.til, til/xmpl/test1.rn.txt
5.1. files: til/xmpl/test1.til, til/xmpl/
7.1. files: til/xmpl/propconst-test2.til, til/xmpl/propconst-test2.txt
7.2. files: til/xmpl/copyprop-test2.til, til/xmpl/copyprop-test2.txt
7.3. files: til/xmpl/cse-test2.til, til/xmpl/cse-test2.txt
7.4. files: til/xmpl/dce-test2.til, til/xmpl/dce-test2.txt
9.1. files: til/xmpl/eblock-desugar-test2.til, til/xmpl/eblock-desugar-test2.txt
9.2. files: til/xmpl/eblock-desugar-test2.txt, til/xmpl/eblock-desugar-test2.cp.txt

Chapter 1. Introduction

1.1. Software Transformations

Program source code is the raw material produced by the software industry. Rather than being an end product, this material requires further processing to turn it into useful products. Compilation, program generation, domain-specific optimization and reverse-engineering are some examples of such processing. All these processes require the manipulation of program source code. In fact, all such manipulations can be viewed as transformations of a program to a derived program. (Here the notion of `program' is interpreted broadly, and includes all kinds of artifacts used in the composition of software systems, including configuration and data files, as long as there contents conform to some formal language.) Hence, software transformation is the unifying notion underlying automatic program processing.

To reach a higher level of automation in software engineering, the use of automatic software transformation is indispensable. However, the realization of software transformation systems is hard. Parts of the process, such as parsing, are supported by generative techniques, but most aspects require hard work. The effective implementation of software transformation systems is a barrier for the wide adoption of software transformation in software engineering. Most transformation techniques used in practice are based on textual generation and manipulation, which poses limitations on what can be done and is error-prone.

The examples contained in the next chapters show how to do software transformation in a structured and robust way. They are all implemented using the Stratego/XT framework. This framework provides a versatile collection of transformation tools that can be applied to transformation of source code as well as documents. The goal of this example-based tutorial is to show how Stratego/XT is applied to practical problems, and is complimentary to the Stratego/XT Tutorial.

1.2. Introducing Stratego/XT

Stratego/XT is a framework for the implementation of transformation systems based on structural representations of programs. This structured representation avoids the limitations and brittleness found in the text-based approaches. Stratego/XT consists of two major parts: XT, a component architecture and collection of components for basic transformation infrastructure, such as parsing and pretty-printing; and Stratego, a strategic term rewriting language for implementing new, custom components.

Together, Stratego and XT aim to provide better productivity in the development of transformation systems through the use of high-level representations, domain-specific languages, and generative programming for various aspects of transformation systems: ATerms for program representation, SDF for syntax definition and parsing, GPP for pretty-printing, Stratego for transformation, XTC for transformation tool composition, and the XT tools for the generation of intermediate products needed in the construction of transformation systems.

The XTC composition system allows the combination of ready-made components found in the XT architecture with new components written in Stratego. This makes Stratego/XT a scalable and flexible environment for developing stand-alone transformation systems.

1.3. Software

To build transformation systems using Stratego/XT you need the following software packages:

  • ATerm Library: library used for structured representation of programs

  • SDF2 Bundle: parser generator and parser for the SDF2 grammar formalism

  • Stratego/XT: the Stratego compiler and the XT tools

The packages are distributed as source files, and installation follows the normal Unix configure and make style. For some operating systems, ready-made packages are also provided. A complete account of the installation procedure for these packages is given in Chapter 2 of the Stratego/XT Tutorial.

Additionally, the following packages will be necessary to get full benefit of all the examples. These packages are not strictly required for building Stratego/XT programs, however.

Once you have this software installed and ready to use on your workstation, you are ready to proceed with testing the examples contained in the next chapters.

1.4. Overview

This tutorial gives an introduction to transformation with Stratego/XT by means of a number of examples that show typical ways of organizing transformation systems. The tutorial is divided into a number of parts, each part dedicated to a particular source language. For each language we show how to define its syntax, create a pretty-printer, and implement a number of transformations. In addition, we show which tools to use to generate parsers from syntax definitions, derive pretty-printers from syntax definitions, and compile transformation programs. The source code of the examples can be downloaded as well, so that you can repeat the experiments from the tutorial and add your own experiments.

1.4.1. TIL: A Tiny Imperative Language

The first example in the tutorial is a tiny imperative language (TIL), which has assignment statements, sequences of statements, and structured control-flow.

For this simple language we define a complete syntax definition, and show how to generate from it a parser, signature, format checker, and pretty-print table. Based on these ingredients we explain how to create a typical transformation pipeline (without any transformations yet).

Next we show how to define a number of typical transformations such as desugaring, bound variable renaming, interpretation, and data-flow transformations.

1.4.2. BibTeX Transformations

BibTeX is a small domain-specific data language for bibliographic information. It is included in the examples collection to show how Stratego/XT can be applied to document processing. In the second part of this tutorial we show the syntax definition for BibTeX and a number of transformations on BibTeX documents.

1.4.3. Tiger

Tiger is the example language in Andrew Appel's compiler textbook series. It is a small imperative language, yet non-trivial with nested functions, arrays and records. The Tiger Base package provides a syntax definition, interpreter, pretty-printer, type checker, and a number of source to source transformations.

1.4.4. Other Applications

This tutorial is not complete. There are many other examples of applications of Stratego that are not (yet) covered by this tutorial. Here are some examples:

  • Analysis: check that variables are defined before use

  • Typechecking: check that variables are used consistently

  • Partial evaluation: specialize programs on specific inputs

  • Custom pretty-printing

  • Configuration and deployment

  • Domain-specific languages: implementation, compilation, optimization

  • Code generation: from specifications, high-level languages

  • Language embedding and assimilation

You are welcome to contribute examples, or request for examples of particular types of applications.