Assignment First Class Pattern Matching

Assignment

Desugar structured control-flow statements in Tiger programs to their unstructured counterparts. In other words, express if, while, for, etc. using =label, goto, and if-goto.

The resulting Tiger functions should have the form

   function f(x*) =
     let var y1 ... var yn
      in stat1; ....; statn 
     end

where the stati are `simple' statements, i.e., assignments, function calls, gotos, and labels.

(It is useful to use the techniques from the liftargs tranformation here.)

Take care that Tiger functions are transformed such that the last expression defines the result of the function. This should not be a label or a goto.

Define a number of small tests to verify your transformations. Apply the transformation to 'real' Tiger programs as well.

By now you should be able to compose this transformation from existing Tiger components and your own components.

Correctness

You can test output of your transformation by running the program with the Tiger interpreter run-tiger.

Submit

Submit all the Stratego modules you developed together with the makefile to compile the transformation components and test them. The makefile should provide a target all which compiles the component, a target .dcf to apply the complete transformation pipeline to a Tiger program, a target check to apply the transformation automatically to your test programs, and a target .run to run a (transformed) Tiger program with the Tiger interpreter.

Examples

fac.tig

-----------------------------------------
let function fact(n : int) : int =
      if n < 1 then 1 else (n * fact(n - 1))
 in printint(fact(10))
end
-----------------------------------------

Is transformed to

-----------------------------------------
let function fact_a_0(b_0 : int) : int =
      let var a_0
          var f_0 : int
          var d_0
          var e_0
          var c_0
      in f_0 := b_0 < 1;
         if f_0 goto h_0;
         d_0 := b_0;
         c_0 := b_0 - 1;
         e_0 := fact_a_0(c_0);
         a_0 := d_0 * e_0;
         goto i_0;
         label h_0;
         a_0 := 1;
         label i_0;
         a_0
      end
    var g_0
in g_0 := fact_a_0(10);
   printint(g_0)
end
-----------------------------------------

fac-iter.tig

-----------------------------------------
let function fact(n : int) : int =
      let function f(n : int, acc : int) : int =
           (while n > 0 do (acc := acc * n; n := n - 1); acc)
       in f(n, 1)
      end
 in fact(10)
end
-----------------------------------------

is transformed to

-----------------------------------------
let function fact_a_0(b_0 : int) : int =
      let var a_0
          function f_c_0(d_0: int, e_0 : int) : int =
            let var c_0
                var f_0 : int
            in f_0 := d_0 > 0;
               label g_0;
               if not(f_0) goto h_0;
               e_0 := e_0 * d_0;
               d_0 := d_0 - 1;
               f_0 := d_0 > 0;
               goto g_0;
               label h_0;
               c_0 := e_0;
               c_0
            end
      in a_0 := f_c_0(b_0, 1);
         a_0
      end
in fact_a_0(10)
end
-----------------------------------------