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.

Deadline: Tuesday, Sep. 27th, 23.59pm.

You must use the interface on http://larasrv05.epfl.ch as follows:

1. Click on the “Deliverables” tab
2. Click “Deliver this version” on the corresponding commit
3. In the dialog, make sure “Lab01 - While Language” is selected, write a comment if you want
4. Click on “Create Deliverable”

To compile and run your submission, we will use our original files together with your Interpreter.scala and TreeSimplifier.scala. Once a deliverable is created you can look at the files we will use by clicking on the “See Files” button. Make sure you only modified the files listed in bold as the other files will not be considered!

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.