Adrian Prantl
TU Vienna

The TERMITE library

The TERM Iteration and Transformation Environment (Termite) is a Prolog library that allows easy manipulation and analysis of C++ Programs that are in the SATIrE term representation.

Termite Dictionary

The SATIrE term representation

SATIrE can export an external term representation of the abstract syntax tree (AST) of a C++ program. This term representation contains all information that is necessary to correctly unparse the program, including line and column information of every expression. The terms are also annotated with the results of any preceding PAG analysis. The syntax of the term representation was designed to match the syntax of Prolog terms. This allows it to be manipulated by Prolog programs very naturally.

Tutorial

1. Easy Program Transformations

Converting while() to for()

In this example we want to convert while()-loops into for()-loops. We do this by implementing a transformation traversal.
#!/usr/bin/pl -t main -f
% -*- prolog -*-
:- use_module(ast_transform),
   use_module(ast_properties).
We want our transformation to only work on simple loops that use an induction variable.
is_simple_update(expr_statement(Op, _, _), Var) :-
  ( Op = plus_plus_op(V, _, _)
  ; Op = assign_op(V, _, _, _)
  ; Op = plus_assign_op(V, _, _, _)
  ; Op = minus_assign_op(V, _, _, _)
  ; Op = rshift_assign_op(V, _, _, _)
  ),
  var_stripped(V, Var).
Furthermore, we want to make sure that the induction variable is not modified by any other statement in the loop body, which is done by checking ast_properties:is_transp/3.
contains_safe_increment(basic_block(Statements, A, Fi),
                        basic_block(ForBody, A, Fi),
                        Var, Increment) :-
  select(Increment, Statements, ForBody),
  is_simple_update(Increment, Var),
  guarantee(Statements, is_transp(Var, local)).
This is the hook for the transformation traversal. It transforms while()-statements (1st clause) and leaves all others untouched (2nd clause).
while_to_for(_, _, _, WhileStmt, ForStmt) :-
  % Detect a WHILE-Statement
  isWhileStatement(WhileStmt, Condition, V, Body, Annot, Fi),
  var_stripped(V, Var),

  % Find and remove Increment from Body
  contains_safe_increment(Body, NewBody, Var, Increment),

  % Construct FOR-Statement
  ForInit = for_init_statement(Annot,Fi),
  ForTest = Condition,
  expr_statement(ForStep, _, _) = Increment,
  ForStmt = for_statement(ForInit, ForTest, ForStep, NewBody, Annot, Fi).

while_to_for(I, I, I, S, S).
Finally, we also want to invoke our traversal and do some basic file I/O.
%-----------------------------------------------------------------------
% MAIN
%-----------------------------------------------------------------------

main :-
  open('input.pl',read,_,[alias(rstrm)]),
  read_term(rstrm,X,[double_quotes(string)]),
  close(rstrm),

  transformed_with(X, while_to_for, [], _, Y),

  open('output.pl',write,_,[alias(wstrm)]),
  write_term(wstrm,Y,[quoted(true),double_quotes(string)]),
  close(wstrm).

To generate an input.pl, we can run any SATIrE-generated analyzer with the --output-term=input.pl option. There are also the c2term and term2c programs to convert form .c to .pl and vice versa.

Let's try it!

First, we create an input file in.c:
int main() {
  int i = 0;
  while (i < 10) {
    printf(".");
    i++;
  }
}
Then we convert it into the term representation and run our program
c2term in.c input.pl
./while2for.pl
term2c output.pl out.c
We can now check out the result file out.c:
int main() {
  int i = 0;
  for ( ; i < 10; i++) {
    printf(".");
  }
}

2. Custom Program Analysis

...to come soon!
Complang Group
Adrian Prantl
   TERMITE
Sitemap
Fast Access:
SATIrE
SATIrE FAQ
Termite Manual
Faculty of Informatics
Vienna University of Technology
top | HTML 4.01 | last update: 2014-06-07 (Adrian)