Type Systems & Type Checking

Dynamic Type and Static Type

  • Runtime vs Compile time
  • Slow vs fast
  • flexible vs inflexible

Strong Typing

  • Sound type system: guarantees that a no type errors can occur at runtime
  • cons
    • Some checks can only be done dynamically (Array bounds checking)
    • Such checking can cause serious performance degradation
    • Even so-called strongly typed languages often have “holes" in the type system (e.g. variant records in Pascal)

Type Equivalence

  • If types are required to match, the question of what types are considered to be “equivalent" arises
  • Structural equivalence requires equivalent structures
    • Identical basic types
    • Same type constructor applied to equivalent types
  • Name equivalence considered types to be equal only if the same names are used
  • C uses structural equivalence except for records

Type Signatures

  • The signature of a procedure is a description of the types of its arguments and type of its result.
  • i.e) sqrt : real -> real, mod: integer X integer -> integer

Polymorphic Procedures

  • A procedure that has multiple type signatures is called polymorphic

Failure Of Type Checking Due To Aliasing, Variant Records, Subroutine Calls


  • Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools

  • UT Austin CS375: Compilers by G.Novak.