Documentation

LeanSce.SCE.SemanticsPreservation

Semantic preservation of elaboration: if a source term evaluates to a value, its elaboration evaluates in Core to the elaboration of that value. The lookup/selection lemmas relate source and Core value lookups; the *_eval lemmas evaluate the composition terms emitted by nmrg, link, linkall.

theorem sel_implies_label_in {v v' : SCE.Exp} {vc : Core.Exp} {A : SCE.Typ} {l : String} (hval : SCE.Value v) (helab : elabExp SCE.Typ.top v A vc) (hsel : S_Sem.Sel v l v') :
theorem lookup_preservation {v_e v' : SCE.Exp} {vc_e : Core.Exp} {A B : SCE.Typ} {i : Nat} (hval : SCE.Value v_e) (helab : elabExp SCE.Typ.top v_e A vc_e) (hlook : S_Sem.LookupV v_e i v') (htyp_look : SCE.SLookup A i B) :
theorem sel_preservation {v_e v' : SCE.Exp} {vc_e : Core.Exp} {A B : SCE.Typ} {l : String} (hval : SCE.Value v_e) (helab : elabExp SCE.Typ.top v_e A vc_e) (hlook : S_Sem.Sel v_e l v') (htyp_look : SCE.SRLookup A l B) :

Evaluation of the composition encodings #

Operational lemmas assembling EBig derivations for the generated terms. Note the premise shapes: each operand evaluation appears once, mirroring the terms themselves.

theorem nmrgCore_eval {ρc vc₁ vc₂ ce₁ ce₂ : Core.Exp} (hρ : Core.Value ρc) (hbig1 : EBig ρc ce₁ vc₁) (hbig2 : EBig ρc ce₂ vc₂) :
EBig ρc (nmrgCore ce₁ ce₂) (vc₁.mrg vc₂)

Non-dependent merge saves the ambient environment and restores it for each operand; the final projection discards the saved environment.

theorem selpkg_elab {Γ₁ D : SCE.Typ} (hok : SCE.LinkOk Γ₁ D) {v pkg : SCE.Exp} {vc : Core.Exp} :
S_Sem.SelPkg v D pkg → SCE.Value v → elabExp SCE.Typ.top v Γ₁ vc → ∃ (cpkg : Core.Exp), elabExp SCE.Typ.top pkg D cpkg
theorem wire_eval {Γ₁ D : SCE.Typ} (hok : SCE.LinkOk Γ₁ D) {v₁ pkg : SCE.Exp} {ρ' vc₁ : Core.Exp} {shift : Nat} :
S_Sem.SelPkg v₁ D pkg → SCE.Value v₁ → elabExp SCE.Typ.top v₁ Γ₁ vc₁ → Core.Value ρ' → Core.LookupV ρ' shift vc₁ → ∃ (cpkg : Core.Exp), EBig ρ' (wire shift (elabTyp D)) cpkg ∧ elabExp SCE.Typ.top pkg D cpkg

The linearized wire evaluates by projection alone. Generalized over the environment: wherever the provider value vc₁ is reachable at index shift, wire_shift ⟦D⟧ evaluates to a package that elaborates the source package. No premise about the provider term appears, because the wire never mentions it.

theorem linkStep_eval {ρc vc₁ vc₂ cpkg vc₃ : Core.Exp} {g1 D B DT : Core.Typ} {ce₁ ce₂ body : Core.Exp} (hρ : Core.Value ρc) (hbig1 : EBig ρc ce₁ vc₁) (hbig2 : EBig ρc ce₂ (vc₂.clos DT body)) (hbigw : EBig (((ρc.mrg vc₁).mrg (vc₂.clos DT body)).mrg vc₁) (wire 0 D) cpkg) (hbig3 : EBig (vc₂.mrg cpkg) body vc₃) :
EBig ρc (linkedCore g1 D B ce₁ ce₂) (vc₁.mrg vc₃)

The assembly lemma for the linearized composition: one evaluation of each operand, one wire evaluation under the spine-built environment ((ρ , v₁) , f) , v₁, one closure-body evaluation — exactly the derivation shape of the term. Shared by link and linkall.

theorem wire_eval_rcd {ρc vc₁ f vc_l : Core.Exp} {l : String} {A : Core.Typ} (hρ : Core.Value ρc) (hv1 : Core.Value vc₁) (hf : Core.Value f) (hsel : Core.RLookupV vc₁ l vc_l) :
EBig (((ρc.mrg vc₁).mrg f).mrg vc₁) (wire 0 (Core.Typ.rcd l A)) (Core.Exp.lrec l vc_l)

The single-import wire evaluated in the spine-built environment: the link instance of wire_eval, stated directly at the target.

theorem semantic_preservation {Γ A : SCE.Typ} {es : SCE.Exp} {ec : Core.Exp} {ρs vs : SCE.Exp} {ρc : Core.Exp} (helab : elabExp Γ es A ec) (heval : S_Sem.BStep ρs es vs) (henv : elabExp SCE.Typ.top ρs Γ ρc) (henv_val : SCE.Value ρs) :
∃ (vc : Core.Exp), EBig ρc ec vc ∧ elabExp SCE.Typ.top vs A vc
theorem whole_program_correctness {A : SCE.Typ} {es : SCE.Exp} {ec : Core.Exp} {vs : SCE.Exp} (helab : elabExp SCE.Typ.top es A ec) (heval : S_Sem.BStep SCE.Exp.unit es vs) :