This week you will implement type checking in your MiniJava+ 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 does.

A valid MiniJava+ program has the following properties:

• It follows the MiniJava+ 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, contrary to Java).
• 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.

The following primary types exist in MiniJava+ (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 in 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 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 System.out.println calls to be valid if the argument is an integer, a Boolean or a string. You are free to decide whether you want to support the printing of arbitrary objects, as in Java. Note that this will make the code generation step slightly harder for you, though. If you decide to do it, 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.

The usual freebies:

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

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

src
 └── minijava
      ├── Compiler.scala         (given this week)
      ├── Main.scala             (given in the previous lab)
      ├── Positional.scala       (given in Lab 02)
      ├── Reporter.scala         (given in Lab 02)
      ├── 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 04)
      │    └── Tokens.scala      (completed in Lab 04)
      │
      └── 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 Wednesday, Nov. 12th, 8.15am. Note that the output of the compiler hasn't changed (on correct benchmarks, that is), except that method calls now have a proper symbol id shown.

Avoid the following in your archives:

• class files
• hidden .svn directories (it's good you're using a collaborative tool, by the way)
• Makefiles
• whatever doesn't look like a .scala file or a README file.