Soundness, optimality, and completeness of affinity inference #
The 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, sounifysucceeds 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′), sosolveAffinitiessucceeds and returns a larger solution (Lemma P); read-back is monotone.
The phases of inference #
@[reducible, inline]
The shape equations of a draft.
Equations
- Determinize.Proof.Frontend.shapeEquations d = List.map (fun (x : Determinize.Frontend.UType × Determinize.Frontend.UType) => (x.1.shape, x.2.shape)) d.relations
Instances For
@[reducible, inline]
abbrev
Determinize.Proof.Frontend.affinityConstraints
(d : Frontend.Draft)
(θ : ℕ → Frontend.Shape)
:
The atomic affinity constraints of a draft under the shapes θ.
Equations
- One or more equations did not get rendered due to their size.
Instances For
theorem
Determinize.Proof.Frontend.solveInput_ok
{input : Spec.Paper.Input}
{s : Frontend.Solution}
(h : Frontend.solveInput input = Except.ok s)
:
∃ (n' : ℕ),
StateT.run (Frontend.generate [] input) 0 = Except.ok (s.draft, n') ∧ Frontend.unify (shapeEquations s.draft) = some s.shapes ∧ Frontend.solveAffinities (affinityConstraints s.draft s.shapes) = some s.affinities
theorem
Determinize.Proof.Frontend.solveInput_of
{input : Spec.Paper.Input}
{d : Frontend.Draft}
{n' : ℕ}
{θ : ℕ → Frontend.Shape}
{ρ : Frontend.AffinityVar → Spec.Paper.Affinity}
(hg : StateT.run (Frontend.generate [] input) 0 = Except.ok (d, n'))
(hu : Frontend.unify (shapeEquations d) = some θ)
(ha : Frontend.solveAffinities (affinityConstraints d θ) = some ρ)
:
theorem
Determinize.Proof.Frontend.infer_ok
{input : Spec.Paper.Input}
{program : Spec.Paper.Annotated}
{ty : Spec.Paper.Ty}
:
Frontend.infer input = Except.ok (program, ty) ↔ ∃ (s : Frontend.Solution),
Frontend.solveInput input = Except.ok s ∧ program = Frontend.Draft.program s.affinities s.draft ∧ ty = s.type s.draft.ty
Soundness #
theorem
Determinize.Proof.Frontend.solveInput_typed
{input : Spec.Paper.Input}
{s : Frontend.Solution}
(h : Frontend.solveInput input = Except.ok s)
(v : ℕ → Spec.Paper.Ty)
:
input.Matches (Frontend.Draft.program s.affinities s.draft) ∧ Spec.Paper.Typed [] (Spec.Paper.interpret ↑(Frontend.Draft.program s.affinities s.draft))
(Frontend.UType.instantiate v s.affinities (Frontend.UType.decorate s.shapes s.draft.ty))
The inferred program is typed at every instance of the decorated type of the draft.
Completeness and optimality #
theorem
Determinize.Proof.Frontend.solveInput_complete
{input : Spec.Paper.Input}
{completion : Spec.Paper.Annotated}
{T : Spec.Paper.Ty}
(hm : input.Matches completion)
(ht : Spec.Paper.Typed [] (Spec.Paper.interpret ↑completion) T)
:
∃ (s : Frontend.Solution),
Frontend.solveInput input = Except.ok s ∧ Spec.AffinityLE completion (Frontend.Draft.program s.affinities s.draft)
A typed completion determines a solution of inference above it.
The statement #
theorem
Determinize.Proof.Frontend.infer_correct
(input : Spec.Paper.Input)
:
match Frontend.infer input with
| Except.error a => ¬∃ (program : Spec.Paper.Annotated), Spec.Completion input program
| Except.ok (program, ty) =>
input.Matches program ∧ Spec.Paper.Typed [] (Spec.Paper.interpret ↑program) ty ∧ ∀ (completion : Spec.Paper.Annotated), Spec.Completion input completion → Spec.AffinityLE completion program