This week you will build an interpreter in Scala for the while language. We provide you with a parser for the language, and you will thus work directly on the Abstract Syntax Tree (AST) representation of programs. The grammar of this very simple language is given by:

• <IDENTIFIER> represents a sequence of letters, digits and underscores, starting with a letter and which is not a keyword. Identifiers are case-sensitive.
• <INTEGER_LITERAL> represents a sequence of digits, with no leading zeros
• <STRING_LITERAL> represents a sequence of arbitrary characters, except new lines and ".
• <EOF> represents the special end-of-file character

Note that variables are always of type integer. When an integer is used as a boolean, any non-zero value evaluates to true and zero evaluates to false. Operators that return truth values always return 0 or 1 (ie. <, ==, &&, etc.).

We provide you with Scala classes for the AST node structure (note that their names match the names of the non-terminals), a pretty-printer for them, as well as some example programs. 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). Operators that return truth values return 0 or 1.
• 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).
• There is no notion of variable scope.

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 that 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.

You can download the stub for your implementation here: labs01.zip. It contains the following files:

• whilelang/Tree.scala contains the AST class hierarchy and the pretty-printer
• whilelang/Interpreter.scala contains a skeleton for the interpreter
• whilelang/TreeSimplifier.scala contains a stub for the for-elimination function
• whilelang/Main.scala contains the main method which runs the interpreter on a given input file
• The progs directory contains some example programs on which you can try your implementation.
• lib/whilelang-parser.jar contains the parser for the while language.

Notice that all classes are in a whilelang package. whilelang.Main is the entry point. See below on how to run the program.

We suggest you use sbt for the development. sbt is a build tool similar in essence to make or ant, but target specifically at compiling Scala projects. The archive we give you contains an sbt project definition (in the project directory). If you do not plan to use sbt, simply delete or ignore this directory. If you decide to use sbt, you can (once you have installed it) type

sbt compile

to compile your code. To try your interpreter on an example, you can run

sbt "run progs/collatz.while"

for instance. Alternatively, you can run

sbt script

to generate a Shell script called whilelang that you can then use as

./whilelang progs/collatz.while

Note that there's an important difference between these two approaches. In the first case, you're using Scala from sbt (you'll see that sbt downloads a copy of Scala the first time you run it), while in the second case you're using the version of Scala installed on your machine. For the script to work, you thus need to have installed Scala 2.8 on your machine alongside sbt.

sbt can also be used as an environment. One neat feature is that you can tell sbt to recompile your project each time you changed a file. To do this, run

sbt

then, from the environment, type

~compile

This will wait for changes in the source files and recompile as needed. We suggest you read the sbt documentation to read about more features.

You must upload to Moodle as a zip file your modified Intepreter.scala and TreeSimplifier.scala files before Tuesday, Oct. 5th, 23.55pm. If you have written more test programs yourself (which we strongly encourage), you can put your programs in the archive 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. All labs are to be 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.