Library Deduxit.Linear.FirstOrderCheck
The checker of first-order proof terms
- The first, introduced, collects the eigenvariables the ∀ steps introduce. It fails when a ∀ step's eigenvariable is introduced again above that step.
- The second, derive, is the propositional checker (Check) over first-order formulas. A ∀ step consumes its body's instance at its eigenvariable, and an ∃ step its body's instance at its witness. It also carries a set of eigenvariables to the root: an ∃ step adds those of its witness, a cut those of its formula, and a ∀ step removes its own.
From Stdlib Require Import Bool List.
From Deduxit.Linear Require Export TermsCheck FirstOrderCalculus FirstOrderProofs.
Import ListNotations.
Sequencing of computations that may fail: k runs on the value of
e, and None is failure. Local to this file.
Local Notation "'let*' x ':=' e 'in' k" :=
(match e with Some x ⇒ k | None ⇒ None end)
(at level 200, x pattern, e at level 100, k at level 200, right associativity).
Section Equality.
Context {symbol : Type} (symbol_eqb : symbol → symbol → bool).
Local Notation term := (term symbol).
Local Notation formula := (formula symbol).
(match e with Some x ⇒ k | None ⇒ None end)
(at level 200, x pattern, e at level 100, k at level 200, right associativity).
Section Equality.
Context {symbol : Type} (symbol_eqb : symbol → symbol → bool).
Local Notation term := (term symbol).
Local Notation formula := (formula symbol).
Structural equality of formulas.
Fixpoint formula_eqb (A B : formula) : bool :=
match A, B with
| var p l, var q k ⇒ symbol_eqb p q && terms_eqb symbol_eqb l k
| covar p l, covar q k ⇒ symbol_eqb p q && terms_eqb symbol_eqb l k
| one, one ⇒ true
| bot, bot ⇒ true
| top, top ⇒ true
| zero, zero ⇒ true
| tens A1 A2, tens B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| parr A1 A2, parr B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| awith A1 A2, awith B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| aplus A1 A2, aplus B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| oc A, oc B ⇒ formula_eqb A B
| wn A, wn B ⇒ formula_eqb A B
| fall A, fall B ⇒ formula_eqb A B
| fex A, fex B ⇒ formula_eqb A B
| _, _ ⇒ false
end.
match A, B with
| var p l, var q k ⇒ symbol_eqb p q && terms_eqb symbol_eqb l k
| covar p l, covar q k ⇒ symbol_eqb p q && terms_eqb symbol_eqb l k
| one, one ⇒ true
| bot, bot ⇒ true
| top, top ⇒ true
| zero, zero ⇒ true
| tens A1 A2, tens B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| parr A1 A2, parr B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| awith A1 A2, awith B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| aplus A1 A2, aplus B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| oc A, oc B ⇒ formula_eqb A B
| wn A, wn B ⇒ formula_eqb A B
| fall A, fall B ⇒ formula_eqb A B
| fex A, fex B ⇒ formula_eqb A B
| _, _ ⇒ false
end.
symbol_eqb decides equality. The soundness theorems assume this,
and a certificate proves it of the equality it uses.
Hypothesis symbol_eqb_spec : ∀ f g, reflect (f = g) (symbol_eqb f g).
Lemma formula_eqb_spec : ∀ A B, reflect (A = B) (formula_eqb A B).
Proof.
induction A; destruct B; cbn; try (constructor; congruence).
all: repeat match goal with
| |- reflect _ (symbol_eqb ?a ?b && _) ⇒ destruct (symbol_eqb_spec a b)
| |- reflect _ (terms_eqb _ ?l ?k) ⇒ destruct (terms_eqb_spec symbol_eqb symbol_eqb_spec l k)
| |- reflect _ (formula_eqb ?A ?B && _) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (formula_eqb ?A ?B) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (true && _) ⇒ cbn
| |- reflect _ (false && _) ⇒ cbn
end.
all: constructor; congruence.
Qed.
Lemma formula_eqb_spec : ∀ A B, reflect (A = B) (formula_eqb A B).
Proof.
induction A; destruct B; cbn; try (constructor; congruence).
all: repeat match goal with
| |- reflect _ (symbol_eqb ?a ?b && _) ⇒ destruct (symbol_eqb_spec a b)
| |- reflect _ (terms_eqb _ ?l ?k) ⇒ destruct (terms_eqb_spec symbol_eqb symbol_eqb_spec l k)
| |- reflect _ (formula_eqb ?A ?B && _) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (formula_eqb ?A ?B) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (true && _) ⇒ cbn
| |- reflect _ (false && _) ⇒ cbn
end.
all: constructor; congruence.
Qed.
Equality of formulas as a decision, used in proofs; the checker
computes with formula_eqb.
Definition formula_eq_dec (A B : formula) : {A = B} + {A ≠ B} :=
reflect_dec _ _ (formula_eqb_spec A B).
End Equality.
Section Eigenvariables.
Context {symbol : Type}.
Local Notation term := (term symbol).
Local Notation formula := (formula symbol).
reflect_dec _ _ (formula_eqb_spec A B).
End Equality.
Section Eigenvariables.
Context {symbol : Type}.
Local Notation term := (term symbol).
Local Notation formula := (formula symbol).
The eigenvariables of a formula, with repetitions.
Fixpoint feigens (A : formula) : list nat :=
match A with
| var _ l | covar _ l ⇒ flat_map teigens l
| one | bot | top | zero ⇒ []
| tens A B | parr A B | awith A B | aplus A B ⇒ feigens A ++ feigens B
| oc A | wn A | fall A | fex A ⇒ feigens A
end.
match A with
| var _ l | covar _ l ⇒ flat_map teigens l
| one | bot | top | zero ⇒ []
| tens A B | parr A B | awith A B | aplus A B ⇒ feigens A ++ feigens B
| oc A | wn A | fall A | fex A ⇒ feigens A
end.
Whether a formula starts with ?. Every calculus may weaken such
a formula.
Definition is_wn (A : formula) : bool :=
match A with
| wn _ ⇒ true
| _ ⇒ false
end.
End Eigenvariables.
Section Check.
Context {symbol : Type} (symbol_eqb : symbol → symbol → bool).
Local Notation term := (term symbol).
Local Notation formula := (formula symbol).
Local Notation proof := (proof symbol).
Local Notation eqb := (formula_eqb symbol_eqb).
match A with
| wn _ ⇒ true
| _ ⇒ false
end.
End Eigenvariables.
Section Check.
Context {symbol : Type} (symbol_eqb : symbol → symbol → bool).
Local Notation term := (term symbol).
Local Notation formula := (formula symbol).
Local Notation proof := (proof symbol).
Local Notation eqb := (formula_eqb symbol_eqb).
Multisets, as lists compared through formula_eqb
Fixpoint remove_one (A : formula) (l : list formula) : option (list formula) :=
match l with
| [] ⇒ None
| B :: l' ⇒ if eqb A B then Some l' else option_map (cons B) (remove_one A l')
end.
match l with
| [] ⇒ None
| B :: l' ⇒ if eqb A B then Some l' else option_map (cons B) (remove_one A l')
end.
Removes every occurrence of A from l.
Definition remove_all (A : formula) (l : list formula) : list formula :=
filter (fun B ⇒ negb (eqb A B)) l.
filter (fun B ⇒ negb (eqb A B)) l.
Removes each formula of l1 from l2. Returns what is left of
l2 when l1 is included in it as a multiset, None otherwise.
Fixpoint take_all (l1 l2 : list formula) : option (list formula) :=
match l1 with
| [] ⇒ Some l2
| A :: l1' ⇒
let× l2' := remove_one A l2 in
take_all l1' l2'
end.
match l1 with
| [] ⇒ Some l2
| A :: l1' ⇒
let× l2' := remove_one A l2 in
take_all l1' l2'
end.
l2 less l1: each formula of l1 is removed from l2 where
l2 has it. l1 ++ diff l2 l1 is the multiset union of the two.
Fixpoint diff (l2 l1 : list formula) : list formula :=
match l1 with
| [] ⇒ l2
| A :: l1' ⇒
diff (match remove_one A l2 with Some l2' ⇒ l2' | None ⇒ l2 end) l1'
end.
match l1 with
| [] ⇒ l2
| A :: l1' ⇒
diff (match remove_one A l2 with Some l2' ⇒ l2' | None ⇒ l2 end) l1'
end.
States
the unrestricted zone the subterm needs
the linear zone
whether a ⊤ above absorbs more
the eigenvariables carried to the root
}.
Consumes one copy of A from a premise's linear zone gamma. When
gamma has none, a ⊤ above (any) supplies it.
Definition take (A : formula) (gamma : list formula) (any : bool)
: option (list formula) :=
match remove_one A gamma with
| Some gamma' ⇒ Some gamma'
| None ⇒ if any then Some gamma else None
end.
: option (list formula) :=
match remove_one A gamma with
| Some gamma' ⇒ Some gamma'
| None ⇒ if any then Some gamma else None
end.
The conclusion of a & rule from its premises, after each has
consumed its own subformula. Both premises must prove the same
context. A premise without any fixes the context, and one with
any adapts to the other; when both have any, the conclusion has
the union of their zones and any set.
Definition join_with (A B : formula) (sl sr : state) : option state :=
let theta := theta sl ++ theta sr in
let eigens := eigens sl ++ eigens sr in
match any sl, any sr with
| false, false ⇒
match take_all (gamma sl) (gamma sr) with
| Some [] ⇒ Some (State theta (awith A B :: gamma sl) false eigens)
| _ ⇒ None
end
| true, false ⇒
let× _ := take_all (gamma sl) (gamma sr) in
Some (State theta (awith A B :: gamma sr) false eigens)
| false, true ⇒
let× _ := take_all (gamma sr) (gamma sl) in
Some (State theta (awith A B :: gamma sl) false eigens)
| true, true ⇒
Some (State theta (awith A B :: gamma sl ++ diff (gamma sr) (gamma sl)) true eigens)
end.
let theta := theta sl ++ theta sr in
let eigens := eigens sl ++ eigens sr in
match any sl, any sr with
| false, false ⇒
match take_all (gamma sl) (gamma sr) with
| Some [] ⇒ Some (State theta (awith A B :: gamma sl) false eigens)
| _ ⇒ None
end
| true, false ⇒
let× _ := take_all (gamma sl) (gamma sr) in
Some (State theta (awith A B :: gamma sr) false eigens)
| false, true ⇒
let× _ := take_all (gamma sr) (gamma sl) in
Some (State theta (awith A B :: gamma sl) false eigens)
| true, true ⇒
Some (State theta (awith A B :: gamma sl ++ diff (gamma sr) (gamma sl)) true eigens)
end.
The first pass
Fixpoint introduced (p : proof) : option (list nat) :=
match p with
| Ax _ _ | One | Top ⇒ Some []
| Par _ _ q | Bot q | Plus _ _ _ q | Bang _ q | Quest _ q | Copy _ q | Weaken _ q
| Exists _ _ q ⇒ introduced q
| Tensor _ _ l r | With _ _ l r | Mix l r | Cut _ l r ⇒
let× il := introduced l in
let× ir := introduced r in
Some (il ++ ir)
| Forall _ a q ⇒
let× i := introduced q in
if existsb (Nat.eqb a) i then None else Some (a :: i)
end.
match p with
| Ax _ _ | One | Top ⇒ Some []
| Par _ _ q | Bot q | Plus _ _ _ q | Bang _ q | Quest _ q | Copy _ q | Weaken _ q
| Exists _ _ q ⇒ introduced q
| Tensor _ _ l r | With _ _ l r | Mix l r | Cut _ l r ⇒
let× il := introduced l in
let× ir := introduced r in
Some (il ++ ir)
| Forall _ a q ⇒
let× i := introduced q in
if existsb (Nat.eqb a) i then None else Some (a :: i)
end.
The second pass
Fixpoint derive (R : Calculus.rules) (p : proof) : option state :=
match p with
| Ax a l ⇒
Some (State [] [covar a l; var a l] false [])
| Tensor A B l r ⇒
let× sl := derive R l in
let× sr := derive R r in
let× gl := take A (gamma sl) (any sl) in
let× gr := take B (gamma sr) (any sr) in
Some (State (theta sl ++ theta sr) (tens A B :: gl ++ gr) (any sl || any sr)
(eigens sl ++ eigens sr))
| Par A B q ⇒
let× s := derive R q in
let× g := take A (gamma s) (any s) in
let× g := take B g (any s) in
Some (State (theta s) (parr A B :: g) (any s) (eigens s))
| One ⇒
Some (State [] [one] false [])
| Bot q ⇒
let× s := derive R q in
Some (State (theta s) (bot :: gamma s) (any s) (eigens s))
| With A B l r ⇒
let× sl := derive R l in
let× sr := derive R r in
let× gl := take A (gamma sl) (any sl) in
let× gr := take B (gamma sr) (any sr) in
join_with A B (State (theta sl) gl (any sl) (eigens sl))
(State (theta sr) gr (any sr) (eigens sr))
| Plus A B side q ⇒
let× s := derive R q in
let× g := take (match side with Left ⇒ A | Right ⇒ B end) (gamma s) (any s) in
Some (State (theta s) (aplus A B :: g) (any s) (eigens s))
| Top ⇒
Some (State [] [top] true [])
| Bang A q ⇒
let× s := derive R q in
let× g := take A (gamma s) (any s) in
match g with
| [] ⇒ Some (State (theta s) [oc A] false (eigens s))
| _ :: _ ⇒ None
end
| Quest A q ⇒
let× s := derive R q in
Some (State (remove_all A (theta s)) (wn A :: gamma s) (any s) (eigens s))
| Copy A q ⇒
let× s := derive R q in
let× g := take A (gamma s) (any s) in
Some (State (A :: theta s) g (any s) (eigens s))
| Weaken A q ⇒
if Calculus.weakening R || is_wn A then
let× s := derive R q in
Some (State (theta s) (A :: gamma s) (any s) (eigens s))
else None
| Mix l r ⇒
if Calculus.mix R then
let× sl := derive R l in
let× sr := derive R r in
Some (State (theta sl ++ theta sr) (gamma sl ++ gamma sr) (any sl || any sr)
(eigens sl ++ eigens sr))
else None
| Cut A l r ⇒
if Calculus.cut R then
let× sl := derive R l in
let× sr := derive R r in
let× gl := take A (gamma sl) (any sl) in
let× gr := take (dual A) (gamma sr) (any sr) in
Some (State (theta sl ++ theta sr) (gl ++ gr) (any sl || any sr)
(feigens A ++ eigens sl ++ eigens sr))
else None
| Forall A a q ⇒
let× s := derive R q in
let× g := take (subst 0 (eigen a) A) (gamma s) (any s) in
Some (State (theta s) (fall A :: g) (any s)
(filter (fun b ⇒ negb (Nat.eqb a b)) (eigens s)))
| Exists A t q ⇒
if tclosed t then
let× s := derive R q in
let× g := take (subst 0 t A) (gamma s) (any s) in
Some (State (theta s) (fex A :: g) (any s) (teigens t ++ eigens s))
else None
end.
match p with
| Ax a l ⇒
Some (State [] [covar a l; var a l] false [])
| Tensor A B l r ⇒
let× sl := derive R l in
let× sr := derive R r in
let× gl := take A (gamma sl) (any sl) in
let× gr := take B (gamma sr) (any sr) in
Some (State (theta sl ++ theta sr) (tens A B :: gl ++ gr) (any sl || any sr)
(eigens sl ++ eigens sr))
| Par A B q ⇒
let× s := derive R q in
let× g := take A (gamma s) (any s) in
let× g := take B g (any s) in
Some (State (theta s) (parr A B :: g) (any s) (eigens s))
| One ⇒
Some (State [] [one] false [])
| Bot q ⇒
let× s := derive R q in
Some (State (theta s) (bot :: gamma s) (any s) (eigens s))
| With A B l r ⇒
let× sl := derive R l in
let× sr := derive R r in
let× gl := take A (gamma sl) (any sl) in
let× gr := take B (gamma sr) (any sr) in
join_with A B (State (theta sl) gl (any sl) (eigens sl))
(State (theta sr) gr (any sr) (eigens sr))
| Plus A B side q ⇒
let× s := derive R q in
let× g := take (match side with Left ⇒ A | Right ⇒ B end) (gamma s) (any s) in
Some (State (theta s) (aplus A B :: g) (any s) (eigens s))
| Top ⇒
Some (State [] [top] true [])
| Bang A q ⇒
let× s := derive R q in
let× g := take A (gamma s) (any s) in
match g with
| [] ⇒ Some (State (theta s) [oc A] false (eigens s))
| _ :: _ ⇒ None
end
| Quest A q ⇒
let× s := derive R q in
Some (State (remove_all A (theta s)) (wn A :: gamma s) (any s) (eigens s))
| Copy A q ⇒
let× s := derive R q in
let× g := take A (gamma s) (any s) in
Some (State (A :: theta s) g (any s) (eigens s))
| Weaken A q ⇒
if Calculus.weakening R || is_wn A then
let× s := derive R q in
Some (State (theta s) (A :: gamma s) (any s) (eigens s))
else None
| Mix l r ⇒
if Calculus.mix R then
let× sl := derive R l in
let× sr := derive R r in
Some (State (theta sl ++ theta sr) (gamma sl ++ gamma sr) (any sl || any sr)
(eigens sl ++ eigens sr))
else None
| Cut A l r ⇒
if Calculus.cut R then
let× sl := derive R l in
let× sr := derive R r in
let× gl := take A (gamma sl) (any sl) in
let× gr := take (dual A) (gamma sr) (any sr) in
Some (State (theta sl ++ theta sr) (gl ++ gr) (any sl || any sr)
(feigens A ++ eigens sl ++ eigens sr))
else None
| Forall A a q ⇒
let× s := derive R q in
let× g := take (subst 0 (eigen a) A) (gamma s) (any s) in
Some (State (theta s) (fall A :: g) (any s)
(filter (fun b ⇒ negb (Nat.eqb a b)) (eigens s)))
| Exists A t q ⇒
if tclosed t then
let× s := derive R q in
let× g := take (subst 0 t A) (gamma s) (any s) in
Some (State (theta s) (fex A :: g) (any s) (teigens t ++ eigens s))
else None
end.
Whether p proves ⊢ sequent in R:
- no eigenvariable its ∀ steps introduce is left in the set its root carries, or occurs in the sequent;
- its root needs no unrestricted zone and proves exactly the sequent's formulas, or a part of them when a ⊤ absorbs the rest.
Definition check (R : Calculus.rules) (p : proof) (sequent : list formula) : bool :=
match introduced p, derive R p with
| Some i, Some (State [] gamma any e) ⇒
forallb (fun a ⇒ negb (existsb (Nat.eqb a) e)
&& forallb (fun A ⇒ negb (occurs a A)) sequent) i &&
match take_all gamma sequent with
| Some [] ⇒ true
| Some (_ :: _) ⇒ any
| None ⇒ false
end
| _, _ ⇒ false
end.
End Check.
Arguments state symbol : clear implicits.
match introduced p, derive R p with
| Some i, Some (State [] gamma any e) ⇒
forallb (fun a ⇒ negb (existsb (Nat.eqb a) e)
&& forallb (fun A ⇒ negb (occurs a A)) sequent) i &&
match take_all gamma sequent with
| Some [] ⇒ true
| Some (_ :: _) ⇒ any
| None ⇒ false
end
| _, _ ⇒ false
end.
End Check.
Arguments state symbol : clear implicits.