Compiler Designing W06L1006

Type Error Recovery

  • Assign Object type to ill-typed expression. Lets take case to show that may be that’s not a such perfect idea:
let y: int  ← x + 2 in y + 2 --x is declared as Object after receiving error of no declaration                             --Error 1: + applied to Object
                             --Error 2: Unknown assignment from Object to integer
  • So a new type is NO_TYPE for ill-typed expressions just for error recovery and NO_TYPE ≤ C(all type)
  • Every operation is possible on NO_TYPE and returns NO_TYPE when used like in the above example:
x + 2 would turn to: NO_TYPE + 2 = NO_TYPE
and int ← NO_TYPE is fine.
  • Issue with NO_TYPE: it makes AST complex.

Compiler Designing W06L1005

Self Type Checking

  • SELF_TYPE’s meaning depends upon the class it is used.
  • Use in the case of dispatch:

CodeCogsEqn (10)

  • Another dispatch when return type is SELF_TYPE:

CodeCogsEqn (11)

  • Dispatch exp can be self_type as M(e0, f) can be replaced by M(C, f) when O,M,C⊦e0: SELF_TYPEC

Compiler Designing W06L1004

Self Type Usage

  • It can appear only where a type may appear but not at all the positions where a type can be written.
  • It is not a class name.
  • x:T then T can be SELF_TYPE
  • let x:T in E then T can be SELF_TYPE
  • new T; T can be SELF_TYPE
  • m@T(a,b,..d); T is not allowed to be SELF_TYPE
  • m(x:T): T'{…}; only T’ can be of SELF_TYPE; in addition if T can also be SELF_TYPE the this case can happen:
class A
{
     function(x:SELF_TYPE): BOOL{...}
};
class B inherits A
{
     x:int;
     function(x:SELF_TYPE): BOOL{... b.x ...}   
};
class main()
{
     let x:A ← new B in ... x.function(new A); //won't work at runtime
};

Compiler Designing W06L1003

Self Type Operations

  • Lets take an example from COOL
class C{... E:SELF_TYPE...}
  • here E can have type that is a subtype of C. It depends on the location of E that what kind type it has. This rule is written as: Rule(*) = SELF_TYPEC ≤ C
  • Rule(*) = SELF_TYPEC ≤ C rule implies that any occurrence of SELF_TYPE can be replaced by class C type.
  • Earlier rules on types are extended for SELF_TYPE:
    • subtype rule T ≤ T’
      • SELF_TYPEC ≤ SELF_TYPEC
        • SELF_TYPEC ≤ SELF_TYPED never happens in COOL
      • SELF_TYPEC ≤ T if C ≤ T
      • T ≤ SELF_TYPE≤  is always false
    • lowest upper bound rule
      • lub(SELF_TYPEC, SELF_TYPEC) = SELF_TYPEC
      • lub(T, SELF_TYPEC) = lub(SELF_TYPEC, T) = lub(C, T)

Compiler Designing W06L1002

Self Type

/Everything here is just for COOL/

Class Main()
{
     Class A()
     {
          i:int ← 0;
          inc():A
          {
               i ← i+1;
               self; --will return A
          }
      };
     Class B inherits A()
     {...};

     B b:B ← (new B).inc(); --inc() will return a type A and hence this statement is invalid
                            --but dynamic type is correct
                            --this means that the statement is not well-typed
};
  • SELF_TYPE is introduced and therefore type rules are also changed. It is static type and not a class name.
inc():SELF_TYPE{...} --indicating that the return value now is of type self parameter.

Compiler Designing W06L1001

Static vs. Dynamic Typing

  • A language is statically typed if the type of a variable is known at compile time and a language is dynamically typed if the type of a variable is on the runtime values of variables.
  • Static Typing detect common errors at the compile time
  • Over years if static typing have problems then the problems are solved in two ways:
    1. Using Dynamic Typing
    2. Making static typing more powerful
  • But making static typing systems powerful make it complex. Some examples of statically typed languages are C, C++, Java.
  • Soundness theorem:- dynamic_type(E)=static_type(E), this means that the type identified at compile time is coming out to be same as that of at runtime.
  • A C++ example on dynamic and static type:
class A(){...}
class B:A() {...}

int main()
{...
     A *a = new B(); //A *a is statically typed and new B() is dynamic typing of a
     B *b = new B(); ...
}

See user9876’s answer on this link.

[II] For COOL:

  • ∀E dynamic_type(E) ≤ static_type(E), this means that subclass can only add methods or attributes.
  • Methods can be redefined with same type.

Compiler Designing W05L0909

Implementing Type Checking

  • COOL type checking can be done in one traversal of AST, passing Typing environment down and types up in the tree.
  • For example,

CodeCogsEqn (2)

TypeCheck(Environment, e1+e2:int)
{
     T1=TypeCheck(Environment, e1);
     T2=TypeCheck(Environment, e2);
     Check if T1==T2==int;
     return int;
}
  • Another Example,

CodeCogsEqn (1)

TypeCheck(Environment, let x:T ← e0 in e1:T1)
{
     T0=TypeCheck(Environment, e0);
     T1=TypeCheck(Environment.add(x:T), e1);
     Check SubType(T0,T1);
     return T1;
}

Compiler Designing W05L0908

Typing Methods

CodeCogsEqn

The question is which type would be return by the method f and if a function and object has the same name then how can it be resolved.

So another mapping function M is introduced for methods given as:

M(C,f)=[T1, T2...Tn, Tn+1], here C is the class of the function f and T1...Tn is the argument of the function and Tn+1 is the result type of the function.
so f(x1:T1, x2:T2.. xn:Tn):Tn+1

So the method dispatch can be written as:

CodeCogsEqn (3)

For static dispatch see video from 4:35 minute.

[II]

In most cases typing methods are passed but only used in the case of dispatch.

In COOOL the ful type environment has three elements O, M, C where C is the Class.

Compiler Designing W05L0907

Subtyping

  • As the name suggests, it is one of the type included in a bigger type; For example, int is an subtype of Object.[valid for COOL]
  • Subtyping is shown by ‘≤’ sign.
  • Relation on classes X, Y and Z
    • X ≤ X;
    • X ≤ Y if X inherits from class Y;
    • X ≤ Z if X ≤ Y and Y ≤ Z
  • Lets say, O is the typing environment, then the example shows subtype assignment to the supertype.

CodeCogsEqn (4)

  • Another example is If a then b else c; then the return type of the expression would be the smallest supertype of b and c denoted by lub(b, c): lowest upper bound of b and c.

CodeCogsEqn (5)

  • lub(X,Y)=Z if X ≤ Z and Y ≤ Z and also if X ≤ Z’ and Y ≤ Z’ then Z ≤ Z’
  • Example is in video.

Compiler Designing W05L0906

Type Environments

  • Some example templates without type environment:

CodeCogsEqn (6)

CodeCogsEqn (7)

  • Type environments give the types of free variables in current scope. If in an expression a variable is not defined just used then that variable is free. As free variables can create problems like this: ⊦x is a variable/⊦x:?
  • type_environment(objectIdentifier)=Type written as O⊦e:T and read as under the assumption that free variables are given by O , it is provable that e has type T.
  • So type check can work if all the free variables are defined by type enviroment.
  • O[T/X](X)=T and O[T/X](Y)=O(Y)

[II]

  • Type environments are passed in AST from root to leaves and types are computer leaves to root.