Dependent Types

Every programmer learns early that types catch mistakes. Pass a string where a number is expected and the compiler complains before the program ever runs. That is type-checking: a mechanical proof that the data shapes match.

But ordinary types are surprisingly vague. A list in most languages has type List<Int> — a list of integers. It says nothing about how many integers. So when you write head(myList) — grab the first element — the compiler waves it through even if myList might be empty. The crash happens at runtime, in production, on a user's machine.

Dependent types fix this by letting a type depend on a value. Instead of "list of integers" you can write "list of exactly n integers" and put the actual number $n$ inside the type. The compiler then knows statically that head on a length-0 list is impossible — not because you wrote a test for it, but because the types make it unrepresentable.

The idea is old: Per Martin-Löf introduced Martin-Löf type theory in the 1970s, connecting types to logic through what is now called the Curry-Howard correspondence: a type is a proposition, a program that has that type is a proof. Dependent types take this all the way — a type can encode any mathematical statement, and writing a program of that type is proving the statement.

This article explores what that means, why it matters, and how you can see it in action with a simple interactive demo.

The core idea of dependent types is easiest to see with length-indexed lists (often called $Vec n$). A $Vec 3 Int$ is a list of exactly 3 integers — the length is part of the type, not just documentation.

The key property is append: if you concatenate a $Vec m$ with a $Vec n$, the result is a $Vec (m+n)$. That arithmetic lives in the type signature. The compiler checks it statically — no runtime assertion needed.

<div class="demo-wrap">
  <div class="panel" id="panel-a">
    <div class="panel-title">Vec A <span class="len-badge" id="badge-a">{{len_init}}</span></div>
    <div class="vec-display" id="vec-a"></div>
    <div class="ops">
      <button id="push-a" type="button">{{push_a}}</button>
      <button id="pop-a" type="button" class="ghost">{{pop_a}}</button>
    </div>
  </div>
  <div class="panel" id="panel-b">
    <div class="panel-title">Vec B <span class="len-badge" id="badge-b">{{len_init}}</span></div>
    <div class="vec-display" id="vec-b"></div>
    <div class="ops">
      <button id="push-b" type="button">{{push_b}}</button>
      <button id="pop-b" type="button" class="ghost">{{pop_b}}</button>
    </div>
  </div>
  <div class="panel result-panel">
    <div class="panel-title">A ++ B <span class="len-badge result-badge" id="badge-r">{{len_init}}</span></div>
    <div class="vec-display" id="vec-r"></div>
    <div class="ops">
      <button id="append-btn" type="button" class="accent">{{append_btn}}</button>
      <button id="head-btn" type="button" class="ghost">{{head_btn}}</button>
    </div>
  </div>
</div>
<div class="type-log" id="type-log">
  <div class="log-title">{{log_title}}</div>
  <div id="log-entries"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; font-size: .92rem; }
.demo-wrap { display: flex; gap: .6rem; flex-wrap: wrap; }
.panel { flex: 1 1 140px; border: 1.5px solid #c8d4de; border-radius: 10px; padding: .6rem .7rem; background: #f4f8fb; }
.result-panel { border-color: #4a7fa5; background: #eaf3fb; }
.panel-title { font-weight: 700; font-size: .85rem; color: #1d3557; margin-bottom: .4rem; display: flex; align-items: center; gap: .4rem; }
.len-badge { background: #1d3557; color: #fff; border-radius: 99px; font-size: .72rem; padding: .1rem .45rem; font-weight: 600; letter-spacing: .02em; }
.result-badge { background: #2a7abf; }
.vec-display { display: flex; flex-wrap: wrap; gap: 4px; min-height: 38px; align-items: center; margin-bottom: .5rem; }
.cell { width: 32px; height: 32px; border-radius: 7px; background: #1d3557; color: #fff; display: flex; align-items: center; justify-content: center; font: 700 .85rem ui-monospace, monospace; transition: transform .12s; }
.cell.new { animation: pop-in .2s ease; }
.cell.from-a { background: #1d6a57; }
.cell.from-b { background: #5a2d8a; }
@keyframes pop-in { from { transform: scale(0.5); opacity: 0; } to { transform: scale(1); opacity: 1; } }
.ops { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 .8rem system-ui, sans-serif; padding: .35rem .7rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; transition: opacity .1s; }
button:hover { opacity: .85; }
button.ghost { background: #fff; color: #1d3557; }
button.accent { background: #2a7abf; border-color: #2a7abf; }
.type-log { margin-top: .7rem; border: 1.5px solid #c8d4de; border-radius: 10px; padding: .55rem .7rem; background: #f9fbfc; font-family: ui-monospace, monospace; font-size: .78rem; max-height: 160px; overflow-y: auto; }
.log-title { font-family: system-ui, sans-serif; font-weight: 700; color: #1d3557; font-size: .82rem; margin-bottom: .35rem; }
.log-entry { padding: .15rem 0; border-bottom: 1px solid #e8eef3; color: #333; line-height: 1.4; }
.log-entry:last-child { border-bottom: none; }
.log-ok { color: #0a7d33; }
.log-err { color: #c92f3c; }
.log-info { color: #1d3557; }

// Code not found

Notice what happened: the compiler (simulated here) tracked lengths through every operation. Building a list checks that each push increases the length by one. Appending two lists checks that the result length equals the sum. If you try to take the head of an empty list, the type system rejects it — not at runtime, but at the type-checking stage, before any code runs.

This is the asymmetry that makes dependent types powerful. Unit tests check behavior on specific inputs at runtime. Types check behavior on all possible inputs at compile time. Dependent types extend that compile-time guarantee to properties that mention actual values — lengths, bounds, invariants — not just shapes.

Dependent types are not just a nicer way to track lengths. They collapse the boundary between programs and proofs.

The Curry-Howard correspondence — discovered independently by Haskell Curry in the 1930s and William Howard in 1969 — states that:

• A type corresponds to a proposition (a mathematical statement).
• A program of that type corresponds to a proof of that proposition.
• Type checking corresponds to proof verification.

In a dependently typed language like Coq, Agda, or Idris, you can write a type that says "for all natural numbers n, sort(list) has the same length as list". A program with that type is a proof that sorting preserves length. The compiler verifies the proof mechanically. No human referee needed.

This has deep theoretical roots: Per Martin-Löf's intuitionistic type theory (1975) gave the first fully rigorous framework, and later the Calculus of Constructions (Coquand & Huet, 1988) underpins Coq. These systems are expressive enough to encode virtually all of mathematics.

There is, however, a price. Type checking becomes undecidable in fully general dependent type theories — the type checker may need to evaluate arbitrary program expressions to compare types. Real systems like Agda require programs to be total (they must terminate) so that type-level computation always halts. This connects directly to the halting problem: you cannot, in general, decide whether two type expressions are equal when they involve arbitrary computation.

The tradeoff is intentional. By restricting to total programs, dependent type systems gain decidable type checking while retaining extraordinary expressive power. Every proof the system accepts is guaranteed correct.

Dependent types have moved from academic curiosity to industrial tool wherever the cost of bugs is highest:

• Verified compilers: CompCert (Leroy, 2006) is a C compiler written and formally verified in Coq. Every optimization pass carries a machine-checked proof that it preserves program meaning. It has never produced a miscompilation in production use.
• Verified operating systems: The seL4 microkernel was verified in Isabelle/HOL (a related system) with a complete proof that the C implementation matches its specification. It is used in safety-critical aerospace and automotive systems.
• Cryptographic protocols: Libraries like Hacl* provide formally verified implementations of TLS, ChaCha20, and Poly1305, with Coq proofs that the code matches the mathematical specification down to the bit level.
• Programming language research: Agda and Idris use dependent types as their native language, letting programmers write proofs and programs in the same syntax. Idris was designed specifically to bring dependent types to general software engineering.
• Teaching logic: Proof assistants like Coq are now standard in graduate mathematics and CS courses. Learning to write a proof in Coq is learning to understand what it means for a statement to be true in the most rigorous sense.

The common thread: wherever a bug is not just an inconvenience but a safety or security catastrophe, dependent types and proof assistants give you a way to be mathematically certain the code is correct — something unit tests, code review, and fuzzing cannot provide.

Compare this to the challenge of program equivalence: deciding whether two arbitrary programs compute the same function is undecidable, but dependent types let you prove equivalence for specific, well-structured programs.

Dependent types start with a simple observation: if a type can carry a value — a length, a bound, a proof — then the compiler can check properties that would otherwise require runtime tests or human audits.

Follow that idea all the way and you reach the Curry-Howard correspondence: types are propositions, programs are proofs, and type checking is mechanical proof verification. The compiler becomes a mathematician's assistant, rejecting any program whose correctness claim cannot be established.

The cost is real: you must write total programs, type signatures get more complex, and the learning curve is steep. But in the domains where it is applied — verified compilers, certified operating systems, cryptographic libraries — the payoff is a class of guarantee that no amount of testing can match: mathematical certainty.

The next time you see an out-of-bounds crash or a null-pointer exception, remember: there is a type system that could have made that bug unrepresentable. We just have to be willing to write down what we actually mean.