Questions: Dependent Types and Value-Level Type Constraints

Question 1

A dependently-typed language defines a function with signature: `matMul : Matrix<m, k> → Matrix<k, n> → Matrix<m, n>`. A programmer calls `matMul A B` where A has type `Matrix<3, 4>` and B has type `Matrix<5, 2>`. What happens?

• A. The program compiles but throws a dimension mismatch exception at runtime
• B. The program fails to type-check at compile time, because 4 ≠ 5 (the inner dimensions don't match)
• C. The program compiles; the type system cannot track numeric values like matrix dimensions
• D. The behavior depends on whether the compiler performs value inference

Answer: (B)

This is the core payoff of dependent types. In a conventional type system, `Matrix` is typed with only element type, and dimension mismatches cause runtime exceptions. In a dependent type system, `Matrix<m, k>` encodes both dimensions as type-level values. When calling `matMul A B`, the compiler unifies the shared dimension: A's second dimension `k` must equal B's first dimension. Since 4 ≠ 5, the types are incompatible and the program is rejected at compile time — before any execution, before any test. The bug is impossible to ship, not just caught after the fact.

Question 2

Why do dependently typed languages like Agda and Idris require all functions used in types to be provably terminating (total functions)?

• A. Totality is a convenience requirement to make programs easier to read, not a formal requirement
• B. Without guaranteed termination, type checking could loop forever trying to evaluate type-level computations
• C. Partial functions cannot be expressed in dependent type systems due to syntactic restrictions
• D. Totality is required only for standard library functions, not user-defined functions

Answer: (B)

Type checking in dependent type systems requires evaluating type-level expressions to determine if two types are equal. For example, to verify that `Vec<T, 2+3>` and `Vec<T, 5>` are the same type, the compiler must evaluate `2+3`. If functions used in types can loop infinitely, type checking can loop infinitely — making type checking undecidable. Requiring totality (all functions terminate on all inputs) guarantees that type-level evaluation always terminates, keeping type checking decidable. This is the mathematical prerequisite for a sound type system, not a convenience choice.

Question 3

A function with type `safeHead : Vec<T, S n> → T` in a dependently-typed language provides a compile-time guarantee that the input list is non-empty.

• T. True
• F. False

Answer: True

True. `Vec<T, S n>` (where `S n` means 'successor of n,' i.e., n+1) is the type of vectors with at least one element — an empty vector has type `Vec<T, 0>` and cannot unify with `Vec<T, S n>`. Any caller of `safeHead` must provide a vector whose length type unifies with `S n` for some n. Passing an empty vector causes a type error at compile time, not a runtime crash. The type signature encodes the precondition, and the type checker enforces it automatically — no runtime guard or documentation needed.

Question 4

Dependent types are a generalization of generic types (parametric polymorphism): instead of parameterizing types over other types, you parameterize them over values.

• T. True
• F. False

Answer: False

False — this description conflates two different dimensions of the lambda cube. Parametric polymorphism (generics like `List<T>`) allows types to depend on *other types*. Dependent types allow types to depend on *values*. These are distinct axes of expressiveness: generics capture 'a list of any element type,' while dependent types capture 'a list of exactly n elements.' A fully dependently-typed system supports types depending on values, types depending on types, terms depending on types, and terms depending on terms. Dependent types are not a generalization of generics — they occupy a different dimension of the type theory design space.

Question 5

In dependent type theory, it is said that 'writing a well-typed program is the same as constructing a proof.' What does this mean concretely, and why does it eliminate certain categories of bugs?

Model answer: By the Curry-Howard correspondence, types are propositions and programs inhabiting those types are proofs. A function `append : Vec<T, m> → Vec<T, n> → Vec<T, m+n>` is not just code — it is a proof that appending an m-element vector to an n-element vector yields an (m+n)-element vector. If the implementation doesn't maintain this invariant, the program fails to type-check (the proof is invalid). Bugs involving invariant violations become type errors caught at compile time rather than runtime failures discoverable only during execution or testing.

The Curry-Howard isomorphism establishes a correspondence between logic and programming: propositions correspond to types, proofs correspond to programs, and proof verification corresponds to type checking. If you can write a well-typed dependently-typed program, you have simultaneously proven the properties encoded in its type signature. Errors like 'I appended two lists and got the wrong length' become logically impossible — they would require an invalid proof, which the type checker rejects. The compiler acts as a proof assistant, verifying invariants mechanically on every compilation.