5 of 63

Type-Checking Table?

For every type, should there be an entry where…

𝛼 × 𝛽 → 𝛾

E.g., int × int → int

Is this enough?
Will every int op int yield an int?��

6 of 63

Type-Checking Table?

For every type, should there be an entry where…

𝛼 × 𝛽 → 𝛾

E.g., int × int → int

What about 3 == 2? �In that case, int × int → boolean��

7 of 63

Type-Checking Table?

Therefore, Type-Checking is a 3 input, 1 output table:

( 𝛽 × 𝛼 × op ) → 𝛾 �

E.g., int × int × {+ ,-,*,/} → int

int × int × {== ,!=,>,>=,<,<=} → boolean

8 of 63

Operator Overloading

Operator Overloading: give custom definitions to ops

Example, consider a “MyData” object that can accumulate integers and sorts them.

In C++, can create a method that defines:

MyData × int × {+} → MyData

Where adding integers to MyData types will call that method

9 of 63

Bad Types

When an entry is missing, then the resultant type should be a specially designated type that is compatible with EVERY type.
This type, “ErrorType”, prevents type-checking errors from filling up your compiler’s error log

10 of 63

Bad Types

This type, “ErrorType”, prevents type-checking errors from filling up your compiler’s error log

Consider miniJava:

(myObj + 3) + 5;

ClassType × int × {+} → ErrorType (report error here)

ErrorType × int × {+} → ErrorType (no need to report)

Second type check was valid.

11 of 63

Bad Types

Generalization:

( {ErrorType} × AnyType × AnyOp ) → ErrorType

( AnyType × {ErrorType} × AnyOp ) → ErrorType

( (TypeA,TypeB,Op) ∉ TypeTable ) → (Result=ErrorType)

( (TypeA,TypeB,Op) ∈ TypeTable ) → ( Result = GetEntry(TypeA,TypeB,Op) )

12 of 63

Does Order Matter?

Is A × B the same as B × A?�
Not for miniJava, but yes for some languages.

Thus, how you construct your type checking table depends on the language.

13 of 63

TypeCasting / Type Conversions

Typecasting (or the conversion of a type) does not have an operator.
Formally:

𝛼 × 𝛽 → 𝛼

Thus, the table for typecasting is:

(TypeA,TypeB) → TypeA

E.g. ( (int)3.4f ) → 3 (an int), which is (int,float)→int

14 of 63

TypeCasting / Type Conversions

𝛼 × 𝛽 → 𝛼

The table for typecasting takes an input of (TypeA,TypeB), result is just TypeA
If (x,y) ∉ Table, then this is a type checking error.
The table usually has a result just to make the code easier to write up.

15 of 63

Automatic Conversions

16 of 63

Automatic Conversions

17 of 63

Automatic Conversions

Automatic conversions are AUTOMATIC
Note:

private int somefun( int a ) { … }

…

somefun( true );

… does not require explicitly typecasting (int)true

18 of 63

Automatic Conversions

19 of 63

Automatic Type Casting Note

20 of 63

Manual Typecasting

21 of 63

Manual Typecasting

22 of 63

Please note: miniJava

23 of 63

Type Checking - PA3

24 of 63

miniJava TypeChecking

leaves of the AST are Terminals: Identifiers, Literals, and Operators

We can assign each of these a specific TypeDenoter (BaseType, ClassType, or ArrayType)
The specific types are manifest (Literals) or extracted from the declaration of an Identifier

Expression, Reference, and Declaration nodes compute their type from their children
specific Statement nodes make some checks for type agreement

AssignStmt
IfStmt

special types

ERROR, UNSUPPORTED

25 of 63

Simple Approach to TypeChecking

Define a set of possible types

set of base types and some ways to build new types

Define a representation of programs

simple class of ASTs

Define a type-assignment algorithm that

labels all nodes of an AST with zero or more types
handles many forms of overloading

essentially all languages have some form of overloading
addition: operation on integers or floats?

Type checking

following type assignment each AST node is labeled with a set of types
program is type correct if all nodes have a single type
program contains type error(s) if some node has no type assignment or more than one possible type assignment

26 of 63

Type-Checking Strategy Details

Implement a TypeChecking Visitor that uses a TypeDenoter return type.

Visiting a node synthesizes a TypeDenoter for that type.
Create a method, input is the two TypeDenoters, (or one for Unary), and output is the resultant TypeDenoter.
Or create a table, but that would have a lot of null entries.

27 of 63

Type-Checking Strategy Details

Ensure index expressions are integers
Ensure condition expressions in if/while are boolean
Ensure operands are compatible, and return the appropriate type when visiting that BinExpr/UnaryExpr

28 of 63

Type Values at Leaves

Declarations provide type value(s) for AST leaves
a variable type is obtained from its (unique) declaration �
constants have a manifest (unique) type �
functions or operators may have multiple types as a result of overloading��

29 of 63

Type Checking in PA3

Bottom-up traversal of AST
Create a TypeDenoter attribute in every Expression node (or possibly in every node)
The type rules for predefined functions are relatively simple:�
Study type related classes in the AST

TypeDenoter, TypeKind, BaseType, ArrayType, Classtype
create an equality function between arbitrary instances of TypeDenoter

Run only if identification has completed successfully!

e.g. A x = new A();��

30 of 63

Special Types

Error type

Error type is equal to any type
limits propagation of errors
gives most useful continuation of type checking after an error

Unsupported type

Unsupported type is not equal to any type
Therefore a value of type unsupported is not type correct in any operation
Predefined name String can have unsupported type��

31 of 63

Type-Checking Table

32 of 63

miniJava – Types must match

For miniJava, the types must match. There is no automatic type conversions nor manual typecasting.

33 of 63

miniJava – Types must match

For miniJava, the types must match. There is no automatic type conversions nor manual typecasting.

Does this mean we can use a REALLY simple type-checking table where both types must match, and the result type is that type?

34 of 63

miniJava – Types must match

Does this mean we can use a REALLY simple type-checking table where both types must match, and the result type is that type?

Still need to formally clarify�Type rules.

35 of 63

Type-Checking Table (2)

Type Checking Rules
Operand Types	Operand	Result
	&&, \|\|	boolean
	>, >=, <, <=	boolean
	+, -, *, /	int
	==, !=	boolean
int	(Unary) -	int
boolean	(Unary) !	boolean

36 of 63

ClassType

If two objects are both ClassType, are they comparable?

37 of 63

ClassType (No polymorphism in miniJava)

If two objects are both ClassType, are they comparable?

No, the underlying Identifier text must match.
Why is this enough?

38 of 63

What type is ArrayType?

Recall: new int[4]
This expression is of ArrayType(IntType)
Thus, it can only be assigned to variables of type�ArrayType(IntType)

IntType is shorthand for:�BaseType( TypeKind.INT )

39 of 63

What type is ArrayType?

For array types:

First: Are both types ArrayType?
Second: Do the element types match? (Recursion)

Recursion needed to match ArrayType of ArrayType of ArrayType of ClassType.

40 of 63

Type-Checking Methods

Scoped Identification only uses context and identifiers. Therefore, overloading methods by parameter types/counts is not allowed in miniJava.

41 of 63

Type-Checking Methods

As such, make sure there is an expression for every parameter, and that the types match.

42 of 63

Back to Identification

43 of 63

Pre-defined Names

miniJava doesn’t have imports, so we need to provide some basic functionality.
You must MANUALLY add these entries into your IDTables for PA3, and we will use them in PA4.

��

Note, println takes an int, not a String.

44 of 63

Out-of-order References

Note: class B is used as a type when B hasn’t yet been declared.

Question: How can we put the classes in our IDTables ahead of time?

45 of 63

Out-of-order References

Additionally, can refer to members of classes that have not yet been declared.

Question: How can we put the members in our IDTables ahead of time?

46 of 63

Strategy: OOO References

Before you visit a method’s StatementList, add all ClassDecls in the Package AST to the level 0 IDTable.
Then, add all MemberDecl (FieldDecl/MethodDecl) to the IDTable as well.
Never drop below scope level 1.

47 of 63

Strategy: OOO References

Private members cannot be accessed externally.
Possible strategy: only add public members first, then when processing a class, add that class’s private members.
When leaving a class, make sure to remove those entries! (How would you handle this?)

Alternatively: check private later when resolving declarations. (this is probably easier than changing your level 1)

48 of 63

Identification of QualRef

49 of 63

Left-most Reference

Only the left-most reference should be resolved normally (start at the top of the SI stack, then work down).
Once you know the Declaration of the left-most reference, you have a context.

50 of 63

Left-most Reference

QualRef(LHS,RHS): LHS is a Reference, and RHS is an Identifier.
With the type of the LHS (the context), resolve the RHS.

51 of 63

Left-most Reference

QualRef(LHS,RHS): LHS is a Reference, and RHS is an Identifier.
With the type of the LHS (the context), resolve the RHS.
a.b means “.b” is resolved in the context of the type of “a”, which is class “A”.

52 of 63

Left-most Reference

With the type of the LHS (the context), resolve the RHS.
Note: this means that you can bypass local variables.

“a.b.c.x” but “b”, “c”, “x” were all locally defined.

53 of 63

QualRef Strategy

Try to get the “context” by visiting the LHS reference.
With that context, resolve the RHS.

E.g. “a.b” will return the context of class “B”, thus allowing resolution of “a.b.c” where “c” is in the context of “B”

54 of 63

No one strategy dominates all others

How you choose to identify “context” is up to you. It can be a String, ClassDecl, TypeDenoter, etc.

Even more important to plan PA3 than other assignments before starting to code.
If you change your Visitor’s parameter or return type, you may have to redo the entire class declaration!

55 of 63

A.b, where A is also a class name

Is it correct to say that if “A” is a class name, then “x” must be a static member?

56 of 63

A.b, where A is also a class name

57 of 63

A.b, where A is also a class name

58 of 63

Static Reference

In miniJava, if the left-most reference is a class name AND is not declared at level 1+, then the RHS must be a static member.

E.g. “CLASSNAME.x”, where “x” must be a static member of “CLASSNAME”

59 of 63

Static Context

If you are in a static method, then you can only access static members in your Class, and public static members in other classes.

Additionally, ThisRef is an identification error as “this” does not resolve to any declaration in a static method.
Question: where is ThisRef in memory?

60 of 63

Other Contextual Constraints

61 of 63

Contextual Analysis

There are contextual parts of Java (and miniJava) that do not quite fit Identification or Type Checking.
We can easily implement these as a part of either.

62 of 63

Contextual Analysis

If an identifier is being declared,�then it cannot be used in the expression.
Even if the expression can be evaluated first!

Not allowed!

63 of 63

Contextual Analysis

You cannot have a variable declaration only�in a scope to itself.
A BlockStmt (new scope) is necessary for VarDeclStmt.

Not allowed!