PT Course

Lab

Contact

Center for ST

Center

Page

Web

Wiki

Log In or Register

Assignment Concrete Object Syntax

Pt

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 profiler tracks the performance of a computer program to find the bottle necks in a program. Different 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 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: 

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

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: 

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

Running this instrumented program results in the following output: 

3628800
fact: 11

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. 

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

Execution of this program produces the following output: 

3628800
top to fact: 1
fact to fact: 10

Assignment

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

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

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: 

$ make checks/power.prof.run

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: 

$ make checks/power.prof.tig

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

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

Tips, Tricks and Issues

See the 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: 

  traversal =
       ?|[ let .. ]|
       ; ...

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

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

    <+ all(traversal)

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 Term Annotations topic. You can also take a look at 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: 

!|[ print("\\n") ]|

Documentation

Stratego Library API

API and source documentation of the Stratego Library is available online.

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

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: 

  Meta([
    Syntax("StrategoTiger")
  ])