THE DEPENDENT TYPE a type that depends on a value — the length lives in the type
A dependent type may mention a value: Vec n a is a list of exactly n elements, where n is a number in the type. Now append : Vec m a → Vec n a → Vec (m+n) a — the type does arithmetic, and a length mismatch is a type error, caught before the program runs. Martin-Löf built a whole intuitionistic type theory this way, and via Curry-Howard its types are propositions and its programs are proofs. Dependent types erase the line between checking a program and proving a theorem — the summit of the discipline.
THE TECHNIQUE types may contain values: Vec m ++ Vec n : Vec (m+n)
append on length-indexed vectors adds the lengths in the type. The demo appends a Vec 3 and a Vec 2 and reads the result length off the type: live demo
HISTORY & CREDIT Martin-Löf 1972 · de Bruijn
“Types describe shapes; values fill them.” — a dependent type lets the value flow back into the shape, so the compiler can check m+n the way it checks anything else. The wall between term and type comes down. cited
1968 · N.G. de Bruijn — AUTOMATH, a language for checking mathematical proofs. 1972+ · Per Martin-Löf — intuitionistic type theory: dependent types, propositions-as-types. now · Agda, Idris, Coq/Rocq, Lean — programming and theorem-proving in one language.
When a type can say m+n, type-checking a program and proving a theorem become the same act. The compiler is a proof assistant; the program is the proof. Martin-Löf
RECOMMEND FOR I-13 type-level length arithmetic, computed
On the canonical compiler, appending Vec 3 and Vec 2 yields a Vec 5 — the length added in the type:
$ i13 run t_dependent.i13 # append Vec m and Vec n
appended_len = 5 -- Vec 3 ++ Vec 2 : Vec (3+2) = Vec 5
Recommend: here is the sharpest version of i13's trade. i13 bounds-checks every array access at runtime (E0501) — a dependent type would move that same check into the type, proving the index in range before the program runs (exactly what dart 241's bounds-check elimination gestured at). i13 computes m+n=5 as a value, but it cannot make that length a type. Dependent types are the ceiling of what types: NOT COVERED forgoes: proofs and programs as one thing — and i13's honesty ledger is a deliberately weaker, runtime-checked cousin of exactly this idea.