Table of Contents
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.
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([])
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"
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
)
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
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
| before | after |
|---|---|
// 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");
|