Correctness of the affinity solver #
The solutions of a list of affinity constraints are closed under pointwise join and meet
(satisfies_join, satisfies_meet; Lemma L).
solveAffinities succeeds exactly when there is a solution, and then returns one that lies above
every solution (solveAffinities_spec; Lemma P).
def
Determinize.Proof.Frontend.Satisfies
{V : Type}
(ρ : V → Spec.Paper.Affinity)
(constraints : List (Frontend.AffinityConstraint V))
:
ρ satisfies every constraint, in the order G ≤ E of Ty.Sub.
Equations
- One or more equations did not get rendered due to their size.
Instances For
theorem
Determinize.Proof.Frontend.sub_float_iff
{a b : Spec.Paper.Affinity}
:
(Spec.Paper.Ty.float a).Sub (Spec.Paper.Ty.float b) ↔ a = b ∨ a = Spec.Paper.Affinity.G ∧ b = Spec.Paper.Affinity.E
Lemma L #
theorem
Determinize.Proof.Frontend.eval_join
{V : Type}
(ρ ρ' : V → Spec.Paper.Affinity)
(t : Frontend.AffinityTerm V)
:
Frontend.AffinityTerm.eval (fun (v : V) => affinityJoin (ρ v) (ρ' v)) t = affinityJoin (Frontend.AffinityTerm.eval ρ t) (Frontend.AffinityTerm.eval ρ' t)
theorem
Determinize.Proof.Frontend.eval_meet
{V : Type}
(ρ ρ' : V → Spec.Paper.Affinity)
(t : Frontend.AffinityTerm V)
:
Frontend.AffinityTerm.eval (fun (v : V) => affinityMeet (ρ v) (ρ' v)) t = affinityMeet (Frontend.AffinityTerm.eval ρ t) (Frontend.AffinityTerm.eval ρ' t)
theorem
Determinize.Proof.Frontend.satisfies_join
{V : Type}
{ρ ρ' : V → Spec.Paper.Affinity}
{constraints : List (Frontend.AffinityConstraint V)}
(h : Satisfies ρ constraints)
(h' : Satisfies ρ' constraints)
:
Satisfies (fun (v : V) => affinityJoin (ρ v) (ρ' v)) constraints
theorem
Determinize.Proof.Frontend.satisfies_meet
{V : Type}
{ρ ρ' : V → Spec.Paper.Affinity}
{constraints : List (Frontend.AffinityConstraint V)}
(h : Satisfies ρ constraints)
(h' : Satisfies ρ' constraints)
:
Satisfies (fun (v : V) => affinityMeet (ρ v) (ρ' v)) constraints
Lemma P #
theorem
Determinize.Proof.Frontend.mem_below
{V : Type}
[DecidableEq V]
{constraints : List (Frontend.AffinityConstraint V)}
{general : Finset V}
{v : V}
:
v ∈ Frontend.below constraints general ↔ ∃ (upper : Frontend.AffinityTerm V),
(Frontend.AffinityTerm.var v, upper) ∈ constraints ∧ Frontend.AffinityTerm.isGeneral general upper = true
theorem
Determinize.Proof.Frontend.eval_of_isGeneral
{V : Type}
[DecidableEq V]
{ρ : V → Spec.Paper.Affinity}
{general : Finset V}
(h : ∀ v ∈ general, ρ v = Spec.Paper.Affinity.G)
{t : Frontend.AffinityTerm V}
(ht : Frontend.AffinityTerm.isGeneral general t = true)
:
A solution is G on every term that isGeneral accepts, if it is G on general.
theorem
Determinize.Proof.Frontend.forcedGeneral_general
{V : Type}
[DecidableEq V]
{ρ : V → Spec.Paper.Affinity}
{constraints : List (Frontend.AffinityConstraint V)}
(hρ : Satisfies ρ constraints)
{general : Finset V}
(h : ∀ v ∈ general, ρ v = Spec.Paper.Affinity.G)
(v : V)
:
v ∈ Frontend.forcedGeneral constraints general → ρ v = Spec.Paper.Affinity.G
Every solution is G on the variables that forcedGeneral collects.
theorem
Determinize.Proof.Frontend.below_forcedGeneral
{V : Type}
[DecidableEq V]
(constraints : List (Frontend.AffinityConstraint V))
(general : Finset V)
:
Frontend.below constraints (Frontend.forcedGeneral constraints general) ⊆ Frontend.forcedGeneral constraints general
The variables that forcedGeneral collects are closed under below.
theorem
Determinize.Proof.Frontend.solveAffinities_sound
{V : Type}
[DecidableEq V]
{constraints : List (Frontend.AffinityConstraint V)}
{ρ : V → Spec.Paper.Affinity}
(h : Frontend.solveAffinities constraints = some ρ)
:
Satisfies ρ constraints
theorem
Determinize.Proof.Frontend.solveAffinities_greatest
{V : Type}
[DecidableEq V]
{constraints : List (Frontend.AffinityConstraint V)}
{ρ ρ' : V → Spec.Paper.Affinity}
(h : Frontend.solveAffinities constraints = some ρ)
(h' : Satisfies ρ' constraints)
(v : V)
:
(Spec.Paper.Ty.float (ρ' v)).Sub (Spec.Paper.Ty.float (ρ v))
The result of solveAffinities lies above every solution.
theorem
Determinize.Proof.Frontend.solveAffinities_complete
{V : Type}
[DecidableEq V]
{constraints : List (Frontend.AffinityConstraint V)}
{ρ' : V → Spec.Paper.Affinity}
(h' : Satisfies ρ' constraints)
:
∃ (ρ : V → Spec.Paper.Affinity), Frontend.solveAffinities constraints = some ρ
theorem
Determinize.Proof.Frontend.solveAffinities_spec
{V : Type}
[DecidableEq V]
(constraints : List (Frontend.AffinityConstraint V))
:
((∃ (ρ : V → Spec.Paper.Affinity), Satisfies ρ constraints) ↔ ∃ (ρ : V → Spec.Paper.Affinity), Frontend.solveAffinities constraints = some ρ) ∧ ∀ (ρ : V → Spec.Paper.Affinity),
Frontend.solveAffinities constraints = some ρ →
Satisfies ρ constraints ∧ ∀ (ρ' : V → Spec.Paper.Affinity),
Satisfies ρ' constraints → ∀ (v : V), (Spec.Paper.Ty.float (ρ' v)).Sub (Spec.Paper.Ty.float (ρ v))
Lemma P: solveAffinities succeeds exactly when the constraints have a solution, and then
returns a solution that lies above every solution.