LARA

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 (4 per group of 2) 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-parser_2.11-2.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 file) 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:

object Identifier { def main ( ) : Unit = { ( 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:

http://lara.epfl.ch/~ekneuss/clp14/toolc-api/#toolc.ast.Trees$

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 straightforwardly represent the different types of values present in Tool (ints, booleans, arrays, objects and strings). 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 an EvaluationContext is passed around during evaluation. 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 MainMethodContext just makes sure you fail if you try to access any of these things from the main method (see the language standard). Make sure you think carefully and update the context correctly, or create a new one, when you encounter a new variable, enter a method etc.

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 couple final notes:

• You can print program output straight to the console.
• 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 method does not define/access variables, and it does not access 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.

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 programs directory contains some example programs on which you can try your implementation.
• lib/toolc-parser_2.11-2.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 programs/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: Wednesday, Sep. 30, 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.