This week you will build an interpreter in Scala for the while language described in Lecture 01. You don't have to write a lexer/parser, as you will instead work directly on the Abstract Syntax Tree (AST) representation of programs. The language is slightly different here as we have added for loops.

We provide you with the Scala classes for the AST node structure, a pretty-printer for them, as well as two example programs in the form of Scala code representing their trees. We also give you a minimal skeleton that you must use for the interpreter, and a testing routine that you should also not modify.

Implement the apply method in the Interpreter object so that it “runs” the program passed to it. Print the output straight to the console. Add as many helper methods and fields as you need in the same file. Keep the following in mind:

• Variables default to 0 when they are read before they are assigned
• When integers represent truth values, 0 is false and any other value is true (including negative ones)
• Your interpreter should run each test case independently from the others (ie. when running test A then test B, test A should have no influence on the output for test B)

The AST class hierarchy we give you can represent both while and for loops, and your interpreter should work on both. However it is sometimes desirable in a compiler to reduce the number of different tree node types by merging constructs which are semantically equivalent, while their concrete syntax is different. This can reduce the amount of work for later phases (for example, it could be simpler to write code to optimize only one type of loops).

Implement the apply method in the TreeSimplifier object so that it replaces all for loops by equivalent subtrees using while loops. Again, add as many methods and members as you wish, but keep them in the same file.

Your interpreter should of course produce the same result whether the programs are simplified or not.

• Tree.scala contains the AST class hierarchy and the pretty-printer
• Interpreter.scala contains the skeleton for the interpreter
• Programs.scala contains example programs written as ASTs
• TreeSimplifier.scala contains the stub for the for-elimination function
• Main.scala contains the main method which runs the interpreter on all test cases

Notice that all classes are in a whilelang package, so you'll need to create one for them to work. Run whilelang.Main to test your interpreter on the programs from Programs.scala.

We suggest you use the Scala Plugin for Eclipse for your development.

If you don't know Scala yet, this resource may be useful: Learning Scala.

You must upload to moodle as a zip file your modified Intepreter.scala and TreeSimplifier.scala files before Tuesday, Sept. 22th, 23.55pm. If you have written more test programs yourself (which we strongly encourage), you can attach your modified Programs.scala file as well. Please don't send any other file however, as your interpreter will have to work with the provided classes. Note that neither the quality nor the quantity of additional test cases play any role in the grading.

This first assignment is not part of the semester-long project that we will start next week. This first lab is to be done individually, while the remaining labs will done in groups of two.

• Scala documentation and dowmload: http://www.scala-lang.org/
• End of Chapter 1 in the Tiger Book presents a similar problem for another mini-language. A comparison of the implementation of ASTs in Java (as shown in the book) and Scala is instructive.