Documentation

Determinize.Proof.Frontend.Completeness

Completeness of generation (Lemma C) #

A typed completion determines a solution of the subtyping constraints of the draft: if ê fills the omitted affinities of e and has type T in a context Γ' above the instance of Γ, then generate succeeds, and the substitution extends to the fresh variables of the draft such that every constraint holds, the draft's type is below T, and the read-back program is ê itself.

The extension is chosen from the typing derivation, one inversion lemma per constructor. The conclusion is robust: it holds for every substitution that agrees with the extension below the final counter, so that the variables of later subterms can still be chosen freely.

What Lemma C establishes about the draft d of a completion ê at the type T.

Equations
Instances For

    Fresh variables #

    Each lemma gives the fresh variables that generate draws at the counter n the values chosen from the typing derivation, and states these values under every substitution that agrees with the extension below the next counter. The counters are written as generate produces them.

    theorem Determinize.Proof.Frontend.fresh₁ (σ : Ground) (n : ℕ) (A : Spec.Paper.Ty) :
    ∃ (σ₀ : Ground), Ground.Agree n σ σ₀ ∧ ∀ (σ' : Ground), Ground.Agree (n + 1) σ₀ σ' → σ'.types n = A
    theorem Determinize.Proof.Frontend.fresh₂ (σ : Ground) (n : ℕ) (A B : Spec.Paper.Ty) :
    ∃ (σ₀ : Ground), Ground.Agree n σ σ₀ ∧ ∀ (σ' : Ground), Ground.Agree (n + 1 + 1) σ₀ σ' → σ'.types n = A ∧ σ'.types (n + 1) = B
    theorem Determinize.Proof.Frontend.fresh₃ (σ : Ground) (n : ℕ) (A B C : Spec.Paper.Ty) :
    ∃ (σ₀ : Ground), Ground.Agree n σ σ₀ ∧ ∀ (σ' : Ground), Ground.Agree (n + 1 + 1 + 1) σ₀ σ' → σ'.types n = A ∧ σ'.types (n + 1) = B ∧ σ'.types (n + 1 + 1) = C
    theorem Determinize.Proof.Frontend.fresh_affinity (σ : Ground) (n : ℕ) (m : Spec.Paper.Affinity) :
    ∃ (σ₀ : Ground), Ground.Agree n σ σ₀ ∧ ∀ (σ' : Ground), Ground.Agree (n + 1) σ₀ σ' → σ'.affinities (Frontend.AffinityVar.generated n) = m
    theorem Determinize.Proof.Frontend.site_complete {r : Option Spec.Paper.Affinity} {m : Spec.Paper.Affinity} (hr : r = none ∨ r = some m) (n : ℕ) (σ : Ground) :
    ∃ (t : Frontend.UType) (n₁ : ℕ), StateT.run (Frontend.site r) n = Except.ok (t, n₁) ∧ n ≤ n₁ ∧ ∃ (σ₁ : Ground), Ground.Agree n σ σ₁ ∧ Robust n₁ σ₁ fun (σ' : Ground) => σ'.inst t = Spec.Paper.Ty.float m ∧ Frontend.UType.affinity σ'.affinities t = m

    The type of a sample site that the completion samples at m becomes float m.

    The type of a draft node.

    Equations
    Instances For

      Split a completion that matches the input node.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        theorem Determinize.Proof.Frontend.generate_complete (e : Spec.Paper.Input) (Γ : List Frontend.UType) (Γ' : List Spec.Paper.Ty) (n : ℕ) (σ : Ground) (ê : Spec.Paper.Annotated) (T : Spec.Paper.Ty) :
        Robust n σ (Context Γ Γ') → e.Matches ê → Spec.Paper.Typed Γ' (Spec.Paper.interpret ↑ê) T → ∃ (d : Frontend.Draft) (n' : ℕ), StateT.run (Frontend.generate Γ e) n = Except.ok (d, n') ∧ n ≤ n' ∧ ∃ (σ₁ : Ground), Ground.Agree n σ σ₁ ∧ Robust n' σ₁ (Fits d ê T)

        Lemma C.