Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Read a proof as a program

Every intuitionistic proof is also a program: its formulas are the program's types, and its hypotheses the program's inputs. This is the Curry-Howard correspondence. --lambda prints the program of a proof as a lambda-term, the notation in which λx. M is the function of x whose result is M, and f x applies f to x:

$ deduxit prove -i --lambda 'a, a -o b |- b'
provable (IMLL, intuitionistic, two-sided engine)
───── ax   ───── ax
a ⊢ a      b ⊢ b
──────────────── ⊸L
  a, a ⊸ b ⊢ b
lambda-term: x : a, f : a ⊸ b ⊢ f x : b

The last line is the term's typing judgement. Left of ⊢ stand the hypotheses' variables with their types: x has the type a, and f the type a ⊸ b. Right of it stands the term, f x, with its type, b. The proof that b follows from a and a ⊸ b is the program that applies f to x.

A proof of intuitionistic linear logic (-i) is a term of a linear lambda calculus, and a derivation of LJ (--logic intuitionistic or minimal) a term of the simply typed lambda calculus. deduxit reads every intuitionistic proof it finds or checks back as its term. The term is computed from the proof the checker accepted, one construction per rule. It is shown, not trusted: the proof stays the certificate.

The linear lambda calculus

In a linear lambda calculus a term uses each variable once, as linear logic uses each hypothesis once. A variable of a ! type may be copied or discarded, and both components of a pair use the same variables, since a program takes only one of them.

A proof of intuitionistic linear logic reads back as a term of the linear lambda calculus of Benton, Bierman, de Paiva and Hyland, "A term calculus for intuitionistic linear logic" (TLCA 1993, LNCS 664, pages 75 to 90). deduxit takes it in the sequent calculus form, with the additives and their units, that G. M. Bierman gives in On Intuitionistic Linear Logic (PhD thesis, University of Cambridge, 1993, published as technical report UCAM-CL-TR-346, 1994), chapter 3, figure 3.2. Each rule of the two-sided sequent calculus has its term:

ruleterm
axiomx
⊸R, ⊸Lλx:A. M; N[x := f M]
⊗R, ⊗LM ⊗ N; let z be x ⊗ y in M
1R, 1L∗; let z be ∗ in M
&R, &L₁, &L₂⟨M, N⟩; M[x := fst(z)], M[x := snd(z)]
⊕R₁, ⊕R₂, ⊕Linl(M), inr(M); case z of inl(x) → M ‖ inr(y) → N
⊤R, 0Ltrue(x⃗); false_A(x⃗; z)
!R, !Lpromote y⃗ for x⃗ in M; M[x := derelict(z)]
!w, !cdiscard z in M; copy z as x, y in M
cut(λx:A. N) M

Every form in the table is the thesis's except the cut's. The thesis's cut is the substitution N[x := M] itself; deduxit writes it as the redex whose reduction is that substitution, in the calculus's own syntax. A left rule substitutes, as in the thesis, so the term of a cut-free proof is in normal form. true and false take every other hypothesis, since ⊤ and 0 discard a linear context only by consuming it. The two components of a pair share their context:

$ deduxit prove -i --lambda --tree never '|- a -o b -o a * b'
provable (IMLL, intuitionistic, two-sided engine)
lambda-term: ⊢ λx. λy. x ⊗ y : a ⊸ (b ⊸ (a ⊗ b))
$ deduxit prove -i --lambda --tree never '1 * a |- a'
provable (IMLL with units, intuitionistic, two-sided engine)
lambda-term: x : 1 ⊗ a ⊢ let x be y ⊗ z in let y be ∗ in z : a
$ deduxit prove -i --lambda --tree never 'a & b |- b & a'
provable (IALL, intuitionistic, additive engine)
lambda-term: x : a & b ⊢ ⟨snd(x), fst(x)⟩ : b & a
$ deduxit prove -i --lambda --tree never 'a + b |- b + a'
provable (IALL, intuitionistic, additive engine)
lambda-term: x : a ⊕ b ⊢ case x of inl(y) → inr(y) ‖ inr(z) → inl(z) : b ⊕ a
$ deduxit prove -i --lambda --tree never 'a, b |- top'
provable (IALL, intuitionistic, two-sided engine)
lambda-term: x : a, y : b ⊢ true(x, y) : ⊤
$ deduxit prove -i --lambda --tree never '0, a |- b'
provable (IALL, intuitionistic, two-sided engine)
lambda-term: x : 0, y : a ⊢ false(y; x) : b
$ deduxit prove -i --lambda --tree never '!a |- a * a'
provable (IMELL, intuitionistic, horn engine)
lambda-term: x : !a ⊢ copy x as y, z in derelict(z) ⊗ derelict(y) : a ⊗ a
$ deduxit prove -i --lambda --tree never '!(a -o b), !a |- !b'
provable (IMELL, intuitionistic, two-sided engine)
lambda-term: x : !(a ⊸ b), y : !a ⊢ promote x, y for z, u in derelict(z) derelict(u) : !b

A proof of affine linear logic (--affine) reads back to the affine lambda calculus: the same terms, with weakening left implicit, so a variable may go unused. Neither the paper nor the thesis gives an affine calculus, so this reading is deduxit's own.

$ deduxit prove -i --affine --lambda --tree never 'a, b |- a'
provable (IMLL, intuitionistic affine, two-sided engine)
lambda-term: x : a, y : b ⊢ x : a

Cuts are redexes

A cut on A between a proof of Γ ⊢ M : A and one of Δ, x : A ⊢ N : C is the redex (λx:A. N) M: a function applied to its argument. Reducing it is the substitution of the thesis's cut, and eliminating the cut (deduxit eliminate, see Eliminate cuts) reduces the term. The session command lambda shows the term of a session that cuts:

$ deduxit interact -i 'a, a -o b |- b'
> cut 0 b 0 1
> close
> lambda
opened goal 1: 0: a, 1: a ⊸ b ⊢ 2: b
opened goal 2: 1: b ⊢ 0: b
goal 1: provable (IMLL, intuitionistic, two-sided engine)
goal 2: provable (IMLL, intuitionistic, two-sided engine)
no goal is open: `proof` checks the proof
x : a, f : a ⊸ b ⊢ (λy. y) (f x) : b

The simply typed lambda calculus

A derivation of LJ, from intuitionistic or minimal logic (--logic, see Decide ordinary logic), reads back to the simply typed lambda calculus with products, sums, a unit and an empty type, as J.-Y. Girard, Y. Lafont and P. Taylor give it in Proofs and Types (Cambridge University Press, 1989), sections 3.1.2 and 10.6. Their π₁, π₂, ι₁, ι₂, δ and ε are written fst, snd, inl, inr, case and abort. The book names no term of the unit type, so ⟨⟩, the empty pair, is deduxit's own notation for it. ¬A is A → ⊥, and A ↔ B the pair of both implications:

$ deduxit prove --logic intuitionistic --lambda --tree never '|- (a -> b) -> (b -> c) -> a -> c'
valid (intuitionistic logic by the SAT solver)
lambda-term: ⊢ λf. λg. λx. g (f x) : (a → b) → ((b → c) → (a → c))
$ deduxit prove --logic intuitionistic --lambda --tree never '~(a \/ b) |- ~a /\ ~b'
valid (intuitionistic logic by the SAT solver)
lambda-term: f : (a ∨ b) → ⊥ ⊢ ⟨λx. f inl(x), λy. f inr(y)⟩ : (a → ⊥) ∧ (b → ⊥)
$ deduxit prove --logic minimal --lambda --tree never '|- a -> ~~a'
valid (minimal logic by the SAT solver)
lambda-term: ⊢ λx. λf. f x : a → ((a → ⊥) → ⊥)

Under --logic, --linear prints the term of the linear proof of the image instead.

What has no term

A proof of classical linear logic may have several conclusions, which no lambda-term types. These have no term either:

  • a derivation of LK;
  • a proof with Mix;
  • a proof of the cyclic or the Lambek calculus, whose terms belong to an ordered calculus of their own;
  • a proof with first-order quantifiers, which are not quantifiers over types.

The line says why:

$ deduxit prove --lambda --tree never '|- a, ~a'
provable (MLL, classical, focus engine)
no lambda-term: a proof of classical logic may have several conclusions, which no lambda-term types; a term needs an intuitionistic proof
$ deduxit prove -i --lambda --tree never 'forall x. p(x) |- p(c)'
provable (IMLL1, intuitionistic, two-sided engine)
no lambda-term: quantifiers over first-order terms are not quantifiers over types

How the term is printed

--lambda-notation ascii writes the term in ASCII, a notation of deduxit's own: \x. M for λx. M, M * N for M ⊗ N, () for ∗, <M, N> for ⟨M, N⟩, -> and | in a case, and the types as the parser reads them. --lambda-types gives every binder its variable's type, λx:A. M, and false and abort their goal's, as the calculus writes them. The settings keys are lambda.notation and lambda.types:

$ deduxit prove -i --lambda --lambda-notation ascii --lambda-types --tree never '|- a -o b -o a * b'
provable (IMLL, intuitionistic, two-sided engine)
lambda-term: |- \x:a. \y:b. x * y : a -o (b -o (a * b))

In a program that uses the library, a lambda::Term prints with Display (term.to_string() is the term alone, in the default notation), and Term::write and Term::write_judgement take the options.

check --lambda prints the term of a proof read from a file, and the session command lambda of interact that of the finished proof or derivation:

$ deduxit prove -i --format json 'a & b |- b & a' > proof.json
$ deduxit check -i --lambda --tree never proof.json
valid proof of a & b ⊢ b & a (intuitionistic)
lambda-term: x : a & b ⊢ ⟨snd(x), fst(x)⟩ : b & a

In LaTeX, Typst, SVG, PNG and PDF the judgement stands under the conclusion of the derivation:

$ deduxit prove -i --lambda --format latex 'a, a -o b |- b'
% provable (IMLL, intuitionistic, two-sided engine)
\begin{prooftree}
\infer0[$\mathrm{ax}$]{a &\vdash a}
\infer0[$\mathrm{ax}$]{b &\vdash b}
\infer2[$\multimap\mathrm{L}$]{a, a \multimap b &\vdash b}
\infer[no rule]1{x : a, f : a \multimap b \vdash f\ x : b}
\end{prooftree}

In JSON the outcome gains the key lambda: the term as data (its calculus, atoms, types, variables, the hypotheses' variables as context, its type as goal, and its nodes, each after the nodes it names, root the whole term), with its text and its judgement as printed, or {"error": …} where there is none:

$ deduxit prove -i --format json --lambda 'a |- a'
{"checked":true,"deduxit":"0.5.0","engine":"two-sided","fragment":"IMLL","lambda":{"atoms":["a"],"calculus":"linear","context":[0],"goal":0,"judgement":"x : a ⊢ x : a","nodes":[{"kind":"var","variable":0}],"root":0,"text":"x","types":[{"atom":0,"kind":"atom"}],"variables":[{"index":0,"letter":"x","type":0}]},"mode":"intuitionistic","nodes":[{"ax":[0,1]}],"sequent":{"antecedents":1,"atoms":["a"],"roots":[0,1],"terms":[{"D":0},{"V":0}]},"statistics":{"copies":0,"forward_copies":0,"links":0,"memo_entries":1,"memo_hits":0,"nodes":1,"splits":0,"tests":0,"work":16},"verdict":"proved","version":1}

A term repeats a left rule's term wherever its hypothesis goes, in both components of a pair, so its text can be longer than the derivation by any factor. A term whose text would pass --derivation-limit is not written, and the line says so.