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 #
The stutter measure #
Number of letb nodes outside binders. Values have measure 0.
Equations
- letbCount SCE.Exp.query = 0
- letbCount (e.proj a) = letbCount e
- letbCount (SCE.Exp.lit a) = 0
- letbCount SCE.Exp.unit = 0
- letbCount (SCE.Exp.lam a a_1) = 0
- letbCount (e1.box e2) = letbCount e1 + letbCount e2
- letbCount (a.clos a_1 a_2) = 0
- letbCount (e1.app e2) = letbCount e1 + letbCount e2
- letbCount (e1.mrg e2) = letbCount e1 + letbCount e2
- letbCount (SCE.Exp.lrec a e) = letbCount e
- letbCount (e.rproj a) = letbCount e
- letbCount e.mstruct = letbCount e
- letbCount (SCE.Exp.mfunctor a a_1 a_2) = 0
- letbCount (a.mclos a_1 a_2) = 0
- letbCount (e1.mlink e2) = letbCount e1 + letbCount e2
- letbCount (e1.mapp e2) = letbCount e1 + letbCount e2
- letbCount (e1.nmrg e2) = letbCount e1 + letbCount e2
- letbCount (e1.letb e2) = letbCount e1 + letbCount e2 + 1
- letbCount (e1.openm e2) = letbCount e1 + letbCount e2
- letbCount (e1.mlinkn e2) = letbCount e1 + letbCount e2
- letbCount (SCE.Exp.inl a e) = letbCount e
- letbCount (SCE.Exp.inr a e) = letbCount e
- letbCount (e.case e1 e2) = letbCount e + letbCount e1 + letbCount e2
- letbCount (SCE.Exp.flam a a_1 a_2) = 0
- letbCount (a.fclos a_1 a_2 a_3) = 0
- letbCount (SCE.Exp.fold a e) = letbCount e
- letbCount e.unfold = letbCount e
Instances For
The simulation relation #
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.
- val {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {e : SCE.Exp} {A : SCE.Typ} {c : Core.Exp} : SCE.Value e → elabExp Γ e A c → Ready ρs ρc Γ e A c
- query {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : SCE.Typ} : Ready ρs ρc Γ SCE.Exp.query Γ Core.Exp.query
- lam {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e : SCE.Exp} {c : Core.Exp} : elabExp (Γ.and A) e B c → Ready ρs ρc Γ (SCE.Exp.lam A e) (A.arr B) (Core.Exp.lam (elabTyp A) c)
- flam {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e : SCE.Exp} {c : Core.Exp} : elabExp ((Γ.and (A.arr B)).and A) e B c → Ready ρs ρc Γ (SCE.Exp.flam A B e) (A.arr B) (Core.Exp.flam (elabTyp A) (elabTyp B) c)
- mfunctor {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {sb : SCE.Sandbox} {A : SCE.Typ} {e : SCE.Exp} {T : SCE.Typ} {c : Core.Exp} : elabExp Γ (SCE.Exp.mfunctor sb A e) T c → Ready ρs ρc Γ (SCE.Exp.mfunctor sb A e) T c
- app1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} : ¬SCE.Value e1 → Ready ρs ρc Γ e1 (A.arr B) r1 → elabExp Γ e2 A c2 → Ready ρs ρc Γ (e1.app e2) B (r1.app c2)
- app2 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {A B : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} : SCE.Value v1 → elabExp Γ v1 (A.arr B) c1 → Ready ρs ρc Γ e2 A r2 → Ready ρs ρc Γ (v1.app e2) B (c1.app r2)
- mapp1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} : ¬SCE.Value e1 → Ready ρs ρc Γ e1 (A.marr B) r1 → elabExp Γ e2 A c2 → Ready ρs ρc Γ (e1.mapp e2) B (r1.app c2)
- mapp2 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {A B : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} : SCE.Value v1 → elabExp Γ v1 (A.marr B) c1 → Ready ρs ρc Γ e2 A r2 → Ready ρs ρc Γ (v1.mapp e2) B (c1.app r2)
- proj {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} {i : Nat} : Ready ρs ρc Γ e A r → SCE.SLookup A i B → Ready ρs ρc Γ (e.proj i) B (r.proj i)
- box1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ Γ' A : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} : ¬SCE.Value e1 → Ready ρs ρc Γ e1 Γ' r1 → elabExp Γ' e2 A c2 → Ready ρs ρc Γ (e1.box e2) A (r1.box c2)
- box2 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ Γ' A : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} : SCE.Value v1 → elabExp SCE.Typ.top v1 Γ' c1 → Ready v1 c1 Γ' e2 A r2 → Ready ρs ρc Γ (v1.box e2) A (c1.box r2)
- mrg1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} : ¬SCE.Value e1 → Ready ρs ρc Γ e1 A r1 → elabExp (Γ.and A) e2 B c2 → Ready ρs ρc Γ (e1.mrg e2) (A.and B) (r1.mrg c2)
- mrg2 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {A B : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} : SCE.Value v1 → elabExp Γ v1 A c1 → Ready (ρs.mrg v1) (ρc.mrg c1) (SCE.Typ.and Γ A) e2 B r2 → Ready ρs ρc Γ (v1.mrg e2) (A.and B) (c1.mrg r2)
- nmrg1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} : ¬SCE.Value e1 → Ready ρs ρc Γ e1 A r1 → elabExp Γ e2 B c2 → Ready ρs ρc Γ (e1.nmrg e2) (A.and B) ((ρc.mrg ((ρc.box r1).mrg ((Core.Exp.query.proj 1).box c2))).proj 0)
- nmrg2 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {A B : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} : SCE.Value v1 → elabExp Γ v1 A c1 → Ready ρs ρc Γ e2 B r2 → Ready ρs ρc Γ (v1.nmrg e2) (A.and B) ((ρc.mrg (c1.mrg (ρc.box r2))).proj 0)
- lrec {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} {l : String} : Ready ρs ρc Γ e A r → Ready ρs ρc Γ (SCE.Exp.lrec l e) (SCE.Typ.rcd l A) (Core.Exp.lrec l r)
- rproj {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} {l : String} : Ready ρs ρc Γ e B r → SCE.SRLookup B l A → Ready ρs ρc Γ (e.rproj l) A (r.rproj l)
- letb {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} : Ready ρs ρc Γ e1 A r1 → elabExp (Γ.and A) e2 B c2 → Ready ρs ρc Γ (e1.letb e2) B ((r1.mrg c2).proj 0)
- letres {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {A B : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} : SCE.Value v1 → elabExp Γ v1 A c1 → Ready (ρs.mrg v1) (ρc.mrg c1) (SCE.Typ.and Γ A) e2 B r2 → Ready ρs ρc Γ ((ρs.mrg v1).box e2) B ((c1.mrg r2).proj 0)
- openm {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} {l : String} : Ready ρs ρc Γ e1 (SCE.Typ.rcd l A) r1 → elabExp (Γ.and A) e2 B c2 → Ready ρs ρc Γ (e1.openm e2) B ((ρc.clos (elabTyp A) c2).app (r1.rproj l))
- mstruct {ρs : SCE.Exp} {ρc : Core.Exp} {Γ B : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} : Ready ρs ρc Γ e B r → Ready ρs ρc Γ e.mstruct B.sig r
- mlink1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ Γ₁ A B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} {l : String} : ¬SCE.Value e1 → Ready ρs ρc Γ e1 Γ₁ r1 → elabExp Γ e2 ((SCE.Typ.rcd l A).marr B) c2 → SCE.SRLookup Γ₁ l A → Ready ρs ρc Γ (e1.mlink e2) (Γ₁.and B) (((ρc.clos (elabTyp Γ₁) (Core.Exp.lam ((elabTyp (SCE.Typ.rcd l A)).arr (elabTyp B)) (linkInner (elabTyp (SCE.Typ.rcd l A))))).app r1).app c2)
- mlink2 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {Γ₁ A B : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} {l : String} : SCE.Value v1 → elabExp Γ v1 Γ₁ c1 → Ready ρs ρc Γ e2 ((SCE.Typ.rcd l A).marr B) r2 → SCE.SRLookup Γ₁ l A → Ready ρs ρc Γ (v1.mlink e2) (Γ₁.and B) (((ρc.mrg c1).clos ((elabTyp (SCE.Typ.rcd l A)).arr (elabTyp B)) (linkInner (elabTyp (SCE.Typ.rcd l A)))).app r2)
- mlinkn1 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ Γ₁ D B : SCE.Typ} {e1 e2 : SCE.Exp} {r1 c2 : Core.Exp} : ¬SCE.Value e1 → Ready ρs ρc Γ e1 Γ₁ r1 → elabExp Γ e2 (D.marr B) c2 → SCE.LinkOk Γ₁ D → Ready ρ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)
- mlinkn2 {ρs : SCE.Exp} {ρc : Core.Exp} {Γ : TyCtx} {Γ₁ D B : SCE.Typ} {v1 e2 : SCE.Exp} {c1 r2 : Core.Exp} : SCE.Value v1 → elabExp Γ v1 Γ₁ c1 → Ready ρs ρc Γ e2 (D.marr B) r2 → SCE.LinkOk Γ₁ D → Ready ρs ρc Γ (v1.mlinkn e2) (Γ₁.and B) (((ρc.mrg c1).clos ((elabTyp D).arr (elabTyp B)) (linkInner (elabTyp D))).app r2)
- linkres
{ρs : SCE.Exp}
{ρc : Core.Exp}
{Γ : TyCtx}
{Γ₁ B : SCE.Typ}
{v1 Y : SCE.Exp}
{c1 ρ' rY : Core.Exp}
: SCE.Value v1 →
elabExp Γ v1 Γ₁ c1 →
Core.Value ρ' →
¬SCE.Value Y →
Ready (ρs.mrg v1) (ρc.mrg c1) (SCE.Typ.and Γ Γ₁) Y B rY →
EnvFree rY → Ready ρs ρc Γ (v1.mrg Y) (Γ₁.and B) (ρ'.box (c1.mrg rY))
the linker's result while the functor body runs: the Core term still sits under the
boxof the linker's inner closure body. - inl {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} : Ready ρs ρc Γ e A r → Ready ρs ρc Γ (SCE.Exp.inl B e) (A.or B) (Core.Exp.inl (elabTyp B) r)
- inr {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} : Ready ρs ρc Γ e B r → Ready ρs ρc Γ (SCE.Exp.inr A e) (A.or B) (Core.Exp.inr (elabTyp A) r)
- case {ρs : SCE.Exp} {ρc : Core.Exp} {Γ A B C : SCE.Typ} {e e1 e2 : SCE.Exp} {r c1 c2 : Core.Exp} : Ready ρs ρc Γ e (A.or B) r → elabExp (Γ.and A) e1 C c1 → elabExp (Γ.and B) e2 C c2 → Ready ρs ρc Γ (e.case e1 e2) C (r.case c1 c2)
- fold {ρs : SCE.Exp} {ρc : Core.Exp} {Γ T : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} : Ready ρs ρc Γ e (SCE.substTyp 0 T.mu T) r → Ready ρs ρc Γ (SCE.Exp.fold T e) T.mu (Core.Exp.fold (elabTyp T) r)
- unfold {ρs : SCE.Exp} {ρc : Core.Exp} {Γ T A : SCE.Typ} {e : SCE.Exp} {r : Core.Exp} : Ready ρs ρc Γ e T.mu r → A = SCE.substTyp 0 T.mu T → Ready ρs ρc Γ e.unfold A r.unfold
Instances For
Administrative prefixes, shared by initialisation and simulation #
The linker step's administrative prefix once the provider is a value.
Environment extension used by every rule that evaluates under ρ , v.
The simulation step #
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
Lift a simulation step through an evaluation context of the Core term.
Forward simulation #
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.