Chapter 5-

TYPE CHECKING
 Type Checking

• Goal: to find out as early as possible, if each procedure and

operator is supplied with the correct type of arguments
– Type error: when a type is used improperly in a context
– Type checking performed to prevent type errors
• Modern PLs often designed to do type checking (as much as
possible) during compilation
• Checking of the source program whether it follows both
syntactic and semantic conventions of the source language
 Type Checker

syntax Intermediat
token syntax Type intermediate
Parser e code
stream tree Checker tree representation
generator
 Static checking
• Type checks
• Flow of control checks
• Uniqueness checks
• Name related checks
 Outline

 Type systems
 Specification of simple type checker
 Equivalence of type expressions
 Type conversions
 Type system
 The design of a type checker for a language is based on the
information about the syntactic constructs in the language.
 Each expression has a type associated with it.
 Types are either basic or constructed. Basic types are atomic
with no internal structure as far as the program is constructed.
Pointers, arrays, functions, records can be treated as
constructor types.
 Type expression
A type expression is either a basic type or is formed by applying
an operator called type constructor to other expressions.

1. A basic type is a type expression- boolean, char, integer and

real, “void” is also a basic type.
2. A type name is a type expression.
3. A type constructor applied to a type expression is a type
expression.
4. Type expressions may contain variables whose values are
type expressions.
 Type Expressions
Example: int[2][3]
array(2,array(3,integer))

• A basic type is a type expression

• A type name is a type expression
• A type expression can be formed by applying the array type constructor
to a number and a type expression.
• A record is a data structure with named field
• A type expression can be formed by using the type constructor g for
function types
• If s and t are type expressions, then their Cartesian product s*t is a type
expression
• Type expressions may contain variables whose values are type
expressions
 Type Constructors
1. Array : If T is a type expression, then array(I,T) is a type
expression, where I is an index set.
2. Products: If T1 and T2 are type expressions, then so is T1 x T2
3. Records: differs from the products as fields have names. The
record type constructor applied to tuple formed from field
names and field types.
4. Pointers: If T is a type expression, then pointer(T) is a type
expression.
 Type Constructors
5. Functions: Functions in a programming language map a
domain type D to a range type R. Often, for implementation
reasons, there are limitations on the types a function can return.

Type Expressions may contain variables whose values are type

expressions.
 Type Systems
A type system is a collection of rules for assigning type expressions
to the various parts of a program. A type checker implements a type
system.

The type of an array includes the index set of an array, so a

function with an array argument can only be applied to arrays with
that index set.
 Static and dynamic types of checking
• Checking done by the compiler is said to be static, while
checking done by target program runs is termed dynamic
• A sound type system eliminates the need for dynamic
checking for type errors. A language is strongly typed if its
compiler can guarantee that the programs it accepts will
execute without type errors.
E.g. array bound checking.
 Error recovery
• Since type checking has the potential for catching errors in
programs, it is important to do something when an error is
discovered.
• The inclusion of error handling may result in a type system
that goes beyond the one needed to specify correct programs.
Specifications of a simple type checker
• The type of each identifier must be declared before the
identifier is used. The type checker is a translation scheme that
synthesizes the type of each expression from the type of its sub-
expressions.
• Type checker can handle arrays, pointers, statements and
functions.

P --> D; E
D--> D; D | id: T
T--> char | integer | array[num] of T | * T
E--> literal | num | id | E mod E | E[E] | E*
Base Types: char, integer, type-error
 Translation schemes
P --> D; E
D--> D;D
D--> id :T { addtype(id.entry,T.type);}
T--> char {T.type= char;}
T--> integer {T.type=integer;}
T-->*T_1 {T.type=pointer(T_1.type);}
T--> array[num] of T_1 { T.type =array(1..num.val,T_1.type); }
 Type Checking of Expressions
E--> literal { E.type=char}
E--> num { E.type =integer}
E--> id { E.type =lookup(id.entry)}
E--> E_1 mod E_2 { E.type =if (E_1.type ==integer) and (E_2. Type ==integer)
then integer; else type-error
E--> E_1[E_2] { E.type=if ((E_2.type==integer) and (E_1.type==array(s,t)) then
t; else type-error;}
E--> *E_1 { E.type = if (E_1.type ==pointer(t)) then t else type-error;
 Type Checking for Statements
S--> id:=E { S.type:= if id.type == E.type then void else type-error}

S--> if E then S {S.type:= if E.type == boolean then S_1.type else

type-error}

S--> while E do S {S.type:= if E.type == boolean S_1.type; else

type-error}

S--> S_1; S_2 {S.type:= if S_1.type==void and S_2.type ==void

then void else type-error}
 Type Checking of Functions
E--> E(E)

T--> T 1’->’ T2 { T.type = T1.type -> T2.type}

E--> E1(E2) {E.type = if E_2.type ==s and E1.type == s--> t

then t; else type-error;
 Type expression
 A base type is a type expression
 A type name is a type expression
 A type constructor is a type expression (arrays, records,
pointers, functions)
 Type equivalence
 Name equivalence - In many languages, e.g. Pascal, types
can be given names. Name equivalence views each distinct
name as a distinct type. So, two type expressions are name
equivalent if and only if they are identical.

 Structural equivalence - Two expressions are structurally

equivalent if and only if they have the same structure; i.e., if
they are formed by applying the same constructor to
structurally equivalent type expressions. It can be so that two
expressions are of the same basic type.
 Strong Typing
• Strongly typed PL- By definition, PL requires all programs to be
type checkable
• Statically strongly typed PL - compiler allows only programs that
can be type checked fully at compile- time
• Dynamically strongly typed PL -Operations include code to check
runtime types of operands, if type cannot be determined at
compile-time
• Pascal, Java
 Type conversion
• x + i, where x is real and i is integer
• Compiler may have to first convert one of the operands of +
to ensure that both operands are of the same type when
addition takes place
• Postfix notation of x + I might be: x i inttoreal real+
• inttoreal operator converts I from integer to real and real+
performs real addition on its operands.
 Coercions
• Implicit conversion(automatic) - coercion
– In C, mixed mode numerical operations
• double d, e; …e=d+2; / / 2 coerced to 2.0
– Usually can use widening or conversion without loss
of precision
– Cannot coerce user-defined types or structures
 Explicit conversion
• The programmer must write something to cause
the conversion
• Just look like function applications to a type
checker