This week you will implement type checking for Amy. The goal of type checking is to prevent certain errors based on the kind or shape of values that the program is manipulating. E.g. we should prevent an integer from being added to a boolean value.
Type checking is the last stage of the compiler frontend. Every program that reaches the end of this stage without an error is correct, and every program that does not is wrong. We are finally ready to interpret the program or compile it to binary code!
Typing rules for Amy are presented in detail in the Amy specification. Make sure to check correct typing for all expressions and patterns.
This assignment focuses on the file
TypeChecker.scala. As usual, the skeleton and helper methods is given to you, and you have to complete the missing parts of the algorithm. In the case of type checking, this consists of implementing typing for all expressions.
The algorithm you will implement traverses the expression and checks each subexpression for correctness in a prefix ways as follows:
- First, you need to recursively call the function on subexpressions, passing the correct
expectedtype. E.g. for an addition, both operands should be integers. Pass
Noneif you cannot restrict the type.
- Then, you need to check the type of the current expression against the expected one. Look at the
checkmethod for help. You then need to return the type of the expression.
- Additionally, when you encounter a new variable or parameter, you have to add it to the symbol table so you can find its type later.
Here are some additional notes:
- There is a type in the tree module called
NothingType, which is not meant as a type that any expression could have in Amy, but we will use it temporarily to denote the type of expressions like
error()which can take any type.
- Sometimes you cannot directly restrict the type of a subexpression, like the branches of equality, which can be anything (as long as they are the same). In those cases, you need to check that the types of the subexpressions are compatible after traversing them, i.e. if they are equal or one of them is Nothing. Use the provided
- As usual, you can check against our reference compiler. Use the
-interpretoption. Make sure you have the latest version!
As usual, merge the stubs of the parser into your main branch by typing
git fetch –all
git merge origin/Lab05
origin is the name of your remote repository).
The structure of your project
src directory should be as following:
amyc ├── Main.scala (updated) │ ├── analyzer │ ├── SymbolTable.scala │ ├── NameAnalyzer.scala │ └── TypeChecker.scala (new) │ ├── ast │ ├── Identifier.scala │ ├── Printer.scala │ └── TreeModule.scala │ ├── interpreter │ └── Interpreter.scala │ ├── parsing │ ├── ASTConstructor.scala │ ├── ASTConstructorLL1.scala │ ├── Parser.scala) │ ├── Lexer.scala │ └── Tokens.scala │ └── utils ├── AmycFatalError.scala ├── Context.scala ├── Document.scala ├── Pipeline.scala ├── Position.scala ├── Reporter.scala └── UniqueCounter.scala
You can deliver this assignment after the midterm.
Deadline: Tuesday 28 November, 23:59
IMPORTANT: Please remember to deliver the commit you want us to grade under https://larasrv13.epfl.ch/clp17/deliverables