Assignment Scoped Dynamic Rewrite Rules

---+ Tiger Profiler

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.

---++ Introduction to Profiling

A [[http://en.wikipedia.org][profiler]] tracks the
performance of a computer program in order that the bottle necks in
the program are found. 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

Implement a module called =tiger-profile= that performs a
transformation from Tiger AST (tas) to Tiger AST. 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.

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

---++ Tips and issues

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

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 =new= 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 =annotations-test.str= in the SSL. This module defines unit tests for
annotations and is thus a good example of the various constructs.

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.

---++ Syntax Definitions

---++++ Syntax of Tiger

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

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

Lexical syntax

   * [[http://www.stratego-language.org/tiger-front/syn/Tiger-Whitespace.sdf][Tiger-Whitespace.sdf]]
   * [[http://www.stratego-language.org/tiger-front/syn/Tiger-Comment.sdf][Tiger-Comment.sdf]]
   * [[http://www.stratego-language.org/tiger-front/syn/Tiger-Literals.sdf][Tiger-Literals.sdf]]
   * [[http://www.stratego-language.org/tiger-front/syn/Tiger-Lexicals.sdf][Tiger-Lexicals.sdf]]

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

   * [[http://www.stratego-language.org/tiger-front/syn/Tiger-BinOps.sdf][Tiger-BinOps.sdf]] 
   * [[http://www.stratego-language.org/tiger-front/syn/Operators.sdf][Operators.sdf]]

---++++ Tiger in Stratego

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

   * [[http://www.stratego-language.org/tiger-front/syn/StrategoTiger.sdf][StrategoTiger.sdf]] : quotation and anti-quotation operators
   * [[http://www.stratego-language.org/tiger-front/syn/Tiger-Variables.sdf][Tiger-Variables.sdf]] : meta-variable declaration