Coq Proof Assistant — Dependently Typed Programming

In this tutorial, you'll learn about Coq Proof Assistant. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Coq is an interactive proof assistant based on the Calculus of Inductive Constructions, enabling users to write mathematical proofs and extract verified programs through dependent typing.

Learning Path

flowchart LR
  A["Theorem Proving"] --> B["Coq Proof Assistant
Dependent Types"]
  B --> C["Isabelle/HOL"]
  B --> D["Correct-by-Construction"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Functional Programming (OCaml or Haskell helps). Propositional and first-order logic.

What Is Coq?

Coq is both a proof assistant and a dependently typed programming language. You write specifications (what the program should do) and proofs (that the implementation meets the specification). Coq checks every proof step mechanically.

Dependent types allow types to depend on values. For example, a list(n) type can encode the list's length, so append can be typed as list(a) -> list(m) -> list(a+n+m).

Step-by-Step: Your First Coq Proof

Step 1: Install Coq

sudo apt-get install coq coqide

Step 2: Define a Simple Property

Theorem add_commutative : forall n m : nat, n + m = m + n.
Proof.
  intros n m.
  induction n as [| n' IH].
  - simpl.
    rewrite <- plus_n_O.
    reflexivity.
  - simpl.
    rewrite IH.
    rewrite plus_n_Sm.
    reflexivity.
Qed.

Step 3: Understand the Tactics

# Python analogy of what each tactic does
def add_commutative_py(n, m):
    # Induction on n
    if n == 0:
        # base case: 0 + m = m + 0
        return 0 + m == m + 0
    else:
        # inductive case: (1+n') + m = m + (1+n')
        # uses IH: n' + m = m + n'
        return (n) + m == m + (n)

print(f"Base case (0, 5): {add_commutative_py(0, 5)}")
print(f"Inductive case (3, 7): {add_commutative_py(3, 7)}")

Expected output:

Base case (0, 5): True
Inductive case (3, 7): True

Step-by-Step: Defining Data Types

Step 1: Define Natural Numbers

Inductive nat : Type :=
  | O : nat
  | S : nat -> nat.

Step 2: Define Addition

Fixpoint add (n m : nat) : nat :=
  match n with
  | O => m
  | S n' => S (add n' m)
  end.

Step 3: Prove a Theorem

Theorem add_O_l : forall n : nat, add O n = n.
Proof.
  intros n.
  simpl.
  reflexivity.
Qed.

Step 4: Python Equivalent

class Nat:
    def __init__(self, is_zero, predecessor=None):
        self.is_zero = is_zero
        self.predecessor = predecessor

    @staticmethod
    def zero():
        return Nat(True)

    def succ(self):
        return Nat(False, self)

def add(n, m):
    if n.is_zero:
        return m
    return add(n.predecessor, m).succ()

def proof_add_O_n(n):
    return add(Nat.zero(), n).to_int() == n.to_int()

# Test
zero = Nat.zero()
three = zero.succ().succ().succ()
print(f"add(O, n) = n: {proof_add_O_n(three)}")

Expected output:

add(O, n) = n: True

Program Extraction

Coq can extract verified programs to OCaml, Haskell, or Scheme:

Require Extraction.
Extraction Language OCaml.
Extraction add.

The extracted add function is guaranteed to satisfy all proven properties.

Common Errors

1. Induction Hypothesis Misuse

The induction hypothesis applies only to structurally smaller arguments. Applying it incorrectly makes the proof circular.

2. Forgetting to simpl

Expressions are not automatically simplified. Use simpl or unfold to expose computational content.

3. Wrong Case Analysis Order

In complex inductive proofs, the order of case analysis matters. Use dependent induction for dependent types.

4. Non-Terminating Fixpoints

Every Fixpoint must have a structurally decreasing argument. Coq rejects non-terminating definitions.

5. Type Mismatch in Dependent Types

In dependently typed programming, seemingly equal types may differ in their index expressions. Use f_equal or inversion to resolve.

Practice Questions

Q1: What is the Calculus of Inductive Constructions?

Coq's underlying type theory combining dependent types, inductive definitions, and impredicative propositions.

Q2: What does reflexivity do?

Proves a goal where both sides of the equality are syntactically identical.

Q3: What is program extraction?

Generating executable code (OCaml, Haskell) from Coq proofs, preserving correctness guarantees.

Q4: What is the difference between Prop and Set in Coq?

Prop is the universe of logical propositions. Set is the universe of computational types. Extraction erases Prop.

Q5: Name a large project verified in Coq.

CompCert (verified C compiler) and seL4 (verified microkernel) are the most famous.

Challenge

Define a binary tree data type in Coq with a function that computes the sum of all leaf values. Prove that mirroring a tree twice returns the original tree. Extract the OCaml code.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.