In this lab assignment, you will get to know the Amy language and implement an interpreter for it.

Setup

Download the project files from this link and decompress them.

This zip file contains a folder with the Scala 3 project that you will be working on in this lab. In particular, it contains the bare-bone structure of the interpreter and a compiled version of the Amy compiler’s frontend (lexer, parser, namer, typer) which are needed before your interpreter can be called.

You should be able to compile the project successfully by typing sbt in the console and then typing compile.

You can also try the commands test and run library/Std.scala examples/Hello.scala, which will initially crash with a scala.NotImplementedError exception, as the project is still missing your interpreter implementation.

Part 1: Your first Amy programs

Write two example Amy programs and make sure you can compile them using the Amy Reference Compiler. Put them under /examples. Please be creative when writing your programs: they should be nontrivial and not reproduce the functionality of the examples in the /library and /examples directories of the repository. Of course you are welcome to browse these directories for inspiration.

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.

If you have questions about how a feature of Amy works, you can always look at the Amy Specification. It’s a good idea to keep a local copy of this document handy – it will be your reference for whenever you are asked to implement an aspect of the Amy language throughout this semester.

Type check examples

You can use the provided Frontend to type check your programs. To do so, run the provided bash script:

./amytc.sh examples/your_program.amy

You can also run the type checker directly from sbt:

  $ sbt
  > run library/Std.amy examples/Hello.amy --type-check
  Hello world!

This will run the compiler frontend up to type checking and report either Type checking successful! or an error message. If you get an error message, you should fix the error before moving on to the next step.

Please examine the bash script amytc.sh and its comments in your editor to understand how it works. Do not modify it.

Troubleshooting

Part 2: An Interpreter for Amy

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

Interpreters

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 such as Java’s; native binary code in case of languages such as C). An alternative 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 interpret its meaning. For example, when encountering a call to the ‘printString’ function, your interpreter should print its argument on the standard output.

The general structure of the Interpreter

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

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 creates a Pipeline, which contains the different stages of the compiler (more on it in later assignments). The Pipeline will first call the Amy frontend, which will parse the source program into an abstract syntax tree (AST) and check it for correctness according to the Amy specification, and then passes the result to the Interpreter. The implementation of the frontend is given to you in compiled form (it lives in the amyc-frontend-1.7.jar file), because you will need to write your own version in the next assignments. Note: You are only allowed to use this binary code to link against your interpreter.

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 in the language specification. E.g. in the language spec we read that a module looks as follows:

Module ::= **object** Id Definition* Expr? **end** Id

and indeed in the implementation we find a class

case class ModuleDef(name: Identifier, defs: List[ClassOrFunDef], optExpr: Option[Expr]) extends Definition

You can find the source code of the AST in src/amyc/ast/TreeModule.scala, in the zip file linked above.

The Interpreter class

Now let’s delve into Interpreter.scala. This file currently only contains a partial implementation, and it is your task for to complete it! The entrypoint into the interpreter is interpret, which takes an expression as input and executes its meaning. The main loop at the end of the class will just take the modules in order and interpret their expression, if present.

interpret returns a Value, which is a type that represents a value that an Amy expression can produce. Value is inherited by classes which represent the different types of values present in Amy (Int, Booleans, Unit, String and ADT values). Value has convenience methods to cast to Int, Boolean and String (as*). Remember we can always call these methods safely when we know the types of an expression (e.g. the operands of an addition), since we know that the program type-checks.

interpret takes an additional implicit parameter as an argument, which is a mapping from variables to values (in the interpreted language). In Scala, when an implicit parameter is expected, the compiler will look in the scope for some binding of the correct type and pass it automatically. This way we do not have to pass the same mapping over and over to all recursive calls to interpret. Be aware, however, that there are some cases when you need to change the locals parameter! Think carefully about when you have to do so. You can explicitly pass implicit parameters with the using keyword. For example:

def f(x: Int)(implicit y: Int) = x + y
f(2)(using 2)

A few final notes:

Implementation skeleton

You will have to complete the interpreter by implementing the missing methods (marked with the placeholder ???).

Testing

When you are done, use sbt to try some of your programs from Part 1:

  $ sbt
  > run library/Std.amy examples/Hello.amy --interpret
  Hello world!

You can also run your interpreter with the amyi.sh script in a similar way as you did with the type checker:

  $ ./amyi.sh examples/Hello.amy
  Hello world!

Note: if you use this method, you have to delete target/scala-<version>/amyc-assembly-1.7.jar before running the script when you modified your interpreter. Otherwise, the script will reuse the previously compiled version of the interpreter and your new modifications would not be taken into account. Therefore this method is more recommended for testing multiple amy programs, rather than testing your interpreter while you are developing it.

There is also testing infrastructure under /test. To add your own tests, you have to add your testcases under /test/resources/interpreter/passing and the expected output under /test/resources/interpreter/outputs. Then, you have to add the name of the new test in InterpreterTests, similarly to the examples given. To allow a test to also use the standard library (e.g., Std.printString), you can copy Std.scala from library/Std.scala to /test/resources/interpreter/passing.

For example, to add a test that expects only “Hello world” to be printed, you can add /test/resources/interpreter/passing/Hello.amy containing:

object Hello
  Std.printString("Hello world")
end Hello

and /test/resources/interpreter/outputs/Hello.txt containing

Hello world

(with a newline in the end!).

You will also have to add a line to /test/scala/amyc/test/InterpreterTests.scala: @Test def testHello = shouldOutput(List("Std", "Hello"), "Hello"). This will pass both files Std.amy and Hello.amy as inputs of the test. When you now run test from sbt, you should see the additional test case (called testHello).

To run the test suites, you can use sbt:

  $ sbt
  > test

Deliverables

You are given 2 weeks for this assignment. Deadline: Wed, Mar 11th, 11pm.

You will need to submit your src/amyc/interpreter/Interpreter.scala file to Canvas – follow this link to the assignment.

Since you will submit a single Scala file, all your changes should be self-contained in that file. To test it, we will replace our own Interpreter.scala file with yours and run the tests on our computer.