Assignment Patterns Rules Strategies Traversals

%TOC%

---++ Introducing the Stratego Compiler and Interpreter

In this assignment you will use Stratego to implement a number of
small Java program transformations. Stratego can be executed in an
interpreter or by compiling it first and then running the executable
program.

---+++ Stratego Programs

A Stratego programs has a main strategy, which can optionally be
specified on the command-line and defaults to =main=. Usually, this
=main= strategy is an =io-wrap= of some strategy. The =io-wrap=
strategy takes care of command-line arguments, input and output.

The skeleton of the Stratego program for this assignment is:

<verbatim>
module pt2
imports
  Java-15
  libstrategolib

strategies

  main =
    io-wrap(exc-4)

strategies

  exc-4 =
    id
</verbatim>

Note that this program imports Java-15. This module is part of
java-front and for this exercise it is easier to copy it to your
working directory:

<verbatim>
$ cp ~/.nix-profile/share/java-front/Java-15.rtree .
</verbatim>

This Stratego Signature for Java describes the AST representation of Java in
Stratego, similar to an RTG. You can find the complete signature at =~/.nix-profile/share/java-front/Java-15.str=.

---+++ Stratego Compiler

Stratego programs can be compiled using the Stratego Compiler:

<verbatim>
$ strc -i pt2.str
</verbatim>

The resulting program will be _much_ faster than the interpreter, but
the compilation itself takes some time. However, for larger examples
this additional compilation time is well spent.

If the Stratego program imports libstrategolib (which is the case for
=pt2.str=, then you need to link with libstratego-lib:

<verbatim>
$ strc -i pt2.str -la stratego-lib
</verbatim>

After compilation, the Stratego program can be applied in a pipeline:

<verbatim>
$ echo "x == true" | parse-java -s Expr | ./pt2 | pp-java
x
</verbatim>

---+++ Stratego Interpreter

A Stratego program can also be interpreted. This is usually a bit
faster then compilation followed by a single application, but soon
gets slower if you want to apply the program multiple times.

<verbatim>
$ echo "x == true" | parse-java -s Expr | stri pt2.str | pp-java
x
</verbatim>

Of course, you'll get a different result, since this is one of the assignments.

---+++ Stratego Shell

For interactively learning the Stratego language, you can use the
Stratego Shell. You can start the Stratego Shell using the shell
command =stratego-shell=. In the Stratego Shell, use the following
command to learn more about the commands of the Stratego Shell.

<verbatim>
stratego> :help
</verbatim>

As an example of a command, you can close the Stratego Shell with
=:quit=, =:exit= or =:q=.

The Stratego Shell can be included in a pipe. In this assignment we
will use the Java language, so you can use =parse-java= to parse input
program and then pipe the result into the Stratego Shell. Optionally,
you can specify a sequence of commands on the command line, separated
by =;;=.

<verbatim>
$ echo "class Foo { void Foo() {} }" | parse-java -s TypeDec | \
    stratego-shell --cmd 'import pt2;; exc-14' | pp-java
class Foo
{
  Foo()
  { }
}
</verbatim>

Note that you can invoke any strategy in this way (in this case
exc-14) and that the strategy is not wrapped in an =io-wrap=. Also, note
that this is again the solution of one of the exercise. In your skeleton, this
strategy is not yet defined and if you define it as id, the output will be
the same as the input.

If you don't provide a =--cmd= argument, then the interactive Stratego
Shell will be started and the current term will be the current term of
the pipe. For example:

<verbatim>
$ echo "if(x != y);" | parse-java -s BlockStm | stratego-shell
stratego> :show
If(NotEq(ExprName(Id("x")),ExprName(Id("y"))),Empty)
stratego> 
</verbatim>

---++++ Stratego Modules

Stratego Modules are stored in files with the =.str= extension. You
can import Stratego modules into the Stratego Shell with the command
=import=.

<verbatim>
stratego> import SmallExercises
</verbatim>

Standard library modules can also be included in this way:
<verbatim>
stratego> import integers
</verbatim>

But, it is more common to import the headers of the separately
compiled Stratego Library:

<verbatim>
stratego> import libstrategolib
</verbatim>

You can use tab expansion to see what strategies are defined.

---++++ Introspection and Debugging

In the Stratego Shell, you can use some commands for debugging and
inspecting the current environment.

   * =:show= prints the current term

   * =:binding= and =:bindings= commands can be used to reflect over
     the current state of your Stratego program.

   * =:trace on= will from now print a very detailed description of
     the strategies that are evaluated by the Stratego Shell. You can
     turn it off using =:trace off=.

   * The strategy =#bar= introduces a break point =bar=. If evaluation
     reaches this break point, then a break shell will be opened. You
     can inspect the state of the program in this break shell and
     continue evaluation using =:continue=.

---+++ Using the Stratego Library

In some parts of this assignment, you are allowed to use the Stratego
Library. The library contains many useful strategies for io, list
processing, traversals, and so on. API and source documentation of the
Stratego Library is available online (see the navigation bar).

---++ Pattern Matching and Strategies

Create a new Stratego module =pt2.str= based on the previously given
template and define the following strategies. Please follow the
suggested naming suggestions (=exc-x=). Prefix _all_ your own
strategies, including auxiliary ones, with =exc=.

Most of the exercises are examples of bug pattern that many bug
detection tools will support. It's interesting to see how easy these
bug detections are to implement in a language that supports pattern
matching.

In this part of the assignment, you are not allowed to use
congruences, generic traversals, or library strategies, unless
explicitly mentioned.

---+++ Find Control-flow Statements (exc-1)

Implement a strategy that succeeds if the _current term_ is a Java
control-flow statement, such as the if statement, for and while
loop. Completeness is not important, but support at least 3
constructs.

Parse the inputs using =parse-java -s <nop>BlockStm=

Example:
<verbatim>
echo "while(true) doFoo();" | parse-java -s BlockStm | stratego-shell --cmd 'import pt2;; exc-1'
</verbatim>

The strategy should fail for non control-flow statements.

---+++ Find Empty If Statements (exc-2)

Implement a strategy that succeeds if it is applied to an =if=
statement that has no statements (i.e. the empty statement) in its then or else branch (for
example =if(x);=). Usually, this indicates a bug.

---+++ Find Equality Check of True (exc-3)

Implement a strategy that succeeds if the current term is an equality
operator where one of the operands is the literal =true=. Equality
comparison to =true= is usually considered poor style.

Parse the inputs using =parse-java -s Expr=

---+++ Remove Equality Check of True (exc-4)

Implement rewrite rules that remove the equality check to true. So,
the comparison of an expression to true should be rewritten to the
expression itself. Apply the rewrite rules in the strategy =exc-4=,
and make it succeed in all cases.

Again, parse the inputs using =parse-java -s Expr=

---+++ Find Control-flow Statements without Braces (exc-5)

Implement a strategy that succeeds if the current term is Java

control-flow statement, where one of the statements of control-flow is
not a block. For example, it should succeed for the Java statement
=if(x) return y;=, but should fail for the Java statement =if(x) { return y; }=.
Again, completeness is not important, but at least support
a few different control-flow statements.

Note that you can give all rules the same name, but you can also use
different names and combine them yourself with the choice operator.

Parse the inputs using =parse-java -s <nop>BlockStm=

---+++ Introduce Braces for Control-flow Statements (exc-6)

Implement a set of conditional rewrite rules that introduce blocks in
the branches control-flow statements, but only if the blocks are
missing. Cover a few different control-flow statements. Again, define
the rules separately and try to apply them in exc-6.

Parse the inputs using =parse-java -s <nop>BlockStm=

---+++ Find Self Assignment (exc-7)

Implement a strategy that succeeds if the current term is an
expression that is a self-assignment, i.e. the left-hand side is
identical to the right-hand side. Self-assignment is a common bug in
constructors and setter methods.

Parse the inputs using =parse-java -s <nop>Expr=

---+++ Invert .equals Constant (exc-8)

For invocations of the =equals= method that involve a string literal,
it is often a good idea to have the string literal on the left-hand
side and not as the argument of the invocation. This will more
gracefully handle the case where the other expression is =null=.

Define a conditional rewrite rule that rewrites such comparisons, but
only if just one of the expressions is a literal. Example:
=bar.equals("foo")= should be rewritten to ="foo".equals(bar)=.

It is ok to assume that the =MethodName(<nop>AmbName(Id("?"))= is a
variable, since we cannot apply disambiguation yet: for
disambiguation, you need to have a full compilation unit, and for
transforming a compilation unit we need traversals.

Try to apply the rewrite rule in the strategy =exc-8=

Parse the inputs using =parse-java -s Expr=

---+++ Invert If Not (exc-9)

Implement a rewrite rule that swaps the branches of an if statement if
the conditional is an inequality check. Of course, you also need to
change the inequality conditional to an equality. Again, invoke the
rewrite rule from =exc-9=.

Example:
<verbatim>
if(x != y)
  doSomething();
else
  doSomethingElse();
</verbatim>

should be rewritten to:

<verbatim>
if(x == y)
  doSomethingElse();
else
  doSomething();
</verbatim>

Define a similar rule for the not operator:
<verbatim>
if(!x)
  doSomething();
else
  doSomethingElse();
</verbatim>

should be rewritten to:

<verbatim>
if(x)
  doSomethingElse();
else
  doSomething();
</verbatim>

---+++ Get Last Statement of Method (exc-10)

Define a strategy that returns the last statement of a method. For
example, if applied to =void foo() { bar(); return x; }= the strategy
should return =return x;=.

The strategy must be defined using a single pattern match, so you are
not allowed to use composition operators (sequential, or
whatever). But, you are allowed to define an auxiliary strategy for
getting the last element of the list of statements.

Parse the input, which is a method declaration, using the start symbol
=ClassBodyDec=.

---+++ Apply First (exc-11)

Define a strategy that applies a strategy parameter =s= to the first
term of a list for which =s= succeeds. The strategy should fail if the
argument cannot be applied to any of the elements. For example,
=exc-apply-first(\ 1 -> 4 \)= applied to =[3, 2, 1, 2, 3, 1]= should
return =[3, 2, 4, 2, 3, 1]=.

Apply the strategy to a small example in =exc-11=.

---+++ Empty Catch Clause (exc-12)

Define a strategy that if applied to a Java statement succeeds if the
statement is a try-catch block where one or more of the catch clauses
is empty. Of course, defining an empty catch clause is bad style. Most
bug detection tools support these checks.

Note that you can use the =exc-apply-first= strategy for this. Check
that you solution can handle empty catches in a =try-catch-finally=.

---+++ Introduce Print Stack Trace (exc-13)

Implement a strategy that inserts prints of the stack trace of an
exception in these empty catch clauses. This is done by invoking the
=printStackTrace= method of the exception. Write a separate rule for
introducing the print statement in a catch clause. Invoke this rule
from your strategy.

It's allowed to use the standard =map= strategy in this exercise.

---+++ Resolve Method Constructor Confusion (exc-14)

Another common mistake in Java code is to define a return type in
front of a constructor, which means that it becomes a method. These
methods can be recognized by their name, which is the same as the
class in which they are defined.

Use the =exc-apply-first= strategy to implement a strategy that
rewrites the first wrong method declaration of a class to a
constructor declaration. Of course, you define a rewrite rule for the
actual rewrite to the method. This rule has to be parameterized with
the name of the class. Example:

<verbatim>
public class Foo {
  int x;

  void Foo() {
    x = 0;
  }

  void bar() {
  }
}
</verbatim>

should be rewritten to:

<verbatim>
public class Foo {
  int x;

  Foo() {
    x = 0;
  }

  void bar() {
  }
}
</verbatim>

It is important that the strategy fails if there is no wrong method
declaration. Next, use the standard =repeat= strategy to rewrite _all_
wrong method declarations of a type declaration.

Parse the inputs with =parse-java -s <nop>TypeDec=.

---+++ Semantics of Choice and Guarded Choice (exc-15)

Find an example that shows the semantic difference between =s1; s2 <+ s3=
(left choice) and =s1 < s2 + s3= (conditional choice). You don't
have to use Java in this example: just use integers, lists, or
whatever you want.

---++ Traversals

---+++ Congruences

In the following two exercises you are not allowed to use generic
traversals. All traversing code must be implemented using congruences.

However, we advice you to reuse the basic elements of a traversal. So,
you can define traversal primitives =all-Java=, =some-Java=, and
=one-Java= (if necessary) specific for Java constructs and define the
traversal strategies by composing them.

---++++ Recursive Rewriting (=exc-16=)

In the first part of this assignment you have defined a number of
rewrite rules that apply rewritings to the current term. In this
exercise, you apply these rewriting recursively all over the tree. For
this, define a congruence-based traversal that traverses a compilation
unit by descending into the statements used in the class. Support a
reasonable set of class body declarations and control-flow statements,
but don't spend too much time on this. The point is to illustrate a
congruence-based traversal and how the transformations are applied
during the traversal, not to deliver a product.

Note that because you have developed the rewrite rules first, you have
been forced to cleanly separate the traversal strategy from the
rewrite rules. This is good style. If you have to refactor the
previously defined rules (for example because you have defined the
rewriting entirely in a single strategy), then just do this and
remember why the rule was not reusable in this strategy.

Apply all your rewritings:
   * Remove Equality Check of True
   * Introduce Braces for Control-flow Statements
   * Invert .equals Constant
   * Invert If Not
   * Introduce Print Stack Trace
   * Resolve Method Constructor Confusion

Note that some rewrite rules apply to the same language
construct. Solve this in you rewriting strategy: don't hack this into
the reusable traversal primitives that you have defined. You don't
want to force all strategies to repeat the application of the rewrite
rules.

An example, illustrating some (not all!) of these problems:
<verbatim>
public class Foo
{
  void f()
  {
    if(x != true)
      doFoo();
    else
    {
      try
      {
        doBar();
      }
      catch(Exception exc)
      {
      }
    }
  }

  void Foo(String x)
  {
    if(x.equals("Blaat"))
      this.x = x;
  }
}
</verbatim>

<verbatim>
$ parse-java -i Foo.java | ./pt2 | pp-java
public class Foo
{
  void f()
  {
    if(x)
    {
      try
      {
        doBar();
      }
      catch(Exception exc)
      {
        exc.printStackTrace();
      }
    }
    else
    {
      doFoo();
    }
  }

  Foo (String x)
  {
    if("Blaat".equals(x))
    {
      this.x = x;
    }
  }
}
</verbatim>

---++++ Replace Symbolic Constant (=exc-17=)

Sloppy user-interface code based on the Java =BorderLayout= sometimes
uses string literals to define the position of a component. Of course,
the constants of the <nop>BorderLayout should be used for this. For
example, =p.add(component, "North")= should be written as
=p.add(component, <nop>BorderLayout.NORTH)=.

First, define a rewrite rule that if applied to a type-checked
expression, rewrites these sloppy invocations of the =add= method of
javax.swing.JPanel to use these <nop>BorderLayout constants. Use the
<nop>DeclaringClass annotation of the expression to figure out if you are
dealing with the right =add= method.

Next, apply this rewrite rule recursively to a Java program by reusing
the congruence-based traversal strategy of the previous exercise.

For this example you have to apply the dryad-front type checker
instead of just parse-java. Add the following code to your module to
make the <nop>DeclaringClass constructor available:

<verbatim>
signature
  constructors
    DeclaringClass : Type -> Attribute
    
strategies

  declaring-class-attr = 
    ?_{a*}
    ; <fetch-elem(?DeclaringClass(<id>))> a*
</verbatim>

Example:
<verbatim>
import java.awt.BorderLayout;
import javax.swing.*;

public class Gui 
{
  public static JPanel gui()
  {
    JPanel p = new JPanel(new BorderLayout(10, 10));
    p.add(new JLabel("Enter something:"), "North");
    p.add(new JScrollPane(new JTextArea(20, 20)), "Center");
    return p;
  }

  public static void main(String[] ps)
  {
    JFrame frame = new JFrame();
    frame.getContentPane().add(gui());
    frame.pack();
    frame.setVisible(true);
  }
}
</verbatim>

<verbatim>
$ dryad-front --tc on -i Gui.java | ./pt2 | pp-java
import java.awt.BorderLayout;
import javax.swing.*;

public class Gui
{
  public static javax.swing.JPanel gui()
  {
    javax.swing.JPanel p = new javax.swing.JPanel(new java.awt.BorderLayout(10, 10));
    p.add(new javax.swing.JLabel("Enter something:"), BorderLayout.NORTH);
    p.add(new javax.swing.JScrollPane(new javax.swing.JTextArea(20, 20)), BorderLayout.CENTER);
    return p;
  }

  public static void main(java.lang.String[] ps)
  {
    javax.swing.JFrame frame = new javax.swing.JFrame();
    frame.getContentPane().add(gui());
    frame.pack();
    frame.setVisible(true);
  }
}
</verbatim>

---+++ Generic Traversals (=exc-18= and =exc-19=)

Redefine the two previous exercises using generic traversals. Try to
find out if you need a single-pass, multi-pass, exhaustive, topdown,
or bottomup rewriting strategy. If you have figured this out, then
don't fix your previous congruence-based traversal if you find a
problematic case that you could not handle earlier.

Try the effect of some different traversals, even if you see the
solution immediately.
 
---+++ Mixing Generic and Data Type Specific Traversals

The traversal you've implemented in the previous exercises are not
that common in real program transformation problems. Instead of doing
the complete traversal specific for a certain data type or completely
generic, the traversal is often a mixture of a generic traversal and
some data type specific cases.

---++++ Find Return in Finally Clause (=exc-20=)

A return statement in a =finally= clause should be avoid, because this
return statement can completely change the original result of the
method: a return or a thrown exception in the =try= part. This is not
the purpose of a finally clause, therefore compilers often warn about
this:

<verbatim>
class Fred
{
  boolean error;

  int g()
  {
    if(error)
      throw new IllegalStateException();
    else
      return 4;
  }

  int f()
  {
    try
    {
      return g();
    }
    finally
    {
      return 5;
    }
  }
}
</verbatim>

<verbatim>
$ javac Fred.java -Xlint
Fred.java:22: warning: [finally] finally clause cannot complete normally
    }
    ^
1 warning
</verbatim>

For this exercise, write an transformation that annotates these
questionable return statements with the string "Error". This is not
entirely trivial. Thanks to local and anonymous class declarations,
not every return statement in a finally clause is incorrect. So, you
need to handle these constructs in a special way.

It is useful to think about this transformation as format
checking. For this problem, a Java source file should be written in
two different languages: in a finally clause, the allowed language is
a subset of the complete Java language: no return statements are
allowed. If we encounter a local or anonymous class declaration, then
we switch back to the complete language.

A useful pattern for the implementation of these problems is to have
two strategies, one for the complete language and one for the
subset. In both strategies, specific cases are handled and maybe the
context is switched to the other strategy. By default, they just
traverse.

You need about 10 lines of code for this, so if your strategy is much
longer, then you're doing something wrong ;)

Example:
<verbatim>
class Fred
{
  int f()
  {
    try
    {
      return g();
    }
    finally
    {
      class Bla
      { 
        void test()
        {
          return 6;
        }
      }
      return 5;
    }
  }
}
</verbatim>

<verbatim>
$ parse-java -i Fred.java | ./pt2 | pp-aterm
...
  [ Try(
      Block(
        [Return(Some(Invoke(Method(MethodName(Id("g"))), [])))]
      )
    , []
    , Block(
        [ ClassDecStm(
            ClassDec(
              ClassDecHead([], Id("Bla"), None, None, None)
            , ClassBody(
                [ MethodDec(
                    MethodDecHead([], None, Void, Id("test"), [], None)
                  , Block([Return(Some(Lit(Deci("6"))))])
                  )
                ]
              )
            )
          )
        , Return(Some(Lit(Deci("5")))){"Error"}
        ]
      )
    )
...
</verbatim>

---++ Submission

Pack your Stratego modules in a =.tar.gz= or =.zip= file and send your
solution by email to =martin@cs.uu.nl=. The same day, you will get a
short notification that I've received your solution. If you don't get
this reply, then please contact me.

---++ Questions

After the lab session you can still send questions to =pt@cs.uu.nl= or
join [[irc://irc.freenode.com/#stratego][#stratego]] at
=irc.freenode.com=.