Documentation

LeanSce.SCE.BehaviourLaws

Behaviour versions of the termination-only results #

Whole-program correctness, unit chains, interface abstraction and confinement were first stated for terminating runs. This file adds their divergence counterparts.

General helpers #

theorem sdiverges_iff_not_terminates {Γ 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) :

For a well-typed source term under a well-typed value environment, divergence is exactly non-termination.

theorem sdiverges_step_iff {ρ e e' : SCE.Exp} (hs : SStep ρ e e') (huniq : ∀ (e'' : SCE.Exp), SStep ρ e e'' → e'' = e') :

A step that is the only step available does not change divergence.

theorem sdiverges_frame {ρ ρ' : SCE.Exp} (W : SCE.Exp → SCE.Exp) (hfwd : ∀ (x x' : SCE.Exp), SStep ρ' x x' → SStep ρ (W x) (W x')) (hinv : ∀ (x y : SCE.Exp), SStep ρ (W x) y → (∃ (x' : SCE.Exp), y = W x' ∧ SStep ρ' x x') ∨ ∀ (z : SCE.Exp), ¬SStep ρ y z) {e : SCE.Exp} :
SDiverges ρ (W e) ↔ SDiverges ρ' e

Divergence through an evaluation frame W whose steps under ρ are exactly the steps of the hole under ρ', except for steps to a normal form.

theorem sdiverges_box_iff {ρ v e : SCE.Exp} (hρ : SCE.Value ρ) (hv : SCE.Value v) :
SDiverges ρ (v.box e) ↔ SDiverges v e

A box with a value environment ignores the ambient environment.

theorem sdiverges_mrg_right_iff {ρ p e : SCE.Exp} (hρ : SCE.Value ρ) (hp : SCE.Value p) :
SDiverges ρ (p.mrg e) ↔ SDiverges (ρ.mrg p) e

The right component of a merge with a value on the left runs under the extended environment.

theorem selpkg_unique {Γ₁ D : SCE.Typ} (hok : SCE.LinkOk Γ₁ D) {v : SCE.Exp} {vc : Core.Exp} (hval : SCE.Value v) (helab : elabExp SCE.Typ.top v Γ₁ vc) {pkg₁ pkg₂ : SCE.Exp} :
S_Sem.SelPkg v D pkg₁ → S_Sem.SelPkg v D pkg₂ → pkg₁ = pkg₂

Unique selection for a well-typed package (public copy of the private selpkg_deterministic of SCE.Semantics.Determinism).

1. Whole programs #

Whole-program correctness, behaviour. A closed program and its elaboration have the same behaviour: same results, and divergence iff divergence.

2. Unit chains #

theorem unit_chain_behaviour {n : Nat} {S : SCE.Exp} {I : SCE.Typ} {L : Core.Exp} (hchain : UnitChain n S I L) :

Unit chains, behaviour.

theorem unit_chain_n_behaviour {n : Nat} {S : SCE.Exp} {I : SCE.Typ} {L : Core.Exp} (hchain : UnitChainN n S I L) :

Multi-import unit chains, behaviour.

3. Interface abstraction #

theorem S_Sem.interface_abstraction_diverges {Γ A B P₁ P₂ : SCE.Typ} {l : String} {ρ e p₁ p₂ vl : SCE.Exp} {ec ρc pc₁ pc₂ : Core.Exp} (he : elabExp Γ e ((SCE.Typ.rcd l A).marr B) ec) (hρ : elabExp SCE.Typ.top ρ Γ ρc) (hρv : SCE.Value ρ) (hp₁v : SCE.Value p₁) (hp₂v : SCE.Value p₂) (hp₁ : elabExp SCE.Typ.top p₁ P₁ pc₁) (hp₂ : elabExp SCE.Typ.top p₂ P₂ pc₂) (hl₁ : SCE.SRLookup P₁ l A) (hl₂ : SCE.SRLookup P₂ l A) (hs₁ : Sel p₁ l vl) (hs₂ : Sel p₂ l vl) :
SDiverges ρ (p₁.mlink e) ↔ SDiverges ρ (p₂.mlink e)

Interface abstraction, divergence. Under the hypotheses of interface_abstraction, the client linked against either provider diverges iff it diverges against the other.

theorem S_Sem.interface_abstraction_behaviour {Γ A B P₁ P₂ : SCE.Typ} {l : String} {ρ e p₁ p₂ vl : SCE.Exp} {ec ρc pc₁ pc₂ : Core.Exp} (he : elabExp Γ e ((SCE.Typ.rcd l A).marr B) ec) (hρ : elabExp SCE.Typ.top ρ Γ ρc) (hρv : SCE.Value ρ) (hp₁v : SCE.Value p₁) (hp₂v : SCE.Value p₂) (hp₁ : elabExp SCE.Typ.top p₁ P₁ pc₁) (hp₂ : elabExp SCE.Typ.top p₂ P₂ pc₂) (hl₁ : SCE.SRLookup P₁ l A) (hl₂ : SCE.SRLookup P₂ l A) (hs₁ : Sel p₁ l vl) (hs₂ : Sel p₂ l vl) :
(∀ (w : SCE.Exp), BStep ρ (p₁.mlink e) (p₁.mrg w) ↔ BStep ρ (p₂.mlink e) (p₂.mrg w)) ∧ (SDiverges ρ (p₁.mlink e) ↔ SDiverges ρ (p₂.mlink e))

Interface abstraction, behaviour. The same exports on termination, and divergence iff divergence.

theorem S_Sem.interface_abstraction_n {Γ D B P₁ P₂ : SCE.Typ} {ρ e p₁ p₂ pkg w : SCE.Exp} {ec ρc pc₁ pc₂ : Core.Exp} (he : elabExp Γ e (D.marr B) ec) (hρ : elabExp SCE.Typ.top ρ Γ ρc) (hρv : SCE.Value ρ) (hp₁v : SCE.Value p₁) (hp₂v : SCE.Value p₂) (hp₁ : elabExp SCE.Typ.top p₁ P₁ pc₁) (hp₂ : elabExp SCE.Typ.top p₂ P₂ pc₂) (hok₁ : SCE.LinkOk P₁ D) (hok₂ : SCE.LinkOk P₂ D) (hs₁ : SelPkg p₁ D pkg) (hs₂ : SelPkg p₂ D pkg) :
BStep ρ (p₁.mlinkn e) (p₁.mrg w) ↔ BStep ρ (p₂.mlinkn e) (p₂.mrg w)

Interface abstraction (n-ary linkall). Two well-typed provider values that select the same package at the client's import interface D drive the client to the same exports.

theorem S_Sem.interface_abstraction_n_diverges {Γ D B P₁ P₂ : SCE.Typ} {ρ e p₁ p₂ pkg : SCE.Exp} {ec ρc pc₁ pc₂ : Core.Exp} (he : elabExp Γ e (D.marr B) ec) (hρ : elabExp SCE.Typ.top ρ Γ ρc) (hρv : SCE.Value ρ) (hp₁v : SCE.Value p₁) (hp₂v : SCE.Value p₂) (hp₁ : elabExp SCE.Typ.top p₁ P₁ pc₁) (hp₂ : elabExp SCE.Typ.top p₂ P₂ pc₂) (hok₁ : SCE.LinkOk P₁ D) (hok₂ : SCE.LinkOk P₂ D) (hs₁ : SelPkg p₁ D pkg) (hs₂ : SelPkg p₂ D pkg) :
SDiverges ρ (p₁.mlinkn e) ↔ SDiverges ρ (p₂.mlinkn e)

Interface abstraction (n-ary linkall), divergence.

theorem S_Sem.interface_abstraction_n_behaviour {Γ D B P₁ P₂ : SCE.Typ} {ρ e p₁ p₂ pkg : SCE.Exp} {ec ρc pc₁ pc₂ : Core.Exp} (he : elabExp Γ e (D.marr B) ec) (hρ : elabExp SCE.Typ.top ρ Γ ρc) (hρv : SCE.Value ρ) (hp₁v : SCE.Value p₁) (hp₂v : SCE.Value p₂) (hp₁ : elabExp SCE.Typ.top p₁ P₁ pc₁) (hp₂ : elabExp SCE.Typ.top p₂ P₂ pc₂) (hok₁ : SCE.LinkOk P₁ D) (hok₂ : SCE.LinkOk P₂ D) (hs₁ : SelPkg p₁ D pkg) (hs₂ : SelPkg p₂ D pkg) :
(∀ (w : SCE.Exp), BStep ρ (p₁.mlinkn e) (p₁.mrg w) ↔ BStep ρ (p₂.mlinkn e) (p₂.mrg w)) ∧ (SDiverges ρ (p₁.mlinkn e) ↔ SDiverges ρ (p₂.mlinkn e))

Interface abstraction (n-ary linkall), behaviour.

4. Confinement #

theorem sandboxed_functor_app_diverges_iff {A : SCE.Typ} {body varg ρ : SCE.Exp} (hρ : SCE.Value ρ) (hvarg : SCE.Value varg) :

A sandboxed functor applied to a value diverges exactly when its body diverges under ε ; varg, whatever the ambient value environment.

theorem sandboxed_functor_confinement_diverges {A : SCE.Typ} {body varg ρ₁ ρ₂ : SCE.Exp} (hρ₁ : SCE.Value ρ₁) (hρ₂ : SCE.Value ρ₂) (hvarg : SCE.Value varg) :

Sandboxed functor confinement, divergence. The application diverges under one ambient value environment iff it diverges under any other.