Chapter 3. Simplification and Desugaring

Table of Contents

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

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 (libstratego-lib), 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");