Assignment Compilation By Transformation

Pt04
%TOC%

---++ Introduction

In this assignment, you will implement a series of small compilation
by transformation phases. In this exercise, you will learn more about
various aspects of compilation, program transformation, and Stratego:
composing transformation tools, using traversals, and implementing
rewritings as separate rewrite rules.

---++ Tiger

We will assume the full Tiger language in this assignment. Tiger
examples are available in the directory
=~/.nix-profile/share/tiger-xmpl/=. You can =cat= these examples to
the standard output using the =tiger-xmpl= tool. For example,

<verbatim>
$ tiger-xmpl -x fac
</verbatim>

Remember that you can run Tiger programs using =run-tiger=. For
example,

<verbatim>
$ tiger-xmpl -x fac | run-tiger
</verbatim>

---++ Setup

Download the [[%ATTACHURL%/template-sa6.tar.gz][tar.gz]] template for
this assignment and unpack it (=tar zxvf template-sa6.tar.gz=). The
tarball contains:

   * =Makefile= for compiling the compiler and applying checks
   * Template Stratego module =compile.str=

Use =make= to compile the compiler. This create the executable
=compile=. This is a complete Tiger to Tiger compiler, so you can
apply it immediately to a Tiger program. For example,

<verbatim>
$ tiger-xmpl -x fac | ./compile
</verbatim>

The =compile= program takes several optional command-line arguments
(all having default values). See =--help= for more information.

The Stratego module =compile.str= already contains an entry-point. The
=main= strategy handled command-line options and defines an XTC
composition. The real transformation is implemented in the strategy
=compile=. This strategy composes the phases you have to
implement. The actual phases are all implemented as identity phases,
so you will not

=make check= runs some checks on the standard examples. You should
extend the test suite yourself by adding Tiger programs to the
=checks= directory. Specifying the expected outcome is not necessary:
this is determined by running the program before _and_ after
compilation and comparing the output. It is important to output
something in your own tests, since there is noting to compare without
some output.

---++ Phases

---+++ Desugar For Loop

In this phase, desugar a Tiger for loop by replacing it with a while
loop. Note that the lower and upperbound of the loop should be
evaluated only ones. Implement this in the =for-with-while=
strategy. Use a separate rewrite rule for the actual rewriting and
apply this rule in a strategy.

In this rewrite rule, you can use the =new= or =newname= strategy from
the module =string= (consult the API documentation). These strategies
create unique names that you can use for introducing new
variables. The =newname= strategy takes a string prefix, which can
make the resulting program more readable. =new= just produces a unique
string.

---++++ Example

<verbatim>
for x := 1 to 10 do
  print("Nog een keer!\n")
</verbatim>

<verbatim>
let var x := 1
    var a_0 := 10
 in while x <= a_0 do
      (print("Nog een keer!\n");
       x := x + 1)
end
</verbatim>

---+++ Make Return Value Explicit

Returns are implicit in Tiger: the return value of a function is that
value of the body, which is an expression. In this compilation phase,
you must introduce a variable =return= in every function. Assign the
result of the function to this variable.

---++++ Example

<verbatim>
let function twice(x : int) : int = x + x
 in printint(twice(10))
end
</verbatim>

<verbatim>
let function twice(x : int) : int =
      let var return
       in return := x + x
        ; return
      end
 in printint(twice(10))
end
</verbatim>

---+++ Mark Procedure Calls

In this phase, you have to mark all the procedure calls with a =Proc=
constructor. This means that all =Call= 's at the statement level should
be wrapped in a =Proc= constructor. Statement levels are:

   * body of the =While=
   * init elements of a =Let=
   * init elements of a =Seq=

Some expressions are at the statement level depending on the context
in which they occur.

   * all expressions of a =Seq= that is itself at the statement level
   * all expression of a =Let= that is itself at the statement level
   * the body of a function declaration, if it is a procedure
   * the branches of an =If=, if the =If= itself is at the statement
     level.

This might sound difficult to implement, but in fact there is nice
idiom for implementing such transformations. For each level, you can
use a separate strategy.

At the statement level, you switch to the expression level when
necessary and stay at the statement level if there is a statement
construct at the statement level. =Call= 's at the statement level are
wrapped in a =Proc=.

At the expression level, you do not wrap =Call= 's and switch to the
statement level for the at a =Seq= or =Let= construct. For
subexpressions, you just traverse.

You can use this template:
<verbatim>
  mark-procedure-calls =
    let stm-level =
          ...

        exp-level =
          ...

     in stm-level
    end
</verbatim>

---++++ Example

<verbatim>
let function twice(x : int) : int = x + x
    var x : int

 in twice(1)
  ; x := twice(2)
  ; while 1 do twice(3)
  ; if 1 then twice(4) else twice(5)
end
</verbatim>

<verbatim>
...
  [ Proc(Call(Var("twice"), [Int("1")]))
  , Assign(
      Var("x")
    , Call(Var("twice"), [Int("2")])
    )
  , While(
      Int("1")
    , Proc(Call(Var("twice"), [Int("3")]))
    )
  , If(
      Int("1")
    , Proc(Call(Var("twice"), [Int("4")]))
    , Proc(Call(Var("twice"), [Int("5")]))
    )
  ]
...
</verbatim>

---+++ Simplify Expressions

In this phase, you have to simplify expressions to a from where all
arguments of operators are atomic. Atomic expressions are:

<verbatim>
  is-atomic = 
    Var(id) + String(id) + Int(id) + NilExp()
</verbatim>

You can implement these simplifications by lifting the more complex
(not atomic) operators. The following util =make-vardecs= can help to
make this implementation easier by separating the introduction of new
declarations in a separate strategy. Use this strategy to lift complex
expressions out of =Call=, =BinOp=, =RelOp=, =Seq=, and so on.

Tip: don't create rewrite rules for these expressions, but for these expressions at the statement level. For example, create a rewrite rule for an =BinOp= in an =Assign= instead of rewrite rule for a =BinOp=.

<verbatim>
  /**
   * @type List(Exp) -> (List(Dec), List(Exp))
   */
  make-vardecs =
    fetch(not(is-atomic))
    ; map(MkVarDec)
    ; unzip
    ; (concat, id)

  MkVarDec :
    e -> ([VarDec(x, NoTp, e)], Var(x))
    where <not(is-atomic)> e
   ; new => x

  MkVarDec :
    e -> ([], e)
    where <is-atomic> e
</verbatim>

---++++ Example

<verbatim>
let var x : int
    var y : int

 in x := 1 + 2 * 3
  ; y := f(4 * 5, 6)
end
</verbatim>

<verbatim>
let var x : int
    var y : int
 in let var a
     in a := 2 * 3;
        x := 1 + a
    end;
    let var c
     in c := 4 * 5;
        y := f(c, 6)
    end
end
</verbatim>

---+++ Remove Structered Control-flow

In this phase, replace the structured control-flow construct =while=
and =if= with =goto= and =label=. You can use =newname= or =new= to
generate unique identifiers for labels.

---++++ Example

<verbatim>
let var x : int := 0

 in while x < 10 do
      x := x + 1

  ; printint(x)
end
</verbatim>

<verbatim>
let var x : int := 0
 in let var d
     in label a;
        d := not(x < 10);
        if d goto c;
        x := x + 1;
        goto a;
        label c
    end;
    printint(x)
end
</verbatim>

---+++ Collect Declarations at Top-level

In this phase, you have to collect all variable declarations at the
top-level. For local variables, this is directly in the body of a
function declaration. For global variables, this is a let declaration
at the top-level of the Tiger program.

Implement this transformation using the =collect= strategy that we
learned about in the previous lecture. Try to reuse the same strategy
for collecting local and global variables.

---++++ Example

<verbatim>
let function f() =
      let var y : int
       in y := 1
        ; if 1 then
            let var x : int
             in x := 2
            end
       end

    var z : int
 in z := 3
  ; printint(z)
end
</verbatim>

<verbatim>
let var z : int
 in let function f() =
          let var y : int
              var x : int
           in y := 1;
              if 1 then
                x := 2
          end
     in z := 3;
        printint(z)
    end
end
</verbatim>

---+++ Flatten Sequences

In this phase, you have to remove all nested sequences in order to
create a simple list of statements. For this phase, you can use the
rewrite rules available in the module
[[https://svn.cs.uu.nl:12443/repos/StrategoXT/trunk/tiger/tiger-front/tas/Tiger-Sugar-Rules.str][Tiger-Sugar-Rules.str]].
This module is already installed and imported, so you don't have to
copy the rules.

You can implement the flattening in two stages.  First, you split all
the existing =Let= and =Seq= constructs into single declarations and
expressions (reuse rules from =Tiger-Sugar-Rules=). Second, you can
combine a set of =Let= and =Seq= flattening rules and apply these in
an innermost fashion.

---++++ Example

<verbatim>
let var x : int
    var y : int
 in ( x := 1 * 2
    ; y := 3
    ; ( x := 4
      ; y := 5
      )
    )
end
</verbatim>

<verbatim>
let var x : int
    var y : int
 in x := 1 * 2;
    y := 3;
    x := 4;
    y := 5
end
</verbatim>

---+++ Removed Procedure Call Marks

The =Proc= markers are now no longer necessary. You have to remove
them to pretty-print the Tiger program, so drop them in a simple
traversal.