CD Notes
Comprehensive exploration of type checking: type system fundamentals, type inference algorithms, compatibility checking, polymorphism handling, practical static type analysis for modern programming languages.
Fundamentals
Type checking verifies that operations in a program are compatible with operand types. Static type checking performs this at compile-time; dynamic type checking at runtime.
Why Type Checking?
| 1. Correctness | Prevent invalid operations |
| 2. Efficiency | Enable optimizations |
| - Know operand sizes | choose efficient instructions |
| 3. Safety | Catch errors early |
| 4. Documentation | Types express intent |
Type System Components
Base Types
Primitive
- int, float, boolean, char, void
Composite
- array: type[size]
- record/struct: { type1 f1; type2 f2; }
- function: (param_types) -> return_type
User-defined
- class, interface, enum
Type Relationships
| - Types compatible if | type1 == type2 OR type1 ≤ type2 |
| - Structural | types equivalent if same structure |
| - Nominal | types equivalent if same name |
Type Inference
Algorithm: Type Inference for Expressions
def infer_type(expr):
if expr.type == NumericLiteral:
if '.' in str(expr.value):
return FloatType()
else:
return IntType()
elif expr.type == StringLiteral:
return StringType()
elif expr.type == Variable:
return symbol_table.lookup(expr.name).type
elif expr.type == BinaryOp:
left_type = infer_type(expr.left)
right_type = infer_type(expr.right)
if expr.op == '+':
if left_type == IntType and right_type == IntType:
return IntType()
elif left_type in NumericTypes and right_type in NumericTypes:
return FloatType()
elif left_type == StringType or right_type == StringType:
return StringType()
else:
return ErrorType()
# ... handle other operators
elif expr.type == FunctionCall:
func = symbol_table.lookup(expr.name)
return func.return_typeCompatibility Checking
Type Compatibility Rules
Numeric types
byte → short → int → long → float → double
Compatibility: Can implicitly promote in chains
Object types (Java)
interface I {}
class C implements I {}
C compatible with I (structural)
Function types
(int, int) → int compatible with (int, int) → int
Covariant return, contravariant parameters (advanced)
Compatibility Checking Algorithm
def is_compatible(actual_type, expected_type):
# Exact match
if actual_type == expected_type:
return True
# Subtype
if is_subtype(actual_type, expected_type):
return True
# Implicit conversion
if can_promote(actual_type, expected_type):
# Insert conversion code
insert_cast(actual_type, expected_type)
return True
return False
def check_assignment(lhs, rhs):
rhs_type = infer_type(rhs)
if is_compatible(rhs_type, lhs.type):
return OK
else:
error(f"Cannot assign {rhs_type} to {lhs.type}")
return ERRORPolymorphism
Parametric Polymorphism (Generics)
Definition
generic<T> T identity(T x) { return x; }
Type checking
identity<int>(5) // T = int
identity<string>("hi") // T = string
During checking
Substitute type parameter with concrete type
Check resulting type constraints
Ad-Hoc Polymorphism (Overloading)
Definition
print(int x) // Version 1
print(string s) // Version 2
print(float f) // Version 3
Type checking
print(5) // Calls Version 1 (int matches)
print("hello") // Calls Version 2 (string matches)
print(3.14) // Calls Version 3 (float matches)
During checking
Find matching overload (exact match preferred)
If ambiguous: error
Practical Type Checking Examples
Type Checking Function Calls
def check_function_call(func_name, arguments):
func = symbol_table.lookup(func_name)
if func is None:
error(f"Undefined function: {func_name}")
return ErrorType()
# Check argument count
if len(arguments) != len(func.parameters):
error(f"Expected {len(func.parameters)} args, got {len(arguments)}")
return ErrorType()
# Check each argument type
for i, (arg, param) in enumerate(zip(arguments, func.parameters)):
arg_type = infer_type(arg)
if not is_compatible(arg_type, param.type):
error(f"Argument {i+1}: expected {param.type}, got {arg_type}")
return ErrorType()
return func.return_typeQuick Revision Notes
- Type checking: Verify operation-operand compatibility
- Static: At compile-time (usually)
- Dynamic: At runtime (less common in compiled languages)
- Type inference: Determine type from context
- Compatibility: Type1 assignable to Type2 (subtype or promotion)
- Promotion: Implicit widening (int → float)
- Polymorphism: Multiple implementations of same interface
Interview Q&A
Q1: What's the difference between static and dynamic type checking?
A: Static: compile-time checking (most errors caught early). Dynamic: runtime checking (more flexible but slower). Modern languages combine both: static for most checks, dynamic for runtime (polymorphism dispatch).
Q2: Why do strongly-typed languages use type inference?
A: Improves usability (don't require explicit types everywhere) while maintaining safety (compiler verifies consistency). Example: x = 5; clearly integer without explicit int x = 5;.
Q3: How do you handle type checking in languages with weak typing (like JavaScript)?
A: Limited static checking; rely on runtime type checks. Or use separate type checker (TypeScript). Type coercions are often implicit and surprising.
Q4: What makes type compatibility checking complex in object-oriented languages?
A: Inheritance hierarchies, polymorphism, generics, constraints. Must handle subtype relationships, variance (covariant vs contravariant), type bounds, and intersection types.
Q5: How do you prevent infinite type checking recursion?
A: Memoization: cache type check results. Occur check: detect cycles in type equations. Bounds on type parameter substitution.
Q6: What's the relationship between type checking and code generation?
A: Type checking validates correctness; code generation produces executable code. Type info guides code generation: operand sizes, calling conventions, layout. Must type-check before generating.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Type Checking: Static Analysis for Type Safety in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, semantic, analysis, type, checking
Related Compiler Design Topics