This week you will implement type checking in your Tool compiler. After this step, you will have completed the front-end of your compiler. This means that it will be able to reject all invalid programs, and accept all valid programs. You will then be able to turn these valid inputs into assembly code that runs on the JVM, just like javac and scalac do. Isn't that great? We think it's great.

A valid Tool program has the following properties:

• It follows the Tool concrete syntax.
• It respects all the constraints mentioned in Labs 06.
• Method overriding respects some typing constraints:
  • The overriding method must have exactly as many arguments as the overridden one.
  • The types of the parameters in the overriding and overridden methods must match exactly (no contravariance allowed).
  • The return type must match exactly (no covariance allowed, as opposed to Java, for instance).
• All expressions typecheck and have the expected type (the returned expression matches the declared return type, for instance).
• All statements typecheck.

Your goal in this assignment is to enforce all the constraints not enforced already by the previous phases.

Note: The language and the type rules presented in the course may differ from the rules of Tool. If there are any differences, please use the description on the current page for your implementation, and not the rules in the lecture. Of course, feel free to clarify with us if you have any changes.

The following primary types exist in Tool (note that we prefix them with T to differentiate them from the tree nodes with the same name, for instance):

• TInt
• TBoolean
• TInt[]
• TString ¹⁾

Additionnally, we have object types:

• TClass[name]

We define a subtyping relation on these types. All primary types are subtypes of themselves and of no other type. For instance:

• TInt <: TInt

All object types are subtypes of themselves and the special “Object” object type. The subtyping relation is also transitive.

• TClass[name] <: TClass[name] and TClass[name] <: TClass[Object]
• TClass[B] <: TClass[A] and TClass[C] <: TClass[B] implies TClass[C] <: TClass[A]

With this in mind, we give some of the non-trivial typing constraints. This is naturally not an exhaustive list of what you should implement, but we expect you to be able to deduce the other rules unambiguously yourself (if in doubt about a rule, ask on the Moodle forum).

The “+” operator can represent integer addition, or string concatenation. If the types of e1 and e2 are T1 and T2 respectively, we have for the type Ts of e1 + e2:

• T1 = TInt and T2 = TInt → Ts = TInt
• T1 = TString and T2 = TInt → Ts = TString
• T1 = TInt and T2 = TString → Ts = TString
• T1 = TString and T2 = TString → Ts = TString

All other values for T1 and T2 should result in type errors.

The “==” operator is also overloaded. The single constraint here is that both arguments must have the same type. All object types can be compared using “==” (we will see later that the semantics of this are simply reference comparison), but an object cannot be checked for equality against a primitive type (including strings and arrays of integers). Expressions of primitive types can only be compared with expressions of the same type.

The dereferenced object must be of an object type, and its class must declare the method called. The number of arguments must of course match the number of parameters. The arguments passed must be subtypes of the declared parameters (matching one-by-one).

Assignment of an expression of type T can only be done to a variable of type S such that T <: S.

Assignment to array elements can only be done through an array variable, and the index must be an integer expression. The assigned value must be an integer.

this is always considered to carry the object type corresponding to the class where it occurs.

The returned expression must be of a subtype of the declared return type.

We will consider println calls to be valid if the argument is an integer, a Boolean or a string. If you want to accept statements that print objects or array you are free to do it, but please let us know in a README file or something similar.

Here are the steps we suggest you take:

• Add our stubs for Types.scala and TypeChecker.scala to your project (read the comments in the files too).
• Add the Typed trait to your expression subtrees, to the VariableSymbol case class (to represent the type), and to the MethodSymbol case class (to represent the return type).
• Modify your analyzer such that it attaches types to the various symbols. Since symbols are shared, this has the advantage that you can recover the proper type from any occurence of the symbol.
• Modify your analyzer so that it enforces the overriding type constraints on methods.
• Implement your typechecker. Make sure you attach the types to the expression subtrees (this will be required for code generation, to differentiate between the versions of the overloaded operators, for instance).
• While you typecheck expressions, attach the proper symbols to the occurences of method calls (since you can now determine the class from which they are called ²⁾.
• Test, test, test!

It is very important that your compiler does not stop at the first type error! TypeChecker.scala contains some hints on how to achieve this. Detect as many errors as possible!

The usual freebies:

• Types.scala
• TypeChecker.scala
• Compiler.scala

…and the usual structure you get if you followed our suggestions:

src
 └── toolc
      ├── Compiler.scala         (given this week)
      ├── Main.scala             (given in Lab 03)
      ├── Positional.scala       (given in Lab 03)
      ├── Reporter.scala         (given in Lab 03)
      ├── TreePrinter.scala      (completed in the previous lab)
      │
      ├── analyzer
      │    ├── Analyzer.scala    (to complete this week)
      │    ├── Symbols.scala     (adapt to the Typed trait)
      │    ├── TypeChecker.scala (stub given this week)
      │    └── Types.scala       (stub given this week)
      │
      ├── lexer
      │    ├── Lexer.scala       (completed in Lab 03)
      │    └── Tokens.scala      (completed in Lab 03)
      │
      └── parser
           ├── Parser.scala      (completed in Lab 04)
           └── Trees.scala       (adapt again)

Submit your src directory archived as a zipped or tarball archive through Moodle before Tuesday, Nov. 16th, 11.55pm (23h55). Note that the output of the compiler hasn't changed since the last lab (on correct benchmarks, that is), except that method calls now must have their proper symbol id displayed. Just like for the last lab, check your solutions with the Tool reference compiler.

Avoid the following in your archives. I mean it:

• class files
• hidden .svn directories.
• Makefiles
• whatever doesn't look like a .scala file or a README file.