Assignment Compilation By Transformation

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,

$ tiger-xmpl -x fac

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

$ tiger-xmpl -x fac | run-tiger

Setup

Download the 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,

$ tiger-xmpl -x fac | ./compile

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

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

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

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

let function twice(x : int) : int = x + x
 in printint(twice(10))
end

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

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:

  mark-procedure-calls =
    let stm-level =
          ...

        exp-level =
          ...

     in stm-level
    end

Example

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

...
  [ 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")]))
    )
  ]
...

Simplify Expressions

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

  is-atomic = 
    Var(id) + String(id) + Int(id) + NilExp()

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.

  /**
   * @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

Example

let var x : int
    var y : int

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

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

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

let var x : int := 0

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

  ; printint(x)
end

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

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

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

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

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 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

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

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

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.