PT Course
Home
Education Page
Description
Schedule
Slides
Literature
Lab
Assignments
Software
Resources
Subversion Server
Stratego/XT Manual
Stratego Library
Dryad Library
Java Syntax
Stratego/Java Syntax
JLS
JVM: Class files
Contact
Mailing List
IRC
Eelco Visser
Martin Bravenboer
Center for ST
Home
Master Program
Center
Home
Courses
People
Projects
Page
Edit Page
Rename Page
Attach File
Printable
Wiki Source
More ...
Web
Recent Changes
Notify Service
News
Page Index
Search
More ...
Wiki
About TWiki
Text Formatting
Registration
Change Password
Reset Password
Users
Groups
Log In
or
Register
Assignment Scoped Dynamic Rewrite Rules
Pt
---+ 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