Type Systems
1. What a Type System Does
A type system assigns a type to every expression and proves no type errors at run time (for safe languages). Compiler uses it to reject bad programs, insert conversions, choose ops/sizes.
2. Components
| Part | Example |
|---|---|
| Base types | int, float, bool, char |
| Constructors | array, pointer, struct, func, generic |
| Rules | E1+E2: lub(type1,type2); if needs bool |
| Equivalence | name (Ada) vs structural (C struct) |
| Checking | static (compile) vs dynamic (run tag) |
| Inference | deduce auto x=5→int (Hindley-Milner) |
= least upper bound: int+float→float.
3. Soundness
Sound = well-typed programs never get stuck on type errors. C is unsound (casts, void*); Java/ML are largely sound (modulo nulls). Strong vs weak, static vs dynamic trade safety for flexibility.
4. Compiler Use
Types drive overload resolution, IR op choice (ADDI vs ADDF), width/offsets, and GC layout.
5. Exam Points
- Define type system + rules with example — 5-7 marks, very frequent.
- Name vs structural equivalence — 3-5 marks, frequent.
- Static vs dynamic, soundness — 3 marks, frequent.