Documentation

LeanSce.SCE.Simulation

Small-step forward simulation for elaboration #

Every source small step of a well-typed expression is matched by one or more Core steps of its elaboration, except one administrative source step (letb entering its body), which is matched by zero Core steps and strictly decreases a measure letbCount on the source term (CompCert's forward_simulation_star shape).

The elaboration of a reduct is in general not the Core reduct: the encodings of ,, (nmrgCore), open and link/linkall (linkedCore) perform administrative Core steps that have no source counterpart, and let is compiled to a merge/projection that never builds the source's box. The relation is therefore

Sim ρs ρc Γ es A ec := ∃ r, ec →* r ∧ Ready ρs ρc Γ es A r

where Ready is elaboration with the administrative steps performed up to the focus of the next source step and no further. Being behind (ec →* r) is harmless; Ready pins how far ahead the Core term may be.

Core preliminaries #

def CPlus (ρ a b : Core.Exp) :

One or more Core steps.

Equations
Instances For
    theorem mstep_lift {ρ ρ' : Core.Exp} (f : Core.Exp → Core.Exp) (hρ' : Core.Value ρ') (hf : ∀ {a b : Core.Exp}, Step ρ a b → Step ρ' (f a) (f b)) {a b : Core.Exp} (h : MStep ρ a b) :
    MStep ρ' (f a) (f b)
    theorem cplus_lift {ρ ρ' : Core.Exp} (f : Core.Exp → Core.Exp) (hρ' : Core.Value ρ') (hf : ∀ {a b : Core.Exp}, Step ρ a b → Step ρ' (f a) (f b)) {a b : Core.Exp} (h : CPlus ρ a b) :
    CPlus ρ' (f a) (f b)
    theorem cplus_mstep {ρ a b : Core.Exp} (h : CPlus ρ a b) :
    MStep ρ a b
    theorem cplus_mstep_trans {ρ a b c : Core.Exp} (h1 : CPlus ρ a b) (h2 : MStep ρ b c) :
    CPlus ρ a c
    theorem mstep_cplus_trans {ρ a b c : Core.Exp} (h1 : MStep ρ a b) (h2 : CPlus ρ b c) :
    CPlus ρ a c
    theorem mstep_one {ρ a b : Core.Exp} (h : Step ρ a b) :
    MStep ρ a b
    theorem cplus_one {ρ a b : Core.Exp} (h : Step ρ a b) :
    CPlus ρ a b
    def EnvFree (c : Core.Exp) :

    Core terms whose steps do not consult the ambient environment.

    Equations
    Instances For
      theorem envfree_step {ρ c c' : Core.Exp} (hf : EnvFree c) (hs : Step ρ c c') {ρ' : Core.Exp} (hρ' : Core.Value ρ') :
      Step ρ' c c' ∧ EnvFree c'
      theorem envfree_mstep {ρ c c' : Core.Exp} (hm : MStep ρ c c') :
      EnvFree c → ∀ {ρ' : Core.Exp}, Core.Value ρ' → MStep ρ' c c' ∧ EnvFree c'
      theorem envfree_cplus {ρ c c' : Core.Exp} (hp : CPlus ρ c c') (hf : EnvFree c) {ρ' : Core.Exp} (hρ' : Core.Value ρ') :
      CPlus ρ' c c' ∧ EnvFree c'
      theorem envfree_progress {ρ ρ' rY c : Core.Exp} {P : Prop} (hEF : EnvFree rY) (hρ' : Core.Value ρ') (h : CPlus ρ rY c ∨ MStep ρ rY c ∧ P) :
      (CPlus ρ' rY c ∨ MStep ρ' rY c ∧ P) ∧ EnvFree c

      The stutter measure #

      theorem letbCount_value {v : SCE.Exp} (hv : SCE.Value v) :

      The simulation relation #

      The body of the inner λ of the linker step linkStep.

      Equations
      Instances For
        theorem linkStep_eq (g1 D B : Core.Typ) :
        inductive Ready :

        Ready ρs ρc Γ es A r: under source environment ρs and Core environment ρc (with ρs : Γ ⤳ ρc), the Core term r is the elaboration of es at type A with exactly the administrative steps before the next source step done.

        Instances For
          def Sim (ρs : SCE.Exp) (ρc : Core.Exp) (Γ : SCE.Typ) (es : SCE.Exp) (A : SCE.Typ) (ec : Core.Exp) :

          The simulation relation: the Core term reaches a Ready form.

          Equations
          Instances For
            theorem ready_value {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {e : SCE.Exp} {A : SCE.Typ} {r : Core.Exp} (h : Ready ρs ρc Γ e A r) (hv : SCE.Value e) :
            elabExp Γ e A r

            A Ready form of a source value is a Core value elaborating it.

            theorem sim_of_mstep {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {es : SCE.Exp} {A : SCE.Typ} {a b : Core.Exp} (hm : MStep ρc a b) (h : Sim ρs ρc Γ es A b) :
            Sim ρs ρc Γ es A a
            theorem sim_of_ready {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {es : SCE.Exp} {A : SCE.Typ} {r : Core.Exp} (hρc : Core.Value ρc) (h : Ready ρs ρc Γ es A r) :
            Sim ρs ρc Γ es A r

            Administrative prefixes, shared by initialisation and simulation #

            theorem app_ready {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} (hρc : Core.Value ρc) (hr1 : Ready ρs ρc Γ e1 (A.arr B) r1) (he2 : elabExp Γ e2 A c2) (h2 : SCE.Value e1 → Sim ρs ρc Γ e2 A c2) :
            Sim ρs ρc Γ (e1.app e2) B (r1.app c2)
            theorem mapp_ready {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} (hρc : Core.Value ρc) (hr1 : Ready ρs ρc Γ e1 (A.marr B) r1) (he2 : elabExp Γ e2 A c2) (h2 : SCE.Value e1 → Sim ρs ρc Γ e2 A c2) :
            Sim ρs ρc Γ (e1.mapp e2) B (r1.app c2)
            theorem box_ready {ρs : SCE.Exp} {ρc : Core.Exp} {Γ Γ' A : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} (hρc : Core.Value ρc) (hr1 : Ready ρs ρc Γ e1 Γ' r1) (he2 : elabExp Γ' e2 A c2) (h2 : SCE.Value e1 → ∀ {c1 : Core.Exp}, elabExp SCE.Typ.top e1 Γ' c1 → Sim e1 c1 Γ' e2 A c2) :
            Sim ρs ρc Γ (e1.box e2) A (r1.box c2)
            theorem mrg_ready {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} (hρc : Core.Value ρc) (hr1 : Ready ρs ρc Γ e1 A r1) (he2 : elabExp (Γ.and A) e2 B c2) (h2 : SCE.Value e1 → ∀ {c1 : Core.Exp}, elabExp Γ e1 A c1 → Sim (ρs.mrg e1) (ρc.mrg c1) (Γ.and A) e2 B c2) :
            Sim ρs ρc Γ (e1.mrg e2) (A.and B) (r1.mrg c2)
            theorem nmrg_ready {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} (hρc : Core.Value ρc) (hr1 : Ready ρs ρc Γ e1 A r1) (he2 : elabExp Γ e2 B c2) (h2 : SCE.Value e1 → Sim ρs ρc Γ e2 B c2) :
            Sim ρs ρc Γ (e1.nmrg e2) (A.and B) ((ρc.mrg ((ρc.box r1).mrg ((Core.Exp.query.proj 1).box c2))).proj 0)
            theorem linker_admin {ρc r1 c2 : Core.Exp} {g1 T : Core.Typ} {M : Core.Exp} (hρc : Core.Value ρc) (hv1 : Core.Value r1) :
            MStep ρc (((ρc.clos g1 (Core.Exp.lam T M)).app r1).app c2) (((ρc.mrg r1).clos T M).app c2)

            The linker step's administrative prefix once the provider is a value.

            theorem mlinkn_ready {ρs : SCE.Exp} {ρc : Core.Exp} {Γ Γ₁ D B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} (hρc : Core.Value ρc) (hr1 : Ready ρs ρc Γ e1 Γ₁ r1) (he2 : elabExp Γ e2 (D.marr B) c2) (hok : SCE.LinkOk Γ₁ D) (h2 : SCE.Value e1 → Sim ρs ρc Γ e2 (D.marr B) c2) :
            Sim ρs ρc Γ (e1.mlinkn e2) (Γ₁.and B) (((ρc.clos (elabTyp Γ₁) (Core.Exp.lam ((elabTyp D).arr (elabTyp B)) (linkInner (elabTyp D)))).app r1).app c2)
            theorem env_ext {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {v : SCE.Exp} {A : SCE.Typ} {c : Core.Exp} (henv : elabExp SCE.Typ.top ρs Γ ρc) (hv : SCE.Value v) (hc : elabExp Γ v A c) :
            elabExp SCE.Typ.top (ρs.mrg v) (Γ.and A) (ρc.mrg c)

            Environment extension used by every rule that evaluates under ρ , v.

            theorem sim_init {Γ : TyCtx} {es : SCE.Exp} {A : SCE.Typ} {ec : Core.Exp} (helab : elabExp Γ es A ec) {ρs : SCE.Exp} {ρc : Core.Exp} :
            SCE.Value ρs → elabExp SCE.Typ.top ρs Γ ρc → Sim ρs ρc Γ es A ec

            The simulation step #

            def SimStep (ρs : SCE.Exp) (ρc : Core.Exp) (Γ : SCE.Typ) (es es' : SCE.Exp) (A : SCE.Typ) (r : Core.Exp) :

            The conclusion of one simulation step: one or more Core steps, or zero or more Core steps with a strict decrease of the stutter measure, reaching a term Sim-related to the source reduct.

            Equations
            Instances For
              theorem simstep_lift {ρs' : SCE.Exp} {ρ' : Core.Exp} {Γ' : SCE.Typ} {e e' : SCE.Exp} {A' : SCE.Typ} {r : Core.Exp} {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {E E' : SCE.Exp} {A : SCE.Typ} (f : Core.Exp → Core.Exp) (hρc : Core.Value ρc) (hf : ∀ {a b : Core.Exp}, Step ρ' a b → Step ρc (f a) (f b)) (hμ : letbCount e' < letbCount e → letbCount E' < letbCount E) (h : SimStep ρs' ρ' Γ' e e' A' r) (hk : ∀ {r' : Core.Exp}, Ready ρs' ρ' Γ' e' A' r' → Sim ρs ρc Γ E' A (f r')) :
              SimStep ρs ρc Γ E E' A (f r)

              Lift a simulation step through an evaluation context of the Core term.

              theorem simstep_redex {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {es es' : SCE.Exp} {A : SCE.Typ} {r c : Core.Exp} (hρs : SCE.Value ρs) (henv : elabExp SCE.Typ.top ρs Γ ρc) (hp : CPlus ρc r c) (he : elabExp Γ es' A c) :
              SimStep ρs ρc Γ es es' A r
              theorem simstep_redex1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {es es' : SCE.Exp} {A : SCE.Typ} {r c : Core.Exp} (hρs : SCE.Value ρs) (henv : elabExp SCE.Typ.top ρs Γ ρc) (hs : Step ρc r c) (he : elabExp Γ es' A c) :
              SimStep ρs ρc Γ es es' A r
              theorem sim_step_ready {ρs es es' : SCE.Exp} (hstep : SStep ρs es es') {ρc : Core.Exp} {Γ A : SCE.Typ} {r : Core.Exp} :
              ¬SCE.Value es → elabExp SCE.Typ.top ρs Γ ρc → Ready ρs ρc Γ es A r → SimStep ρs ρc Γ es es' A r

              Forward simulation #

              theorem elab_forward_simulation {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A : SCE.Typ} {es es' : SCE.Exp} {ec : Core.Exp} (henv : elabExp SCE.Typ.top ρs Γ ρc) (hstep : SStep ρs es es') (hsim : Sim ρs ρc Γ es A ec) :
              ∃ (ec' : Core.Exp), (CPlus ρc ec ec' ∨ MStep ρc ec ec' ∧ letbCount es' < letbCount es) ∧ Sim ρs ρc Γ es' A ec'

              Forward simulation (star with measure). If the source takes a small step, a Sim-related Core term takes one or more steps, or zero or more steps while the stutter measure strictly decreases, to a term related to the source reduct.

              theorem elab_sim {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {es : SCE.Exp} {A : SCE.Typ} {ec : Core.Exp} (helab : elabExp Γ es A ec) (hρs : SCE.Value ρs) (henv : elabExp SCE.Typ.top ρs Γ ρc) :
              Sim ρs ρc Γ es A ec

              An elaboration is related to its source term.

              theorem sim_final {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} {v : SCE.Exp} {A : SCE.Typ} {ec : Core.Exp} (hsim : Sim ρs ρc Γ v A ec) (hv : SCE.Value v) :
              ∃ (vc : Core.Exp), MStep ρc ec vc ∧ Core.Value vc ∧ elabExp Γ v A vc

              At a source value, the related Core term reaches the elaboration of it.