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 (*)
10.1.
10.2.
10.3.
11. BibTeX Tools (*)
11.1.
11.2.
11.3.

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/test1.run
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/test1.tc
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.

Part I. A Tiny Imperative Language

Chapter 2. Syntax Definition and Pretty-Printing

2.1. TIL: a Tiny Imperative Language

This chapter shows how to define a syntax definition in SDF and how to derive a number of artifacts from such a definition, i.e., a parser, a pretty-printer, and a Stratego signature. The chapter also introduces TIL, a Tiny Imperative Language, which is used in many of the examples.

TIL is a tiny imperative language designed for the demonstration of language and transformation definition formalisms. The language has two data-types, integers and strings. A TIL program consists of a list of statements, which can be variable declarations, assignments, I/O instructions, and control-flow statements. Statements can use expressions to compute values from integer and string constants, and the values of variables.

The following example gives an impression of the language.

Figure 2.1. file: til/xmpl/test1.til

// TIL program computing the factorial

var n;
n := readint();
var x;
var fact;
fact := 1;
for x := 1 to n do
  fact := x * fact;
end
write("factorial of ");
writeint(n);
write(" is ");
writeint(fact);
write("\n");

2.2. Syntax Definition

This section shows a modular definition of the syntax of TIL, the generation of a parse table from that definition, and its use for parsing program texts into abstract syntax trees.

2.2.1. Modules

The following files define the syntax of TIL in the syntax definition formalism SDF. SDF is a modular formalism that supports the definition of lexical and context-free syntax. Modularity entails that a syntax definition can be composed from multiple modules, and that such modules can be reused in multiple syntax definitions. Also, syntax definitions of different languages can be combined.

2.2.1.1. Layout

Module TIL-layout defines the syntax of LAYOUT, the symbols that occur between every two context-free non-terminals. This is the way to introduce the whitespace and comments for a language. The definition uses character classes to indicate classes of characters. For instance, whitespace consists of spaces, tabs, newlines, and carriage returns. Likewise, comments consist of two slashes followed by zero or more characters which are not newlines or carriage returns. The follow restriction prevents ambiguities in parsing layout.

Figure 2.2. file: til/syn/TIL-layout.sdf

module TIL-layout
exports 
  lexical syntax
    [\ \t\n\r]    -> LAYOUT
    "//" ~[\n\r]* -> LAYOUT
  context-free restrictions
    LAYOUT? -/- [\ \t\n\r]

2.2.1.2. Literals

Module TIL-literals defines the syntax of identifiers, integer constants, and string literals. Note again the use of character classes to indicate collections of characters and regular expressions to indicate lists of zero or more (*), or one or more (+) elements. String characters (StrChar) are any characters other than double quote, backslash, or newline, and escaped versions of these characters.

Figure 2.3. file: til/syn/TIL-literals.sdf

module TIL-literals
exports 
  sorts Id Int String StrChar
  lexical syntax
    [A-Za-z][A-Za-z0-9]* -> Id
    [0-9]+               -> Int
    "\"" StrChar* "\""   -> String
    ~[\"\\\n]            -> StrChar
    [\\][\"\\n]          -> StrChar
  lexical restrictions
    Id  -/- [A-Za-z0-9]
    Int -/- [0-9]    

2.2.1.3. Expressions

Module TIL-expressions defines the syntax of expressions that compute a value. Basic expressions are identifiers (variables), integer constants, and string literals. More complex expressions are obtained by the arithmetic and relational operators. The constructor attributes of productions (e.g., cons("Add")) indicates the constructor to be used in the construction of an abstract syntax tree from a parse tree. Ambiguities of and between productions are solved by means of associativity and priority declarations.

Figure 2.4. file: til/syn/TIL-expressions.sdf

module TIL-expressions
imports TIL-literals
exports 
  sorts Exp
  context-free syntax
    "true"       -> Exp {cons("True")}
    "false"      -> Exp {cons("False")}
    Id           -> Exp {cons("Var")}
    Int          -> Exp {cons("Int")}
    String       -> Exp {cons("String")}
    Exp "*" Exp  -> Exp {cons("Mul"),assoc}
    Exp "/" Exp  -> Exp {cons("Div"),assoc}
    Exp "%" Exp  -> Exp {cons("Mod"),non-assoc}
    Exp "+" Exp  -> Exp {cons("Add"),assoc}
    Exp "-" Exp  -> Exp {cons("Sub"),left}
    Exp "<" Exp  -> Exp {cons("Lt"),non-assoc}
    Exp ">" Exp  -> Exp {cons("Gt"),non-assoc}
    Exp "<=" Exp -> Exp {cons("Leq"),non-assoc}
    Exp ">=" Exp -> Exp {cons("Geq"),non-assoc}
    Exp "=" Exp  -> Exp {cons("Equ"),non-assoc}
    Exp "!=" Exp -> Exp {cons("Neq"),non-assoc}
    Exp "&" Exp  -> Exp {cons("And"),assoc}
    Exp "|" Exp  -> Exp {cons("Or"),assoc}
    "(" Exp ")"  -> Exp {bracket}
  context-free priorities
    {left: 
       Exp "*" Exp -> Exp 
       Exp "/" Exp -> Exp }
  > {left: 
       Exp "+" Exp -> Exp 
       Exp "-" Exp -> Exp }
  > {non-assoc: 
       Exp "<" Exp  -> Exp 
       Exp ">" Exp  -> Exp
       Exp "<=" Exp -> Exp 
       Exp ">=" Exp -> Exp
       Exp "="  Exp -> Exp 
       Exp "!=" Exp -> Exp }
  > Exp "&" Exp  -> Exp
  > Exp "|" Exp  -> Exp

2.2.1.4. Statements

Module TIL-statements defines the syntax of statements, i.e., instructions to be executed. The assignment statement assigns the value of the right-hand side expression to the variable in the left-hand side. The read and write statements read a value from standard input or write a value to standard output. The control-flow constructs use lists of statements.

Figure 2.5. file: til/syn/TIL-statements.sdf

module TIL-statements
imports TIL-expressions TIL-types
exports 
  sorts Stat
  context-free syntax
    "var" Id ";"			                    -> Stat {cons("Declaration")}
    "var" Id ":" Type ";"			            -> Stat {cons("DeclarationTyped")}
    Id ":=" Exp ";"                             -> Stat {cons("Assign")}
    "begin" Stat* "end"                         -> Stat {cons("Block")}
    "if" Exp "then" Stat* "end"                 -> Stat {cons("IfThen")}
    "if" Exp "then" Stat* "else" Stat* "end"    -> Stat {cons("IfElse")}
    "while" Exp "do" Stat* "end"                -> Stat {cons("While")}
    "for" Id ":=" Exp "to" Exp "do" Stat* "end" -> Stat {cons("For")}


2.2.1.5. Function and Procedure Calls

Module TIL-calls defines the syntax of function and procedure calls. Even though TIL does not have function definitions, it is useful to be able to call primitive functions and procedures.

Figure 2.6. file: til/syn/TIL-calls.sdf

module TIL-calls
imports TIL-expressions TIL-statements
exports
  context-free syntax
    Id "(" {Exp ","}* ")"     -> Exp  {cons("FunCall")}
    Id "(" {Exp ","}* ")" ";" -> Stat {cons("ProcCall")}

2.2.1.6. Programs

Module TIL (Figure 2.7) defines the syntax of the complete language by importing the modules above, and defining a Program as a list of statements. In addition, the module introduces a start-symbol. This is the sort that a parser will start parsing with. There may be multiple start symbols.

Figure 2.7. file: til/syn/TIL.sdf

module TIL
imports TIL-layout TIL-literals TIL-expressions TIL-statements TIL-calls
exports 
  sorts Program
  context-free syntax
    Stat* -> Program {cons("Program")}

  context-free start-symbols Program

2.2.2. Parse Table Generation

The following maak script first collects the modules of the syntax definition and then generates a parse table. The result of pack-sdf is a `definition' file (as opposed to a single module file, as we saw above) that contains all modules imported by the main module, TIL.sdf in this case (Figure 2.9). The parser generator sdf2table creates a parse table from a syntax definition. Note the use of the -m flag to indicate the main module from which to generate the table. The parse table (TIL.tbl) is a file in ATerm format, that is interpreted by the sglri tool to parse text files.

Figure 2.8. file: til/syn/maak

#! /bin/sh -e

# collect modules 
pack-sdf -i TIL.sdf -o TIL.def

# generate parse table
sdf2table -i TIL.def -o TIL.tbl -m TIL

Figure 2.9. file: til/syn/TIL.def

definition
module TIL-calls
imports TIL-expressions TIL-statements
exports
  context-free syntax
    Id "(" {Exp ","}* ")"     -> Exp  {cons("FunCall")}
    Id "(" {Exp ","}* ")" ";" -> Stat {cons("ProcCall")}

module TIL-types
imports TIL-literals
exports 
 sorts Type
  context-free syntax
    Id -> Type {cons("TypeName")}

module TIL-statements
imports TIL-expressions TIL-types
exports 
  sorts Stat
  context-free syntax
    "var" Id ";"			                    -> Stat {cons("Declaration")}
    "var" Id ":" Type ";"			            -> Stat {cons("DeclarationTyped")}
    Id ":=" Exp ";"                             -> Stat {cons("Assign")}
    "begin" Stat* "end"                         -> Stat {cons("Block")}
    "if" Exp "then" Stat* "end"                 -> Stat {cons("IfThen")}
    "if" Exp "then" Stat* "else" Stat* "end"    -> Stat {cons("IfElse")}
    "while" Exp "do" Stat* "end"                -> Stat {cons("While")}
    "for" Id ":=" Exp "to" Exp "do" Stat* "end" -> Stat {cons("For")}

module TIL-expressions
imports TIL-literals
exports 
  sorts Exp
  context-free syntax
    "true"       -> Exp {cons("True")}
    "false"      -> Exp {cons("False")}
    Id           -> Exp {cons("Var")}
    Int          -> Exp {cons("Int")}
    String       -> Exp {cons("String")}
    Exp "*" Exp  -> Exp {cons("Mul"),assoc}
    Exp "/" Exp  -> Exp {cons("Div"),assoc}
    Exp "%" Exp  -> Exp {cons("Mod"),non-assoc}
    Exp "+" Exp  -> Exp {cons("Add"),assoc}
    Exp "-" Exp  -> Exp {cons("Sub"),left}
    Exp "<" Exp  -> Exp {cons("Lt"),non-assoc}
    Exp ">" Exp  -> Exp {cons("Gt"),non-assoc}
    Exp "<=" Exp -> Exp {cons("Leq"),non-assoc}
    Exp ">=" Exp -> Exp {cons("Geq"),non-assoc}
    Exp "=" Exp  -> Exp {cons("Equ"),non-assoc}
    Exp "!=" Exp -> Exp {cons("Neq"),non-assoc}
    Exp "&" Exp  -> Exp {cons("And"),assoc}
    Exp "|" Exp  -> Exp {cons("Or"),assoc}
    "(" Exp ")"  -> Exp {bracket}
  context-free priorities
    {left: 
       Exp "*" Exp -> Exp 
       Exp "/" Exp -> Exp }
  > {left: 
       Exp "+" Exp -> Exp 
       Exp "-" Exp -> Exp }
  > {non-assoc: 
       Exp "<" Exp  -> Exp 
       Exp ">" Exp  -> Exp
       Exp "<=" Exp -> Exp 
       Exp ">=" Exp -> Exp
       Exp "="  Exp -> Exp 
       Exp "!=" Exp -> Exp }
  > Exp "&" Exp  -> Exp
  > Exp "|" Exp  -> Exp


module TIL-literals
exports 
  sorts Id Int String StrChar
  lexical syntax
    [A-Za-z][A-Za-z0-9]* -> Id
    [0-9]+               -> Int
    "\"" StrChar* "\""   -> String
    ~[\"\\\n]            -> StrChar
    [\\][\"\\n]          -> StrChar
  lexical restrictions
    Id  -/- [A-Za-z0-9]
    Int -/- [0-9]

module TIL-layout
exports 
  lexical syntax
    [\ \t\n\r]    -> LAYOUT
    "//" ~[\n\r]* -> LAYOUT
  context-free restrictions
    LAYOUT? -/- [\ \t\n\r]

module TIL
imports TIL-layout TIL-literals TIL-expressions TIL-statements TIL-calls
exports 
  sorts Program
  context-free syntax
    Stat* -> Program {cons("Program")}

  context-free start-symbols Program

2.2.3. Parsing Programs

The sglri tool parses a text file given a parse table generated by sdf2table. The result is an abstract syntax term in the ATerm format. In order to inspect this term it is useful to `pretty-print' it using the pp-aterm tool. Compare the resulting term with the program in Figure 2.1.

Figure 2.10. file: til/xmpl/parse-test

# parse input file
sglri -p ../syn/TIL.tbl -i test1.til -o test1.ast

# `pretty-print' abstract syntax term
pp-aterm -i test1.ast -o test1.atil

Figure 2.11. file: til/xmpl/test1.atil

Program(
  [ Declaration("n")
  , Assign("n", FunCall("readint", []))
  , Declaration("x")
  , Declaration("fact")
  , Assign("fact", Int("1"))
  , For(
      "x"
    , Int("1")
    , Var("n")
    , [Assign("fact", Mul(Var("x"), Var("fact")))]
    )
  , ProcCall("write", [String("\"factorial of \"")])
  , ProcCall("writeint", [Var("n")])
  , ProcCall("write", [String("\" is \"")])
  , ProcCall("writeint", [Var("fact")])
  , ProcCall("write", [String("\"\\n\"")])
  ]
)

2.3. Term Format

The result of parsing a text is an abstract syntax tree represented by means of an ATerm. When produced by a parser, one can be sure that an ATerm has the right format, since it was derived directly from a parse tree. However, terms can also be produced by other components, e.g., be the result of a transformation. In those cases it may worthwhile to check that the term is well-formed according to some schema. In Stratego/XT tree schemas are described by Regular Tree Grammars (RTGs). Stratego signatures are used within Stratego programs to verify some aspects of Stratego programs. RTGs and signatures can be derived automatically from a syntax definition in SDF.

The following maak scripts derives from a syntax definition first an RTG, and from the RTG a Stratego signature.

Figure 2.12. file: til/sig/maak

#! /bin/sh -e

# generate regular tree grammar from syntax definition
sdf2rtg -i ../syn/TIL.def -o TIL.rtg -m TIL

# generate Stratego signature from regular tree grammar
rtg2sig -i TIL.rtg -o TIL.str 

2.3.1. Regular Tree Grammars

A regular tree grammar defines well-formedness rules for a set of trees (or terms). The following regular tree grammar has been generated from the syntax definition of TIL and precisely describes the abstract syntax trees of TIL programs.

Figure 2.13. file: til/sig/TIL.rtg

regular tree grammar
  start Program
  productions
    ListStarOfStat0    -> ListPlusOfStat0
    ListStarOfStat0    -> <nil>()
    ListStarOfStat0    -> <conc>(ListStarOfStat0,ListStarOfStat0)
    ListPlusOfStat0    -> <conc>(ListStarOfStat0,ListPlusOfStat0)
    ListPlusOfStat0    -> <conc>(ListPlusOfStat0,ListStarOfStat0)
    ListPlusOfStat0    -> <conc>(ListPlusOfStat0,ListPlusOfStat0)
    ListPlusOfStat0    -> <cons>(Stat,ListStarOfStat0)
    ListStarOfExp0     -> ListPlusOfExp0
    ListStarOfExp0     -> <nil>()
    ListStarOfExp0     -> <conc>(ListStarOfExp0,ListStarOfExp0)
    ListPlusOfExp0     -> <conc>(ListStarOfExp0,ListPlusOfExp0)
    ListPlusOfExp0     -> <conc>(ListPlusOfExp0,ListStarOfExp0)
    ListPlusOfExp0     -> <conc>(ListPlusOfExp0,ListPlusOfExp0)
    ListPlusOfExp0     -> <cons>(Exp,ListStarOfExp0)
    ListStarOfStrChar0 -> <string>
    ListPlusOfStrChar0 -> <string>
    Program            -> Program(ListStarOfStat0)
    Stat               -> ProcCall(Id,ListStarOfExp0)
    Exp                -> FunCall(Id,ListStarOfExp0)
    Stat               -> For(Id,Exp,Exp,ListStarOfStat0)
    Stat               -> While(Exp,ListStarOfStat0)
    Stat               -> IfElse(Exp,ListStarOfStat0,ListStarOfStat0)
    Stat               -> IfThen(Exp,ListStarOfStat0)
    Stat               -> Block(ListStarOfStat0)
    Stat               -> Assign(Id,Exp)
    Stat               -> DeclarationTyped(Id,Type)
    Stat               -> Declaration(Id)
    Type               -> TypeName(Id)
    Exp                -> Or(Exp,Exp)
    Exp                -> And(Exp,Exp)
    Exp                -> Neq(Exp,Exp)
    Exp                -> Equ(Exp,Exp)
    Exp                -> Geq(Exp,Exp)
    Exp                -> Leq(Exp,Exp)
    Exp                -> Gt(Exp,Exp)
    Exp                -> Lt(Exp,Exp)
    Exp                -> Sub(Exp,Exp)
    Exp                -> Add(Exp,Exp)
    Exp                -> Mod(Exp,Exp)
    Exp                -> Div(Exp,Exp)
    Exp                -> Mul(Exp,Exp)
    Exp                -> String(String)
    Exp                -> Int(Int)
    Exp                -> Var(Id)
    Exp                -> False()
    Exp                -> True()
    StrChar            -> <string>
    String             -> <string>
    Int                -> <string>
    Id                 -> <string>

2.3.2. Signatures

Algebraic signatures are similar to regular tree grammars. Stratego requires signatures for the declaration of term constructors to be used in transformation programs. The following Stratego signature is generated from the regular tree grammar above, and thus describes the constructors of TIL abstract syntax trees.

Figure 2.14. file: til/sig/TIL.str

module TIL

signature
  constructors
    Program          : List(Stat) -> Program
    ProcCall         : Id * List(Exp) -> Stat
    For              : Id * Exp * Exp * List(Stat) -> Stat
    While            : Exp * List(Stat) -> Stat
    IfElse           : Exp * List(Stat) * List(Stat) -> Stat
    IfThen           : Exp * List(Stat) -> Stat
    Block            : List(Stat) -> Stat
    Assign           : Id * Exp -> Stat
    DeclarationTyped : Id * Type -> Stat
    Declaration      : Id -> Stat
    TypeName         : Id -> Type
    FunCall          : Id * List(Exp) -> Exp
    Or               : Exp * Exp -> Exp
    And              : Exp * Exp -> Exp
    Neq              : Exp * Exp -> Exp
    Equ              : Exp * Exp -> Exp
    Geq              : Exp * Exp -> Exp
    Leq              : Exp * Exp -> Exp
    Gt               : Exp * Exp -> Exp
    Lt               : Exp * Exp -> Exp
    Sub              : Exp * Exp -> Exp
    Add              : Exp * Exp -> Exp
    Mod              : Exp * Exp -> Exp
    Div              : Exp * Exp -> Exp
    Mul              : Exp * Exp -> Exp
    String           : String -> Exp
    Int              : Int -> Exp
    Var              : Id -> Exp
    False            : Exp
    True             : Exp
                     : String -> String
                     : String -> Int
                     : String -> Id


signature
  constructors
    Some : a -> Option(a)
    None : Option(a)


signature
  constructors
    Cons : a * List(a) -> List(a)
    Nil  : List(a)
    Conc : List(a) * List(a) -> List(a)

2.3.3. Format Checking

The well-formedness of a term with respect to a regular tree grammar can be checked using the format-check tool. When well-formed the tool prints the type of the term. If not it indicates, which subterms cannot be typed. The following examples illustrate checking of a well-formed and non well-formed term.

Figure 2.15. file: til/xmpl/fc-test1

format-check --rtg ../sig/TIL.rtg -i test1.atil -s Program 2> test1.atil.fc

Figure 2.16. file: til/xmpl/test1.atil.fc


Figure 2.17. file: til/xmpl/test1-wrong.atil

Program(
  [ Declaration("fact")
  , Assig("fact", Int("1"))
  , Assign("fact", Mul("x", Var("fact")))
  ]
)

Figure 2.18. file: til/xmpl/fc-test2

format-check --rtg ../sig/TIL.rtg -i test1-wrong.atil -s Program 2> test1-wrong.atil.fc

Figure 2.19. file: til/xmpl/test1-wrong.atil.fc

error: cannot type Assig("fact",Int("1"))
    inferred types of subterms: 
    typed "fact" as String, Int, Id, <string>
    typed Int("1") as Exp
error: cannot type Mul("x",Var("fact"))
    inferred types of subterms: 
    typed "x" as String, Int, Id, <string>
    typed Var("fact") as Exp

2.4. Pretty-Printing

After transforming a program we need to turn it into a program text again. Unparsing is the reverse of parsing and turns an abstract syntax tree into a text. Pretty-printing is unparsing with an attempt at creating a readable program text. There is a direct correspondence between abstract syntax trees and the program text from which they were produced defined by the syntax definition. This can be used in the other direction as well to generate a pretty-printer from a syntax definition. The following maak script generates from the TIL syntax definition a pretty-print table TIL.pp using ppgen and a parenthesizer using sdf2parenthesize. The latter is a Stratego program, which is compiled using the Stratego compiler strc.

Figure 2.20. file: til/pp/maak

#! /bin/sh -e

# generate pretty-print table from syntax definition
ppgen -i ../syn/TIL.def -o TIL.pp

# generate program to insert parentheses
sdf2parenthesize -i ../syn/TIL.def -o til-parenthesize.str -m TIL --lang TIL

# compile the generated program
strc -i til-parenthesize.str -I ../sig -m io-til-parenthesize -la stratego-lib

2.4.1. Pretty-Print Table

A pretty-print table defines a mapping from abstract syntax trees to expressions in the Box Formatting Language. The following pretty-print table is generated from the syntax definition for TIL. It is a default table and only ensures that the program text resulting from pretty-printing is syntactically correct, not that it is actually pretty.

Figure 2.21. file: til/pp/TIL.pp

[
   FunCall                  -- _1 KW["("] _2 KW[")"],
   FunCall.2:iter-star-sep  -- _1 KW[","],
   ProcCall                 -- _1 KW["("] _2 KW[")"] KW[";"],
   ProcCall.2:iter-star-sep -- _1 KW[","],
   TypeName                 -- _1,
   Declaration              -- KW["var"] _1 KW[";"],
   DeclarationTyped         -- KW["var"] _1 KW[":"] _2 KW[";"],
   Assign                   -- _1 KW[":="] _2 KW[";"],
   Block                    -- V  [V vs=2 [KW["begin"] _1] KW["end"]],
   Block.1:iter-star        -- _1,
   IfThen                   -- KW["if"] _1 KW["then"] _2 KW["end"],
   IfThen.2:iter-star       -- _1,
   IfElse                   -- KW["if"] _1 KW["then"] _2 KW["else"] _3 KW["end"],
   IfElse.2:iter-star       -- _1,
   IfElse.3:iter-star       -- _1,
   While                    -- KW["while"] _1 KW["do"] _2 KW["end"],
   While.2:iter-star        -- _1,
   For                      -- KW["for"] _1 KW[":="] _2 KW["to"] _3 KW["do"] _4 KW["end"],
   For.4:iter-star          -- _1,
   True                     -- KW["true"],
   False                    -- KW["false"],
   Var                      -- _1,
   Int                      -- _1,
   String                   -- _1,
   Mul                      -- _1 KW["*"] _2,
   Div                      -- _1 KW["/"] _2,
   Mod                      -- _1 KW["%"] _2,
   Add                      -- _1 KW["+"] _2,
   Sub                      -- _1 KW["-"] _2,
   Lt                       -- _1 KW["<"] _2,
   Gt                       -- _1 KW[">"] _2,
   Leq                      -- _1 KW["<="] _2,
   Geq                      -- _1 KW[">="] _2,
   Equ                      -- _1 KW["="] _2,
   Neq                      -- _1 KW["!="] _2,
   And                      -- _1 KW["&"] _2,
   Or                       -- _1 KW["|"] _2,
   Program                  -- _1,
   Program.1:iter-star      -- _1
]

2.4.2. Applying Pretty-Print Tables

A pretty-print table is applied using the ast2text tool, which translates an abstract syntax term to text given a pretty-print table. (In fact, ast2text is a composition of ast2abox and abox2text.) The pp-test1 script shows how to use a pretty-print table. The result of unparsing the AST for the test1.til program is clearly not very pretty, but it is a syntactically correct TIL program. This is tested by the subsequent commands in the script, which parse the test1.txt1 program and compare the resulting AST to the original AST. It turns out that the two programs have the exact same AST.

Figure 2.22. file: til/xmpl/pp-test1

# abstract syntax term to text
ast2text -p ../pp/TIL.pp -i test1.atil -o test1.txt1

# test unparsed code
sglri -p ../syn/TIL.tbl -i test1.txt1 | pp-aterm -o test1.atxt1

# test if the terms are the same
diff test1.atil test1.atxt1

Figure 2.23. file: til/xmpl/test1.txt1

var n ; n := readint (  ) ; var x ; var fact ; fact := 1 ; for x := 1 to n do
fact := x * fact ; end write ( "factorial of " ) ; writeint ( n ) ; write (
" is " ) ; writeint ( fact ) ; write ( "\n" ) ;

2.4.3. Adapting the Pretty-Print Table

To get more readable programs after pretty-printing we adapt the generated pretty-print table using constructs from the Box Formatting Language to indicate how each construct should be formatted.

Figure 2.24. file: til/pp/TIL-pretty.pp

[
   FunCall                  -- H hs=0 [_1 KW["("] H  [_2] KW[")"]],
   FunCall.2:iter-star-sep  -- H hs=0 [_1 KW[","]],
   ProcCall                 -- H hs=0 [_1 KW["("] H  [_2] KW[")"] KW[";"]],
   ProcCall.2:iter-star-sep -- H hs=0 [_1 KW[","]],
   Declaration              -- H hs=0 [H  [KW["var"] _1] KW[";"]],
   DeclarationTyped         -- H hs=0 [H  [KW["var"] _1 KW[":"] _2] KW[";"]],
   Assign                   -- H hs=0 [H  [_1 KW[":="] _2] KW[";"]],
   Read                     -- H hs=0 [H  [KW["read"] _1] KW[";"]],
   Write                    -- H hs=0 [H  [KW["write"] _1] KW[";"]],
   Block                    -- V  [V is=2 [KW["begin"] V  [_1]] KW["end"]],
   Block.1:iter-star        -- _1,
   IfThen                   -- V  [V is=2 [H  [KW["if"] _1 KW["then"]] V  [_2]] KW["end"]],
   IfThen.2:iter-star       -- _1,
   IfElse                   -- V  [V is=2 [H  [KW["if"] _1 KW["then"]] V  [_2]] V is=2 [KW["else"] V  [_3]] KW["end"]],
   IfElse.2:iter-star       -- _1,
   IfElse.3:iter-star       -- _1,
   While                    -- V  [V is=2 [H  [KW["while"] _1 KW["do"]] _2] KW["end"]],
   While.2:iter-star        -- _1,
   For                      -- V  [V is=2 [H  [KW["for"] _1 KW[":="] _2 KW["to"] _3 KW["do"]] _4] KW["end"]],
   For.4:iter-star          -- _1,
   True                     -- KW["true"],
   False                    -- KW["false"],
   Var                      -- _1,
   Int                      -- _1,
   String                   -- _1,
   Mul                      -- H hs=1 [_1 KW["*"] _2],
   Div                      -- H hs=1 [_1 KW["/"] _2],
   Mod                      -- H hs=1 [_1 KW["%"] _2],
   Add                      -- H hs=1 [_1 KW["+"] _2],
   Sub                      -- H hs=1 [_1 KW["-"] _2],
   Lt                       -- H hs=1 [_1 KW["<"] _2],
   Gt                       -- H hs=1 [_1 KW[">"] _2],
   Leq                      -- H hs=1 [_1 KW["<="] _2],
   Geq                      -- H hs=1 [_1 KW[">="] _2],
   Equ                      -- H hs=1 [_1 KW["="] _2],
   Neq                      -- H hs=1 [_1 KW["!="] _2],
   And                      -- H hs=1 [_1 KW["&"] _2],
   Or                       -- H hs=1 [_1 KW["|"] _2],
   Program                  -- V  [_1],
   Program.1:iter-star      -- _1,
   Parenthetical            -- H hs=0 ["(" _1 ")"],
   TypeName                 -- _1
]

Using the same procedure as before, but using the adapted pretty-print table (see til/xmpl/pp-test2) we not get a program that is much closer to the original.

Figure 2.25. file: til/xmpl/test1.txt2

var n;
n := readint();
var x;
var fact;
fact := 1;
for x := 1 to n do
  fact := x * fact;
end
write("factorial of ");
writeint(n);
write(" is ");
writeint(fact);
write("\n");

2.4.4. Restoring Parentheses

The til-parenthesize program generated by sdf2parenthesize is a simple rewrite system with rules that add a Parenthetical constructor around subtrees that have a priority or associativity conflict with their parent node. The implementation in til/pp/til-parenthesize.str is not of interest here. The program is used before applying the pretty-print table, as illustrated with the following example. The test2.txt1 program is produced without introducing parentheses and clearly has a different meaning than the original program. The test2.txt2 program has parentheses in the right places.

Figure 2.26. file: til/xmpl/pp-test3

# pretty-print without parentheses
ast2text -p ../pp/TIL-pretty.pp -i test2.atil -o test2.txt1

# add parentheses to abstract syntax term
../pp/til-parenthesize -i test2.atil | pp-aterm -o test2.atil.par

# pretty-print without parentheses
ast2text -p ../pp/TIL-pretty.pp -i test2.atil.par -o test2.txt2

Figure 2.27. file: til/xmpl/test2.atil

Program(
  [ IfElse(
      Equ(
        Mul(Var("x"), Add(Var("y"), Int("10")))
      , Int("34")
      )
    , [ Assign(
          "x"
        , Div(Var("x"), Sub(Var("y"), Int("1")))
        )
      ]
    , [ Assign(
          "x"
        , Mul(Var("x"), Div(Var("y"), Int("3")))
        )
      ]
    )
  ]
)

Figure 2.28. file: til/xmpl/test2.txt1

if x * y + 10 = 34 then
  x := x / y - 1;
else
  x := x * y / 3;
end

Figure 2.29. file: til/xmpl/test2.atil.par

Program(
  [ IfElse(
      Equ(
        Mul(
          Var("x")
        , Parenthetical(Add(Var("y"), Int("10")))
        )
      , Int("34")
      )
    , [ Assign(
          "x"
        , Div(
            Var("x")
          , Parenthetical(Sub(Var("y"), Int("1")))
          )
        )
      ]
    , [ Assign(
          "x"
        , Mul(
            Var("x")
          , Parenthetical(Div(Var("y"), Int("3")))
          )
        )
      ]
    )
  ]
)

Figure 2.30. file: til/xmpl/test2.txt2

if x * (y + 10) = 34 then
  x := x / (y - 1);
else
  x := x * (y / 3);
end

2.5. A Complete Pipeline

Given an SDF syntax definition we can produce a parser, a format checker, a parenthesizer, and a pretty-printer. Together these tools form the basic ingredients of a transformation pipeline. The composition in til-process shows how the tools are combined. This composition is not so useful as it only turns a program in a pretty-printed version of itself. In the next chapters we'll see how this pipeline can be extended with transformation tools.

Figure 2.31. file: til/xmpl/til-process

# a parse, check, parenthesize, pretty-print pipeline

sglri -p ../syn/TIL.tbl -i $1           |\
format-check --rtg ../sig/TIL.rtg       |\
../pp/til-parenthesize                  |\
 ast2text -p ../pp/TIL-pretty.pp -o $2

Chapter 3. Simplification and Desugaring

Given the infrastructure presented in the previous chapter we can create a basic pipeline for performing transformations on abstract syntax trees. What is missing is the actual transformations to perform. In the Stratego/XT setting, we use the Stratego language for defining transformations on abstract syntax trees. In this chapter we show how to define a collection of basic term rewrite rules, and how to combine these using the standard innermost strategy to simplify TIL programs.

3.1. Constant Folding Rules

Stratego is a modular programming languages and supports the definition of named rewrite rules. These rules can be used in many different transformations by importing the module defining them and using their names as arguments of rewriting strategies.

Module til-eval imports the signature of TIL, which defines the constructors of the abstract syntax of TIL. Then the module defines rewrite rules for evaluating constructs that are (partially) constant. For instance, the addition of two integer constants can be reduced to the integer constant of their sum.

Figure 3.1. file: til/sim/til-eval.str

module til-eval
imports TIL
rules

  EvalAdd :
    Add(Int(i), Int(j)) -> Int(<addS>(i,j))

  EvalAdd :
    Add(String(i), String(j)) -> String(<conc-strings>(i,j))

  EvalSub : 
    Sub(Int(i), Int(j)) -> Int(<subtS>(i,j))

  EvalMul :
    Mul(Int(i), Int(j)) -> Int(<mulS>(i,j))

  EvalDiv :
    Div(Int(i), Int(j)) -> Int(<divS>(i,j))

  EvalMod :
    Mod(Int(i), Int(j)) -> Int(<modS>(i,j))

  EvalLt :
    Lt(Int(i), Int(j)) -> <compare(ltS)>(i,j)

  EvalGt :
    Gt(Int(i), Int(j)) -> <compare(gtS)>(i,j)

  EvalLeq :
    Leq(Int(i), Int(j)) -> <compare(leqS)>(i,j)

  EvalGeq :
    Geq(Int(i), Int(j)) -> <compare(geqS)>(i,j)

  EvalEqu :
    Equ(Int(i), Int(j)) -> <compare(eq)>(i,j)
    
  EvalNeq :
    Neq(Int(i), Int(j)) -> <compare(not(eq))>(i,j)
    
  compare(s) =
    if s then !True() else !False() end
    
  EvalOr :
    Or(True(), e) -> True()
    
  EvalOr :
    Or(False(), e) -> e
    
  EvalAnd :
    And(True(), e) -> e
    
  EvalAnd :
    And(False(), e) -> False()
    
  AddZero :
    Add(e, Int("0")) -> e

  AddZero :
    Add(Int("0"), e) -> e

  MulOne :
    Mul(e, Int("1")) -> e

  MulOne :
    Mul(Int("1"), e) -> e
    
  EvalS2I :
    FunCall("string2int", [String(x)]) -> Int(x)
    where <string-to-int> x
   
  EvalI2S :
    FunCall("int2string", [Int(i)]) -> String(i)
 
  EvalIf :
    IfElse(False(), st1*, st2*) -> Block(st2*)

  EvalIf :
    IfElse(True(), st1*, st2*) -> Block(st1*)

  EvalWhile :
     While(False(), st*) -> Block([])

3.2. Desugaring Rules

Another common kind of rules are desugaring rules, which define a language construct in terms of other language constructs. Module til-desugar defines rules ForToWhile and IfThenToIfElse. The ForToWhile rule rewrites For loops to a While loop, which requires the introduction of a new variable to hold the value of the upperbound. The IfThenToIfElse transforms if-then statements into if-then-else statements.

Figure 3.2. file: til/sim/til-desugar.str

module til-desugar
imports TIL 
rules

  ForToWhile :
    For(x, e1, e2, st*) ->
      Block([
        DeclarationTyped(y, TypeName("int")), 
        Assign(x, e1), 
        Assign(y, e2), 
        While(Leq(Var(x), Var(y)), 
          <conc>(st*, [Assign(x, Add(Var(x), Int("1")))])
        )
      ])
    where new => y

  IfThenToIfElse :
    IfThen(e, st*) -> IfElse(e, st*, [])

  DefaultDeclaration :
    Declaration(x) -> DeclarationTyped(x, TypeName("int"))

  WriteInt :
    ProcCall("writeint", [e]) -> 
    ProcCall("write", [FunCall("int2string", [e])])
    
  ReadInt :
    FunCall("readint", []) -> 
    FunCall("string2int", [FunCall("read", [])])
 
  BinOpToFunCall :
    op#([e1,e2]){t*} -> FunCall(op, [e1,e2]){t*}
    where <is-bin-op> op
    
  FunCallToBinOp :
    FunCall(op, [e1,e2]){t*} -> op#([e1,e2]){t*}
    where <is-bin-op> op
     
  is-bin-op =
    "Add" <+ "Mul" <+ "Subt" <+ "Div" <+ "Mod"
    <+ "Geq" <+ "Leq" <+ "Gt" <+ "Lt" <+ "Equ" <+ "Neq"

3.3. Simplying by Term Rewriting

Module til-simplify is a basic Stratego program. It imports the til-eval and til-desugar modules, and the Stratego standard library (liblib), which defines standard rewriting strategies and additional utilities for I/O and such.

The io-til-simplify strategy of til-simplify represents the entry point for the program when it is invoked. It uses the io-wrap strategy to parse command-line arguments, read the input term, and write the output term.

The til-simplify strategy defines the actual transformation, which is a complete normalization of the input term with respect to the rewrite rules introduced above. The normalization strategy chosen here is innermost, which exhaustively applies its argument strategy starting with the innermost nodes of the tree.

Figure 3.3. file: til/sim/til-simplify.str

module til-simplify
imports liblib til-eval til-desugar 
strategies

  io-til-simplify =
    io-wrap(til-simplify)

  til-simplify =
    innermost(
      ForToWhile <+ IfThenToIfElse
      <+ AddZero <+ MulOne 
      <+ EvalAdd <+ EvalMul <+ EvalSub <+ EvalDiv
      <+ EvalLeq <+ EvalGeq <+ EvalEqu <+ EvalNeq
      <+ DefaultDeclaration
      <+ ReadInt <+ WriteInt
    )

3.4. Compiling the Simplifier

Stratego programs are compiled to executable programs by the Stratego compiler strc. The -I option is used to indicate that some modules imported by this program (TIL.str) resides in the ../sig directory. The -la option is used to link the separately compiled Stratego library.

Figure 3.4. file: til/sim/maak

#! /bin/sh -e

# compile til-simplify
strc -i til-simplify.str -I ../sig -la stratego-lib -m io-til-simplify

3.5. Applying the Simplifier

A compiled Stratego program is an ordinary executable. When the io-wrap strategy was used the program has a -i option for indicating the input file, and a -o option to indicate the output file. Thus, the program reads the ATerm in the input file, transforms it, and writes the resulting ATerm back to the output file.

The following test script shows how the til/xmpl/test1.til file is simplified, and the result pretty-printed.

Figure 3.5. file: til/xmpl/simplify-test

# simplify program
../sim/til-simplify -i test1.atil -o test1.sim.atil

# check result
format-check --rtg ../sig/TIL.rtg -i test1.sim.atil

# parentheses
../pp/til-parenthesize -i test1.sim.atil -o test1.sim.par.atil

# pretty-print
ast2text -p ../pp/TIL-pretty.pp -i test1.sim.par.atil -o test1.sim.txt

Table 3.1. files: til/xmpl/test1.til, til/xmpl/test1.sim.txt

beforeafter
// TIL program computing the factorial

var n;
n := readint();
var x;
var fact;
fact := 1;
for x := 1 to n do
  fact := x * fact;
end
write("factorial of ");
writeint(n);
write(" is ");
writeint(fact);
write("\n");
var n : int;
n := string2int(read());
var x : int;
var fact : int;
fact := 1;
begin
  var a_0 : int;
  x := 1;
  a_0 := n;
  while x <= a_0 do
    fact := x * fact;
    x := x + 1;
  end
end
write("factorial of ");
write(int2string(n));
write(" is ");
write(int2string(fact));
write("\n");

Chapter 4. Bound Variable Renaming (*)

Work in Progress

This chapter is work in progress. Not all parts have been finished yet. The latest revision of this manual may contain more material. Refer to the online version.

renaming of bound variables

4.1. Renaming Bound Variables

Figure 4.1. file: til/renaming/til-rename-vars.str

module til-rename-vars
imports TIL liblib
strategies

  io-til-rename-vars =
    io-wrap(til-rename-vars)

  til-rename-vars =
    Var(RenameVar)
    <+ Assign(RenameVar, til-rename-vars)
//    <+ Read(RenameVar)
    <+ For(RenameVar, til-rename-vars, til-rename-vars, til-rename-vars)
    <+ RenameDeclaration
    <+ Block({| RenameVar : map(til-rename-vars) |})
    <+ all(til-rename-vars)

  RenameDeclaration :
    Declaration(x) -> Declaration(y)
    where <newname> x => y
        ; rules( RenameVar : x -> y )

  RenameDeclaration :
    DeclarationTyped(x, t) -> DeclarationTyped(y, t)
    where <newname> x => y
        ; rules( RenameVar : x -> y )
        

4.2. Example

Figure 4.2. file: til/xmpl/rename-test

sglri -p ../syn/TIL.tbl -i test1.til |\
../renaming/til-rename-vars |\
ast2text -p ../pp/TIL-pretty.pp -o test1.rn.txt

Table 4.1. files: til/xmpl/test1.til, til/xmpl/test1.rn.txt

beforeafter
// TIL program computing the factorial

var n;
n := readint();
var x;
var fact;
fact := 1;
for x := 1 to n do
  fact := x * fact;
end
write("factorial of ");
writeint(n);
write(" is ");
writeint(fact);
write("\n");
var n0;
n0 := readint();
var x0;
var fact0;
fact0 := 1;
for x0 := 1 to n0 do
  fact0 := x0 * fact0;
end
write("factorial of ");
writeint(n0);
write(" is ");
writeint(fact0);
write("\n");

Chapter 5. Typechecking (*)

Work in Progress

This chapter is work in progress. Not all parts have been finished yet. The latest revision of this manual may contain more material. Refer to the online version.

propagation of variable types and type annotation of expressions and statements

5.1. Typechecking

Figure 5.1. file: til/tc/til-typecheck.str

module til-typecheck
imports liblib til-typecheck-stats
strategies

  io-til-typecheck =
    io-wrap(typecheck-program)
    
  typecheck-program =
    Program(typecheck-stats)

Figure 5.2. file: til/tc/til-typecheck-exp.str

module til-typecheck-exp
imports TIL
strategies

  typecheck-exp(typecheck-var) = 
    bottomup(try(
      typecheck-var <+ TypecheckAdd <+ TypecheckMul <+ TypecheckSub <+ TypecheckDiv <+ TypecheckMod
      <+ TypecheckLeq <+ TypecheckGeq <+ TypecheckLt <+ TypecheckGt <+ TypecheckEqu <+ TypecheckNeq
      <+ TypecheckOr <+ TypecheckAnd
      <+ TypecheckInt <+ TypecheckString <+ TypecheckBool
    ))

rules

  typeof :
    e{t*} -> t
    where <fetch-elem(is-type)> t* => t
    
  is-type = 
    ?TypeName(_)
    
  TypecheckInt :
    Int(i) -> Int(i){TypeName("int")}

  TypecheckString :
    String(x) -> String(x){TypeName("string")}

  TypecheckBool :
    True() -> True(){TypeName("bool")}
    
  TypecheckBool :
    False() -> False(){TypeName("bool")}
    
  TypecheckAdd :
    Add(e1, e2) -> Add(e1, e2){TypeName("string")}
    where <typeof> e1 => TypeName("string")
        ; <typeof> e2 => TypeName("string")

  TypecheckAdd :
    Add(e1, e2) -> Add(e1, e2){TypeName("int")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")

  TypecheckMul :
    Mul(e1, e2) -> Mul(e1, e2){TypeName("int")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")

  TypecheckSub :
    Sub(e1, e2) -> Sub(e1, e2){TypeName("int")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")

  TypecheckDiv :
    Div(e1, e2) -> Div(e1, e2){TypeName("int")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")
 
  TypecheckMod :
    Mod(e1, e2) -> Mod(e1, e2){TypeName("int")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")

  TypecheckLt :
    Lt(e1, e2) -> Lt(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")

  TypecheckGt :
    Gt(e1, e2) -> Gt(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")
   
  TypecheckLeq :
    Leq(e1, e2) -> Leq(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")
        
  TypecheckGeq :
    Geq(e1, e2) -> Geq(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")
 
  TypecheckEqu :
    Equ(e1, e2) -> Equ(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")
        
  TypecheckNeq :
    Neq(e1, e2) -> Neq(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")
           
  TypecheckAnd :
    And(e1, e2) -> And(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("bool")
        ; <typeof> e2 => TypeName("bool")
           
  TypecheckOr :
    Or(e1, e2) -> Or(e1, e2){TypeName("bool")}
    where <typeof> e1 => TypeName("bool")
        ; <typeof> e2 => TypeName("bool")
           

    

Figure 5.3. file: til/tc/til-typecheck-stats.str

module til-typecheck-stats
imports til-typecheck-var
strategies

  typecheck-block = 
    Block(typecheck-stats)

  typecheck-stats = 
    {| TypeOf : map(typecheck-stat) |}

  typecheck-stat = 
    typecheck-block
    <+ typecheck-declaration
    <+ Assign(id, typecheck-exp)
       ; try(TypecheckAssign)
    <+ IfElse(typecheck-exp, typecheck-stats, typecheck-stats)
       ; TypecheckIf
    <+ IfThen(typecheck-exp, typecheck-stats)
       ; TypecheckIf
    <+ While(typecheck-exp, typecheck-stats)
       ; TypecheckWhile
    <+ ProcCall(id, map(typecheck-exp))
       ; typecheck-proccall
    <+ For(id, typecheck-exp, typecheck-exp, typecheck-stats)
       ; TypecheckFor
    <+ debug(!"unknown statement: ")
       ; <exit> 1

  TypecheckIf :
    IfElse(e, st1*, st2*) -> IfElse(e, st1*, st2*){TypeName("void")}
    where <typeof> e => TypeName("bool")
    
  TypecheckIf :
    IfThen(e, st*) -> IfThen(e, st*){TypeName("void")}
    where <typeof> e => TypeName("bool")

  TypecheckWhile : 
    While(e, st*) -> While(e, st*){TypeName("void")}
    where <typeof> e => TypeName("bool")

  TypecheckFor : 
    For(x, e1, e2, st*) -> For(x, e1, e2, st*){TypeName("void")}
    where <TypeOf> x => TypeName("int")
        ; <typeof> e1 => TypeName("int")
        ; <typeof> e2 => TypeName("int")
    

Figure 5.4. file: til/tc/til-typecheck-var.str

module til-typecheck-var
imports til-typecheck-exp
strategies

  typecheck-declaration = 
    ?Declaration(x)
    ; rules( TypeOf+x : x -> TypeName("int") )

  typecheck-declaration = 
    ?DeclarationTyped(x, t)
    ; rules( TypeOf+x : x -> t )
 
  TypecheckVar :
    Var(x) -> Var(x){t}
    where <TypeOf> x => t

  TypecheckAssign :
    Assign(x, e) -> Assign(x, e){TypeName("void")}
    where <typeof> e => t
    	; <TypeOf> x => t
    
strategies // expressions with variables and calls

  typecheck-exp = 
    typecheck-exp(TypecheckVar <+ typecheck-funcall)
    
  typecheck-funcall = 
    TypecheckRead <+ TypecheckS2I <+ TypecheckI2S <+ TypecheckB2S
    
  typecheck-proccall =
    TypecheckWrite
	
strategies // built-in functions
 
  TypecheckS2I :
    FunCall("string2int", [e]) -> FunCall("string2int", [e]){TypeName("int")}
    where <typeof> e => TypeName("string")
    
  TypecheckI2S :
    FunCall("int2string", [e]) -> FunCall("int2string", [e]){TypeName("string")}
    where <typeof> e => TypeName("int")
    
  TypecheckB2S :
    FunCall("bool2string", [e]) -> FunCall("bool2string", [e]){TypeName("string")}
    where <typeof> e => TypeName("bool")
    
  TypecheckRead :
    FunCall("read", []) -> FunCall("read", []){TypeName("string")}
    
  TypecheckRead :
    FunCall("readint", []) -> FunCall("readint", []){TypeName("int")}

strategies // built-in procedures

  TypecheckWrite :
    ProcCall("write", [e]) -> ProcCall("write", [e]){TypeName("void")}
    where <typeof> e => TypeName("string")

  TypecheckWrite :
    ProcCall("writeint", [e]) -> ProcCall("writeint", [e]){TypeName("void")}
    where <typeof> e => TypeName("int")



 
 

5.2. Example

Figure 5.5. file: til/xmpl/typecheck-test1

# typecheck test1.til after parsing 
../tc/til-typecheck -i test1.atil | pp-aterm > test1.tc

Table 5.1. files: til/xmpl/test1.til, til/xmpl/test1.tc

beforeafter
// TIL program computing the factorial

var n;
n := readint();
var x;
var fact;
fact := 1;
for x := 1 to n do
  fact := x * fact;
end
write("factorial of ");
writeint(n);
write(" is ");
writeint(fact);
write("\n");
Program(
  [ Declaration("n")
  , Assign("n", FunCall("readint", []){TypeName("int")}){TypeName("void")}
  , Declaration("x")
  , Declaration("fact")
  , Assign("fact", Int("1"){TypeName("int")}){TypeName("void")}
  , For(
      "x"
    , Int("1"){TypeName("int")}
    , Var("n"){TypeName("int")}
    , [Assign("fact", Mul(Var("x"){TypeName("int")}, Var("fact"){TypeName("int")}){TypeName("int")}){TypeName("void")}]
    ){TypeName("void")}
  , ProcCall("write", [String("\"factorial of \""){TypeName("string")}]){TypeName("void")}
  , ProcCall("writeint", [Var("n"){TypeName("int")}]){TypeName("void")}
  , ProcCall("write", [String("\" is \""){TypeName("string")}]){TypeName("void")}
  , ProcCall("writeint", [Var("fact"){TypeName("int")}]){TypeName("void")}
  , ProcCall("write", [String("\"\\n\""){TypeName("string")}]){TypeName("void")}
  ]
)

Chapter 6. Interpretation

Interpreting programs does not seem a typical application of program transformation. However, in partial evaluation a program is evaluated as far as possible. Also in simpler transformations, evaluating a part of a program is a common operation. Furthermore, in order to execute programs in our TIL language, it is useful have an interpreter.

This chapter shows how to construct an interpreter for typical elements of an imperative language, such as expressions, variable access constructs, and control-flow statements. The specification uses advanced features of Stratego such as traversal strategies, pattern match operations, match-project, and dynamic rewrite rules. So don't be surprised if you don't get it all on a first reading.

The interpreter developed in this chapter requires the parsing and simplification infrastructure from the previous chapters. That is, the interpreter operates on the abstract syntax tree of a program after simplification.

6.1. Evaluating Expressions

Expressions can be evaluated using a simple bottom-up traversal of the AST. The bottomup traversal strategy does just that; it applies its argument strategy first to the leaves of the tree, and then to each level above. The try strategy makes its argument strategy always succeeding. Thus, the eval-exp strategy performs a bottomup traversal of the AST of an expression, applying the Eval rules from module sim/til-eval. The eval-exp strategy is parameterized with a strategy for evaluating variables; their values depend on prior assignments in the program.

Figure 6.1. file: til/run/til-eval-exp.str

module til-eval-exp
imports til-eval
strategies

  eval-exp(eval-var) = 
    bottomup(try(
      eval-var <+ EvalAdd <+ EvalMul <+ EvalSub <+ EvalDiv <+ EvalMod
      <+ EvalLeq <+ EvalGeq <+ EvalLt <+ EvalGt <+ EvalEqu <+ EvalNeq
      <+ EvalOr <+ EvalAnd <+ EvalS2I <+ EvalI2S
    ))



    

6.2. Evaluating Variable Accesses

The essence of an imperative language is the manipulation of values in the store, held by variables. In TIL variables are introduced by the Declaration construct. The values of variables is set, or changed by the Assign assignment statement, and the Read input statement. The Write statement prints the value of an expression. The interpreter uses the dynamic rewrite rule EvalVar to store the mappings from variables to their values.

When encountering a variable declaration, the current scope is labeled with the name of that variable, and its mapping is undefined, reflecting the fact that the variable doesn't have a value after being declared. Note that the scope of a variable in TIL is the rest of the current block. When encountering an assignment statement the EvalVar rule for the variable being assigned is updated. Thus, after an assignment to a variable x, EvalVar rewrites that variable to its value. Similarly, the Read input statement reads the next line from the stdin stream, decides whether it represents an integer or a string, and defines the EvalVar rule for the variable. Finally, the eval-exp strategy is now defined in terms of the parameterized eval-exp strategy from module run/til-eval-exp using the EvalVar rule as strategy for evaluating variables. In addition, the VarUndefined strategy is provided to catch variables that are used before being assigned to.

Figure 6.2. file: til/run/til-eval-var.str

module til-eval-var
imports til-eval-exp
strategies

  eval-declaration = 
    (?Declaration(x) <+ ?DeclarationTyped(x, t))
    ; rules( EvalVar+x :- Var(x) )

  eval-assign = 
    Assign(?x, eval-exp => val)
    ; rules(EvalVar.x : Var(x) -> val)

  EvalRead :
    FunCall("read", []) -> String(x)
    where stdin-stream; read-text-line => x

  eval-write = 
    ?ProcCall("write", [<eval-exp>])
    ; ?String(<try(un-double-quote); try(unescape)>)
    ; <fprint>(<stdout-stream>, [<id>])

  VarUndefined =
    ?Var(<id>)
    ; fatal-err(|<concat-strings>["variable ", <id>, " used before being defined"])

  eval-exp = 
    eval-exp(EvalVar <+ VarUndefined <+ EvalRead)

6.3. Evaluating Statements

What remains is the interpretation of control-flow statements. A block statements simply entails the execution of each statement in the block in order. Any variables declared within the block are local, and shadow variables with the same name in outer blocks. For this purpose a dynamic rule scope {| EvalVar : ... |} is used to restrict the scope of EvalVar rules to the block. The statements in a block are evaluated by mapping the eval-stat strategy over the list of statements. For the execution of the if-then-else construct, first the condition is evaluated. The EvalIf rule then evaluates the construct, reducing it to one of its branches. The resulting block statement is then evaluated by eval-stat. The while statement is evaluated by transforming the loop to an if-then-else statement, with a Goto at the end of the body. The dynamic rule EvalGoto maps the goto statement for the new label to the if-then-else statement.

Figure 6.3. file: til/run/til-eval-stats.str

module til-eval-stats
imports til-eval-var
signature
  constructors
    Goto : String -> Stat
strategies

  eval-block = 
    ?Block(<eval-stats>)

  eval-stats = 
    {| EvalVar : map(eval-stat) |}

  eval-stat = //debug(!"eval-stat: "); (
    eval-assign
    <+ eval-write
    <+ eval-declaration
    <+ eval-block
    <+ eval-if
    <+ eval-while
    <+ EvalGoto
  //)

  eval-if = 
    IfElse(eval-exp, id, id)
    ; EvalIf
    ; eval-stat

  eval-while = 
    ?While(e, st*)
    ; where(new => label)
    ; where(<conc>(st*, [Goto(label)]) => st2*)
    ; rules( EvalGoto : Goto(label) -> <eval-stat>IfElse(e, st2*, []) )
    ; <eval-stat> Goto(label)

6.4. The Complete Interpreter

To complete the interpreter we define an interpretation strategy for the Program constructor, and a main strategy that takes care of I/O. The program is compiled in the usual way, taking into account the include paths for the ../sig and ../sim directories that contain the TIL signature and evaluation rules, respectively.

Figure 6.4. file: til/run/til-run.str

module til-run
imports libstrategolib til-eval-stats
strategies

  io-til-run = 
    io-wrap(eval-program)

  eval-program = 
    ?Program(<eval-stats>)
    ; <exit> 0

Figure 6.5. file: til/run/maak

#! /bin/sh -e

# compile til-simplify
strc -i til-run.str -I ../sig -I ../sim -la stratego-lib -m io-til-run

6.5. Running TIL Programs

Now it is time to try out the interpreter at our test1.til program that computes the factorial of its input. Note that the interpreter operates on a parsed and simplified version of the program; not directly on the text file.

Figure 6.6. file: til/xmpl/run-test1

# run test1.til after parsing and simplification
echo "10" | ../run/til-run -i test1.sim.atil > test1.run

Figure 6.7. file: til/xmpl/test1.run

factorial of 10 is 3628800

Chapter 7. Data-flow Transformation (*)

Work in Progress

This chapter is work in progress. Not all parts have been finished yet. The latest revision of this manual may contain more material. Refer to the online version.

This chapter shows examples of data-flow transformations

7.1. Preliminaries

Figure 7.1. file: til/opt/til-opt-lib.str

module til-opt-lib
imports liblib TIL til-eval 
strategies

  contains(|x) =  // should be in stratego-lib
    oncetd(?x)

  elem-of(|xs) = // should be in stratego-lib
    ?x; where(<fetch(?x)> xs)

  get-var-names =
    collect(?Var(<id>))

  get-var-dependencies =
    collect(?Var(<!(<id>,<id>)>))

  EvalExp = 
    EvalAdd <+ EvalMul <+ EvalSub <+ EvalDiv <+ EvalMod
    <+ EvalLt <+ EvalGt <+ EvalEqu <+ EvalNeq

  is-var = 
    ?Var(_)

  is-value = 
    ?Int(_) <+ ?String(_)

  is-pure-exp = 
    ?Var(_) <+ ?Int(_) <+ ?String(_) 
    <+ is-bin-op#([is-pure-exp, is-pure-exp])
    
  is-bin-op = 
    ?"Or" <+ ?"And" <+ ?"Neq" <+ ?"Equ" <+ ?"Gt" <+ ?"Lt" <+ ?"Sub"
    <+ ?"Add" <+ ?"Mod" <+ ?"Div" <+ ?"Mul"

7.2. Constant Propagation

Figure 7.2. file: til/xmpl/propconst-test2

sglri -p ../syn/TIL.tbl -i propconst-test2.til |\
../sim/til-simplify |\
../opt/til-propconst |\
ast2text -p ../pp/TIL-pretty.pp -o propconst-test2.txt

Table 7.1. files: til/xmpl/propconst-test2.til, til/xmpl/propconst-test2.txt

beforeafter
var x; 
var y;
var z; 
var a; 
var b;
z := readint();
x := 1;        // constant value
y := 2;        // not constant
x := 3;        // override
a := x + 4;    // compute constant
y := x + z;    // not constant
if y then
  z := 8;
  x := z - 5;  // constant
else
  x := a - 4;  // constant
  z := a + z;  // z is not constant
end
b := a + z;    // a still constant, z not
z := a + x;
writeint(b + z);
var x : int;
var y : int;
var z : int;
var a : int;
var b : int;
z := string2int(read());
x := 1;
y := 2;
x := 3;
a := 7;
y := 3 + z;
if y then
  z := 8;
  x := 3;
else
  x := 3;
  z := 7 + z;
end
b := 7 + z;
z := 10;
write(int2string(b + 10));

Figure 7.3. file: til/opt/til-propconst.str

module til-propconst
imports til-opt-lib
strategies

  io-til-propconst = 
    io-wrap(propconst)

  propconst = 
    PropConst
    <+ propconst-declaration
    <+ propconst-assign 
    <+ propconst-block
    <+ propconst-if
    <+ propconst-while
    <+ all(propconst); try(EvalExp)

  propconst-block =
    Block({| PropConst : map(propconst) |})

  propconst-declaration = 
    (?Declaration(x) <+ ?DeclarationTyped(x, t))
    ; rules( PropConst+x :- Var(x) )

  propconst-assign = 
    Assign(?x, propconst => e)
    ; if <is-value> e then
        rules( PropConst.x : Var(x) -> e )
      else
        rules( PropConst.x :- Var(x) )
      end

  propconst-if =
    IfElse(propconst, id, id)
    ; (EvalIf; propconst
       <+ IfElse(id, propconst, id) /PropConst\ IfElse(id,id,propconst))

  propconst-while =
    ?While(_, _)
    ; (/PropConst\* While(propconst, propconst))

7.3. Copy Propagation

Figure 7.4. file: til/xmpl/copyprop-test2

sglri -p ../syn/TIL.tbl -i copyprop-test2.til |\
../sim/til-simplify |\
../opt/til-copyprop |\
ast2text -p ../pp/TIL-pretty.pp -o copyprop-test2.txt

Table 7.2. files: til/xmpl/copyprop-test2.til, til/xmpl/copyprop-test2.txt

beforeafter
var x : int;
var y : int;
x := string2int(read());
y := x;
y := y + 1;
x := y;
write(int2string(x));
var x : int;
var y : int;
x := string2int(read());
y := x;
y := x + 1;
x := y;
write(int2string(y));

Figure 7.5. file: til/opt/til-copyprop.str

module til-copyprop
imports til-opt-lib
strategies

  io-til-copyprop = 
    io-wrap(copyprop)

  copyprop = 
    CopyProp
    <+ copyprop-declaration
    <+ copyprop-assign 
    <+ copyprop-block
    <+ copyprop-if
    <+ copyprop-while
    <+ all(copyprop)

  copyprop-block =
    Block({| CopyProp : map(copyprop) |})

  copyprop-declaration = 
    (?Declaration(x) <+ ?DeclarationTyped(x, t))
    ; new-CopyProp(|x, x)

  copyprop-assign = 
    Assign(?x, copyprop => e)
    ; undefine-CopyProp(|x)
    ; where( innermost-scope-CopyProp => z )
    ; if <?Var(y)> e then
        rules( CopyProp.z : Var(x) -> Var(y) depends on [(x,x),(y,y)] )
      end

  copyprop-if =
    IfElse(copyprop, id, id)
    ; (IfElse(id, copyprop, id) /CopyProp\ IfElse(id,id,copyprop))

  copyprop-while =
    ?While(_, _)
    ; (/CopyProp\* While(copyprop, copyprop))

  innermost-scope-CopyProp = 
    get-var-names => vars
    ; innermost-scope-CopyProp(elem-of(|vars))

7.4. Reverse Copy Propagation

Figure 7.6. file: til/opt/til-copyprop-rev.str

module til-copyprop-rev
imports til-opt-lib
strategies

  io-til-copyprop-rev = 
    io-wrap(copyprop-rev)

  copyprop-rev = 
    CopyPropRev
    <+ copyprop-rev-declaration
    <+ copyprop-rev-assign 
    <+ copyprop-rev-block
    <+ copyprop-rev-if
    <+ copyprop-rev-while
    <+ all(copyprop-rev)

  copyprop-rev-block =
    Block({| CopyPropRev : map(copyprop-rev) |})

  copyprop-rev-declaration = 
    (?Declaration(x) <+ ?DeclarationTyped(x, t))
    ; new-CopyPropRev(|x, x)

  copyprop-rev-assign = 
    Assign(?x, copyprop-rev => e)
    ; undefine-CopyPropRev(|x)
    ; where( innermost-scope-CopyPropRev => z )
    ; if <?Var(y)> e then
        rules( CopyPropRev.z : Var(y) -> Var(x) depends on [(x,x),(y,y)] )
      end

  copyprop-rev-if =
    IfElse(copyprop-rev, id, id)
    ; (IfElse(id, copyprop-rev, id) /CopyPropRev\ IfElse(id,id,copyprop-rev))

  copyprop-rev-while =
    ?While(_, _)
    ; (/CopyPropRev\* While(copyprop-rev, copyprop-rev))

  innermost-scope-CopyPropRev = 
    get-var-names => vars
    ; innermost-scope-CopyPropRev(elem-of(|vars))

7.5. Common-subexpression Elimination

Figure 7.7. file: til/xmpl/cse-test2

sglri -p ../syn/TIL.tbl -i cse-test2.til |\
../sim/til-simplify |\
../opt/til-cse |\
ast2text -p ../pp/TIL-pretty.pp -o cse-test2.txt

Table 7.3. files: til/xmpl/cse-test2.til, til/xmpl/cse-test2.txt

beforeafter
var a;
var b;
var x;
a := readint();
b := readint();
x := a + b;
writeint(a + b);
a := 23;
x := a + b;
writeint(a + b);
var a : int;
var b : int;
var x : int;
a := string2int(read());
b := string2int(read());
x := a + b;
write(int2string(x));
a := 23;
x := a + b;
write(int2string(x));

Figure 7.8. file: til/opt/til-cse.str

module til-cse
imports til-opt-lib
strategies

  io-til-cse = 
    io-wrap(cse)

  cse = 
    CSE
    <+ cse-declaration
    <+ cse-assign 
    <+ cse-if
    <+ cse-block
    <+ cse-while
    <+ all(cse)

  cse-block =
    Block({| CSE : map(cse) |})

  cse-declaration = 
    (?Declaration(x) <+ ?DeclarationTyped(x, t))
    ; new-CSE(|x, x)

  cse-assign = 
    Assign(?x, cse => e)
    ; undefine-CSE(|x)
    ; if <not(contains(|Var(x)))> e then
        where( innermost-scope-CSE => z )
        ; where( get-var-dependencies => deps )
        ; rules( CSE.z : e -> Var(x) depends on deps )
      end

  cse-if =
    IfElse(cse, id, id)
    ; (IfElse(id, cse, id) /CSE\ IfElse(id,id,cse))

  cse-while =
    ?While(_, _)
    ; (/CSE\* While(cse, cse))

  innermost-scope-CSE = 
    get-var-names => vars
    ; innermost-scope-CSE(elem-of(|vars))

7.6. Forward Substitution

Figure 7.9. file: til/opt/til-forward-subst.str

module til-forward-subst
imports til-opt-lib
strategies

  io-til-forward-subst = 
    io-wrap(forward-subst)

  forward-subst = 
    ForwardSubst
    <+ forward-subst-declaration
    <+ forward-subst-assign 
    <+ forward-subst-if
    <+ forward-subst-block
    <+ forward-subst-while
    <+ all(forward-subst)

  forward-subst-block =
    Block({| ForwardSubst : map(forward-subst) |})

  forward-subst-declaration = 
    (?Declaration(x) <+ ?DeclarationTyped(x, t))
    ; new-ForwardSubst(|x, x)

  forward-subst-assign = 
    Assign(?x, forward-subst => e)
    ; undefine-ForwardSubst(|x)
    ; if <not(is-var); is-pure-exp; not(contains(|Var(x)))> e then
        where( innermost-scope-ForwardSubst => z )
        ; where( get-var-dependencies => deps )
        ; rules( ForwardSubst.z : Var(x) -> e depends on deps )
      end

  forward-subst-if =
    IfElse(forward-subst, id, id)
    ; (IfElse(id, forward-subst, id) /ForwardSubst\ IfElse(id,id,forward-subst))

  forward-subst-while =
    ?While(_, _)
    ; (/ForwardSubst\* While(forward-subst, forward-subst))

  innermost-scope-ForwardSubst = 
    get-var-names => vars
    ; innermost-scope-ForwardSubst(elem-of(|vars))

7.7. Dead Code Elimination

Figure 7.10. file: til/xmpl/dce-test2

sglri -p ../syn/TIL.tbl -i dce-test2.til |\
../sim/til-simplify |\
../opt/til-dce |\
ast2text -p ../pp/TIL-pretty.pp -o dce-test2.txt

Table 7.4. files: til/xmpl/dce-test2.til, til/xmpl/dce-test2.txt

beforeafter
var x;
var y;
var z;
var a;
var b;
z := readint();
x := 1;
y := 2;
x := 3;
a := 7;
y := 3 + z;
if y then
  z := 8;
  x := 3;
else
  x := 3;
  z := 7 + z;
end
b := 7 + z;
z := 10;
writeint(b + 10);
var y : int;
var z : int;
var b : int;
z := string2int(read());
y := 3 + z;
if y then
  z := 8;
else
  z := 7 + z;
end
b := 7 + z;
write(int2string(b + 10));

Figure 7.11. file: til/opt/til-dce.str

module til-dce
imports TIL til-eval liblib
rules

  ElimDecl : 
    [Declaration(x) | st*] -> st*
    where <not(VarUsed)> Var(x)

  ElimDecl : 
    [DeclarationTyped(x, t) | st*] -> st*
    where <not(VarUsed)> Var(x)

  ElimAssign :
    Assign(x, e) -> Block([])
    where <not(VarNeeded)> Var(x)

  ElimIf :
    IfElse(e, [], []) -> Block([])

strategies

  io-til-dce = 
    io-wrap(dce-program)

  dce-stat = 
    ElimAssign
    <+ dce-assign 
    <+ dce-proccall
    <+ dce-if; try(ElimIf)
    <+ dce-block
    <+ dce-while

  dce-program = 
    Program(dce-stats)

  dce-block =
    Block(dce-stats)

  dce-stats = 
    dce-stats-decl
    <+ dce-stats-other 
    <+ []

  dce-stats-decl = 
    (?[Declaration(x) | _] <+ ?[DeclarationTyped(x, t) | _])
    ; {| VarNeeded, VarUsed 
       : rules(
           VarNeeded+x :- Var(x)
           VarUsed+x   :- Var(x)
         )
       ; [id | dce-stats]
       ; try(ElimDecl)
       |}
       
  dce-stats-other =
    [not(?Declaration(_) <+ ?DeclarationTyped(_, _)) | dce-stats]
    ; [dce-stat | id]
    ; try(?[Block([]) | <id>])

  dce-assign = 
    ?Assign(x, _)
    ; rules( VarNeeded.x :- Var(x) )
    ; Assign(id, declare-var-needed)

  dce-proccall =
    ProcCall(id, map(declare-var-needed))

  declare-var-needed = 
    alltd({x :
      ?Var(x)
      ; rules(
          VarNeeded.x : Var(x)
          VarUsed.x   : Var(x)
         )
    })

  dce-if =
    ?IfElse(_,_,_)
    ; (IfElse(id,dce-stats,id) /VarNeeded,VarUsed\ IfElse(id,id,dce-stats))
    ; IfElse(declare-var-needed, id, id)

  dce-while =
    ?While(_, _)
    ; (\VarNeeded,VarUsed/* While(declare-var-needed, dce-stats))

7.8. Compiling the Transformations

Figure 7.12. file: til/opt/maak

#! /bin/sh -e

INCL="-I ../sig -I ../sim"

# compile forward-subst
strc ${INCL} -i til-forward-subst.str -la stratego-lib -m io-til-forward-subst -O 2

# compile dce
strc ${INCL} -i til-dce.str -la stratego-lib -m io-til-dce -O 2

# compile cse
strc ${INCL} -i til-cse.str -la stratego-lib -m io-til-cse

# compile copyprop
strc -i til-copyprop.str ${INCL} -la stratego-lib -m io-til-copyprop

# compile copyprop-rev
strc -i til-copyprop-rev.str ${INCL} -la stratego-lib -m io-til-copyprop-rev

# compile propconst
strc -i til-propconst.str ${INCL} -la stratego-lib -m io-til-propconst

Chapter 8. Typestate Checking

Chapter 9. Expression Blocks (*)

Work in Progress

This chapter is work in progress. Not all parts have been finished yet. The latest revision of this manual may contain more material. Refer to the online version.

Sometimes it is useful to extend a language in order to ease transformations.

9.1. Syntax of Expression Blocks

Figure 9.1. file: til/til-eblock/TIL-eblocks.sdf

module TIL-eblocks
imports TIL
exports
  context-free syntax
    "begin" Stat* "return" Exp ";" Stat* "end" -> Exp {cons("EBlock")}

9.2. Desugaring Expression Blocks

Figure 9.2. file: til/til-eblock/til-eblock-desugar.str

module til-eblock-desugar
imports liblib TIL-eblocks
strategies

  io-til-eblock-desugar =
    io-wrap(til-eblock-desugar)

  til-eblock-desugar =
    bottomup(try(FunCallToEBlock))
    ; innermost(
        EBlockEBlock
	<+ NoStatements
	<+ MovePostStatementsInFront
        <+ HoistEBlockFromFunCall 
	<+ HoistEBlockFromBinOp 
	<+ HoistEBlockFromAssign 
	<+ HoistEBlockFromProcCall 
//	<+ HoistEBlockFromWrite 
	<+ HoistEBlockFromIf 
	<+ HoistEBlockFromWhile 
	<+ HoistEBlockFromFor
      )
    ; bottomup(try(flatten-block))

rules

  FunCallToEBlock :
    FunCall(f, e*) -> 
    EBlock([Declaration(x), Assign(x, FunCall(f, e*))], Var(x), [])
    where new => x

  NoStatements :
    EBlock([], e, []) -> e

  MovePostStatementsInFront :
    EBlock(st1*, e, st2*@[_|_]) -> 
    EBlock([Declaration(x), st1*, Assign(x, e), st2*], Var(x), [])
    where new => x

  EBlockEBlock :
    EBlock(st1*, EBlock(st2*, e, st3*), st4*) ->
    EBlock([st1*, st2*], e, [st3*, st4*])

  HoistEBlockFromFunCall :
    FunCall(f, e1*) -> EBlock(st1*, FunCall(f, e2*), [])
    where <collect-eblocks> e1* => (st1*, e2*)

  HoistEBlockFromBinOp :
    op#([e1, e2]) -> EBlock(st1*, op#([e1', e2']), [])
    where <is-bin-op> op
	; <collect-eblocks> [e1, e2] => (st1*, [e1', e2'])

  is-bin-op =
    ?"Or" <+ ?"And" <+ ?"Neq" <+ ?"Equ" <+ ?"Gt" <+ ?"Lt" <+ ?"Sub"
    <+ ?"Add" <+ ?"Mod" <+ ?"Div" <+ ?"Mul"

  HoistEBlockFromAssign :
    Assign(x, EBlock(st1*, e, st2*)) -> Block([st1*, st2*, Assign(x, e)])

  HoistEBlockFromProcCall :
    ProcCall(f, e1*) -> Block([st*, ProcCall(f, e2*)])
    where <collect-eblocks> e1* => (st*, e2*)

//  HoistEBlockFromWrite :
//    Write(EBlock(st1*, e, st2*)) -> Block([st1*, Write(e), st2*])

  HoistEBlockFromIf :
    IfElse(EBlock(st1*, e, st2*), st3*, st4*) -> 
    Block([st1*, IfElse(e, [st2*,st3*], [st2*,st4*])])

  HoistEBlockFromIf :
    IfThen(EBlock(st1*, e, st2*), st3*) -> 
    Block([st1*, IfElse(e, [st2*,st3*], st2*)])

  HoistEBlockFromWhile :
    While(EBlock(st1*, e, st2*), st3*) -> 
    Block([st1*, While(e, [st2*,st3*,st1*])])

  HoistEBlockFromFor :
    For(x, e1, e2, st1*) -> 
    Block([st2*, For(x, e1', e2', st1*)])
    where <collect-eblocks> [e1, e2] => (st2*, [e1', e2'])

  collect-eblocks = 
    fetch(?EBlock(_,_,_))
    ; map({where(new => x); !([Declaration(x), Assign(x, <id>)], Var(x))})
    ; unzip
    ; (concat, id)

  
  flatten-block =
    Block(
      foldr(![], \ (Block(st2*), st3*) -> [st2*, st3*] \ 
                     <+ \ (st, st*) -> [st | st*] \ )
      ; partition(?Declaration(_))
      ; conc
    )
   

9.3. Example

desugar expresion blocks, then perform simplification, copy propagation, constant propagation, and finally dead code elimination.

Figure 9.3. file: til/xmpl/eblock-desugar-test2

#! /bin/sh -v 

sglri -p ../til-eblock/TIL-eblocks.tbl -i eblock-desugar-test2.til |\
../sim/til-simplify |\
../renaming/til-rename-vars |\
../til-eblock/til-eblock-desugar -o eblock-desugar-test2.des.til

ast2text -p ../pp/TIL-pretty.pp \
	-i eblock-desugar-test2.des.til \
	-o eblock-desugar-test2.txt

../opt/til-copyprop-rev -i eblock-desugar-test2.des.til |\
../opt/til-forward-subst |\
../opt/til-copyprop |\
../opt/til-propconst |\
../opt/til-dce |\
ast2text -p ../pp/TIL-pretty.pp -o eblock-desugar-test2.cp.txt

Table 9.1. files: til/xmpl/eblock-desugar-test2.til, til/xmpl/eblock-desugar-test2.txt

beforeafter
write(
  begin
    var x;
    x := read();
    return 
      x + begin 
            x := readint(); 
            return x; 
            x := x * 2; 
          end + 1;
    x := x + 1;
    write(x);
  end
);
begin
  var k_0;
  var j_0;
  var a_0;
  var h_0;
  var f_0;
  var g_0;
  var e_0;
  var c_0;
  var d_0;
  var b_0;
  var i_0;
  var x0 : int;
  a_0 := read();
  x0 := a_0;
  f_0 := x0;
  b_0 := read();
  d_0 := b_0;
  c_0 := string2int(d_0);
  x0 := c_0;
  e_0 := x0;
  x0 := x0 * 2;
  g_0 := e_0;
  h_0 := f_0 + g_0;
  i_0 := 1;
  j_0 := h_0 + i_0;
  x0 := x0 + 1;
  write(x0);
  k_0 := j_0;
  write(k_0);
end

Table 9.2. files: til/xmpl/eblock-desugar-test2.txt, til/xmpl/eblock-desugar-test2.cp.txt

beforeafter
begin
  var k_0;
  var j_0;
  var a_0;
  var h_0;
  var f_0;
  var g_0;
  var e_0;
  var c_0;
  var d_0;
  var b_0;
  var i_0;
  var x0 : int;
  a_0 := read();
  x0 := a_0;
  f_0 := x0;
  b_0 := read();
  d_0 := b_0;
  c_0 := string2int(d_0);
  x0 := c_0;
  e_0 := x0;
  x0 := x0 * 2;
  g_0 := e_0;
  h_0 := f_0 + g_0;
  i_0 := 1;
  j_0 := h_0 + i_0;
  x0 := x0 + 1;
  write(x0);
  k_0 := j_0;
  write(k_0);
end
begin
  var a_0;
  var c_0;
  var b_0;
  a_0 := read();
  b_0 := read();
  c_0 := string2int(b_0);
  write(c_0 * 2 + 1);
  write(a_0 + c_0 + 1);
end

Part II. Example Packages (*)

Work in Progress

This chapter is work in progress. Not all parts have been finished yet. The latest revision of this manual may contain more material. Refer to the online version.

This part introduces several example packages.

Chapter 10. Tiger Base (*)

Table of Contents

10.1.
10.2.
10.3.

10.1. 

10.2. 

10.3. 

Chapter 11. BibTeX Tools (*)

Table of Contents

11.1.
11.2.
11.3.

11.1. 

11.2. 

11.3.