WebHome
Education Page
Description
Schedule
Slides
Assignments

Center
Master Program

Center

Page

Web

Wiki

Log In or Register

Assignment Concrete Syntax

Pt03
The goal of this assignment is to learn the use concrete syntax in Stratego for the specification of rewrite rules and to improve your term rewriting skills.

Argument Lifting with Concrete Syntax

Assignment

The assignment builds on Assignment Term Rewriting. The goal is to (1) specify the argument lifting transformation using concrete syntax and (2) extend that transformation to cover more cases.

The transformation pipeline that you should build has the following components:

  • tiger-xmpl -x fac-tail (or cat file.tig)
  • parse-tiger
  • Tiger-Desugar
  • Tiger-Rename
  • ./liftargs (your transformation
  • Tiger-Ensugar
  • pp-tiger

Remarks

  • liftargs is a better name for the transformation than simplify
  • let flattening is now done by Tiger-Ensugar

To pass you should minimally cover the following

  • Lifting from BinOps, RelOps, If, IfThen, For, While
  • Let and seq hoisting for 'simple' cases (i.e., not involving lists)

For a higher grade you could extend this with (some of)

  • Lifting from function calls, array access, record
  • Hoisting lets as high up as possible
  • Splitting var declarations into a non-initialized declaration and an assignment

Again: more is better than less, but correctness is more important than completeness.

Correctness

The ultimate test for the correctness of your transformation is running the transformed program. The Tiger toolkit contains run-tiger which interprets a Tiger program. Some good examples for running are

  • fac.tig : compute factorial of 10
  • queens.tig : prints all solutions for placing 8 queens
  • prettyprint.tig : prints tree structure

Testing

Compiling and running the transformation from the command-line or in a script must be getting boring by now. Write a Makefile to automate compilation of the program and testing it. The Makefile should have the following targets:

  • liftargs : compile the transformation
  • file.show : show (cat) a Tiger program file.tig
  • file.run : run a Tiger program with run-tiger
  • file.lif : result of applying the liftargs transformation pipeline
  • check : run a number of correctness tests on (small) Tiger programs
  • clean : remove all derived files

It should be possible to 'make fac.lif.run' to first apply the transformation and then run the resulting program. All 'file' targets are for arbitrary files of course.

For convenience you might include sub-targets to express the results of intermediate results.

Submit

Submit the following files

  • liftargs.str : implementation of argument lifting with concrete syntax
  • liftargs.meta : declaration of concrete syntax used in the program
  • Makefile : with the targets as described above
  • Tiger programs you have developed for testing the transformation

Syntax Definitions

Syntax of Tiger

The syntax definition of Tiger is defined in the following modules:

Lexical syntax

Desugaring turns operators into generic BinOps and RelOps:

Tiger in Stratego

The full syntax of the embedding of Tiger in Stratego is defined in the following modules.

Note that the 

  [[...]]
quotation operators are legacy and should not be used.

A Stratego module that uses concrete object syntax must specify the syntax of the module in a .meta file. For concrete Tiger syntax in Stratego this syntax is called StrategoTiger. Specify this syntax for a Stratego module foo.str in a file foo.meta using: 

  Meta([
    Syntax("StrategoTiger")
  ])

Add the following argument to the call of the Stratego compiler to include the StrategoTiger syntax in the include path: 

-I ${TIGER}/share/sdf/tiger-front
where ${TIGER} points to the location where Tiger is installed. This is /projects/stratego/tiger.

Example

Here is the result of liftargs applied to prettyprint.tig. This could be further improved by recognizing that nil is a constant that does not have to be lifted. 

--------------------------------------------------------
let type a_0 = {key : string, left : a_0, right : a_0}
    function prettyprint_b_0(d_0 : a_0) : string =
      let var e_0
      in e_0 := "";
         let function write_g_0(i_0 : string) =
               e_0 := concat(e_0, i_0)
             function show_h_0(k_0: int, l_0 : a_0) =
               let function indent_n_0(o_0 : string) =
                     (write_g_0("\n");
                      for p_0 := 1 to k_0 do
                        write_g_0("  ");
                      e_0 := concat(e_0, o_0))
                   var n_0 : int
                   var b_0 : int
                   var c_0 : int
                   var f_0
                   var g_0
                   var h_0
                   var j_0
                   var m_0
               in b_0 := l_0;
                  c_0 := nil;
                  n_0 := b_0 = c_0;
                  if n_0
                  then indent_n_0(".")
                  else (f_0 := l_0.key;
                        indent_n_0(f_0);
                        g_0 := k_0 + 1;
                        h_0 := l_0.left;
                        show_h_0(g_0, h_0);
                        j_0 := k_0 + 1;
                        m_0 := l_0.right;
                        show_h_0(j_0, m_0))
               end
         in show_h_0(0, d_0);
            e_0
         end
      end
    function node_c_0(q_0: string, r_0: a_0, s_0 : a_0) : a_0 =
      a_0{key = q_0, left = r_0, right = s_0}
    var t_0
    var a_1
    var u_0
    var v_0
    var b_1
    var y_0
    var z_0
    var w_0
    var x_0
    var c_1
in u_0 := nil;
   v_0 := nil;
   a_1 := node_c_0("b", u_0, v_0);
   y_0 := nil;
   w_0 := nil;
   x_0 := nil;
   z_0 := node_c_0("d", w_0, x_0);
   b_1 := node_c_0("c", y_0, z_0);
   t_0 := node_c_0("a", a_1, b_1);
   c_1 := prettyprint_b_0(t_0);
   print(c_1);
   print("\n")
end
--------------------------------------------------------