Assignment Patterns And Strategies

Pt04
%TOC%

---++ Using The Stratego Shell

In this assignment you will learn more about the Stratego language by
using 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>

For example, you can close the Stratego Shell with =:quit=, =:exit= or
=:q=.

---+++ Introspection and Debugging

   * =: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 openend. You
     can inspect the state of the program in this break shell and
     continue evaluation using =:continue=.

---+++ Stratego Shell Scripts

You can store a sequence of Stratego Shell commands in a Stratego
Shell script. In a Stratego Shell script the commands must be
terminated by =;;=. Stratego Shell scripts used the file extension
=.strs=. You can run a Stratego Shell script using:

<verbatim>
$ stratego-shell --script file.strs
</verbatim>

The Stratego Shell can be included in a pipe. In this assigment we
will use the Tiger language, so you can use =parse-tiger= to parse
input program and then pipe the result into the Stratego Shell.

<verbatim>
$ echo "a + 2 * c" | parse-tiger | stratego-shell --script file.strs
</verbatim>

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

<verbatim>
$ echo "a + 2 * c" | parse-tiger | stratego-shell
stratego> :show
Plus(Var("a"),Times(Int("2"),Var("c")))
</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>

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

---++ Try Examples of the Slides

First of all, try the examples of the slides. Change the strategies to
test different variants. You don't need to submit anything about your
experiments, but playing a bit the various constructs is an effective
way of learning the language.

---++ Small Exercises

Implement the following small exercises as a series of commands in a
Stratego Shell script =part1.strs=.

Feel free to use separate Stratego modules for rewrite rules or
strategies. You can import them into your shell script using the
=import= command. In these modules, you have to import the Tiger
module. In the Stratego Shell itself this is not necessary. The
easiest way to get this working is to copy
=~/.nix-profile/share/tiger-front/Tiger.rtree= to your working
directory. The full syntax definition of Tiger is available in
=~/.nix-profile/share/sdf/tiger-front/= (=Tiger.def= or the separate
=.sdf= modules).

   * Implement a strategy that succeeds if the current term is a Tiger
     binary operator arithmetic expression (=Plus=, =Times=
     etc.). Completeness is not important, but support at least 3
     constructs.

   * Implement a strategy that succeeds if the current term is a Tiger
     function call with two arguments and at least one of the
     arguments is an assignment.

   * In a single strategy (no rules and no sequential composition),
     change the current term from a Tiger function call to its first
     argument. For example, the strategy should return =Int("1")= if applied to the Tiger call =Call(Var("foo"), [Int("1"), Int("2")])=

   * Same for the tail of the list of arguments (all arguments except the first). Thus, the result of this strategy is a list. For the previous example, the strategy should return =[Int("2")]=.

   * 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 Tiger in this example.

   * Define a strategy that returns the last term of a list. For example, =last= applied to =[1, 2, 3]= returns =3=.

   * Define a strategy that removes all terms from the beginning of a list that can be applied to a strategy to parameter =s=. For example, =remove-from-start(?1)= applied to =[1, 1, 2]= should return =[2]=. =remove-from-start(?t)= applied to =[2, 2, 3, 4]= should return =[3, 4]=.

   * 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, =apply-first(\ 1 -> 4 \)= applied to =[3, 2, 1, 2, 3]= should return =[3, 2, 4, 2, 3]=.

   * Use the =apply-first= strategy you just defined to get the first assignment from the actual parameters of a Tiger function call. Also, rewrite the assignment in this list of expressions to the left-hand-side. The final result should be a =Seq= of the new function call and the assignment. For example, the Tiger expression (for convenience written in concrete syntax) 
<verbatim>
f(1, x := 2, 3)
</verbatim>
should be rewritten to 
<verbatim>
( x := 2
; f(1, x, 3)
)
</verbatim>
Of course, your strategy should work on plain abstract syntax.

---++ Recursive Strategies (a first look at traversals)

---+++ Collecting Variables

Implement a strategy that collects all variables that are used in a
Tiger expression. The result must be a list of the variables in the
expression. You should support =Plus=, =Times=, =Int=, and =Var=.

In this exercise, you can use rewrite rules that produce a list of
variables. Recursively apply the rules to produce the result for the
subterms.

You are allowed to import the module =list= in this exercise, since
you will need the =conc= strategy, which concats a tuple of two lists
into a singe list. Try to use this strategy first. Functional
programming geeks can try to avoid the =conc= invocations by using an
accumulator.

Invoke your implementation from a Stratego Shell script
=part2.strs=. Again, feel free to use separate Stratego modules.

---+++ Expression Evaluator

Implement an evaluator for simple Tiger expressions (=Plus=, =Times=,
=Int=). You can use rewrite rules to evaluate the expressions. Invoke
you evaluator in a Stratego Shell script =part3.strs=.

You can choose from several different styles to implement your
evaluator. The first option is to keep your rewrite rules clean by
implementing a separate strategy that in a bottomup fashion applies
the rewrite rule (i.e. first apply the rule to the subterms, then to
the term itself). An alternative solution is to do recursive calls in
the rewrite rules themselves.

You need to import the module =integers= to be able to use some
strategies that you need in this exercise:

   * =string-to-int= converts a string to an int
   * =int-to-string= converts an int to a string
   * =add= adds two integers in a tuple
   * =mul= multiplies two integers in a tuple

---++ Submission

Pack your Stratego Shell scripts and Stratego modules in a =.tar.gz=
or =.zip= file and send your solution by email to =martin@cs.uu.nl= at
least 15 minutes before the lecture of Thursday, i.e. 12:45. 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=.