Documentation

Determinize.Proof.Frontend.Ground

Ground substitutions for generation #

The drafts that generate produces have types over type variables and affinity variables. A Ground substitution replaces all of them; Solves says that it satisfies every subtyping constraint of a draft. Lemma S (Proof/Frontend/Soundness.lean) types the read-back program under every solution, and Lemma C (Proof/Frontend/Completeness.lean) builds a solution from a typed completion.

Generation draws fresh variables from a counter, so Lemma C extends a substitution on the variables at or above the counter, and must know that this does not disturb what is already established. Agree n σ σ' says that two substitutions agree on the variables below n, and Robust n σ P that P holds for every substitution that agrees with σ below n.

The file also collects the monad lemmas for unfolding generate, and shows that the read-back program is monotone in the affinities (program_le).

Unfolding generate #

theorem Determinize.Proof.Frontend.bind_eq_ok {ε α β : Type} {x : Except ε α} {f : α → Except ε β} {b : β} :
x >>= f = Except.ok b ↔ ∃ (a : α), x = Except.ok a ∧ f a = Except.ok b
theorem Determinize.Proof.Frontend.ok_bind {ε α β : Type} {a : α} {f : α → Except ε β} :
Except.ok a >>= f = f a
theorem Determinize.Proof.Frontend.pure_eq_ok {ε α : Type} {a b : α} :
pure a = Except.ok b ↔ a = b

Unfold one call of generate in a hypothesis (generate Γ e).run n = .ok (d, n') into the successful runs of its steps.

Equations
  • One or more equations did not get rendered due to their size.
Instances For

    Unfold one call of generate in a goal (generate Γ e).run n = …, keeping site.

    Equations
    Instances For

      Ground substitutions #

      A type for every type variable and an affinity for every affinity variable.

      Instances For

        σ makes the first type of every relation a subtype of the second.

        Equations
        Instances For
          @[simp]
          @[simp]
          theorem Determinize.Proof.Frontend.Ground.inst_sum (σ : Ground) (a b : Frontend.UType) :
          σ.inst (a.sum b) = (σ.inst a).sum (σ.inst b)
          @[simp]
          theorem Determinize.Proof.Frontend.Ground.inst_arr (σ : Ground) (a b : Frontend.UType) :
          σ.inst (a.arr b) = (σ.inst a).arr (σ.inst b)
          Equations
          Instances For

            σ and σ' agree on the type variables and generated affinity variables below n.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              theorem Determinize.Proof.Frontend.Ground.Agree.type {n : ℕ} {σ σ' : Ground} (h : Agree n σ σ') {i : ℕ} (hi : i < n) :
              σ'.types i = σ.types i
              theorem Determinize.Proof.Frontend.Ground.Agree.step {n n₁ : ℕ} {σ σ₁ σ' : Ground} (a : Agree n σ σ₁) (h : Agree n₁ σ₁ σ') (le : n ≤ n₁) :
              Agree n σ σ'

              Agreement below n followed by agreement below a larger n₁.

              theorem Determinize.Proof.Frontend.Ground.Agree.setType {n i : ℕ} {σ σ' : Ground} (h : Agree n σ σ') (hi : n ≤ i) (A : Spec.Paper.Ty) :
              Agree n σ (σ'.setType i A)
              theorem Determinize.Proof.Frontend.Ground.Agree.setAffinity {n i : ℕ} {σ σ' : Ground} (h : Agree n σ σ') (hi : n ≤ i) (m : Spec.Paper.Affinity) :
              Agree n σ (σ'.setAffinity i m)
              @[simp]
              theorem Determinize.Proof.Frontend.Ground.setType_types (σ : Ground) (i : ℕ) (A : Spec.Paper.Ty) (j : ℕ) :
              (σ.setType i A).types j = if j = i then A else σ.types j

              Split the relations of a draft node into those of its children and casts, and instantiate the cast types.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For

                The read-back of a draft node.

                Equations
                Instances For

                  P holds for every substitution that agrees with σ below n.

                  Equations
                  Instances For
                    theorem Determinize.Proof.Frontend.Robust.extend {n n₁ : ℕ} {σ σ₁ : Ground} {P : Ground → Prop} (h : Robust n σ P) (a : Ground.Agree n σ σ₁) (le : n ≤ n₁) :
                    Robust n₁ σ₁ P

                    The instances of a context are pointwise subtypes of Γ'.

                    Equations
                    Instances For
                      theorem Determinize.Proof.Frontend.Robust.cons {n : ℕ} {σ : Ground} {Γ : List Frontend.UType} {Γ' : List Spec.Paper.Ty} {t : Frontend.UType} {A : Spec.Paper.Ty} (hΓ : Robust n σ (Context Γ Γ')) (ht : Robust n σ fun (σ' : Ground) => (σ'.inst t).Sub A) :
                      Robust n σ (Context (t :: Γ) (A :: Γ'))
                      theorem Determinize.Proof.Frontend.context_getElem? {Γ : List Frontend.UType} {Γ' : List Spec.Paper.Ty} {σ : Ground} (h : Context Γ Γ' σ) {i : ℕ} {A : Spec.Paper.Ty} (hA : Γ'[i]? = some A) :
                      ∃ (t : Frontend.UType), Γ[i]? = some t ∧ (σ.inst t).Sub A

                      A variable of a context is found in the corresponding position.

                      Monotonicity of read-back #

                      theorem Determinize.Proof.Frontend.Draft.induction {P : Frontend.Draft → Prop} (node : ∀ (e : Spec.Paper.Input) (t : Frontend.UType) (children : List Frontend.Draft), (∀ c ∈ children, P c) → P (Frontend.Draft.node e t children)) (cast : ∀ (body : Frontend.Draft) (t : Frontend.UType), P body → P (body.cast t)) (d : Frontend.Draft) :
                      P d

                      Induction on drafts, with a hypothesis for every child of a node.

                      Read-back is monotone: larger affinities give a larger program.