Assignment Concrete Object Syntax

Pt04
%TOC%

In this assignment you will implement a transformation that instruments a Tiger program with statements to gather profile information at runtime and print this information to standard
output. You should use strategies, rewrite rules, dynamic rewrite rules, and concrete syntax in this exercise.

You don't need an extraordinary number of lines of code for this assignment: our implementation is 64 lines of code, including whitespace. The important aspect of this assignment is to learn using concrete syntax and to have some more experience in using dynamic rules.

---++ Introduction to Profiling

A
[[http://en.wikipedia.org/wiki/Profiler_(computer_science)][profiler]]
tracks the performance of a computer program to find the bottle necks
in a program. Different
[[http://en.wikipedia.org/wiki/Software_metric][metrics]] can be used
to measure properties of a program that might, or might not, be
related to the performance of the program.

Profiler tools can be implemented to be applied at runtime,
compile-time, or both. The Java Virtual Machine for example allows an
=-Xprof= argument. The JVM will output profiling information to
standard output if this argument is supplied. GCC (the GNU Compiler
Collection), of which the C compiler used on typical GNU/Linux systems
is a part, takes a =-pg= argument, which instructs the compiler to add
extra code that writes profile information. The program must also be
linked with the runtime part of the profiler. During an execution,
profile information is produced, which can be analyzed with the
[[http://www.gnu.org/manual/gprof-2.9.1/][GNU Profiler]], =gprof=.

A possible metric is the number of times a function is called during
the execution of a program. Functions in a program might be called
more (or less) often then you expected. This profile information can
be collected by instrumenting the original program with statements to
keep track of the calls to a function.

Take for example the following Tiger program:
<verbatim>
let function fact(n : int) : int =
      if n < 1 then 1 else (n * fact(n - 1))
 in printint(fact(10))
end
</verbatim>

This program can be instrumented with an additional variable to count
the number of times the function =fact= is called. This is illustrated
in the following Tiger program:

<verbatim>
let var fact := 0
 in let function fact(n : int) : int =
        ( fact := fact + 1
        ; if n < 1 then 1 else (n * fact(n - 1))
        )
     in printint(fact(10))
    end
  ; print("\nfact: ")
  ; printint(fact)
end
</verbatim>

Running this instrumented program results in the following output:
<verbatim>
3628800
fact: 11
</verbatim>

As you can see in this example, function _declarations_ are
instrumented with an additional statement to increment the counter for
the function that is declared.

In this example, the program just keeps track of the number of times
functions are called. There is no information where these calls
originated from. If we want more detailed information on the function
calls in a program, the instrumentation shown above will no longer
work: there is no way to find out who the _caller_ is as soon as the
execution has arrived in the _callee_.

This information can be obtained by not instrumenting function
declarations, but function _calls_. At the location of a function
call, it is possible to determine what function is being called (the
callee), and who is calling the function (the caller). The counter for
this function pair can be increased at the location of the function call.

The following Tiger program shows how the previous example might be
extended to collect this profile information.
<verbatim>
let var  top_fact := 0
    var fact_fact := 0
 in let function fact(n : int) : int =
          if n < 1
          then 1
          else
            (n * (
              fact_fact := fact_fact + 1
            ; fact(n - 1))
            )
     in printint(
        ( top_fact := top_fact + 1
        ; fact(10))
        )
    end

  ; print("\ntop to fact: ")
  ; printint(top_fact)

  ; print("\nfact to fact: ")
  ; printint(fact_fact)
end
</verbatim>

Execution of this program produces the following output:
<verbatim>
3628800
top to fact: 1
fact to fact: 10
</verbatim>

---++ Assignment

Download the [[%ATTACHURL%/sa9-template.tar.gz][template]] for this assignment and implement the profiler in the module =Tiger-Profile=. This module performs a transformation from Tiger AST to Tiger AST. The transformation of this module must extend the input program with statements to output detailed information on the number of function calls.

The output program must on execution output information on the number
of calls for each caller, callee pair. For this you have to instrument
function calls in a Tiger program. At a function call you need context
information to increase the correct counter: what function is the
caller and what function is being called? Your implementation must use
dynamic rewrite rules to generate the instrumenting rewrite rules at
the locations where the information is available (i.e. the function
declaration).

Your implementation must be able to distinguish local redeclarations
of functions, and in general function declarations with the same
name. Applying =Tiger-Rename= to solve this problem is not allowed:
the function names must not be obfuscated. Providing more
detailed information the location of the caller and callee in the
presentation is an optional challenge.

Apply your =Tiger-Profile= module in the following pipeline of Tiger
transformation tools:

<verbatim>
  parse-tiger -i $< \
  | Tiger-Desugar \
  | ./Tiger-Profile \
  | Tiger-Ensugar \
  | pp-tiger -o $@
</verbatim>

The resulting program is to be executed with the Tiger interpreter,
=run-tiger=. In the supplied =Makefile= this pipeline is available
using the command =make ${file}.prof.tig= (where the Tiger program is
supposed to be in =${file.tig}=).

Your solution will be judged on the actual results and the style and
clearness of the code. If all the examples work, then this is not a
guarantee that you will get a 10. For example, you have to restrict
the scope of dynamic rules in the right way. You are not allowed to
use abstract syntax for Tiger.

---++ Examples

The template zip contains some example programs. You can execute these
tests using:

<verbatim>
$ make checks/power.prof.run
</verbatim>

An overview of the tests:
   * =test-1, test-2, power, fact=: simple tests
   * =test-3=: multiple declaration
   * =test-4, test-5=: local redeclarations
   * =test-6=: program without functions
   * =test-7=: calls to primitives (bonus if you profile as well, i.e. in an attractive way)
   * =queens=: larger program

Some of the expected results:
   * =power=: top 1 pow, pow 4 pow, pow 4 even, even 4 pow, pow 2 square
   * =test-3=: top 1 f, top 1 f, f 5 f, f 5 f
   * =queens=: top 1 try, try 2056 try, try 92 printboard

If you need to inspect the instrumented Tiger code:
<verbatim>
$ make checks/power.prof.tig
</verbatim>

The =fact= example in previous section was written by hand. To
illustrate how the outcome of an actual implementation could look
like, we give the output of =power.prof.tig= in our
implementation. Note that it might be useful to filter variable
declarations by checking if an assignment has been generated
(optional).

<verbatim>
let var top_top : int := 0
    var top_square_0 : int := 0
    var top_mod_0 : int := 0
    var top_even_0 : int := 0
    var top_power_0 : int := 0
    var square_0_top : int := 0
    var square_0_square_0 : int := 0
    var square_0_mod_0 : int := 0
    var square_0_even_0 : int := 0
    var square_0_power_0 : int := 0
    var mod_0_top : int := 0
    var mod_0_square_0 : int := 0
    var mod_0_mod_0 : int := 0
    var mod_0_even_0 : int := 0
    var mod_0_power_0 : int := 0
    var even_0_top : int := 0
    var even_0_square_0 : int := 0
    var even_0_mod_0 : int := 0
    var even_0_even_0 : int := 0
    var even_0_power_0 : int := 0
    var power_0_top : int := 0
    var power_0_square_0 : int := 0
    var power_0_mod_0 : int := 0
    var power_0_even_0 : int := 0
    var power_0_power_0 : int := 0
 in let function square(x : int) : int =
          x * x

        function mod(x: int, y : int) : int =
          x - x / y * y

        function even(x : int) : int =
          (even_0_mod_0 := even_0_mod_0 + 1;
           mod(x, 2))= 0

        function power(x: int, n : int) : int =
          if n= 0
          then 1
          else if (power_0_even_0 := power_0_even_0 + 1;
                   even(n))
               then (power_0_square_0 := power_0_square_0 + 1;
                     square((power_0_power_0 := power_0_power_0 + 1;
                             power(x, n / 2))))
               else x * (power_0_power_0 := power_0_power_0 + 1;
                         power(x, n - 1))
     in printint((top_power_0 := top_power_0 + 1;
                  power(2, 5)));
        print("\n")
    end;
    ... print results ...
end
</verbatim>

---++ Tips, Tricks and Issues

See the [[http://www.stratego-language.org/Tiger/TigerLanguage][Tiger Language]]
topic if you need information on Tiger.

---+++ Abstract Syntax

You can the abstract syntax implementation of =Tiger-Profile.str= by
running =make Tiger-Profile.ppstr=. This module can explain the
meaning of concrete syntax fragments, if their meaning is unclear.

---+++ Traversal Strategy

In the traversal you have to handle three cases in a special way: a
let, a function declaration and a call. We can use the following
traversal scheme for that:

<verbatim>
  traversal =
       ?|[ let .. ]|
       ; ...

    <+ ?|[ function ...  ]|
       ; ...

    <+ ?|[ ... call ... ]|

    <+ all(traversal)
</verbatim>

The most attractive implementation is define an =InstrumentCall=
dynamic rule for the scope of a function declaration. The scope of a
function declaration is the =let= in which the function is
declared. This =InstrumentCall= should rewrite a function call to a
sequence of an assignment and a the call. The =InstrumentCall= dynamic
rule can use another dynamic rule, e.g. =CurrentFun=, for determining
the current function declaration. Both dynamic rules have to be
scoped, obviously in a different way.

---++++ Termination of Call Instrumentation

Instrumentation of call can easily result in non-termination. Hence,
your traversal has to jump over the code that you have inserted. You
can implement this by parameterizing the dynamic rule with the
traversal strategy.

---++++ Handling Multiple Declarations

In a Tiger program multiple declarations of functions with a certain
name can occur. The function name is thus not an unique identification
of a function declaration. To obtain a unique identifier of a function
declaration, the function declarations in the Tiger program could be
annotated with such an identifier. Remember that unique identifiers
can be generated with the =newname= strategy. You can find more
information on the usage of annotations at the
[[http://www.stratego-language.org/Stratego/TermAnnotation][Term Annotations]] topic.  You can also take a look at
[[%SVN%/stratego-lib/tests/annotations-test.str][annotations-test.str]]
in the Stratego Library. This module defines unit tests for
annotations and is thus a good example of the various constructs.

---+++ Useful Library Strategies

   * =cart(s)= applies s to the cartesian product of two lists.
   * =concat-strings= concats a list of strings
   * =conc-strings= concats a tuple of strings

---+++ Escapes in Tiger Code

Unfortunately there are some problems with including newlines (and
other escape sequences) in generated Tiger code.  You should escape
the =\= in an escape sequence: =\\n= .  This problem is caused by the
application of Stratego desugarings to concrete syntax sections.

So, you can generate a print newline statement using:
<verbatim>
!|[ print("\\n") ]|
</verbatim>

---++ Documentation

---+++ Stratego Library API

[[http://catamaran.labs.cs.uu.nl/dist/stratego/stratego-lib-docs-9033/docs/][API and source documentation]] of the Stratego Library is available online.

---+++ Syntax Definitions

---++++ Syntax of Tiger

<!--
   * Set TIGER = https://svn.cs.uu.nl:12443/repos/StrategoXT/trunk/tiger/
   * Set SVN = https://svn.cs.uu.nl:12443/repos/StrategoXT/trunk/StrategoXT
-->

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

   * [[%TIGER%/tiger-front/syn/Tiger.sdf][Tiger.sdf]] : main module importing others
   * [[%TIGER%/tiger-front/syn/Tiger-Declarations.sdf][Tiger-Declarations.sdf]] : type, variable, and function declarations
   * [[%TIGER%/tiger-front/syn/Tiger-Statements.sdf][Tiger-Statements.sdf]] : assignment, conditional, loops, etc.
   * [[%TIGER%/tiger-front/syn/Tiger-Expressions.sdf][Tiger-Expressions.sdf]] : function call, arrays, records, etc.
   * [[%TIGER%/tiger-front/syn/Tiger-Operators.sdf][Tiger-Operators.sdf]] : infix arithmetic and logical operators

Lexical syntax

   * [[%TIGER%/tiger-front/syn/Tiger-Whitespace.sdf][Tiger-Whitespace.sdf]]
   * [[%TIGER%/tiger-front/syn/Tiger-Comment.sdf][Tiger-Comment.sdf]]
   * [[%TIGER%/tiger-front/syn/Tiger-Literals.sdf][Tiger-Literals.sdf]]
   * [[%TIGER%/tiger-front/syn/Tiger-Lexicals.sdf][Tiger-Lexicals.sdf]]

Desugaring turns operators into generic =BinOps= and =RelOps=:

   * [[%TIGER%/tiger-front/syn/Tiger-BinOps.sdf][Tiger-BinOps.sdf]]
   * [[%TIGER%/tiger-front/syn/Operators.sdf][Operators.sdf]]

---++++ Tiger in Stratego

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

   * [[%TIGER%/tiger-front/syn/StrategoTiger.sdf][StrategoTiger.sdf]]: quotation and anti-quotation
   * [[%TIGER%/tiger-front/syn/Tiger-Variables.sdf][Tiger-Variables.sdf]]: meta-variables
   * [[%TIGER%/tiger-front/syn/Tiger-Congruences.sdf][Tiger-Congruences.sdf]]: congruences

Note that the 
<verbatim>
  [[...]]
</verbatim>
quotation operators are legacy and should not be used. 

---++++ Specifying Concrete Object Syntax

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=. As you can see, this
syntax is already specified in =Tiger-Profile.meta= in the following
way:

<verbatim>
  Meta([
    Syntax("StrategoTiger")
  ])
</verbatim>