Tiger Profiler

Introduction

The purpose of this assignment is to implement a first transformation on a more or less real program. 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, concrete syntax and tool composition with XTC in this exercise.

In the tiger-profile package you will implement the Tiger-Profile module. The Tiger-Profile tool implements a transformation from Tiger AST (tas) to Tiger AST. The tiger-prof tool wraps the Tiger-Profile tool into a Tiger source (tig) to Tiger source transformation by parsing the input and pretty printing the output. You don't have to modify this module.

Example

The most obvious profile information is the number of times a method is called during the execution of a program. You could implement this by maintaining this information for every method in a variable and increase this variable at every invocation. You could instrument the Tiger example fac in the following way:

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

  let var a_0 := 0
      function fact(n : int) : int =
        ( a_0 := a_0 + 1
        ; n < 1 | n * fact(n - 1))
   in printint(fact(10))
    ; print("\n\nProfile information\n")
    ; print("fact: ")
    ; printint(a_0)
    ; print("\n")
  end

The output of the instrumented fac will be:

  3628800
 
  Profile information
  fact: 11

The Tiger example fac-tail is a simple example with nested functions.

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

You could instrument this program like this:

  let var a_0 := 0
      var b_0 := 0
      function fact(n : int) : int =
        (a_0 := a_0 + 1;
         let function f(n: int, acc : int) : int =
               (b_0 := b_0 + 1;
                if n < 1
                then acc
                else f(n - 1, n * acc))
         in f(n, 1)
         end)
   in fact(10)
    ; print("\n\nProfile information: \n")
    ; print("fact: ")
    ; printint(a_0)
    ; print("\n"))
    ; print("f: ")
    ; printint(b_0)
    ; print("\n")
  end

Getting started

Installation

In this assignment you should install the tools that you're writing. First of all download the package that serves as the skeleton for this assignment.

• tiger-profile-0.1.tar.gz

The package should be configured, build and installed with the following commands, which assumes that you want to install the tools in the ${HOME}/pt2003/tiger-profile directory:

  ./configure --prefix=${HOME}/pt2003/tiger-profile --with-xt=/usr --with-tiger=/usr
  make
  make install

To execute the tools you can add the ${HOME}/pt2003/tiger-profile/bin directory to your PATH, run the tools from this directory or specify the full path on the command-line. If you want to try the tools after you've modified the Stratego sources, you should do a make and make install again.

Running your tools

You can run a Tiger example with

  tiger-xmpl -x fac | run-tiger

The first part will produce the source code of the specified example from the tiger-xmpl package. See the directory /usr/share/tiger-xmpl for the available examples. run-tiger is an interpreter for Tiger programs (written in Stratego). You can insert your profiler in the following way:

  tiger-xmpl -x fac | tiger-prof | run-tiger

If you leave out the | run-tiger part, you will see the result of your transformation on standard output. When you start with your assigment, this will just be the pretty-printed version of the example. There might be some small differences between the input and output, because the modules are in fact also desugared and ensugared.

Requirements

Tiger supports local redeclarations of functions. Your implementation must be able to handle this.

Tips and issues

See the Tiger Language topic if you need information on Tiger.

You can find the sources of the modules of the Stratego Standard Library (SSL) in /usr/share/ssl/doc . If you cannot find a strategy that you would expect to be in a library, just do a grep in this directory or ask someone.

A possible solution is the use of annotations. 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 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.

Handing in your solution

You should hand in the project by extending the package name with your login. You can set the name of the package in configure.in . You can mention your full name and studentnumber in the AUTHORS file. Run the bootstrap script to reconfigure the package and do a make dist to create a distribution of your work.