Contents

• Homework Description (Reference: Decaf manual, in PDF)
• Project Path
• Deliverables
• Grading
• Submission
• Change Log

Read the following description carefully before starting on the assignment. Also, go through the brief overview of the project path that describes the steps involved. A list of what materials are available and what you are expected to submit are also given.

Homework Description

In this assignment, you will build a type checker for Decaf. Recall the description of Decaf's syntax is given in its manual, and the AST you built in HW #3. The type checker you will build in this assignment will:

• Add type information to AST
• Resolve names used in field access and method invocation expressions

As in the past, you will produce a compiler front end that will take a single command-line argument, which is a file name; if that file contains a syntactically valid Decaf program, then it will construct an AST for that program. Upon successful construction of the AST, it check the type constraints as outlined in this handout (see section on type checking), and resolve any names that could not be resolved when the AST was constructed (see section on name resolution). Any errors found during type checking and name resolution should be reported with sufficient detail (including the nature of the error and the line numbers in the source program corresponding to the error). If type checking and name resolution proceeded without any error, it will then print the AST decorated with types to standard output (see section on printing).

1. Changes to the AST Structure
2. Type Checking Constraints
3. Name Resolution
4. Additional Error Checks
5. Printing the AST
6. Initialization
7. CSE 504 vs. CSE 304

Each type is either an array type are an elementary type. Elementary types, in turn, may be one of built-in types: int, float, boolean, or string; or a user-defined type, which is a class name.

An array type is parameterized by its "base type", which is another type.

• To the above, we add void as a built-in elementary type.

  This was an omission in HW#3.

• We add a class-literal type, which has a class name as a parameter. While user(A) denotes an object belonging to class "A", class-literal(A) denotes the class "A" itself.

  The use of class-literal types will be described when type constraints for expressions are explained (see section type checking below).

• We also add error and null as a built-in elementary type to indicate type errors and null object references (respectively).

• Type T is a subtype of itself (i.e. the subtype relation is reflexive).
• int is a subtype of float.
• user(A) is a subtype of user(B) if A is a subclass of B.
• null is a subtype of user(A) for any class A.
• array(T1) is a subtype of array(T2) if T1 is a subtype of T2.
• null is a subtype of array(T) for any type T.
• class-literal(A) is a subtype of class-literal(B) if A is a subclass of B.

Changes to Expressions:

1. If-stmt: This statement is type correct if if the condition part is of boolean type; and the "Then" and "Else" parts are type correct.
2. While-stmt: This statement is type correct if if the condition part is of boolean type; and the loop body is type correct.
3. For-stmt: This statement is type correct if if the condition part is of boolean type; and the initializer expression, update expression and the loop body are all type correct.
4. Return-stmt: This statement is type correct if the type of the expression matches the declared return type of the current method.
   • If the expression is empty, then the declared return type of the method must be void (and vice versa).
   • If the expression is not empty, then its must be type correct, and its type must be a sub-type of the declared return type of the method.
5. Expr-stmt: This statement is type correct if the expression is type correct.
6. Block-stmt: This statement is type correct if all the statements in the sequence are type correct.

1. Constant-expressions:
   • Integer-constant: has type int.
   • Float-constant: has type float.
   • String-constant: has type string.
   • True and False have type boolean.
   • Null has type null.
2. Var-expression: has, as its type, the declared type of the corresponding variable.
3. Unary-expressions:
   • uminus e: has the same type as e if e's type is int or float; has type error otherwise.
   • neg e: has type boolean if e's type is boolean; has type error otherwise.
4. Binary-expressions:
   • Arithmetic operations add, sub, mul, div: have type int if both operands have type int; otherwise, have type float if both operands have type int or float; otherwise have type error.
   • Boolean operations and, or: have type int boolean if both operands have type boolean; otherwise have type error.
   • Arithmetic comparisons lt, leq, gt, geq: have type boolean if both operands have type int or float; otherwise have type error.
   • Equality comparisons eq, neq: have type boolean if the type of one operand is the subtype of another; otherwise have type error.
5. Assign-expression: Consider e1 = e2. The type of this expression is e2's type, provided:
   • e1 and e2 are type correct,
   • e2's type is a subtype of e1's type.
6. Auto-expression: has the same type as its argument expression e if e's type is int or float; has type error otherwise.
7. Field-access-expression: Let p.x be the field access expression, and let z be the field obtained by name resolution. Then this expression's type is same as z's declared type, provided:
   • p's type is user(A), and z is a non-static field.
   • p's type is class-literal(A) and z is a static field.
   This expressions type is error if name resolution had errors or the above conditions do not hold.
8. Method-call-expression: Let p.f(e1, ..., en) be the method access expression, and let h be the method obtained by name resolution. Then this expression's type is same as h's declared return type, provided:
   • p's type is user(A), and h is a non-static method.
   • p's type is class-literal(A) and h is a static method.
   This expressions type is error if name resolution had errors or the above conditions do not hold.
9. New-object-expression: Let A(e1,...,en) be the constructor and arguments in this expression. The type of this expression is user(A) if name resolution succeeds.
10. This-expression: has type user(A) where A is the current class.
11. Super-expression: has type user(B) if B is the immediate superclass of the current class; and error if the current class has no superclass.
12. Class-reference-expression: has type class-literal(A) where A is the literal class name in this expression.
13. Array-access-expression:^{504 only} has type T if the base expression's type is array(T) and the index expression's type is int; has type error otherwise.
14. New-array-expression:^{504 only} Let T be the base type and e1,...,en be the sequence of array dimensions. Then, this expression has type array(array(...repeated n times (T)...)), provided each expression ei is of type int. This expression has type error if any of the dimension expressions is not of int type.

Note that all local variables are resolved while constructing the AST. The only names that are not resolved at that time are the fields, methods and constructors.

Fields:

• If e's type is user(A): Then the expression resolves to field with id j if B is the most specific superclass of A such that
  • B has a declared non-static field named x with id j,
  • and the field is accessible (based on the public/private declarations) from the current method.
• If e's type is class-literal(A): same as above except B has a static field named x.

Methods:^{Simpler for 304}

Let the types of e1,...,en be T1,...,Tn, and all the argument expressions are type correct.

• If e's type is user(A): Then the expression resolves to method with id j if B is the most specific superclass of A such that
  • B has a declared non-static method named f with id j such that
  • the method j is applicable: i.e., the types of the formal parameters of that method are T1',...,Tn' and each Ti is a subtype of Ti',
  • there is no other non-static method named f in B that is also applicable and has formal parameter types T1'',...,Tn'' that are not all subtypes of T1',...,Tn'.
  • and the method is accessible (based on the public/private declarations) from the current method.
• If e's type is class-literal(A): same as above except B has a static method named f.

Constructors:^{Simpler for 304}

Let the types of e1,...,en be T1,...,Tn, and all the argument expressions are type correct.

The constructor resolved for this expression is the constructor with id j declared in class A such that:

• the constructor j is applicable: i.e., the types of the formal parameters of that constructor are T1',...,Tn' and each Ti is a subtype of Ti',
• there is no other constructor in A that is also applicable and has formal parameter types T1'',...,Tn'' that are not all subtypes of T1',...,Tn'.
• and the constructor is accessible (based on the public/private declarations) from the current method.

Additional error checks:504 only

Note that there may be multiple methods (and, of course, constructors) with the same name defined in a single class. For overloaded methods/constructors, we will now impose an additional constraint. For every pair of methods with the same name (or constructors) defined in a single class:

1. Let T1 → S1 and T2 → S2 be their signatures. Then either T1 is a strict subclass of T2 or T2 is a strict subclass of T1.

   Here, we say that T is a strict subclass of T' if T is a subclass of T', and T is not identical to T'.

• Each field access, method invocation and new object creation expression will contain additional information: the id of the resolved field/method/constructor respectively. For instance, instead of

  Field-access(This, x)
  

  you should print

  Field-access(This, x, 1)
  

  (if "1" is the id of the resolved field named "x").
• Each assignment expression will additionally contain the types of the LHS and RHS expressions. Note this is only for assignment expressions, and not for others. For instance, instead of

    Expr( Assign(Variable(1), Method-call(This, f, [])) )
  

  you should print

    Expr( Assign(Variable(1), Method-call(This, f, []), int, int) )
  

• CSE 504 students are expected to construct a type checker for the entire Decaf language.
• CSE 304 students are expected to construct a type checker for the a subset of Decaf that is the whole language except the following:
  • Arrays: there are no arrays in the CSE 304 subset.
  • Implicit field accesses: all field accesses in the CSE 304 subset will specify the object explicitly.
  • Implicit method calls: all method calls in the CSE 304 subset will specify the object explicitly.
  • No overloaded methods/constructors: Assume that in each class, there is at most one constructor, and at most one method with a given name. Also assume that names of methods defined in a class are distinct from method names in its super classes. You do not need to check for these constraints. Your type checker can safely assume these are true!.
  • The above assumption leads to a significant simplification in name resolution. This also eliminates additional error checks.

Project Path

1. Start with a working AST builder.
2. Assume no method invocations, constructors or field accesses; Write a type checker that works on this restricted subset of programs. You may want to work with even smaller subsets than these.
3. Proceed by adding field accesses first, and finally method invocations and constructors.

Deliverables

1. Lexer:    decaflexer.py, PLY/lex scanner specification file. (unchanged from HW2)
2. Parser:    decafparser.py, PLY/yacc parser specification file. (unchanged from HW3)
3. AST:    ast.py, table and class definitions for Decaf's AST (modified from HW3 to add type-related fields and definitions).
4. Type Checker:    typecheck.py, definitions for evaluating the type constraints and for name resolution.

   Note: This may be folded into ast.py as long as readability is maintained.

5. Main Top-Level:    decafch.py, containing the main python function that ties the modules together, takes command line argument of input file name, and processes the Decaf program in that file.
6. Documentation:    README.txt which documents the contents of all the other files.

Grading

As usual, complicated programs may not get the full grade unless accompanied by comments documenting it.

Submission

We will assume that HW4 will be submitted by the same teams that submitted HW3. If there is any change in the team structure, you must inform the instructor the Friday before the submission deadline (Fri. April 1) and get the submission repositories for the new teams set up.

You may submit the homework multiple times; the last submission will be graded.

Change Log

• Tue Mar 29 20:08:43: Types for "and" and "or" binary operators were incorrectly specified in the original handout. Expressions with these operators at root should be boolean, not int!