Documentation

LeanSce.SCE.Divergence

Divergence preservation and behaviour equivalence #

Divergence is an infinite small-step sequence (SDiverges, CDiverges). The forward simulation of SCE.Simulation turns an infinite source sequence into an infinite Core sequence: between two CPlus steps the source can stutter only finitely often, since each stutter strictly decreases letbCount.

With type safety of both calculi and determinism of Core, termination and divergence are then each preserved and reflected: a well-typed source term and its elaboration have the same behaviour.

Divergence #

def SDiverges (ρ e : SCE.Exp) :

A source term diverges: it starts an infinite small-step sequence.

Equations
Instances For
    def CDiverges (ρ e : Core.Exp) :

    A Core term diverges: it starts an infinite small-step sequence.

    Equations
    Instances For
      theorem infinite_chain {α : Type} (R : α → α → Prop) (Q : α → Prop) (H : ∀ (a : α), Q a → ∃ (b : α), R a b ∧ Q b) {a : α} (ha : Q a) :
      ∃ (f : Nat → α), f 0 = a ∧ ∀ (n : Nat), R (f n) (f (n + 1))

      An invariant that always admits a further step yields an infinite sequence.

      theorem cdiverges_of_cplus {ρ : Core.Exp} (P : Core.Exp → Prop) (H : ∀ (c : Core.Exp), P c → ∃ (c' : Core.Exp), CPlus ρ c c' ∧ P c') {c : Core.Exp} (hc : P c) :

      Divergence preservation for elaboration #

      theorem elab_preserves_divergence {Γ A : SCE.Typ} {es ρs : SCE.Exp} {ec ρc : Core.Exp} (helab : elabExp Γ es A ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) (hdiv : SDiverges ρs es) :
      CDiverges ρc ec

      Elaboration preserves divergence.

      Divergence for separate compilation #

      theorem separate_compilation_diverges {Γ Γ₁ A B : SCE.Typ} {l : String} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp Γ es₂ ((SCE.Typ.rcd l A).marr B) ec₂) (hlookup : SCE.SRLookup Γ₁ l A) (hlink : CoreLink l (elabTyp Γ₁) (elabTyp A) (elabTyp B) ec₁ ec₂ ec) (hdiv : SDiverges ρs (es₁.mlink es₂)) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
      CDiverges ρc ec

      Separate compilation (binary link), divergence.

      theorem separate_compilation_sandboxed_diverges {Γ Γ₁ A B : SCE.Typ} {l : String} {es₁ body : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top (SCE.Exp.mfunctor SCE.Sandbox.sandboxed (SCE.Typ.rcd l A) body) ((SCE.Typ.rcd l A).marr B) ec₂) (hlookup : SCE.SRLookup Γ₁ l A) (hlink : CoreLink l (elabTyp Γ₁) (elabTyp A) (elabTyp B) ec₁ ec₂ ec) (hdiv : SDiverges ρs (es₁.mlink (SCE.Exp.mfunctor SCE.Sandbox.sandboxed (SCE.Typ.rcd l A) body))) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
      CDiverges ρc ec

      Sandboxed client, binary link, divergence.

      theorem separate_compilation_closed_diverges {Γ₁ A B : SCE.Typ} {l : String} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ : Core.Exp} (helab₁ : elabExp SCE.Typ.top es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top es₂ ((SCE.Typ.rcd l A).marr B) ec₂) (hlookup : SCE.SRLookup Γ₁ l A) (hdiv : SDiverges SCE.Exp.unit (es₁.mlink es₂)) :

      Closed units, empty environment, binary link, divergence.

      theorem separate_compilation_n_diverges {Γ Γ₁ D B : SCE.Typ} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp Γ es₂ (D.marr B) ec₂) (hok : SCE.LinkOk Γ₁ D) (hlink : CoreLinkN D (elabTyp Γ₁) (elabTyp B) ec₁ ec₂ ec) (hdiv : SDiverges ρs (es₁.mlinkn es₂)) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
      CDiverges ρc ec

      Separate compilation (n-ary linkall), divergence.

      theorem separate_compilation_n_sandboxed_diverges {Γ Γ₁ D B : SCE.Typ} {es₁ body : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top (SCE.Exp.mfunctor SCE.Sandbox.sandboxed D body) (D.marr B) ec₂) (hok : SCE.LinkOk Γ₁ D) (hlink : CoreLinkN D (elabTyp Γ₁) (elabTyp B) ec₁ ec₂ ec) (hdiv : SDiverges ρs (es₁.mlinkn (SCE.Exp.mfunctor SCE.Sandbox.sandboxed D body))) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
      CDiverges ρc ec

      Sandboxed client, n-ary linkall, divergence.

      theorem separate_compilation_n_closed_diverges {Γ₁ D B : SCE.Typ} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ : Core.Exp} (helab₁ : elabExp SCE.Typ.top es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top es₂ (D.marr B) ec₂) (hok : SCE.LinkOk Γ₁ D) (hdiv : SDiverges SCE.Exp.unit (es₁.mlinkn es₂)) :

      Closed units, empty environment, n-ary linkall, divergence.

      Behaviour equivalence #

      theorem source_terminates_or_diverges {Γ A : SCE.Typ} {es ρs : SCE.Exp} {ec ρc : Core.Exp} (helab : elabExp Γ es A ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
      (∃ (vs : SCE.Exp), S_Sem.BStep ρs es vs) ∨ SDiverges ρs es

      Source type safety: a well-typed source term terminates or diverges.

      theorem core_diverges_not_terminates {E A : Core.Typ} {ρ e v : Core.Exp} (ht : HasType E e A) (hρ : HasType Core.Typ.top ρ E) (hdiv : CDiverges ρ e) (hm : MStep ρ e v) (hv : Core.Value v) :

      A well-typed Core term cannot both diverge and reach a value.

      theorem core_mstep_value_unique {E A : Core.Typ} {ρ e v1 v2 : Core.Exp} (ht : HasType E e A) (hρ : HasType Core.Typ.top ρ E) (hm1 : MStep ρ e v1) (hv1 : Core.Value v1) (hm2 : MStep ρ e v2) (hv2 : Core.Value v2) :
      v1 = v2

      Well-typed Core multi-step evaluation has at most one value.

      theorem core_typed_of_elab {Γ A : SCE.Typ} {es ρs : SCE.Exp} {ec ρc : Core.Exp} (helab : elabExp Γ es A ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) :
      theorem elab_reflects_termination {Γ A : SCE.Typ} {es ρs : SCE.Exp} {ec ρc vc : Core.Exp} (helab : elabExp Γ es A ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) (hbig : EBig ρc ec vc) :

      Termination is reflected: if the elaboration terminates, so does the source, at a value whose elaboration is the Core result.

      theorem elab_reflects_divergence {Γ A : SCE.Typ} {es ρs : SCE.Exp} {ec ρc : Core.Exp} (helab : elabExp Γ es A ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) (hdiv : CDiverges ρc ec) :
      SDiverges ρs es

      Divergence is reflected: if the elaboration diverges, so does the source.

      def SameBehaviour (A : SCE.Typ) (ρs es : SCE.Exp) (ρc ec : Core.Exp) :

      The behaviour of a well-typed term and of its elaboration: the same values (up to elaboration) on termination, and divergence iff divergence.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        theorem elab_behaviour_equiv {Γ A : SCE.Typ} {es ρs : SCE.Exp} {ec ρc : Core.Exp} (helab : elabExp Γ es A ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
        SameBehaviour A ρs es ρc ec

        Behaviour equivalence for elaboration.

        Behaviour equivalence for separate compilation #

        theorem separate_compilation_behaviour {Γ Γ₁ A B : SCE.Typ} {l : String} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp Γ es₂ ((SCE.Typ.rcd l A).marr B) ec₂) (hlookup : SCE.SRLookup Γ₁ l A) (hlink : CoreLink l (elabTyp Γ₁) (elabTyp A) (elabTyp B) ec₁ ec₂ ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
        SameBehaviour (Γ₁.and B) ρs (es₁.mlink es₂) ρc ec

        Separate compilation (binary link), behaviour equivalence.

        theorem separate_compilation_sandboxed_behaviour {Γ Γ₁ A B : SCE.Typ} {l : String} {es₁ body : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top (SCE.Exp.mfunctor SCE.Sandbox.sandboxed (SCE.Typ.rcd l A) body) ((SCE.Typ.rcd l A).marr B) ec₂) (hlookup : SCE.SRLookup Γ₁ l A) (hlink : CoreLink l (elabTyp Γ₁) (elabTyp A) (elabTyp B) ec₁ ec₂ ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
        SameBehaviour (Γ₁.and B) ρs (es₁.mlink (SCE.Exp.mfunctor SCE.Sandbox.sandboxed (SCE.Typ.rcd l A) body)) ρc ec

        Sandboxed client, binary link, behaviour equivalence.

        theorem separate_compilation_closed_behaviour {Γ₁ A B : SCE.Typ} {l : String} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ : Core.Exp} (helab₁ : elabExp SCE.Typ.top es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top es₂ ((SCE.Typ.rcd l A).marr B) ec₂) (hlookup : SCE.SRLookup Γ₁ l A) :
        SameBehaviour (Γ₁.and B) SCE.Exp.unit (es₁.mlink es₂) Core.Exp.unit (linkedCore (elabTyp Γ₁) (elabTyp (SCE.Typ.rcd l A)) (elabTyp B) ec₁ ec₂)

        Closed units, empty environment, binary link, behaviour equivalence.

        theorem separate_compilation_n_behaviour {Γ Γ₁ D B : SCE.Typ} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp Γ es₂ (D.marr B) ec₂) (hok : SCE.LinkOk Γ₁ D) (hlink : CoreLinkN D (elabTyp Γ₁) (elabTyp B) ec₁ ec₂ ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
        SameBehaviour (Γ₁.and B) ρs (es₁.mlinkn es₂) ρc ec

        Separate compilation (n-ary linkall), behaviour equivalence.

        theorem separate_compilation_n_sandboxed_behaviour {Γ Γ₁ D B : SCE.Typ} {es₁ body : SCE.Exp} {ec₁ ec₂ ec : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} (helab₁ : elabExp Γ es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top (SCE.Exp.mfunctor SCE.Sandbox.sandboxed D body) (D.marr B) ec₂) (hok : SCE.LinkOk Γ₁ D) (hlink : CoreLinkN D (elabTyp Γ₁) (elabTyp B) ec₁ ec₂ ec) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
        SameBehaviour (Γ₁.and B) ρs (es₁.mlinkn (SCE.Exp.mfunctor SCE.Sandbox.sandboxed D body)) ρc ec

        Sandboxed client, n-ary linkall, behaviour equivalence.

        theorem separate_compilation_n_closed_behaviour {Γ₁ D B : SCE.Typ} {es₁ es₂ : SCE.Exp} {ec₁ ec₂ : Core.Exp} (helab₁ : elabExp SCE.Typ.top es₁ Γ₁ ec₁) (helab₂ : elabExp SCE.Typ.top es₂ (D.marr B) ec₂) (hok : SCE.LinkOk Γ₁ D) :
        SameBehaviour (Γ₁.and B) SCE.Exp.unit (es₁.mlinkn es₂) Core.Exp.unit (linkedCore (elabTyp Γ₁) (elabTyp D) (elabTyp B) ec₁ ec₂)

        Closed units, empty environment, n-ary linkall, behaviour equivalence.