In Oat, identifiers that begin with uppercase letters are types; identifiers beginning with lowercase letters are non-types. In particular, in all of the places you saw an IDENT in the previous assignment, you are now required to use a lower-case identifier.

Programs in Oat have the following top-level structure:

It is now mandatory that all constant definitions be floated to the top of the file. Constants are still non-mutually-recursive; they may also not refer to any classes save for Object. Class declarations, which are covered in detail below, are mutually recursive (modulo some details) with other class declarations and function declarations.

new[len](exp)'s semantics have changed: exp is now evaluated for every location a0..aLEN-1 in the new array (in order). Code for this is provided.

The types from the previous assignment return, along with some new ones:

Note that references (R) have been split between not-null references and nullable references. A regular string may now not take on the value null; however, the nullable string? may do so.

Oat provides a safe way to cast from a nullable type to a regular type. This is demonstrated in the example code above:

Classes must have superclasses, constructors, and unique names:

Classes may also have zero or more methods and zero or more fields. The semicolon after a field definition is mandatory (as with constants) and the parenthesis around methods are mandatory (as with toplevel functions). Methods may be overridden provided that the return type of the derived method is narrower and the argument types of the derived method are wider. A field name, once declared in some ancestor class, may not be re-declared in any child of that ancestor.

Since Oat does not support overloading or static methods, every class must have exactly one constructor (which is declared with the new keyword). This constructor can accept arguments (the first pair of parenthesis) and pass those arguments to a superclass constructor.

At runtime, Oat always checks that notnull members of a new object are initialized correctly when the object's constructor exits.

Oat allows checked downcasts for objects at runtime:

If at runtime the Object d is discovered to have type Dog, adog is set to d's current value and the left-hand branch of the cast is evaluated. If not, the right-hand branch is evaluated (and adog is not bound).

There are several new syntactic forms beyond those that were in the arrproc language. These include:

• Field access: foo.bar.baz. Associates left to right, just as in Java. While inside a class member function, you must refer to fields through this (this.foo).
• Member invocation: foo.bar(). As with fields, to call methods within a member function you must call them through this (or super): this.foo()
• Calling constructors: new Foo(bar, baz).
• Nullness and dynamic type checks: covered above.
• Special functions: there are two builtin functions, arrlen (which returns the length of any notnull array) and fail (which takes a type and a single string argument, returns something of that type, and immediately ends the program printing an error at runtime). Since Oat's type system is not polymorphic, we need to bake these into the typing rules.

Complete typecheck as defined in fulltypecheck.mli. There is some code in fulltypecheck.ml to get you started. Part of your grade for this section depends on the quality of the error messages you raise for the user. Simply printing Type error. for badly-formed programs is insufficient. Give more details about what kind of error occurred.

is pronounced 'join'; is read as 'any operator'. Type equality = is equivalent to OCaml structural equality on type ASTs.

There are three different judgement types :

• TsNormal is the regular .
• TsMethod C is for typechecking inside methods of some class C.
• TsCtor (P,C) is for typechecking inside the constructor of some class C with parent class P.

Oat's rules for subtyping () follow. Subtyping depends on a signature context .

• class_subtype T S determines if class S is a supertype of class T based on the signatures in .

Function names must be unique and they may not share names with constants. Class names must also be unique. Parent classes must be declared before child classes (so you don't have to check for cycles in the inheritance hierarchy).

We suggest the following multi-pass algorithm for typechecking:

• Check all constants in turn, adding each one to .
• Check and register all class names and supertype relationships.
• Check and register all class and function signatures.
• Check all code.

Typechecking constants occurs under the empty binding context. The signature context contains nothing but constants that have been declared previously to the constant being checked and no classes but Object. Constant names should be unique. should be TsNormal.

Registering a class name requires that you verify that the class name is unique and that the class's superclass exists. Checking the well-formedness of a class signature is a little more involved:

• A field F in class C may not shadow any other fields declared in C, nor may it shadow any fields declared in any superclass of C.
• All fields must have well-formed types. Fields may not have type TUnit.
• A member function with name M may be declared up to once in a given class C.
• Overriding member functions must follow the Override rule (where is defined on ): T S SM TM ( M [1,N]) T f(T1 t1 ... TN tN) may override S f(S1 s1 ... SN sN)
• Member functions are subject to the same well-formedness requirements as top-level functions, but member functions may not be extern.
• Every class must have exactly one constructor.

Typechecking functions occurs under the binding context consisting only of that function's argument names. The signature context contains all constants, all functions (including the one being checked), and all classes. This is nearly the same as it was in the last assignment but with the addition of subtyping and a parameterized judgment.

Checking a DeclFunction uses rule T-DFuncMethodCtor and takes place under = TsNormal.

Checking a MemberFunction on a class C uses rule T-DFuncMethodCtor and takes place under = TsMethod C

Checking a MemberConstructor on a class C with parent P uses rule T-DFuncMethodCtor (ignoring the initialization list and the return type) and takes place under = TsCtor (P,C). In addition, the constructor's initialization list must follow the rule CtorInit with = TsNormal:

Oat's rules for typing expressions depend on a signature context , a binding context , and a judgment type . Most rules behave the same under any judgment type. Take here to mean defined on the context .

The following rules are brand new for this assignment.

The following rules differ in behavior depending on the judgment type.

= TsMethod C:

= TsCtor (P,C):

The next group of rules are old rules that have been updated for this assignment.

• well_formed is the standard well-formedness relation; well_formed' allows TUnit to be well-formed.
• The typechecker should convert Fail nodes to Invoke nodes (that invoke the function named fail).

Fullil defines the record classtbl, which you should fill out with the vtable and runtime type information for each class:

For example, the fully-specified classtbl for the class:

is:

Which, in assembled form, becomes:

An object of type WindupDog will at runtime occupy 3 words. It is first allocated using the newcls runtime service routine, which returns a pointer to the second word. Thus, the field numbers (for FieldDeref, FieldMove and FieldNullCheck) look like:

• The ordering of the vtable is significant. Methods are called by slot number using the InvokeVirtual instruction.
• The constructor does not appear anywhere in the classtbl. Constructors are always called statically.
• The pointer to the superclass comes as the word directly before the first entry of the dispatch table. If you have a pointer to the dispatch table, you can access this pointer using the FieldDeref instruction with an offset of -1. This pointer will be null (0) for the classtbl of Object.

The Oat calling convention for methods requires that the this pointer be passed on the stack as though it were the first parameter to a cdecl function. The argument is given the name .this so as to prevent possible clashes with user-provided argument names. Method labels should be decorated with the decorate_method_name function.

Calling a method C.f() requires that you look up the index for f in C's vtable at compile time. You can then use this index to emit an InvokeVirtual instruction, which takes care of both the runtime lookup in the vtable and adding the this pointer to the argument list.

Oat allows a child class C to invoke any of its parent class's member functions, even if C overrides one of these functions. For this it provides the super keyword. super.f() requires that you make a regular InvokeCdecl call to f. You should use get_static_decorated_method to get the label for the method from the superclass (which should be available from the typing information on the Super node). You will need to explicitly pass the this pointer as the first argument to the InvokeCdecl instruction.

Assigning into fields and reading from fields requires the use of the FieldMove and FieldDeref instructions. For some field C.f, you will need to look up the index of f in C's runtime object representation.

As stated before, objects are allocated at runtime using the newcls service routine. newcls takes a single argument that represents the number of words to allocate including the word for the vtable pointer. It returns a pointer to the word directly following the vtable pointer.

Constructors are always statically linked and called with InvokeCdecl. If you have a cgcxt_class record, you can get the label for its constructor using the decorate_ctor_name function. Like member functions, their first argument is always .this, which starts out as a pointer into an allocated but uninitialized object record. The return value of a constructor is always ignored.

The base case for any object construction is always the constructor for class Object. This constructor needs only set the vtable of the passed-in .this to Object's vtable.

For any other constructor on class C with parent P:

• Evaluate all of the initializer arguments in the context including the constructor's arguments. Use these initializer arguments to call P's constructor. Remember to pass the .this pointer as the first argument. (This is how we passed the name into Animal in the introductory demo.)
• When P's constructor exits, the vtable set on .this will be P's vtable. Evaluate the expression in C's constructor.
• After evaluating the expression, check that all non-nullable reference fields have been initialized. The IL provides an instruction FieldNullCheck that takes a list of non-nullable reference field indices specifically for this purpose.
• Finally, set .this's vtable pointer to C's vtable.

• fail: fail should have been converted to a regular Invoke during typechecking.
• super.f(): Covered above. Arguments to the function should be evaluated from left to right.
• a.f(): Covered above. Evaluate the object (a) first, then evaluate the arguments from left to right.
• a.f = b: Evaluate the object (a) first, then evaluate the value to set (b). You can move values into fields using the FieldMove instruction.
• new C(): Covered above. Evaluate the arguments from left to right.
• a.f: Evaluate the object (a), then use the FieldDeref instruction to retrieve the data stored in f.
• if?(T v = a) (l) else (r): First evaluate a. If a is not null, evaluate l with v bound to a and use the result. Otherwise evaluate r and use the result. If the if? was assigned the type TUnit, then you should discard any result after evaluation.
• cast(T v = a) (l) else (r): First evaluate a. Determine if the runtime type of a is a subtype of T. (Remember that only objects can be used in cast.) If so, evaluate l with v bound to a and use the result. Otherwise evaluate r and use the result. If the cast was assigned the type TUnit, then you should discard any result after evaluation.

You can receive extra credit for this project by extending the language to support first-class functions. We have provided AST nodes for function types and function expressions. You do not need full support for closures to be awarded extra credit points, but you should let us know about your plans so that we can tell you how many points you might be given.

The different parts that you can complete include:

• Written-out rules (in your readme.txt) for typechecking function expressions (fun(int x, int y) (x + y)) and for typechecking closure application (a(1,2), where a is a closure with the appropriate type).
• Implementation of these rules in fulltypecheck.ml.
• Closure conversion and lifting. We provide a function lift_typed in the module Fulllift that is called by the compiler after typechecking but before IL generation. From there you should transform the closure-containing code to closure-free code.

You should target using only explicit fun expressions to introduce closures; don't try to give anything that can be executed a function type. You do not need to support, for instance, storing a methods (some_fun = obj.method) or top-level functions (some_fun = string_cat). While you should allow closures to participate in subtyping as was discussed in class, you should not attempt to allow closures to participate in runtime type tests (cast()).