Assignment Patterns And Strategies

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.

stratego> :help

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:

$ stratego-shell --script file.strs

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.

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

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:

$ echo "a + 2 * c" | parse-tiger | stratego-shell
stratego> :show
Plus(Var("a"),Times(Int("2"),Var("c")))

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.

stratego> import SmallExercises

Standard library modules can also be included in this way:

stratego> import integers

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)

f(1, x := 2, 3)

should be rewritten to

( x := 2
; f(1, x, 3)
)

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 #stratego at irc.freenode.com.