1Type Checking Type Systems Type Equivalence Typing Expressions Coercion Overloading Error Recovery Typing Statements Polymorphic TypesType Checking Situations Expression typing Operands matching Selecting operand Coercing types Selecting among overload possibilities Polymorphic type expansion2Type Systems - Rules Rules of a language Definition: What are the base/immutable types? What type constructors are available? Can types be named? Resolution: What operators can be applied to what types? What forms of coercion are allowed? How are overloading situations resolved?Type Systems – Base types Base/immutable types Generally objects with a direct machine representation, where the objects can not be further divided Examples: bool, char, int, float, double, long int, unsigned int, … Simple objects have direct types Literals: 3 (int), -5.0 (double) Variables: int x; (int) double y; (double)3Type Systems –Pointer Constructor Constructors Pointer In C++ type*name, result is a pointer to a type (ptr to type) Examples: int *x; (x is a ptr to an int) float **y; (y is a ptr to a ptr to a float) Operators related to pointer: *x – dereference x (go to what x points at), in terms of types, * applied to ptr to y, results in y x-> equivalent to (*x). – compose * and . operations x[…] – pointers can be used as standins for arrays (array ref is just an address, pointer operation)Type Systems –Array Constructor Constructors Arrays In C++ type name[size], result is array (0..size-1) of type Examples: int z[10]; array (0..9) of int float *w[5]; array (0..4) of pointer to float double t[10][9] is array (0..9) of array (0..8) of double Operators related to pointer: x[expr] – refers to element of an array – equivalent to *(x + sizeof(ArrayEl) * expr) – why arrays start at 0 in C/C++ If x of type array (lo..hi) of typex[…] returns type4Type Systems – Products Constructors Products Certain operations result in products Function parameter lists Function argument lists Class/structure fields Type is the product composition of the individual types Examples: (int x, float y, char z) – int X float X char (3,’X’,2.0,0) – int X char X double X int class x { int y; float z; }; - int X float Parameters, class fields are namedType Systems –Class/Struct/Record Constructor Constructors Structures – classes, records, etc. Types are products with named fields (can refer to indivdual members by giving field name) Type is the product of the field types with names attached Example: class t { char x; int y; float z;}; - type is char(x) X int(y) X float(z) with names attached Operators: . operator (x.y) – if x is of type … X typ (y) X …, resulting type is typ -> operator – composition of * and . operator x->y is (*x).5Type Systems –Function Constructor Constructors Functions Types are left hand side of products, followed by ->, followed by result type Example: int foo (float x, char y) { } – float X char → int Operator:fname(args) – function call, if argsmatch left hand size of type associated with fname, resulting type is the right hand side of type associated with fname example: foo(3.0,’X’) has result type of int (from above)Type Systems – Type Variables Type variables Some languages allow the definition of type variables (often useful in dealing with cyclic/recursively defined types) Type variable names often associated with constructed types (e.g., class names) But allowing type names can introduce some equivalence problems (more later)6Forms of Checking Static type checking – type checking done at compile type Used in many strongly typed languages (where all variables/objects must have types) Dynamic type checking – done at runtime Often used in languages where objects not strongly type (e.g., Lisp)  Type checking must be done at runtime (since objects not guaranteed to have a single type)Type Equivalence Name equivalence – objects are considered to be equivalent if they have the same (or in the case of operators – appropriate names) Problem – if a type name is given to a type (Number declared a synonym for int) this may introduce type errors that are not real errors Structural equivalence – objects are considered equivalent if they have similar structures Useful but can allow some mappings we may not want: class x { int y; float z;}; class position { int angle, float distance; }; x and position would be considered to be structurally equivalent7Cyclic Types Many structures in programming languages are declared recursively (linked lists, trees, etc.) Example:class LinkedList {int data;LinkedList *next;}; next field’s type is based on the type it is part of Cyclic Type GraphsLinkedListint X ptr toBut how to compare this type(structurally or by name)?Often use names for types to make graphs easier(makes equivalence easier to determine)LinkedListint X ptr toLinkedList8Sample Language ExpressionsintLit(e.g., 1, 3, -5)boolLit(e.g., 0, 1)varnamee1+ e2e1/ e2e1== e2e1< e2 not ee1and e2f(arglist)v.field* e Statementsif (e) stmt1; else stmt2; fi;ident= expr;f(arglist); Simple types bool, int, void Constructors Products Structures PointersPossible Nodes IntLitNode (ival) BoolLitNode (bval) VariableNode (name) BinaryNode (op,leftarg,rightarg) UnaryNode (op,arg) RecFieldNode (recexpr,fname) FuncCallNode (fname,arglist) IfNode(bexpr,ifstmt,elsestmt) Other: ArgListNode(arg,next) StmtListNode(stmt,next)9When to Type Check Depending on language, type checks can often be done in parsing Can also be done as a separate process If done as a separate process, performed as a traversal of the AST(s) from the program Generally two routines: Type of expressions Type of statementsTyping Expressions Deals with expressions, possibly complex expressions where we assume the expressions will result in type Some simple:TypeIntLitNode::expr_type() { return int; }TypeBoolLitNode::expr_type() { return int; }TypeVariableNode::expr_type() { return type of variable; }10Typing Expressions - Operations Type arguments, then check/compare resultsTypeBinaryNode::expr_type() { lefttype