COMPILER DESIGN

Type Checking & Runtime Environments

Part 1: TYPE CHECKING

1. Definition of Type Checking

Type checking is the process of verifying and enforcing the constraints of types in a programming
language. It ensures that every operation in the program is applied to operands of the correct type.

Type A set of values and a set of operations on those values. E.g., integer:
values {…,-2,-1,0,1,2,…}, operations {+, -, *, /, mod, <, >}

Type Checker A component of the compiler that assigns types to language

constructs and ensures consistency of types throughout the
program.

Goals of Type Checking:

• Detect errors early — before runtime
• Ensure operations are meaningful (e.g., you can't add a string to a boolean)
• Guide code generation (e.g., integer ADD vs. floating-point FADD)
• Provide documentation and improve readability

✏️ Example — Type Errors Detected by Type Checker:

int x = "hello"; // Error: string assigned to int
boolean b = 5 + true; // Error: arithmetic on boolean
float f = x[2]; // Error: x is not an array
int y = x + 3.5; // Warning/Error: type mismatch in addition

2. Type Expressions
A type expression is a formal notation used to describe the type of a language construct. Type
expressions are built from basic types using type constructors.
▶ Basic (Primitive) Types
• integer — whole numbers
• real / float — floating point numbers
• boolean — true or false
• char — single character
• void — no value (used for procedures)
• error — special type used when a type error is detected

▶ Type Constructors
Constructor Notation Example Meaning
Array array(I, T) array(1..10, int) Array of 10 integers
Pointer pointer(T) pointer(int) Pointer to an integer
Product T1 × T2 int × real Pair: one int and one
real
Function T1 → T2 int → bool Function taking int,
returning bool
Record record(fields) record(name:char, Struct with named fields
age:int)

✏️ Examples — Type Expressions:

int a[10][20] → array(1..10, array(1..20, int))
int *p → pointer(int)
int f(float, float) → real × real → int
struct { int age; char grade; } → record(age:int, grade:char)

🔑 Type expressions are the formal language of the type system — every value and
variable has a type expression.

3. Type Systems
A type system is a set of rules that assigns type expressions to constructs in a programming language.
A sound type system guarantees that a type-correct program will not produce type errors at runtime.

▶ Components of a Type System

• Type rules — how types are assigned to expressions and statements
• Type environment (Γ) — a mapping from variable names to their types
• Type inference — deriving the type of an expression from the types of its parts
 • Type compatibility — rules for when one type can be used in place of another

▶ Type Rules (Inference Rules)

Type rules are written in the form: Premise₁, Premise₂ ⊢ Conclusion

Rule 1 (Literal): ⊢ n : integer (integer literal has type integer)

Rule 2 (Variable): x : T ∈ Γ ⊢ x : T (variable has its declared type)
Rule 3 (Addition): E1 : integer, E2 : integer ⊢ E1+E2 : integer
Rule 4 (Array Index): E1 : array(s,T), E2 : integer ⊢ E1[E2] : T
Rule 5 (Function App): E1 : S→T, E2 : S ⊢ E1(E2) : T
Rule 6 (Assignment): x : T ∈ Γ, E : T ⊢ x := E : void

✏️ Example — Applying Type Rules:

Given: int a[10]; int i;

Type derivation for a[i] + 5:

Step 1: a : array(1..10, int) [from declaration]
Step 2: i : int [from declaration]
Step 3: a[i] : int [Rule 4: array index]
Step 4: 5 : int [Rule 1: literal]
Step 5: a[i] + 5 : int [Rule 3: addition]

4. Static and Dynamic Type Checking

Aspect Static Checking Dynamic Checking

When At compile time At runtime
Errors found Before execution During execution
Performance No runtime overhead Runtime overhead (type tags)
Flexibility Less flexible More flexible
Examples C, C++, Java, Go Python, JavaScript, Ruby, Lisp
Type info stored In symbol table With every value (tags)

▶ Static Type Checking

All types are known at compile time. The type checker analyzes source code and reports errors before
the program runs.
• Advantages: Faster programs, early error detection, better tooling (autocomplete)
• Disadvantages: Less flexible, requires type declarations
 ✏️ Static Type Checking (Java):
int x = 5;
String s = "hello";
int y = x + s; // COMPILE-TIME ERROR: cannot add int and String

▶ Dynamic Type Checking

Types are checked at runtime. Each value carries a type tag that is inspected before operations.
• Advantages: Very flexible, no need for declarations
• Disadvantages: Runtime errors, slower execution

✏️ Dynamic Type Checking (Python):

x = 5
x = "hello" # OK — Python allows reassignment to different types
y = x + 10 # RUNTIME ERROR: TypeError: can only concatenate str to
str

▶ Strongly Typed vs Weakly Typed

Strongly Typed No implicit type conversions; all type mismatches are errors (e.g.,
Python, Java)

Weakly Typed Implicit coercions allowed; types converted automatically (e.g., C,

JavaScript)

✏️ Weak Typing (JavaScript):

"5" + 3 → "53" (number coerced to string!)
"5" - 3 → 2 (string coerced to number!)
This inconsistency is a source of many bugs.

5. Specification of a Simple Type Checker

A simple type checker can be specified using grammar rules annotated with type-checking semantic
actions. Consider this simple language grammar:

P → D ; E
D → D ; D | id : T
T → boolean | integer | array [ num ] of T | ↑T
E → literal | num | id | E mod E | E [ E ] | E ↑
▶ Type Checking Rules for the Grammar

P → D ; E { if [Link] ≠ error then [Link] = [Link] }

D → id : T { addtype([Link], [Link]) }

T → boolean { [Link] = boolean }

T → integer { [Link] = integer }
T → array[num] { [Link] = array(1..[Link], [Link]) }
of T1
T → ↑T1 { [Link] = pointer([Link]) }

E → literal { [Link] = char }

E → num { [Link] = integer }
E → id { [Link] = lookup([Link]) }
E → E1 mod E2 { if [Link]=integer and [Link]=integer
then [Link] = integer
else [Link] = error }
E → E1[E2] { if [Link]=integer and [Link]=array(s,t)
then [Link] = t
else [Link] = error }
E → E1↑ { if [Link] = pointer(t)
then [Link] = t
else [Link] = error }

✏️ Example — Running the Type Checker:

Declarations: a : array[10] of integer; i : integer

Checking expression: a[i] mod 5

[Link] = array(1..10, integer) [lookup in symbol table]

[Link] = integer [lookup in symbol table]
a[i].type = integer [array index rule: t = integer]
[Link] = integer [literal rule]
a[i] mod 5 : integer [mod rule: both integer → OK]

6. Equivalence of Type Expressions

When two types are declared separately, the compiler must decide if they are 'the same type'. There
are two major approaches:

▶ a) Structural Equivalence
Two type expressions are equivalent if they have the same structure — same constructors applied in
the same way to equivalent component types.
• Compare type expressions recursively
• Arrays must have same index range AND same element type
• Records must have same field names with same types
 Algorithm: structurallyEquivalent(s, t)
if s and t are same basic type → return true
if s = array(s1,s2) and t = array(t1,t2)
→ return structurallyEquivalent(s1,t1) AND structurallyEquivalent(s2,t2)
if s = pointer(s1) and t = pointer(t1)
→ return structurallyEquivalent(s1,t1)
if s = s1→s2 and t = t1→t2
→ return structurallyEquivalent(s1,t1) AND structurallyEquivalent(s2,t2)
return false

✏️ Example — Structural Equivalence:

type Link = ↑Cell;
type Cell = record { info: integer; next: Link }

p : Link; q : ↑Cell

Are p and q equivalent?

[Link] = pointer(Cell)
[Link] = pointer(Cell)
structurallyEquivalent(pointer(Cell), pointer(Cell)) → TRUE ✅
So p and q are type-compatible under structural equivalence.

▶ b) Name Equivalence
Two type expressions are equivalent ONLY if they were declared with the SAME type name. Each type
declaration creates a unique type.
• Stricter than structural equivalence
• Used in languages like Pascal (strict), Ada
• Two variables of separately-declared identical structures are NOT compatible

✏️ Example — Name Equivalence (Pascal-like):

type A = array[1..10] of integer;
type B = array[1..10] of integer;

var x : A;
var y : B;

x := y; // NAME EQUIVALENCE ERROR! A and B are different type names

// even though their structures are identical.

Property Structural Equivalence Name Equivalence

Basis Shape/structure of types Declaration name only
 Strictness Less strict More strict
Used in C (for structs), ML Pascal (strict), Ada
Two identical structs Compatible Incompatible (unless same name)
Aliases Compatible with original May be different (impl-dependent)

7. Type Conversions
Type conversion (coercion) changes a value of one type to another type. There are two kinds:

▶ a) Implicit Conversion (Coercion / Widening)

Automatically done by the compiler when needed. No data loss occurs (goes from narrower to wider
type).

Widening conversions (safe, no data loss):

byte → short → int → long → float → double
char → int

In a type checker, if E1 : int and E2 : real, then E1+E2:

→ emit a 'widen' instruction: temp = inttoreal(E1)
→ compute temp + E2 as real arithmetic
→ result type: real

✏️ Example — Implicit Coercion:

int i = 5;
float f = 3.14;
float result = i + f; // i is AUTOMATICALLY widened to 5.0
// result = 5.0 + 3.14 = 8.14

Three-address code generated:

t1 = inttoreal(i) // widen i to real
t2 = t1 + f // real addition
result = t2

▶ b) Explicit Conversion (Casting / Narrowing)

Programmer-specified conversion. May lose information (goes from wider to narrower type).

✏️ Example — Explicit Cast (Narrowing):

double d = 9.99;
int i = (int) d; // EXPLICIT cast — programmer takes responsibility
// Result: i = 9 (fractional part lost!)
 float f = 1234567890.0f;
int x = (int) f; // May lose precision — overflow possible

▶ Type Checking with Coercions — Semantic Rules

E → E1 + E2:
if [Link] = integer AND [Link] = integer:
[Link] = integer
[Link] = [Link] || [Link] || 'ADD'

else if [Link] = real AND [Link] = real:

[Link] = real
[Link] = [Link] || [Link] || 'FADD'

else if [Link] = integer AND [Link] = real:

[Link] = real
t = newtemp()
[Link] = [Link] || 'inttoreal' [Link] 'into' t
|| [Link] || 'FADD' t [Link]

else: [Link] = error

Part 2: RUNTIME ENVIRONMENTS

1. Source Language Issues

The design of a runtime environment is heavily influenced by the features of the source programming
language. Key language issues include:

▶ Procedures and Scope

• Can procedures be recursive? (Requires activation records on a stack)
• Can procedures be nested? (Requires access links for non-local variables)
• What is the scope rule — static (lexical) or dynamic?

Static Scoping Name refers to the nearest enclosing declaration in the source code.
Used in C, Java, Python. Resolved at compile time.

Dynamic Scoping Name refers to the most recently activated declaration at runtime.
Used in older Lisps, some shell scripting.

✏️ Example — Static vs Dynamic Scoping:

int x = 1;

void f() { print(x); } // What does x refer to?

void g() { int x = 2; f(); }

Static scoping: f() prints 1 (x refers to global x in f's source scope)

Dynamic scoping: f() prints 2 (x refers to g's x, most recently
activated)

▶ Other Language Issues Affecting Runtime

• Value vs Reference parameters — affects how arguments are passed
• First-class functions / closures — require heap allocation for environments
• Garbage collection — automatic memory management
• Exceptions — require stack unwinding mechanisms

2. Storage Organization
A running program uses memory organized into several regions, each serving a different purpose:
 Memory Layout of a Running Program

Code (Text) Segment Executable instructions of the program

Static / Global Data Global variables, string literals, static vars
Heap (grows ↓) Dynamically allocated memory (malloc, new)
↕ (free space)
Stack (grows ↑) Activation records (local vars, parameters, return addr)

🔑 Stack grows toward lower addresses; Heap grows toward higher addresses. They must
not collide — that would be a stack overflow or heap overflow.

▶ Activation Record (Stack Frame)

Each procedure call creates an activation record on the stack containing:
• Return value — space for the result returned to the caller
• Actual parameters — values passed by the caller
• Control link (dynamic link) — pointer to caller's activation record
• Access link (static link) — pointer to enclosing scope's activation record
• Saved machine state — registers, program counter to restore on return
• Local data — local variables of the procedure
• Temporaries — intermediate values used during computation

✏️ Example — Stack at Runtime for factorial(3):

factorial(3) calls factorial(2) calls factorial(1):

┌─────────────────────────┐ ← Stack top

│ factorial(1) │ n=1, return_val=1
├─────────────────────────┤
│ factorial(2) │ n=2, return_val=?
├─────────────────────────┤
│ factorial(3) │ n=3, return_val=?
├─────────────────────────┤
│ main() │ caller
└─────────────────────────┘ ← Stack bottom

3. Storage Allocation Strategies

▶ a) Static Allocation
Memory for all variables is determined at compile time. The memory stays allocated for the entire
duration of the program.
• Used for: global variables, static local variables, string literals
• Advantage: Simple, no runtime overhead
• Disadvantage: Cannot support recursion (only one copy of each variable exists)

✏️ Example — Static Allocation (FORTRAN-style):

COMMON /BLOCK/ X, Y, Z ! Global common block — fixed addresses

SUBROUTINE FOO(A)
SAVE I ! I retains value between calls (static)
I = I + 1
END

All variables have fixed addresses assigned at compile time.

No stack needed — but recursion is IMPOSSIBLE.

▶ b) Stack (Dynamic) Allocation

Activation records are pushed/popped on a runtime stack. Memory for local variables is allocated on
procedure entry and freed on return.
• Used for: local variables, parameters in recursive languages
• Advantage: Supports recursion naturally, memory reused efficiently
• Disadvantage: Variable sizes must be known at compile time (for most languages)

✏️ Example — Stack Allocation Sequence:

void g(int x) { int b = x*2; }

void f(int a) { int y = a+1; g(y); }
main() { f(5); }

Execution:
main enters → push main's frame
f(5) called → push f's frame {a=5, y=6}
g(6) called → push g's frame {x=6, b=12}
g returns → pop g's frame
f returns → pop f's frame
main returns → pop main's frame

▶ c) Heap Allocation
Memory is allocated and deallocated in any order at runtime, using explicit allocation (malloc/new) or
garbage collection.
• Used for: dynamically created objects, data structures of unknown size
• Advantage: Flexible, objects can outlive the procedure that created them
 • Disadvantage: Fragmentation, overhead, memory leaks (if manual)

✏️ Example — Heap Allocation (C/Java):

// C — manual heap management

int* arr = (int*) malloc(n * sizeof(int)); // allocate on heap
arr[0] = 42;
free(arr); // must manually free!

// Java — automatic garbage collection

int[] arr = new int[n]; // heap allocation
// no free needed — GC handles it

Strategy When Allocated When Freed Supports Use Case

Recursion
Static Compile time Program end No Global vars,
FORTRAN
Stack Procedure entry Procedure exit Yes Local vars, C/Java
Heap Runtime (explicit) Runtime Yes Dynamic objects
(explicit/GC)

4. Access to Non-local Names

In languages with nested procedures (Pascal, Python), a procedure may need to access variables
declared in an enclosing procedure. This requires special runtime support.

▶ a) Static (Access) Links

Each activation record stores a pointer (static link) to the activation record of its statically enclosing
procedure.
• To access a variable k levels up, follow k static links
• Used in languages with nested scopes

✏️ Example — Static Links (Pascal-like):

procedure A;
var x : integer;
procedure B;
var y : integer;
procedure C;
begin
x := 5; { access x — 2 levels up in source }
end;
 end;
end;

At runtime, C's activation record has:

static link → B's record (1 hop)
B's record has static link → A's record (2 hops)
x is found by following 2 static links

▶ b) Display
A global array (the display) where display[i] holds a pointer to the most recent activation record at
nesting depth i. Faster than chasing static links.
• Access at nesting depth k: one pointer lookup — display[k]
• More efficient than static links for deep nesting

▶ c) Lambda Lifting (for Closures)

Free variables of a nested function are passed as extra parameters. Used in functional languages.

5. Parameter Passing
When a procedure is called, arguments must be communicated to the called procedure. There are
several mechanisms:

▶ a) Call by Value
A copy of the actual parameter's value is passed. Changes to the formal parameter do NOT affect the
actual.

✏️ Example — Call by Value (C):

void swap(int a, int b) {
int t = a; a = b; b = t;
}

int x = 5, y = 10;
swap(x, y);
// After call: x = 5, y = 10 (UNCHANGED!)
// Only copies were swapped inside swap()

▶ b) Call by Reference
The address of the actual parameter is passed. The formal parameter is an alias for the actual.
Changes DIRECTLY affect the actual.
 ✏️ Example — Call by Reference (C++):
void swap(int &a, int &b) {
int t = a; a = b; b = t;
}

int x = 5, y = 10;
swap(x, y);
// After call: x = 10, y = 5 (SWAPPED!)
// a and b are aliases for x and y

▶ c) Call by Value-Result (Copy-Restore)

Copies value in at call time (like value), then copies the final value back to the actual at return time.
Used in Ada (IN OUT parameters).

✏️ Example — Value-Result:
Procedure foo(a: IN OUT integer)
a := a + 1
End;

x = 5; foo(x);
Step 1: Copy x=5 into formal a
Step 2: a becomes 6 inside foo
Step 3: On return, copy a=6 BACK to x
Result: x = 6

▶ d) Call by Name
The actual parameter expression is substituted textually into the procedure body and re-evaluated each
time the formal is used. Used in Algol 60.

✏️ Example — Call by Name (Algol 60 style):

procedure increment(x) { x := x + 1; }

Call: increment(a[i])
Textual substitution: a[i] := a[i] + 1

If i changes during the call, a[i] refers to DIFFERENT array elements!

This can cause surprising behavior but is very powerful.

Mechanism What is Passed Caller Affected? Language Example

Call by Value Copy of value No C, Java (primitives)
Call by Reference Address of actual Yes (directly) C++ (&), Fortran
 Call by Value-Result Value in; copy back on Yes (on return) Ada IN OUT
return
Call by Name Un-evaluated expression Depends Algol 60
Call by Sharing Reference to object Yes (object Python, Java (objects)
mutation)

6. Symbol Tables
A symbol table is a data structure used by the compiler to store information about identifiers (variables,
functions, types) declared in the program.

▶ Information Stored in Symbol Table

• Name — the identifier string
• Type — the type expression (int, float, array, etc.)
• Scope — which scope the identifier belongs to
• Memory location / offset — where in memory the value is stored
• For functions: number and types of parameters, return type
• For arrays: element type, dimensions, size

▶ Operations on Symbol Table

insert(name, type) Add a new identifier with its type to the table

lookup(name) Find and return the type/info for an identifier; error if not found

delete(name) Remove an identifier when its scope ends

▶ Implementation Strategies
Structure Lookup Time Insert Time Best For
Linked List O(n) O(1) Small tables, simple compilers
Binary Search Tree O(log n) O(log n) Medium-sized tables
Hash Table O(1) avg O(1) avg Large tables — most compilers
use this
Trie O(|key|) O(|key|) String keys, prefix matching

▶ Scoped Symbol Tables

For languages with nested scopes, a separate symbol table is maintained for each scope. They are
organized in a stack:
• On entering a new scope → push a new table
• On lookup → search current table, then enclosing tables outward
• On exiting a scope → pop the table (identifiers go out of scope)

✏️ Example — Scoped Symbol Tables:

int x = 1; // Scope 0 (global): {x: int}

void f(int a) { // Scope 1: {a: int}
int y = 2; // {y: int}
{
int x = 3; // Scope 2: {x: int} ← shadows global x
print(x); // Lookup x: found in Scope 2 → prints 3
print(y); // Lookup y: not in Scope 2, found in Scope 1 →
prints 2
print(a); // Lookup a: not in Scope 2, found in Scope 1 →
value of a
} // Scope 2 popped
print(x); // Lookup x: Scope 2 gone, found in Scope 0 →
prints 1
}

Symbol Table Stack at innermost point:

Scope 2: { x: int }
Scope 1: { a: int, y: int }
Scope 0: { x: int, f: int→void }

▶ Hash Table Implementation

Hash function: h(s) = (s[0] + s[1]*31 + s[2]*31² + ...) mod tableSize

Symbol table entry structure:

struct Entry {
char* name; // identifier name
Type type; // type expression
int offset; // memory offset
Entry* next; // for chaining (collision resolution)
};

insert(name, type):
h = hash(name)
create new Entry e with [Link]=name, [Link]=type
[Link] = table[h] // chain at front
table[h] = e

lookup(name):
h = hash(name)
e = table[h]
 while e != null:
if [Link] == name: return e
e = [Link]
return NOT_FOUND

Quick Summary — All Topics

Topic Core Idea Key Term

Type Checking Verify type consistency of all operations Type safety
Type Expressions Formal notation for types using array(T), pointer(T), S→T
constructors
Type Systems Rules assigning types to program Type environment (Γ)
constructs
Static Checking Types checked at compile time C, Java, Go
Dynamic Checking Types checked at runtime with tags Python, JavaScript
Simple Type Checker Grammar + semantic rules for type lookup(), addtype()
assignment
Structural Equivalence Same structure = same type Recursive comparison
Name Equivalence Same name = same type only Pascal strict mode
Type Conversion Implicit (widen) vs Explicit (cast) inttoreal, (int)x
Source Language Issues Scoping, recursion affect runtime design Static vs dynamic scope
Storage Organization Code / Static / Heap / Stack regions Activation record
Static Allocation Fixed addresses at compile time No recursion
Stack Allocation Push/pop on procedure call/return Supports recursion
Heap Allocation Dynamic, any order, GC or manual malloc/new
Non-local Access Static links or display for nested scopes Access link
Parameter Passing Value / Reference / Value-Result / Name Aliasing
Symbol Tables Store id → type mappings per scope Hash table, scoped stack

— END OF NOTES —