import Determinize.Proof.Frontend.Soundnessimport Determinize.Proof.Frontend.Completenessimport Determinize.Proof.Frontend.Decomposeimport Determinize.Proof.Frontend.Unify/-!# Soundness, optimality, and completeness of affinity inferenceThe proof of `Theorems.inference_correctness`, assembled from the lemmas of the other files in`Proof/Frontend/`:* `solveInput_typed` (soundness): the most general shapes and the greatest solution of the affinity constraints solve the subtyping constraints of the draft (Lemma S′), so the read-back program is typed (Lemma S). The draft's type may keep shape variables after decoration; they are unconstrained, and any instance of them types the program.* `solveInput_complete` (completeness and optimality): a typed completion solves the subtyping constraints (Lemma C). Its shapes unify the shape equations, so `unify` succeeds and they factor through the most general shapes; its affinities, read off at the leaves of the decorated shapes, solve the atomic constraints (Lemma C′), so `solveAffinities` succeeds and returns a larger solution (Lemma P); read-back is monotone.-/namespace Determinize.Proof.Frontendopen Determinize.Frontend Spec Spec.Paper Ground/-! ## The phases of inference -//-- The shape equations of a draft. -/abbrev shapeEquations (d : Draft) : List (Shape × Shape) := d.relations.map fun x ↦ (x.1.shape, x.2.shape)/-- The atomic affinity constraints of a draft under the shapes `θ`. -/abbrev affinityConstraints (d : Draft) (θ : Nat → Shape) : List (AffinityConstraint AffinityVar) := d.relations.flatMap fun x ↦ decompose (x.1.decorate θ) (x.2.decorate θ)theorem solveInput_ok {input : Input} {s : Solution} (h : solveInput input = .ok s) : ∃ n', (generate [] input).run 0 = .ok (s.draft, n') ∧ unify (shapeEquations s.draft) = some s.shapes ∧ solveAffinities (affinityConstraints s.draft s.shapes) = some s.affinities := by unfold solveInput at h simp only [bind_eq_ok] at h obtain ⟨⟨d, n'⟩, hg, h⟩ := h split at h · rename_i θ hu split at h · rename_i ρ ha rw [pure_eq_ok] at h subst h exact ⟨n', hg, hu, ha⟩ · cases h · cases htheorem solveInput_of {input : Input} {d : Draft} {n' : Nat} {θ : Nat → Shape} {ρ : AffinityVar → Affinity} (hg : (generate [] input).run 0 = .ok (d, n')) (hu : unify (shapeEquations d) = some θ) (ha : solveAffinities (affinityConstraints d θ) = some ρ) : solveInput input = .ok ⟨d, θ, ρ⟩ := by unfold solveInput simp only [hg, ok_bind] simp only [shapeEquations, affinityConstraints] at hu ha simp only [hu, ha] rfltheorem infer_ok {input : Input} {program : Annotated} {ty : Ty} : Frontend.infer input = .ok (program, ty) ↔ ∃ s, solveInput input = .ok s ∧ program = s.draft.program s.affinities ∧ ty = s.type s.draft.ty := by simp only [Frontend.infer, bind_eq_ok, pure_eq_ok, Prod.mk.injEq] exact ⟨fun ⟨s, hs, h₁, h₂⟩ ↦ ⟨s, hs, h₁.symm, h₂.symm⟩, fun ⟨s, hs, h₁, h₂⟩ ↦ ⟨s, hs, h₁.symm, h₂.symm⟩⟩/-! ## Soundness -//-- The inferred program is typed at every instance of the decorated type of the draft. -/theorem solveInput_typed {input : Input} {s : Solution} (h : solveInput input = .ok s) (v : Nat → Ty) : input.Matches (s.draft.program s.affinities) ∧ Typed [] (interpret (s.draft.program s.affinities)) ((s.draft.ty.decorate s.shapes).instantiate v s.affinities) := by obtain ⟨n', hg, hu, ha⟩ := solveInput_ok h let σ : Ground := ⟨fun α ↦ ((UType.var α).decorate s.shapes).instantiate v s.affinities, s.affinities⟩ have inst : ∀ u, σ.inst u = (u.decorate s.shapes).instantiate v s.affinities := fun u ↦ (instantiate_decorate _ _ _ u).symm have solves : σ.Solves s.draft.relations := by intro p mem rw [inst, inst] refine decompose_sound v s.affinities _ _ ?_ ?_ · rw [shape_decorate, shape_decorate] exact unify_sound hu (p.1.shape, p.2.shape) (List.mem_map.2 ⟨p, mem, rfl⟩) · exact fun c hc ↦ solveAffinities_sound ha c (List.mem_flatMap.2 ⟨p, mem, hc⟩) have := generate_sound σ input [] 0 s.draft n' hg solves rw [inst] at this exact this/-! ## Completeness and optimality -//-- A typed completion determines a solution of inference above it. -/theorem solveInput_complete {input : Input} {completion : Annotated} {T : Ty} (hm : input.Matches completion) (ht : Typed [] (interpret completion) T) : ∃ s, solveInput input = .ok s ∧ AffinityLE completion (s.draft.program s.affinities) := by -- Lemma C: the completion solves the subtyping constraints. obtain ⟨d, n', hg, -, σ₁, -, F⟩ := generate_complete input [] [] 0 ⟨fun _ ↦ .unit, fun _ ↦ .G⟩ completion T (fun _ _ ↦ List.Forall₂.nil) hm ht -- Its shapes unify the shape equations. let δ : Nat → Shape := fun α ↦ shapeOf (σ₁.types α) obtain ⟨S₁, -, -⟩ := F σ₁ (Agree.refl _ _) have unifies : Unifies δ (shapeEquations d) := by intro e he obtain ⟨p, mem, rfl⟩ := List.mem_map.1 he have := shapeOf_sub (S₁ p mem) rwa [Ground.inst, Ground.inst, shape_instantiate, shape_instantiate] at this obtain ⟨θ, hu⟩ := unify_complete unifies have factor := unify_mostGeneral hu unifies -- Its affinities, read off at the leaves, solve the atomic constraints. let ρ : AffinityVar → Affinity := fun | .generated j => σ₁.affinities (.generated j) | .leaf α p => affinityAt (σ₁.types α) p let σ₂ : Ground := ⟨σ₁.types, ρ⟩ obtain ⟨S₂, -, program⟩ := F σ₂ fun _ _ ↦ ⟨rfl, rfl⟩ have satisfies : Satisfies ρ (affinityConstraints d θ) := by intro c hc' obtain ⟨p, mem, hc⟩ := List.mem_flatMap.1 hc' have approx := approx_decorate (θ := θ) (types := σ₁.types) (ρ := ρ) factor fun _ _ ↦ rfl exact decompose_complete (S₂ p mem) _ _ (approx p.1) (approx p.2) c hc obtain ⟨ρmax, ha⟩ := solveAffinities_complete satisfies refine ⟨_, solveInput_of hg hu ha, ?_⟩ rw [← program] exact program_le (solveAffinities_greatest ha satisfies) d/-! ## The statement -/theorem infer_correct (input : Input) : match infer input with | .error _ => ¬ ∃ program : Annotated, Completion input program | .ok (program, ty) => input.Matches program ∧ Typed [] (interpret program) ty ∧ ∀ completion : Annotated, Completion input completion → AffinityLE completion program := by split · rintro ⟨completion, hm, T, ht⟩ obtain ⟨s, hs, -⟩ := solveInput_complete hm ht rename_i h rw [infer_ok.2 ⟨s, hs, rfl, rfl⟩] at h cases h · rename_i program ty h obtain ⟨s, hs, rfl, rfl⟩ := infer_ok.1 h obtain ⟨hm, ht⟩ := solveInput_typed hs fun _ ↦ .unit refine ⟨hm, ht, ?_⟩ rintro completion ⟨hm', T, ht'⟩ obtain ⟨s', hs', le⟩ := solveInput_complete hm' ht' rw [hs, Except.ok.injEq] at hs' subst hs' exact leend Determinize.Proof.Frontend