Start by setting up your environment as described. Familiarize yourself with the Tool Programming Language and the Tool Compiler Project.

Write two example Tool programs each and make sure you can compile them using the Tool Reference Compiler. Please be creative when writing your programs. We don't need 5 versions of a program computing the Fibonacci sequence. The examples at the end of the Tool page should convince you that you can write interesting programs.

Remember that you will use these programs in the remaining of the semester to test your compiler, so don't make them too trivial! Try to test many features of the language.

The main task of the first lab is to write an interpreter for Tool.

The way to execute programs you have mostly seen so far is compilation to some kind of low-level code (bytecode for a Virtual Machine, or native binary code). The other way to execute programs is interpretation. According to Wikipedia, “an interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without previously compiling them into a machine language program”. In other words, your interpreter is supposed to directly look at the code and perform its meaning. For example, when encountering a 'println' statement, your interpreter should print its argument on the standard output, and when encountering an assignment statement like “x = 42”, it should store in its memory that the variable x now has the value 42. We will sometimes call the interpreter an evaluator.

The skeleton of the assignment is provided by us in three files:

- The Main.scala source file

- The Evaluator.scala source file and

- the toolc-frontend_2.11-3.0.jar bytecode file, which is located under lib/ .

Now let's look into the code in a little more detail.

In Main.scala, take a look at the main method, which is the entry point to your program. After processing the command line arguments of the interpreter, the main method calls a Parser, which will parse the source program into an abstract syntax tree (AST), initializes an Evaluator, and calls its .eval method, which will interpret the parsed program. The implementation of the parser is given to you in compiled form, because you will need to write your own version in the next assignments.

So what is this AST we've mentioned? For the computer to “understand” the meaning of a program, it first has to transform it from source (text) form to a more convenient form, which we call an abstract syntax tree. The AST abstracts away uninteresting things of the program (e.g. parentheses, whitespace, operator precedence…) and keeps the essential structure of the program.

In Scala, we represent the AST as a tree-form object. The tree has different types of nodes, each one representing a different programming structure. The types of nodes are of course represented as different classes, which all inherit from a class called Tree. Conveniently enough, the classes correspond pretty much one-to-one to the rules of the BNF grammar given to you in the standard of the language. E.g. in the language standard we read that the main object looks as follows:

MainObject ::= program Identifier { ( Statement )* }

and indeed in the implementation we find a class

case class MainObject(id: Identifier, stats: List[StatTree]) extends Tree

You can find the API of the AST here.

Now let's delve into Evaluator. This file is incomplete and it is your task for this week to fill it up! The evaluator has two basic methods: evalStatement and evalExpr. You will notice that the evalStatement method has return type Unit. This makes sense: We do not expect from a statement to return a value, just to produce some side-effects, like assigning a value to a variable or printing on the screen. evalExpr on the other hand does return an object of type Value.

Value is inherited by classes which represent the different types of values present in Tool (ints, booleans, arrays, objects and strings). Whereas ints, booleans and strings are represented by simple wrapper classes, the case is more complicated for arrays and objects. ArrayValue's contain the array they represent, along with helper methods to read from and store to the array. Object values contain their defining object class, and methods to set and retrieve the object's fields. When you initialize an ObjectValue you have to declare all the fields of its class to be able to look them up later.

The entry point of the Evaluator is the eval() method, which just looks into the main object's main method and executes all its statements.

You will see that both eval* methods take an implicit EvaluationContext as parameter. In Scala, if you invoke a method with an implicit parameter, the compiler will look in the scope of this method invocation for objects of the same type and pass them to the method automatically for you; this way, you don't have to pass the same EvaluationContext manually from one call to the next! Careful however!!! Sometimes you will need to pass a different context, and if you forget to, Scala will silently pass the one you already defined.

EvaluationContext keeps track of information you need during the evaluation, that is, the values of all variables in scope and the current object (this). The MainContext just makes sure you fail if you try to access any of these things from the main object (see the language standard). Think carefully when you need to declare or set the value for variables in the context, or create a new context altogether (hint: entering a method is the most challenging case!).

Finally, let's look at a small example. We want to interpret equality of two expressions. How would we do this? In the language standard we read that equality is defined as value equality for integers and booleans, and reference equity for every other type (e.g. two strings are not equal if they are not the actual same object in memory, even if they contain the same characters). evalExpr does exactly that: it evaluates both sides of equality, and if it encounters two integers or two booleans it calls Scala value equality (==), otherwise it calls reference equality (eq). Finally, because it needs to return an object of type Value, it wraps its boolean result in a BoolValue class.

A few final notes:

• You can print program output straight to the console.
• In case you encounter an uninitialized field, it is easiest to just fail on the spot.
• You can assume the input programs are correct:
  1. no undefined variables/fields being accessed
  2. the program type-checks
  3. referenced methods and classes are correctly defined
  4. The main object does not try to access local variables or methods, or this.
  5. …

Your interpreter is free to crash with runtime errors in case any of the above is violated. It should not crash on valid programs. To crash the evaluator, please use the fatal method which is imported from ctx.reporter.

For this lab, we provide you with a compiled version of the Trees, as well as a functioning parser. You have to complete the implementation of your Evaluator.

If you have followed Labs Setup, you should have a working Eclipse project with a stub implementation, containing the following files:

• src/main/scala/toolc/eval/Evaluator.scala contains a partially implemented interpreter/evaluator
• src/main/scala/toolc/Main.scala contains the main method which runs the interpreter on a given input file
• The examples directory contains some example programs on which you can try your implementation.
• lib/toolc-parser_2.11-3.0.jar contains a compiled lexer and parser, as well as all the trees.

Notice that all classes are in a toolc package. toolc.Main is the entry point.

You will have to complete the implementation of two methods: evalExpr and evalStmt. Whenever the program contains ???, you should replace it with a proper implementation. A few examples are already implemented to help you get started.

On examples/Pi.tool for instance, your interpreter should produce the following output:

  First method
  ************
  0/1 ~= 0.0000000000
  47/15 ~= 3.1333333333
  102913/32760 ~= 3.1414224664
  5454389/1739700 ~= 3.1352468816
  
  Second method
  *************
  0.0000000000
  3.1333333333
  3.1414224663
  3.1415873902
  3.1415924574
  3.1415956774
  3.1416184816
  3.1416185815
  Ok

You are given 2 weeks for this assignment.

Deadline: Tuesday, Oct 4th, 23.59pm.

You must use the interface on http://larasrv09.epfl.ch:9000/clp16/repository as follows:

1. Click on the “Deliverables” tab
2. Click “Deliver this version” on the commit corresponding to the version of your code you want to submit

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