Conversion-typed processes have no sum or replication to Peer of a passive send head has an equivalent receive head
TheoremConversion-typed processes have no sum or replication#✓fully proved
Typing excludes sum and repl by syntax, not by a caller fragment premise.
theorem HasType.finiteLinear {n : Nat} {Δ : Context} {p : Proc} (h : HasType n Δ p) :
FiniteLinear p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def FiniteLinear : Proc → Prop
| .nil => True
| .out _ _ p | .inp _ p | .nu p => FiniteLinear p
| .par p q => FiniteLinear p ∧ FiniteLinear q
| .repl _ | .sum _ _ => False
CSLibExt/Languages/SessionTypes/Endpoint/Fragment.lean:28
Uses 15 · Used by 5
TheoremParallel inversion for conversion typing#✓fully proved
Parallel inversion derives its actual disjoint map split.
theorem HasType.par_inv {n : Nat} {Δ : Context} {p q : Proc} (h : HasType n Δ (.par p q)) :
∃ Γ Θ, Δ = Γ ∪ Θ ∧ Finmap.Disjoint Γ Θ ∧ HasType n Γ p ∧ HasType n Θ q
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
Uses 14 · Used by 8
TheoremRestriction inversion for conversion typing#✓fully proved
The private pair comes from the actual restriction derivation.
theorem HasType.nu_inv {n : Nat} {Δ : Context} {p : Proc} (h : HasType n Δ (.nu p)) :
∃ c, HasType (n + 1) (Context.bind c Δ) p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def Context.bind (c : Capability) (Δ : Context) : Context :=
(lift 0 Δ).insert ⟨.var 0, .positive⟩ c |>
Finmap.insert ⟨.var 0, .negative⟩ c.dual
CSLibExt/Languages/SessionTypes/Endpoint/ContextTransport.lean:49
Uses 14 · Used by 7
TheoremNil inversion for conversion typing#✓fully proved
Nil exposes actual completed ownership and key scope.
theorem HasType.nil_inv {n : Nat} {Δ : Context} (h : HasType n Δ .nil) :
Δ.Completed ∧ (∀ e ∈ Δ, e.name.ClosedAt n)
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
Uses 14 · Used by 5
TheoremTyped nil admits a completed scoped capability#✓fully proved
Only a scoped actually completed capability can be added at nil.
theorem HasType.nil_insert {n : Nat} {Δ : Context} {e : Key} {c : Capability}
(h : HasType n Δ .nil) (hc : c.protocol.unfold = .done) (he : e.name.ClosedAt n) :
HasType n (Δ.insert e c) .nil
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
structure Key where
name : PiCalculus.Name
role : Role
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:30
structure Capability where
rank : Nat
protocol : Protocol
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:27
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
Uses 13 · Used by 2
TheoremWeakening conversion typing by a completed capability#✓fully proved
An unused completed endpoint may be added through every current typing constructor. Scope and freshness are explicit; active weakening is not admitted.
theorem HasType.weaken_completed {n : Nat} {Δ : Context} {p : Proc}
(h : HasType n Δ p) {z : Key} {u : Capability} (hz : z ∉ Δ)
(hu : u.protocol.unfold = .done) (hscope : z.name.ClosedAt n) :
HasType n (Δ.insert z u) p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
structure Key where
name : PiCalculus.Name
role : Role
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:30
structure Capability where
rank : Nat
protocol : Protocol
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:27
Uses 26 · Used by 2
TheoremWeakening conversion typing by a disjoint completed context#✓fully proved
A disjoint completed context can be reattached to any typed process, with the exact finite-map union required by parallel-nil congruence.
theorem HasType.weaken_completed_union {n : Nat} {Δ Θ : Context} {p : Proc}
(h : HasType n Δ p) (hd : Finmap.Disjoint Δ Θ) (hc : Θ.Completed)
(hs : ∀ e ∈ Θ, e.name.ClosedAt n) : HasType n (Δ ∪ Θ) p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
Uses 13 · Used by 1
TheoremRemoving a parallel nil preserves conversion typing#✓fully proved
Removing a parallel nil reattaches exactly its completed ownership; no active capability is silently dropped.
theorem HasType.par_nil_elim {n : Nat} {Δ : Context} {p : Proc}
(h : HasType n Δ (.par p .nil)) : HasType n Δ p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
Uses 12 · Used by 1
TheoremErasing a role with an absent name preserves typing#✓fully proved
A role can be erased when its physical name is absent from every subject, payload and binder-adjusted continuation position of the typed term.
theorem HasType.erase_nameAbsent {n : Nat} {Δ : Context} {p : Proc}
(h : HasType n Δ p) {z : Key} (hab : NameAbsent z.name p) :
HasType n (Δ.erase z) p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
structure Key where
name : PiCalculus.Name
role : Role
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:30
def NameAbsent (a : Name) : Proc → Prop
| .nil => True
| .out b c p => a ≠ b ∧ a ≠ c ∧ NameAbsent a p
| .inp b p => a ≠ b ∧ NameAbsent (liftName 0 a) p
| .par p q | .sum p q => NameAbsent a p ∧ NameAbsent a q
| .nu p => NameAbsent (liftName 0 a) p
| .repl p => NameAbsent a p
CSLibExt/Languages/SessionTypes/Endpoint/NameAbsence.lean:29
Uses 24 · Used by 2
TheoremOwned capabilities with absent names are completed#✓fully proved
An owned capability with no physical-name occurrence must already be completed. This is derived from typing, including endpoint payload positions.
theorem HasType.absent_lookup_completed {n : Nat} {Δ : Context} {p : Proc}
(h : HasType n Δ p) {z : Key} {t : Capability}
(hz : Δ.lookup z = some t) (hab : NameAbsent z.name p) :
t.protocol.unfold = .done
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
structure Key where
name : PiCalculus.Name
role : Role
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:30
structure Capability where
rank : Nat
protocol : Protocol
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:27
def NameAbsent (a : Name) : Proc → Prop
| .nil => True
| .out b c p => a ≠ b ∧ a ≠ c ∧ NameAbsent a p
| .inp b p => a ≠ b ∧ NameAbsent (liftName 0 a) p
| .par p q | .sum p q => NameAbsent a p ∧ NameAbsent a q
| .nu p => NameAbsent (liftName 0 a) p
| .repl p => NameAbsent a p
CSLibExt/Languages/SessionTypes/Endpoint/NameAbsence.lean:29
Uses 20 · Used by 2
TheoremRetyping along ownership-map equivalence#✓fully proved
GENERAL arbitrary-depth, arbitrary-context retyping, by all seven typing constructors. Target ownership, ranks and every unfolded branch are derived.
theorem HasType.retype {n : Nat} {Δ Ξ : Context} {p : Proc}
(h : HasType n Δ p) (he : ContextEquivalent Δ Ξ) : HasType n Ξ p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def ContextEquivalent (Δ Ξ : Context) : Prop :=
∀ e, Option.Rel Capability.Equivalent (Δ.lookup e) (Ξ.lookup e)
CSLibExt/Languages/SessionTypes/Endpoint/ContextEquivalence.lean:28
Uses 30 · Used by 2
TheoremOwnership-map equivalence preserves typing in both directions#✓fully proved
Equivalence transports typing in BOTH directions at the same process/depth.
theorem HasType.retype_iff {n : Nat} {Δ Ξ : Context} {p : Proc}
(he : ContextEquivalent Δ Ξ) : HasType n Δ p ↔ HasType n Ξ p
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
def ContextEquivalent (Δ Ξ : Context) : Prop :=
∀ e, Option.Rel Capability.Equivalent (Δ.lookup e) (Ξ.lookup e)
CSLibExt/Languages/SessionTypes/Endpoint/ContextEquivalence.lean:28
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
TheoremCollision-free renaming preserves conversion typing#✓fully proved
GENERAL name transport with collision freedom on actual owned keys and canonical ambient name scope; protocol codes, roles and ranks stay exact.
theorem HasType.rename {n m : Nat} {Δ : Context} {p : Proc} {f : Name → Name}
(h : HasType n Δ p) (hscope : ∀ a, a.ClosedAt n → (f a).ClosedAt m)
(hf : Set.InjOn (Key.mapName f) {e | e ∈ Δ}) :
HasType m (Context.rekey (Key.mapName f) Δ hf) (mapProc f p)
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive Name where
| const (n : ℕ) : Name
| var (i : ℕ) : Name
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:45
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def Key.mapName (f : PiCalculus.Name → PiCalculus.Name) (e : Key) : Key :=
⟨f e.name, e.role⟩
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:60
def Context.rekey (f : Key → Key) (Δ : Context)
(hf : Set.InjOn f {e | e ∈ Δ}) : Context where
entries := Δ.entries.map (fun x => ⟨f x.1, x.2⟩)
nodupKeys := by
apply Multiset.nodup_keys.mp
have h := Multiset.Nodup.map_on hf Δ.nodupKeys.nodup_keys
simpa [Multiset.keys, Multiset.map_map, Function.comp_def] using h
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:45
def mapProc (f : Name → Name) : Proc → Proc
| .nil => .nil
| .out a b p => .out (f a) (f b) (mapProc f p)
| .inp a p => .inp (f a) (mapProc (under f) p)
| .par p q => .par (mapProc f p) (mapProc f q)
| .nu p => .nu (mapProc (under f) p)
| .repl p => .repl (mapProc f p)
| .sum p q => .sum (mapProc f p) (mapProc f q)
CSLibExt/Languages/SessionTypes/Endpoint/Renaming.lean:39
Uses 33 · Used by 4
TheoremLifting past a binder preserves conversion typing#✓fully proved
Lift uses the canonical cutoff-aware name and process operations.
theorem HasType.lift {n : Nat} {Δ : Context} {p : Proc} (h : HasType n Δ p) (k : Nat) :
HasType (n + 1) (Context.lift k Δ) (liftProc k p)
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def Context.lift (k : Nat) (Δ : Context) : Context :=
rekey (Key.mapName (liftName k)) Δ
(fun _ _ _ _ h => Key.mapName_injective (liftName_injective k) h)
CSLibExt/Languages/SessionTypes/Endpoint/ContextTransport.lean:28
def liftProc (cutoff : ℕ) : Proc → Proc
| .nil => .nil
| .out a b p => .out (liftName cutoff a) (liftName cutoff b) (liftProc cutoff p)
| .inp a p => .inp (liftName cutoff a) (liftProc (cutoff + 1) p)
| .par p q => .par (liftProc cutoff p) (liftProc cutoff q)
| .nu p => .nu (liftProc (cutoff + 1) p)
| .repl p => .repl (liftProc cutoff p)
| .sum p q => .sum (liftProc cutoff p) (liftProc cutoff q)
CSLibExt/Languages/PiCalculus/Basic.lean:70
Uses 18 · Used by 2
TheoremSwapping adjacent binders preserves conversion typing#✓fully proved
Swap retains roles, protocols and ranks while permuting two ambient binders.
theorem HasType.swap {n k : Nat} {Δ : Context} {p : Proc} (h : HasType n Δ p) (hk : k + 1 < n) :
HasType n (Context.swap k Δ) (swapProc k p)
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def Context.swap (k : Nat) (Δ : Context) : Context :=
rekey (Key.mapName (swapNameAt k)) Δ
(fun _ _ _ _ h => Key.mapName_injective (swapNameAt_injective k) h)
CSLibExt/Languages/SessionTypes/Endpoint/SwapTyping.lean:25
def swapProc (cutoff : ℕ) : Proc → Proc
| .nil => .nil
| .out a b p => .out (swapNameAt cutoff a) (swapNameAt cutoff b) (swapProc cutoff p)
| .inp a p => .inp (swapNameAt cutoff a) (swapProc (cutoff + 1) p)
| .par p q => .par (swapProc cutoff p) (swapProc cutoff q)
| .nu p => .nu (swapProc (cutoff + 1) p)
| .repl p => .repl (swapProc cutoff p)
| .sum p q => .sum (swapProc cutoff p) (swapProc cutoff q)
CSLibExt/Languages/PiCalculus/Basic.lean:119
Uses 18 · Used by 1
TheoremEndpoint substitution preserves conversion typing#✓fully proved
GENERAL endpoint substitution: retain the ACTUAL transmitted capability's code and rank at the sent polarized key, allowing its opposite-role alias. Collision freedom is needed only for that exact key and canonical substitution.
theorem HasType.subst_endpoint {n : Nat} {Δ : Context} {b : Name} {r : Role}
{c v : Capability} {p : Proc}
(h : HasType (n + 1) ((Context.lift 0 Δ).insert ⟨.var 0, r⟩ c) p)
(he : v.Equivalent c) (hb : b.ClosedAt n) (hfresh : (⟨b, r⟩ : Key) ∉ Δ) :
HasType n (Δ.insert ⟨b, r⟩ v) (PiCalculus.subst p b)
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Name where
| const (n : ℕ) : Name
| var (i : ℕ) : Name
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:45
inductive Role where
| positive
| negative
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:24
structure Capability where
rank : Nat
protocol : Protocol
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:27
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def Context.lift (k : Nat) (Δ : Context) : Context :=
rekey (Key.mapName (liftName k)) Δ
(fun _ _ _ _ h => Key.mapName_injective (liftName_injective k) h)
CSLibExt/Languages/SessionTypes/Endpoint/ContextTransport.lean:28
structure Key where
name : PiCalculus.Name
role : Role
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:30
def subst (p : Proc) (n : Name) : Proc := substProc n 0 p
CSLibExt/Languages/PiCalculus/Basic.lean:108
Uses 25 · Used by 1
TheoremEndpoint substitution with freshness from a disjoint split#✓fully proved
GENERAL split-derived freshness: actual payload ownership and the receiver's already-owned carrier derive non-aliasing even after advancement.
theorem HasType.subst_endpoint_from_split {n : Nat} {Γ Θ : Context} {b : Name} {r : Role}
{c v old next : Capability} {e : Key} {p : Proc}
(hd : Finmap.Disjoint Γ Θ) (hv : Γ.lookup ⟨b, r⟩ = some v)
(hc : Θ.lookup e = some old)
(h : HasType (n + 1) ((Context.lift 0 (Θ.insert e next)).insert ⟨.var 0, r⟩ c) p)
(he : v.Equivalent c) (hb : b.ClosedAt n) :
HasType n ((Θ.insert e next).insert ⟨b, r⟩ v) (PiCalculus.subst p b)
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Name where
| const (n : ℕ) : Name
| var (i : ℕ) : Name
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:45
inductive Role where
| positive
| negative
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:24
structure Capability where
rank : Nat
protocol : Protocol
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:27
structure Key where
name : PiCalculus.Name
role : Role
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:30
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def Context.lift (k : Nat) (Δ : Context) : Context :=
rekey (Key.mapName (liftName k)) Δ
(fun _ _ _ _ h => Key.mapName_injective (liftName_injective k) h)
CSLibExt/Languages/SessionTypes/Endpoint/ContextTransport.lean:28
def subst (p : Proc) (n : Name) : Proc := substProc n 0 p
CSLibExt/Languages/PiCalculus/Basic.lean:108
Uses 14 · Used by 1
TheoremPassive name substitution preserves conversion typing#✓fully proved
GENERAL passive substitution transports all scoped positions but adds NO capability. The input context contains only lifted outer ownership.
theorem HasType.subst_passive {n : Nat} {Δ : Context} {p : Proc} {b : Name}
(h : HasType (n + 1) (Context.lift 0 Δ) p) (hb : b.ClosedAt n) :
HasType n Δ (PiCalculus.subst p b)
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
inductive Proc where
| nil : Proc
| out (a b : Name) (p : Proc) : Proc
| inp (a : Name) (p : Proc) : Proc
| par (p q : Proc) : Proc
| nu (p : Proc) : Proc
| repl (p : Proc) : Proc
| sum (p q : Proc) : Proc
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:52
inductive Name where
| const (n : ℕ) : Name
| var (i : ℕ) : Name
deriving DecidableEq, Repr
CSLibExt/Languages/PiCalculus/Basic.lean:45
inductive HasType : Nat → Context → Proc → Prop where
| nil {n : Nat} {Δ : Context} :
Δ.Completed → (∀ e ∈ Δ, e.name.ClosedAt n) → HasType n Δ .nil
| outName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{b : Name} {s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .sendName s →
e.name.ClosedAt n → b.ClosedAt n →
HasType n (Δ.insert e ⟨c.rank, s⟩) p → HasType n Δ (.out e.name b p)
| inpName {n : Nat} {Δ : Context} {e : Key} {c : Capability}
{s : Protocol} {p : Proc} :
Δ.lookup e = some c → c.protocol.unfold = .recvName s → e.name.ClosedAt n →
HasType (n + 1) (Context.lift 0 (Δ.insert e ⟨c.rank, s⟩)) p →
⋯
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:69
def Context.lift (k : Nat) (Δ : Context) : Context :=
rekey (Key.mapName (liftName k)) Δ
(fun _ _ _ _ h => Key.mapName_injective (liftName_injective k) h)
CSLibExt/Languages/SessionTypes/Endpoint/ContextTransport.lean:28
def subst (p : Proc) (n : Name) : Proc := substProc n 0 p
CSLibExt/Languages/PiCalculus/Basic.lean:108
Uses 19 · Used by 3
TheoremCommunicating subjects have semantically dual capabilities#✓fully proved
At a semantically compatible combined interface, actual disjoint same-name ownership derives opposite roles, literal cap-rank agreement and semantic duality, not raw capability equality.
theorem communicating_equivalent {Γ Θ : Context} {e f : Key} {c d : Capability}
(hd : Finmap.Disjoint Γ Θ) (hc : Γ.lookup e = some c) (hp : Θ.lookup f = some d)
(hn : e.name = f.name) (hco : Compatible (Γ ∪ Θ)) : d.Equivalent c.dual
abbrev Context := Finmap (fun _ : Key => Capability)
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:32
structure Key where
name : PiCalculus.Name
role : Role
deriving DecidableEq, Repr
CSLibExt/Languages/SessionTypes/Endpoint/Identity.lean:30
structure Capability where
rank : Nat
protocol : Protocol
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:27
def Compatible (Δ : Context) : Prop :=
∀ e c d, Δ.lookup e = some c → Δ.lookup e.opposite = some d → d.Equivalent c.dual
CSLibExt/Languages/SessionTypes/Endpoint/ConversionTyping.lean:57
Uses 10 · Used by 8
TheoremPeer of a passive send head has an equivalent receive head#✓fully proved
Semantic duality forces an actual receive-name head and equivalent tail, while keeping the receiver's literal continuation code.
theorem passive_peer_head {c d : Capability} {s : Protocol}
(he : d.Equivalent c.dual) (hh : c.protocol.unfold = .sendName s) :
∃ u, d.protocol.unfold = .recvName u ∧ u.TreeEquiv s.dual
structure Capability where
rank : Nat
protocol : Protocol
CSLibExt/Languages/SessionTypes/Endpoint/Context.lean:27
inductive Protocol where
| done
| sendName (next : Protocol)
| recvName (next : Protocol)
| sendEndpoint (role : Role) (rank : Nat) (payload next : Protocol)
| recvEndpoint (role : Role) (rank : Nat) (payload next : Protocol)
| regular (graph : Graph) (cursor : Fin graph.size) (reversed : Bool)
CSLibExt/Languages/SessionTypes/Endpoint/Protocol.lean:26
Uses 13 · Used by 4
Loading dependency explorer…
The dependency explorer needs JavaScript and its graph data.