type-checker-generator

name: type-checker-generator description: 'Generates type checkers from language specifications. Use when: (1) Designing a new programming language, (2) Adding type checking to an interpreter, (3) Implementing core language proofs, (4) Building language prototypes.' version: 1.0.0 tags:

• type-systems
• type-checking
• compiler
• static-analysis difficulty: intermediate languages:
• python
• ocaml dependencies:
• lambda-calculus-interpreter

Type Checker Generator

Generates sound and complete type checkers from formal type system specifications.

When to Use

• Designing a new programming language
• Implementing type systems from research papers
• Building interpreters with static type checking
• Proving type soundness properties
• Creating minimal viable languages (MVLs)

What This Skill Does

1. Parses type system specifications - Reads formal rules (typing judgments)
2. Generates type checker code - Produces executable type checker
3. Proves soundness - Outputs progress + preservation proof sketch
4. Handles edge cases - Generates error messages for type errors

How to Use

1. Specify syntax and declarative typing rules for your language
2. Encode algorithmic checking rules (and inference where needed)
3. Add substitution/unification support for polymorphism
4. Validate with positive/negative tests and meta-theory checks

Key Concepts

Type System Components

Soundness Theorem

A type system is sound if:

1. Progress: A well-typed term is either a value or can take a step
2. Preservation: If ⊢ e : τ and e → e', then ⊢ e' : τ

Implementation Patterns

Structure

class TypeChecker:
    def __init__(self, type_system: TypeSystem):
        self.type_system = type_system
        self.context = {}
        self.errors = []
    
    def check(self, term: Term) -> Optional[Type]:
        """Main entry point: check term is well-typed"""
        pass
    
    def check_app(self, func: Term, arg: Term) -> Optional[Type]:
        """Check application using T-App rule"""
        pass
    
    def unify(self, t1: Type, t2: Type) -> bool:
        """Unify two types (for inference)"""
        pass

Error Reporting

def type_error(self, term: Term, expected: Type, actual: Type):
    self.errors.append(TypeError(
        location=term.location,
        message=f"Expected {expected}, got {actual}"
    ))

Common Patterns

Bidirectional Type Checking

Separate into:

• Checking: Given τ, verify e : τ (easier)
• Inferring: Given e, infer τ (harder)

def synth(self, e: Term) -> Optional[Type]:
    """Synthesis/inference mode"""
    match e:
        case Var(x): return self.lookup(x)
        case App(e1, e2):
            t1 = self.synth(e1)
            t2 = self.check(e2, t1.param_type)  # Check against expected
            return t1.return_type

def check(self, e: Term, tau: Type) -> bool:
    """Checking mode"""
    match e:
        case Lam(x, body):
            self.check(body, tau.body)  # Generalize
        case _:
            tau' = self.synth(e)
            return tau' <= tau  # Subtype check

Constraint-Based Typing

Collect constraints during traversal, solve afterward:

def infer(self, e: Term) -> (Type, Constraints):
    constraints = []
    match e:
        case App(e1, e2):
            t1, c1 = self.infer(e1)
            t2, c2 = self.infer(e2)
            fresh = fresh_type_var()
            constraints.append((t1, Fun(t2, fresh)))
            return (fresh, c1 ++ c2 ++ constraints)

Tips

• Start with the simply-typed lambda calculus (STLC)
• Add products, sums, then polymorphism
• Prove soundness alongside implementation
• Use bidirectional typing for better error messages
• Track source locations for meaningful errors

Common Issues

Tradeoffs and Limitations

Design Tradeoffs

When NOT to Use This Approach

• For very large codebases: Consider separate type checker as a service
• For gradual typing: Use gradual type inference instead (different algorithm)
• For dependent types: Requires theorem proving; see dependent-type-implementer
• For row polymorphism: See specialized row-polymorphism skill

Limitations

• Soundness vs completeness: Type checkers are usually sound (reject some valid programs) but complete checking is undecidable for rich type systems
• Error localization: Precise error locations require source tracking throughout
• Incremental checking: Not built-in; requires separate infrastructure

Assessment Criteria

A high-quality type checker implementation should have:

Quality Indicators

✅ Good: Passes all well-typed programs, rejects ill-typed, produces clear errors ⚠️ Warning: Incomplete coverage, cryptic error messages, no inference ❌ Bad: Soundness bugs, crashes on valid input

Related Skills

• type-inference-engine - Type inference (without annotations)
• subtyping-verifier - Verify subtyping relations
• lambda-calculus-interpreter - Interpreter for lambda calculi
• hoare-logic-verifier - Prove soundness theorems

Canonical References

Research Tools & Artifacts

For implementing type checkers, refer to these research-quality implementations:

Coq Formalizations (for verification)

• "Types and Programming Languages" in Coq - Full formalization of TAPL
• Coq's kernel - Certified type checker implementation
• Iris (MPI-Freiburg) - Higher-order separation logic

Relevant Papers with Implementations

• "Practical Type Inference for the GHC Type System" (Jones, 2007) - GHC's implementation
• "Complete and Easy Bidirectional Type Checking" (Pfenning & Davies, 2001) - The gold standard for bidirectional typing
• "Extensible records with scoped labels" (Leijen, 2005) - Practical row polymorphism design

Research Frontiers

Current active research directions in type checking:

1. Gradual Typing & Reliability

• Key papers: "Gradual Typing for Functional Languages" (Siek & Taha, 2006), "Reticulated Python" (Vitousek et al.)
• Challenge: Blending static and dynamic typing seamlessly
• Tools: Pyre (Facebook), mypy, TypeScript

2. Bidirectional Type Checking

• Key papers: "Reconstructing Type Inference" (Dunfield & Krishnaswami, 2023)
• Challenge: Balancing inference power with error messages
• Tools: Agda, Idris, Deduce

3. Effect Systems & Capabilities

• Key papers: "Koka: Programming with Row Polymorphic Effect Types" (Leijen, 2017)
• Challenge: Tracking side effects without monads
• Tools: Koka, Frank, Eff

4. Qualified Types & Type Classes

• Key papers: "How to Make Ad-hoc Polymorphism Less Ad-hoc" (Wadler & Blott, 1989)
• Challenge: Overloading without violating parametricity
• Tools: GHC Haskell, PureScript

Implementation Pitfalls

Common mistakes in production type checker implementations:

The "Value Restriction" Story

The original Hindley-Milner let-polymorphism was unsound:

(* Unsound in original ML *)
let pair = (ref [], ref []) in
let (a, b) = pair in
  a := [1];  (* Add int to list *)
  b := [true]  (* Now a contains bools! *)

Solution: Only generalize at value bindings (not function arguments). This is why you see let vs let rec semantics differ in OCaml.

Principal Types Are Not Always Principal

Even with Hindley-Milner, certain programs have no principal type. Know when to report ambiguity vs. try harder:

-- Which type is principal?
f x = [x, x + 1]  -- [Int] or [Num a]?