Library Deduxit.Linear.Check
The checker
- Θ is the least unrestricted zone the subterm needs (a Copy adds its formula, a Quest removes it);
- Γ is the linear zone, a multiset;
- a flag says that a ⊤ above absorbs any further linear context.
From Stdlib Require Import Bool List.
From Deduxit.Linear Require Export Calculus Proofs.
Import ListNotations.
Sequencing of computations that may fail: k runs on the value of
e, and None is failure. Local to this file, so that it clashes
with no other library's notation.
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 Check.
Context {atom : Type} (atom_eqb : atom → atom → bool).
Local Notation formula := (formula atom).
Local Notation proof := (proof atom).
Local Notation eqb := (formula_eqb atom_eqb).
(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 Check.
Context {atom : Type} (atom_eqb : atom → atom → bool).
Local Notation formula := (formula atom).
Local Notation proof := (proof atom).
Local Notation eqb := (formula_eqb atom_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
}.
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
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)
| _ ⇒ None
end
| true, false ⇒
let× _ := take_all (gamma sl) (gamma sr) in
Some (State theta (awith A B :: gamma sr) false)
| false, true ⇒
let× _ := take_all (gamma sr) (gamma sl) in
Some (State theta (awith A B :: gamma sl) false)
| true, true ⇒
Some (State theta (awith A B :: gamma sl ++ diff (gamma sr) (gamma sl)) true)
end.
let theta := theta sl ++ theta 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)
| _ ⇒ None
end
| true, false ⇒
let× _ := take_all (gamma sl) (gamma sr) in
Some (State theta (awith A B :: gamma sr) false)
| false, true ⇒
let× _ := take_all (gamma sr) (gamma sl) in
Some (State theta (awith A B :: gamma sl) false)
| true, true ⇒
Some (State theta (awith A B :: gamma sl ++ diff (gamma sr) (gamma sl)) true)
end.
The pass
Fixpoint derive (R : rules) (p : proof) : option state :=
match p with
| Ax a ⇒
Some (State [] [covar a; var a] 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))
| 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))
| One ⇒
Some (State [] [one] false)
| Bot q ⇒
let× s := derive R q in
Some (State (theta s) (bot :: gamma s) (any 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)) (State (theta sr) gr (any 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))
| 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)
| _ :: _ ⇒ None
end
| Quest A q ⇒
let× s := derive R q in
Some (State (remove_all A (theta s)) (wn A :: gamma s) (any 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))
| Weaken A q ⇒
if weakening R || is_wn A then
let× s := derive R q in
Some (State (theta s) (A :: gamma s) (any s))
else None
| Mix l r ⇒
if 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))
else None
| Cut A l r ⇒
if 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))
else None
end.
match p with
| Ax a ⇒
Some (State [] [covar a; var a] 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))
| 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))
| One ⇒
Some (State [] [one] false)
| Bot q ⇒
let× s := derive R q in
Some (State (theta s) (bot :: gamma s) (any 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)) (State (theta sr) gr (any 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))
| 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)
| _ :: _ ⇒ None
end
| Quest A q ⇒
let× s := derive R q in
Some (State (remove_all A (theta s)) (wn A :: gamma s) (any 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))
| Weaken A q ⇒
if weakening R || is_wn A then
let× s := derive R q in
Some (State (theta s) (A :: gamma s) (any s))
else None
| Mix l r ⇒
if 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))
else None
| Cut A l r ⇒
if 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))
else None
end.