Shared: typing and soundness
When a give copies
The type of a place tells us whether giving it moves or copies.
Consider a box whose field has type Token:
struct Token {}
struct Box { item: Token }
let b = new Box(new Token());
let s = b→share;
let u = s.item→;
let v = s.item→;
| Statement | Result type | Effect on the source |
|---|---|---|
Construct b | Box | — |
Give-share b | shared Box | b becomes empty. |
Give s.item into u | shared Token | The field stays initialized. |
Give s.item into v | shared Token | The field stays initialized. |
The field is declared Token, but access through s makes its effective type
shared Token. The first field give changes its stored reference to shared and
returns a shared copy; the second copies it again. Neither changes s’s type.
This chapter adds two permissions, given and shared, to
Given’s types and views.
Token is shorthand for given Token. It also carries
Given’s unpacking patterns into Shared, with
unpacking restricted to unique results.
example : SequenceTyped classes [] copyProgram copyFinal ∧
Unpacking.StepsExactly classes.erase ⟨State.empty, copyProgram⟩ 4 ⟨boxCopiedTwice, []⟩ ∧
Eval classes.erase boxShared (.give (field "s" "item"))
⟨boxCopied.objects, boxShared.variables, 2⟩ (.shared 0) ∧
Eval classes.erase boxCopied (.give (field "s" "item")) boxCopied (.shared 0) ∧
copyFinal.lookup "b" = some none ∧
copyFinal.lookup "s" = some (some box.shared) ∧
copyFinal.lookup "u" = some (some token.shared) ∧
copyFinal.lookup "v" = some (some token.shared) ∧
(1, ⟨"Box", [("item", some (.owned 0))]⟩) ∈ boxShared.objects ∧
(1, ⟨"Box", [("item", some (.shared 0))]⟩) ∈ boxCopied.objects ∧
("s", some (.shared 1)) ∈ boxCopiedTwice.variables ∧
("u", some (.shared 0)) ∈ boxCopiedTwice.variables ∧
("v", some (.shared 0)) ∈ boxCopiedTwice.variables := by
exact ⟨copy_typed, copy_execution, first_copy, second_copy, by decide, by decide, by decide, by decide,
by decide, by decide, by decide, by decide, by decide⟩
Permissions and field declarations
A permission \(\pi\) describes unique or shared access. A nominal type \(N\) pairs a class name \(C\) with a signed view \(A\). A type \(T\) may apply a permission to another type:
Bare \(C\) still abbreviates \(C.\{\epsilon\}\). Positive view entries expose initialized subtrees; negative entries describe empty slots; omitted branches are unknown and inaccessible. Views do not assign ownership modes to objects.
inductive Perm where
| given
| shared
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
abbrev Nominal := Unique.Typing.ViewType
inductive RawType where
| nominal (view : Nominal)
| apply (permission : Perm) (inner : RawType)
deriving DecidableEq, Repr
def ValueType.whole (name : ClassName) (permission : Perm := .given) : ValueType :=
⟨permission, .whole name⟩
Permission composition \(\pi\pi'\) combines an outer permission with an
inner one. The result is given only when both are given:
| Outer permission | Inner given | Inner shared |
|---|---|---|
given | given | shared |
shared | shared | shared |
def Perm.comp : Perm → Perm → Perm
| .given, .given => .given
| _, _ => .shared
Type normalization combines nested permissions and normalizes the nominal view. Its normalized form has exactly one outer permission:
Combine permissions using composition and these equations:
Normalize the nominal view using
Given’s view normalization.
For a class or ordinary struct, a bare nominal type supplies the outer
permission given; we omit that permission when printing. For a shared struct,
the nominal declaration supplies shared instead; applying given does not
remove that intrinsic sharing. Thus shared shared Token normalizes to
shared Token.
structure ValueType where
permission : Perm
nominal : Nominal
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
def RawType.normalize (classes : ClassTable) : RawType → ValueType
| .nominal view =>
⟨initialPermission ((classes.lookup view.className).map TypedClass.kind |>.getD .classType),
Unique.Typing.normalize classes.nominal view⟩
| .apply permission inner =>
let result := inner.normalize classes
{ result with permission := permission.comp result.permission }
def normalize (classes : ClassTable) (ty : ValueType) : ValueType :=
{ ty with nominal := Unique.Typing.normalize classes.nominal ty.nominal }
def Normalized (classes : ClassTable) (ty : ValueType) : Prop :=
Unique.Typing.Normalized classes.nominal ty.nominal
def initialPermission : Kind → Perm
| .sharedStruct => .shared
| _ => .given
The permission of a type \(\operatorname{perm}(T)\) is its outer permission in normalized form:
A bare class or ordinary struct type has permission given. A bare shared
struct type has permission shared, as specified by normalization.
def ValueType.perm (ty : ValueType) : Perm := ty.permission
The base class \(\operatorname{base}(T)\) is the class named by a type, independent of its permission and view. For a normalized type:
def ValueType.base (ty : ValueType) : ClassName := ty.nominal.className
A typed nominal table \(\Sigma\) records each declaration kind and gives each field a permission and a nominal type. Constructor arguments must supply whole values of the declared types:
Here \(F\) also denotes the set of field types generated by its grammar. The declaration
kind belongs to the set Kind generated by the grammar for k. Below,
Σ(C) = [f₁:F₁, …, fₙ:Fₙ] abbreviates lookup of just the ordered fields;
kindΣ(C) selects the declaration kind. Field permissions are normalized,
including the intrinsic sharing of shared struct types. The table records
normalized field types, so path permission composition uses those permissions.
structure FieldType where
permission : Perm
className : ClassName
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
def FieldType.toType (field : FieldType) : ValueType :=
.whole field.className field.permission
structure TypedClass where
fields : List (FieldName × FieldType)
kind : Kind := .structType
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
abbrev ClassTable := List (ClassName × TypedClass)
A typed class table \(\Sigma\) is well formed when class names are distinct, field names within each class are distinct, and every class named by a field type is declared in \(\Sigma\).
For every struct or shared struct declaration, each field type F must
satisfy struct(F). A class declaration has no such restriction. A field with
shared permission must have a struct type even when its container is a class.
These checks inspect nominal declarations, not field accessibility in a view.
def ClassTable.WellFormed (classes : ClassTable) : Prop :=
(classes.map Prod.fst).Nodup ∧
∀ entry ∈ classes, (entry.2.fields.map Prod.fst).Nodup ∧
∀ field ∈ entry.2.fields, field.2.className ∈ classes.map Prod.fst ∧
KindValid classes field.2.toType ∧
(entry.2.kind.isStruct = true → StructType classes field.2.toType)
Class-table erasure \(\lfloor\Sigma\rfloor\) supplies the operational class table by removing field types. It retains every nominal name, declaration kind, and field order:
def ClassTable.erase (classes : ClassTable) : Classes :=
classes.map fun (name, declaration) => (name, ⟨declaration.fields.map Prod.fst, declaration.kind⟩)
The nominal class table \(\Sigma_{\mathrm{nom}}\) supplies Given’s typed class table by removing declaration kinds and each field’s permission, retaining the nominal names and field order:
Use this table for Given’s relative paths and views, view normalization, nominal focusing, and emptying.
def ClassTable.nominal (classes : ClassTable) : Unique.Typing.ClassTable :=
classes.map fun (name, declaration) =>
(name, ⟨declaration.fields.map fun (field, ty) => (field, ty.className)⟩)
A type is well formed when its base class is
declared and its view satisfies
Given’s view conditions under
the nominal class table: paths are valid,
distinct, and pairwise prefix-incomparable. In addition, a shared permission
requires struct(T). A shared struct has shared permission after normalization;
there is no normalized given type for its instances.
def ValueType.WellFormed (ty : ValueType) (classes : ClassTable) : Prop :=
ty.nominal.WellFormed classes.nominal ∧ KindValid classes ty
def KindValid (classes : ClassTable) (ty : ValueType) : Prop :=
(classes.lookup ty.base).any (fun declaration => kindAllows declaration.kind ty.permission) = true
def kindAllows (kind : Kind) (permission : Perm) : Bool :=
match kind with
| .classType => permission == .given
| .structType => true
| .sharedStruct => permission == .shared
The known-initialized paths \(\operatorname{pos}_{\Sigma}(T)\) and known-empty paths \(\operatorname{neg}_{\Sigma}(T)\) depend on a type’s nominal view, not its permission. For normalized \(T=\pi N\), use Given’s observations under the nominal class table:
A positive entry exposes a whole declared subtree, including shared fields. A negative entry describes an empty slot; an omitted branch remains unknown and inaccessible.
def Pos (classes : ClassTable) (ty : ValueType) (path : Path) : Prop :=
Unique.Typing.Pos classes.nominal ty.nominal path
def Neg (ty : ValueType) (path : Path) : Prop :=
Unique.Typing.Neg ty.nominal path
Following a path
A shared link may occur anywhere along a path:
struct Token {}
struct Box { item: Token }
class Outer { box: shared Box }
struct Holder { item: shared Token }
Consider initialized variables b: Box, s: shared Box, o: Outer, and
h: Holder:
| Place | Effective type | Giving it |
|---|---|---|
b.item | Token | Moves the token. |
s.item | shared Token | Copies a shared reference. |
o.box.item | shared Token | Copies a shared reference. |
h.item | shared Token | Copies a shared reference. |
In the third row, o is unique but its box field is shared. In the fourth,
the final field itself is declared shared. A unique container can therefore
contain a field that is copied when given.
example :
focus classes box ["item"] = some token ∧
focus classes box.shared ["item"] = some token.shared ∧
focus classes (.whole "Outer") ["box", "item"] = some token.shared ∧
focus classes holder ["item"] = some token.shared ∧
give classes [("b", some box)] (field "b" "item") =
some (token, [("b", some ⟨.given, ⟨"Box", [.negative ["item"]]⟩⟩)]) ∧
give classes [("s", some box.shared)] (field "s" "item") =
some (token.shared, [("s", some box.shared)]) ∧
give classes [("o", some (.whole "Outer"))] (place :=
.field (field "o" "box") "item") =
some (token.shared, [("o", some (.whole "Outer"))]) ∧
give classes [("h", some holder)] (field "h" "item") =
some (token.shared, [("h", some holder)]) := by
exact ⟨by decide, by decide, by decide, by decide,
by decide, by decide, by decide, by decide⟩
The declared permission \(\operatorname{decl}_{\Sigma}(C,\rho)\) combines the field permissions along a relative path \(\rho\) from class \(C\), using permission composition:
It is defined exactly on paths valid from \(C\) under the nominal class table.
def declaredPermission (classes : ClassTable) (name : ClassName) : Path → Option Perm
| [] => some .given
| field :: rest => do
let declaration ← classes.lookup name
let target ← declaration.fields.lookup field
let permission ← declaredPermission classes target.className rest
return target.permission.comp permission
Focusing \(T\downarrow\rho\) finds the type reached by a path, carrying the enclosing permission into each field. Access to a field declared \(F\) through a whole value of type \(\pi\,C\) has type \(\pi F\).
Using permission composition, extend Given’s focusing operation (\(\href{given-typing.html#claim-given.typing.focus}{N\downarrow\rho}\)) to a type \(T=\pi N\), where the nominal type is \(N=C.A\):
The nominal focus uses the nominal class table and preserves the field’s current view, including holes. The new operation \(T\downarrow\rho\) adds the effective permission and normalizes the result. It does not restore moved or hidden fields.
def focus (classes : ClassTable) (ty : ValueType) (path : Path) : Option ValueType := do
let nominal ← Unique.Typing.focus classes.nominal ty.nominal path
let permission ← declaredPermission classes ty.base path
return ⟨ty.permission.comp permission, nominal⟩
Emptying \(T[-\rho]\) marks a field path as empty while retaining the outer permission and every other branch’s information. For normalized \(T=\pi N\):
The right-hand side uses Given’s emptying operation under the nominal class table. Normalize the result.
def emptyPath (classes : ClassTable) (ty : ValueType) (path : Path) : Option ValueType :=
(Unique.Typing.emptyPath classes.nominal ty.nominal path).map fun remaining =>
⟨ty.permission, remaining⟩
The static give operation
A slot description \(B\) is either \(0\), for an empty variable, or a type. A typing environment \(\Gamma\) describes every variable slot:
Types must be well formed and normalized. Empty variables remain in the domain and cannot be reused as fresh names.
abbrev SlotDescription := Option ValueType
abbrev Environment := List (VariableId × SlotDescription)
def Environment.WellFormed (environment : Environment) (classes : ClassTable) : Prop :=
(environment.map Prod.fst).Nodup ∧
environment.all (fun entry => match entry.2 with
| none => true
| some ty => decide (Admissible classes ty)) = true
def Environment.lookup (environment : Environment) (name : VariableId) :
Option SlotDescription :=
(environment.find? fun entry => entry.1 == name).map Prod.snd
def Environment.replace (environment : Environment) (name : VariableId)
(description : SlotDescription) : Environment :=
environment.map fun entry => if entry.1 = name then (name, description) else entry
The static give operation computes the type produced by giving a place and the environment afterwards. Write \(\mathsf{give}_{\Sigma}(\Gamma,p)=(T,\Gamma')\): the result has type \(T\), and the variable slots have descriptions \(\Gamma'\).
Write a place as \(p=x.\rho\): for o.box.item, the root variable is o
and the relative path is box.item; for o, the relative path is
\(\epsilon\). The operation is defined exactly when \(\Gamma(x)=U\)
and \(\rho\in\href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(U)}\). Its outputs are:
The last case empties the field path. A given result requires every permission along its route to be given. A shared result leaves the entire environment unchanged. An absent variable, an empty source, or an inaccessible field makes this static give operation undefined. A field hidden by a view may still hold a value at runtime.
def splitPlace : Place → VariableId × Path
| .variable name => (name, [])
| .field base name =>
let (root, path) := splitPlace base
(root, path ++ [name])
def give (classes : ClassTable) (environment : Environment) (place : Place) :
Option (ValueType × Environment) := do
let (root, path) := splitPlace place
let source ← environment.lookup root
let source ← source
let result ← focus classes source path
if result.permission = .shared then
return (result, environment)
else if path = [] then
return (result, environment.replace root none)
else
let remaining ← emptyPath classes source path
return (result, environment.replace root (some remaining))
Weakening a view
As in Given, view weakening can hide initialization facts while preserving the permission. For normalized types \(T=\pi C.A\) and \(U=\pi'C'.A'\), define:
For example, shared Box can be weakened to shared Box.{}. There is no
weakening from Box to shared Box: creating a shared reference requires the
runtime give-share operation. Different aliases may expose different views
of the same object.
def Subtype (classes : ClassTable) (source target : ValueType) : Prop :=
source.permission = target.permission ∧
Unique.Typing.Subtype classes.nominal source.nominal target.nominal
Typing expressions
Expression typing \(\Sigma;\Gamma\vdash e:T\;\triangleright\;\Gamma'\)
records the result’s type and the variable descriptions after evaluation.
All type expressions in the rules use
type normalization.
Both Give and Give-share use the
static give operation
\(\href{#claim-shared.typing.giving}{\mathsf{give}_{\Sigma}(\Gamma,p)=(T,\Gamma')}\) defined above.
Give returns its result type. Give-share additionally requires struct(T)
and applies shared to that type:
Both rules make the same change to the source. Give-share preserves the result’s view: it changes permission, not initialization.
Construct checks arguments from left to right against the declared field
types. Define initΣ(C) to be shared for a shared struct declaration and
given for a class or ordinary struct. This permission describes the constructor
result; the arguments retain their own permissions:
The argument count must match the declaration. With no arguments, the environment is unchanged. Arguments still require their whole declared types. A result may expose a weaker view:
inductive ExprTyped (classes : ClassTable) : Environment → Value → ValueType → Environment → Prop where
| give {before after : Environment} {place : Place} {ty : ValueType} :
before.WellFormed classes →
Typing.give classes before place = some (ty, after) →
Admissible classes ty → after.WellFormed classes →
ExprTyped classes before (.give place) ty after
| giveShare {before after : Environment} {place : Place} {ty : ValueType} :
before.WellFormed classes →
Typing.give classes before place = some (ty, after) →
Admissible classes ty → after.WellFormed classes →
StructType classes ty →
ExprTyped classes before (.giveShare place) ty.shared after
| new {before after : Environment} {name : ClassName} {declaration : TypedClass}
{arguments : List Value} :
(name, declaration) ∈ classes →
ArgsTyped classes before arguments (declaration.fields.map Prod.snd) after →
Admissible classes (ValueType.whole name (initialPermission declaration.kind)) →
(declaration.kind.isStruct = true →
∀ field ∈ declaration.fields, StructType classes field.2.toType) →
ExprTyped classes before (.new name arguments)
(ValueType.whole name (initialPermission declaration.kind)) after
| weaken {before after : Environment} {value : Value} {ty other : ValueType} :
ExprTyped classes before value ty after →
Admissible classes other → Subtype classes ty other →
ExprTyped classes before value other after
inductive ArgsTyped (classes : ClassTable) : Environment → List Value → List FieldType → Environment → Prop where
| nil {environment : Environment} :
environment.WellFormed classes → ArgsTyped classes environment [] [] environment
| cons {before middle after : Environment} {value : Value} {values : List Value}
{field : FieldType} {fields : List FieldType} :
ExprTyped classes before value field.toType middle →
ArgsTyped classes middle values fields after →
ArgsTyped classes before (value :: values) (field :: fields) after
def StructType (classes : ClassTable) (ty : ValueType) : Prop :=
(classes.lookup ty.base).any (fun declaration => declaration.kind.isStruct) = true
def initialPermission : Kind → Perm
| .sharedStruct => .shared
| _ => .given
With Token, Box, and Holder declared above:
let t = new Token();
let h = new Holder(t→share);
let a = h.item→;
let b = h.item→;
The constructor rule requires a shared Token, so its argument explicitly shares
the token. Afterwards t is empty, h: Holder, and both a and b have
type shared Token. Giving h.item does not empty it.
Replacing the constructor argument with t→ is rejected: its type is Token,
not the declared shared Token. Conversely, new Box(a→) is rejected because
the shared result cannot supply the given Token required by Box.
example : SequenceTyped classes [] argumentProgram argumentFinal ∧
Unpacking.Steps classes.erase ⟨State.empty, argumentProgram⟩ ⟨Unpacking.argumentsFinished, []⟩ ∧
argumentFinal.lookup "t" = some none ∧
argumentFinal.lookup "h" = some (some holder) ∧
argumentFinal.lookup "a" = some (some token.shared) ∧
argumentFinal.lookup "b" = some (some token.shared) ∧
(∀ ty after, ¬ ExprTyped classes [("t", some token)]
(.new "Holder" [.give (.variable "t")]) ty after) ∧
(∀ ty after, ¬ ExprTyped classes argumentFinal
(.new "Box" [.give (.variable "a")]) ty after) := by
exact ⟨arguments_typed, Unpacking.arguments_execution, by decide, by decide, by decide, by decide,
fun _ _ => holder_requires_sharing, fun _ _ => box_rejects_shared⟩
Sharing also preserves a partially moved value:
struct Token {}
struct Pair { left: Token, right: Token }
let p = new Pair(new Token(), new Token());
let t = p.left→;
let s = p→share;
let a = s.right→;
let b = s.right→;
Moving left leaves p: Pair.{-left, right}. Give-share then empties p and
produces s: shared Pair.{-left, right}. The last two statements produce
shared tokens and preserve that view of s.
Giving s.left→ is rejected because left is empty.
Weakening s’s view could hide that fact, but
could not make the field accessible again.
example : SequenceTyped classes [] partialProgram partialFinal ∧
Unpacking.StepsExactly classes.erase ⟨State.empty, partialProgram⟩ 5 ⟨pairCopiedTwice, []⟩ ∧
partialFinal.lookup "s" = some (some partialPair.shared) ∧
partialFinal.lookup "a" = some (some token.shared) ∧
partialFinal.lookup "b" = some (some token.shared) ∧
(2, ⟨"Pair", [("left", none), ("right", some (.shared 1))]⟩) ∈ pairCopiedTwice.objects ∧
("p", none) ∈ pairCopiedTwice.variables ∧
("a", some (.shared 1)) ∈ pairCopiedTwice.variables ∧
("b", some (.shared 1)) ∈ pairCopiedTwice.variables ∧
(∀ ty after, ¬ ExprTyped classes partialFinal (.give (field "s" "left")) ty after) := by
exact ⟨partial_typed, partial_execution, by decide, by decide, by decide,
by decide, by decide, by decide, by decide,
fun _ _ => failed_give_not_typed (by decide)⟩
Binding results
An unpacking pattern consumes a uniquely owned container and transfers its field slots to fresh variables. This extends Shared’s statements with Given’s flat binding patterns \(b\):
Each declared field must appear exactly once; destination variables are distinct
and fresh in the variable table after expression evaluation. Field order in the
pattern is immaterial. f abbreviates f: f;
there are no _ or .. patterns here.
inductive Pattern where
| variable (name : VariableId)
| unpack (className : ClassName) (fields : List (FieldName × VariableId))
deriving DecidableEq, Repr
structure Statement where
pattern : Pattern
value : Value
deriving Repr
The program configuration keeps its heap and optional initial frame. Its frame now contains pattern-binding statements. A local-frame observation \(\langle S,P\rangle\) pairs the frame’s storage with its remaining statements for local evaluation. It is not a complete program lifetime.
structure Frame (Instruction : Type) where
variables : List (VariableId × Slot)
code : List Instruction
deriving Repr
structure Configuration (Instruction : Type) where
objects : List (ObjectId × Object)
nextId : Nat
frame : Option (Frame Instruction)
deriving Repr
structure Configuration where
state : State
code : List Statement
deriving Repr
A local-frame observation pairs storage with the remaining statement sequence.
An extended local operation runs one let statement with a
binding pattern.
Write \(\href{shared.html#claim-shared.evaluation}{\Delta\vdash\langle S,e\rangle\Downarrow\langle S',r\rangle}\) for Shared’s expression evaluation. It is unchanged. The extended step first evaluates the expression, then binds its result:
- A variable pattern stores the reference, of either mode, in its fresh slot.
- A
C → { ... }pattern requires \(r=(\mathsf{unique},\alpha)\) and an allocatedCobject at \(\alpha\). Transfer every field slot to its named destination and remove \(\alpha\) from the object table.
Field references retain their modes and targets; empty fields become empty
variables. All other storage and the allocation counter remain as in
\(S'\). The statement is removed from the remaining sequence. A shared
result has no unpacking transition: consuming its container would invalidate
other owners. The program machine applies patternOperation and collects after this local
operation; its frame-exit rule is unchanged.
structure Configuration where
state : State
code : List Statement
deriving Repr
inductive Transfer : List (FieldName × VariableId) → List (FieldName × Slot) → List (VariableId × Slot) → Prop where
| nil : Transfer [] [] []
| cons {field name slot pattern before after bindings} :
Transfer pattern (before ++ after) bindings →
Transfer ((field, name) :: pattern) (before ++ (field, slot) :: after)
((name, slot) :: bindings)
inductive Bind (classes : Classes) : State → Reference → Pattern → State → Prop where
| variable {state object name} :
name ∉ state.variables.map Prod.fst →
Bind classes state object (.variable name) (state.bind name object)
| unpack {before after variables nextId object className fields pattern bindings declaration} :
(className, declaration) ∈ classes →
fields.map Prod.fst = declaration.fields →
(pattern.map Prod.fst).Nodup →
(pattern.map Prod.snd).Nodup →
(∀ name ∈ pattern.map Prod.snd, name ∉ variables.map Prod.fst) →
Transfer pattern fields bindings →
Bind classes ⟨before ++ (object, ⟨className, fields⟩) :: after, variables, nextId⟩
(.owned object) (.unpack className pattern)
⟨before ++ after, bindings ++ variables, nextId⟩
inductive Step (classes : Classes) : Configuration → Configuration → Prop where
| letValue {before evaluated after pattern value object rest} :
Eval classes before value evaluated object →
Bind classes evaluated object pattern after →
Step classes ⟨before, ⟨pattern, value⟩ :: rest⟩ ⟨after, rest⟩
A finite execution \(\Delta\vdash K\longrightarrow_u^{*}K'\) consists of zero or more program steps, including collection and frame exit, all using the same class table \(\Delta\).
def Steps (operation : LocalStep Instruction) (before after : Configuration Instruction) : Prop :=
∃ count, StepsExactly operation before count after
inductive StepsExactly (operation : LocalStep Instruction) : Configuration Instruction → Nat → Configuration Instruction → Prop where
| refl (configuration) : StepsExactly operation configuration 0 configuration
| step {before middle after count} :
Step operation before middle → StepsExactly operation middle count after →
StepsExactly operation before (count + 1) after
A configuration is finished exactly when its initial frame has been popped, as in Shared completion. Exhausted statements alone do not finish the program.
def Configuration.finished (configuration : Configuration Instruction) : Prop :=
configuration.frame = none
A configuration is stuck if it is not finished and has no successor. An exhausted live frame can still take its exit step, so it is neither finished nor stuck.
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after
The field description \(\mathsf{field}_{\Sigma}(T,f)\) tells an unpacking pattern whether a direct field is empty or which type it transfers:
An unknown field has no description.
def fieldDescription (classes : ClassTable) (ty : ValueType) (name : FieldName) :
Option SlotDescription :=
if Unique.Typing.negative ty.nominal [name] then some none
else (focus classes ty [name]).map some
Binding typing \(\Sigma;\Gamma\vdash b:T\Rightarrow\Gamma'\) describes where a result goes in the environment. A fresh variable receives its type unchanged:
For unpacking, the container must be given and every direct field’s status must be known. Unpacking transfers its field descriptions:
The displayed fields are ordered as declared. A transferred field can be shared even though the container must be given. As in Given’s binding rules, a field’s interior may have a partial view; only its direct slot status must be known.
inductive FieldBindings (classes : ClassTable) (ty : ValueType) : List (FieldName × VariableId) → Environment → Prop where
| nil : FieldBindings classes ty [] []
| cons {field : FieldName} {destination : VariableId} {description : SlotDescription}
{fields : List (FieldName × VariableId)} {bindings : Environment} :
fieldDescription classes ty field = some description →
FieldBindings classes ty fields bindings →
FieldBindings classes ty ((field, destination) :: fields)
((destination, description) :: bindings)
inductive BindingTyped (classes : ClassTable) : Environment → Unpacking.Pattern → ValueType → Environment → Prop where
| variable {environment : Environment} {name : VariableId} {ty : ValueType} :
environment.WellFormed classes → Admissible classes ty →
name ∉ environment.map Prod.fst →
BindingTyped classes environment (.variable name) ty ((name, some ty) :: environment)
| unpack {before : Environment} {ty : ValueType} {name : ClassName}
{declaration : TypedClass} {fields : List (FieldName × VariableId)}
{bindings : Environment} :
before.WellFormed classes → Admissible classes ty →
ty.permission = .given → ty.nominal.className = name → (name, declaration) ∈ classes →
(fields.map Prod.fst).Perm (declaration.fields.map Prod.fst) →
(fields.map Prod.snd).Nodup →
(∀ destination ∈ fields.map Prod.snd, destination ∉ before.map Prod.fst) →
FieldBindings classes ty fields bindings →
(bindings ++ before).WellFormed classes →
BindingTyped classes before (.unpack name fields) ty (bindings ++ before)
Continuing the Holder example:
let Holder → { item } = h→;
let c = item→;
The unpacking rule empties h, consumes the holder, and binds
item: shared Token. The aliases a and b still own the token. The second
copies it again, leaving item initialized.
If s: shared Holder, the pattern let Holder → { item } = s→ is rejected.
The result is shared even if this happens to be the only reference to that
holder. A type grants the access its permission describes; it does not count
aliases to recover unique ownership.
example : SequenceTyped classes argumentFinal
[⟨.unpack "Holder" [("item", "item")], .give (.variable "h")⟩,
⟨.variable "c", .give (.variable "item")⟩] unpackFinal ∧
Unpacking.StepsExactly classes.erase
⟨State.empty, Unpacking.unpackingProgram⟩ 6 ⟨Unpacking.unpackingFinished, []⟩ ∧
unpackFinal.lookup "h" = some none ∧
unpackFinal.lookup "item" = some (some token.shared) ∧
unpackFinal.lookup "a" = some (some token.shared) ∧
unpackFinal.lookup "b" = some (some token.shared) ∧
unpackFinal.lookup "c" = some (some token.shared) ∧
¬ Allocated Unpacking.unpackingFinished 1 ∧
(∀ after, ¬ BindingTyped classes [("s", some holder.shared)]
(.unpack "Holder" [("item", "item")]) holder.shared after) := by
refine ⟨unpack_typed, Unpacking.unpacking_execution, by decide, by decide,
by decide, by decide, by decide, ?_, ?_⟩
· change (1 : ObjectId) ∉ [0]; decide
· intro after typed
cases typed with
| unpack _ _ given => cases given
Statement typing \(\Sigma;\Gamma\vdash t\Rightarrow\Gamma'\) threads the environment through expression typing and binding typing:
inductive StatementTyped (classes : ClassTable) : Environment → Unpacking.Statement → Environment → Prop where
| letValue {before middle after : Environment} {pattern : Unpacking.Pattern}
{value : Value} {ty : ValueType} :
ExprTyped classes before value ty middle →
BindingTyped classes middle pattern ty after →
StatementTyped classes before ⟨pattern, value⟩ after
Statement-sequence typing \(\Sigma;\Gamma\vdash P\Rightarrow\Gamma_f\) passes each statement’s resulting environment to the next. Here \(P\) is an ordered sequence of statements:
inductive SequenceTyped (classes : ClassTable) : Environment → List Unpacking.Statement → Environment → Prop where
| nil {environment : Environment} :
environment.WellFormed classes → SequenceTyped classes environment [] environment
| cons {before middle after : Environment} {statement : Unpacking.Statement}
{rest : List Unpacking.Statement} :
StatementTyped classes before statement middle →
SequenceTyped classes middle rest after →
SequenceTyped classes before (statement :: rest) after
A well-typed program has a well-formed typed class table \(\Sigma\) and a statement sequence \(P\) that typechecks from the empty environment:
The final environment describes locals before frame exit and need not be empty. Completion pops the initial frame and collects the heap.
def ProgramTyped (classes : ClassTable) (code : List Unpacking.Statement) : Prop :=
classes.WellFormed ∧ ∃ finalEnvironment, SequenceTyped classes [] code finalEnvironment
Relating types to storage
The runtime mode \(\operatorname{mode}(\pi)\) maps a type permission to the corresponding reference mode:
def Perm.toMode : Perm → Mode
| .given => .unique
| .shared => .shared
For \(r=(\kappa,\alpha)\), the reference-path read \(\mathsf{read}_S(r,\rho)\) follows a relative path \(\rho\) from \(\alpha\), accumulating reference modes starting with \(\kappa\), as in refshared.resolution. The empty path returns \(r\) if its object exists. A missing object or field encountered while following the path, or an empty intermediate slot, makes traversal undefined. The final slot may be empty; if occupied, its reference is returned without dereferencing the target.
def enter (permission : Mode) (reference : Reference) : Reference :=
⟨permission.join reference.mode, reference.object⟩
def readPath (state : State) (reference : Reference) : List FieldName → Option Slot
| [] => do
let _ ← state.objects.lookup reference.object
return some reference
| field :: rest => do
let data ← state.objects.lookup reference.object
let slot ← data.fields.lookup field
match rest with
| [] => return slot.map (enter reference.mode)
| _ :: _ => do
let target ← slot
readPath state (enter reference.mode target) rest
Reference realization \(\Sigma;S\models r:T\) says that a reference’s type describes access from that reference. It does not prescribe one view for the object independent of its aliases.
Using the reference-path read, the relation holds for a normalized type \(T=\pi C.A\), when:
- The root reference has mode \(\href{#claim-shared.typing.mode}{\operatorname{mode}(\pi)}\) and targets an allocated object of class \(C\).
- Every \(\rho\in\href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(T)}\) reaches an allocated object of its declared class. Every \(\rho\in\href{#claim-shared.typing.observations}{\operatorname{neg}_{\Sigma}(T)}\) reaches an existing empty slot.
- Every valid finite path read from \(C\) that reaches an occupied slot from this root, including paths hidden by the view, has effective mode \(\href{#claim-shared.typing.mode}{\operatorname{mode}}(\pi\href{#claim-shared.typing.declared_permission}{\operatorname{decl}_{\Sigma}(C,\rho)})\).
The third condition composes permissions along the whole route. A field declared given inside a shared container may store a unique reference before copying and a shared one afterwards. Both routes have effective shared mode.
structure Satisfies (classes : ClassTable) (state : State) (reference : Reference) (ty : ValueType) : Prop where
mode : reference.mode = ty.permission.toMode
root : ∃ data, (reference.object, data) ∈ state.objects ∧ data.className = ty.nominal.className
positive : ∀ path, Pos classes ty path →
∃ target data, readPath state reference path = some (some target) ∧
(target.object, data) ∈ state.objects ∧
Unique.Typing.classAt classes.nominal ty.nominal.className path = some data.className
negative : ∀ path, Neg ty path → readPath state reference path = some none
modes : ∀ path target permission,
declaredPermission classes ty.nominal.className path = some permission →
readPath state reference path = some (some target) →
target.mode = (ty.permission.comp permission).toMode
Storage realization \(\Sigma;\Gamma\models(S;R)\) relates all variables and pending results to their type descriptions.
Here \(S=\langle O,V,\nu\rangle\) is the storage, and \(R\) is an ordered list of pending values \((r:T)\): expression results not yet stored by a binding or constructor. The relation holds when:
- The structural clauses of refshared.well_formed hold, counting pending references alongside all stored owning occurrences. The additional declaration-kind invariants are not premises of this relation; the operational preservation result establishes them for executions from the empty initial state.
- Every occupied field targets an object of its declared class, including fields hidden by views.
- \(\operatorname{dom}(\Gamma)=\operatorname{dom}(V)\). A description \(\Gamma(x)=0\) means \(V(x)=\bot\); a description \(\Gamma(x)=T\) means \(V(x)=r\) with reference realization \(\href{#claim-shared.typing.reference_realization}{\Sigma;S\models r:T}\).
- Every pending pair \((r:T)\) satisfies \(\href{#claim-shared.typing.reference_realization}{\Sigma;S\models r:T}\).
The table \(\Sigma\) and all types must be well formed. Shared aliases may carry different views; each must describe the actual storage. Hidden references still contribute to ownership and liveness.
def FieldsMatchClasses (classes : ClassTable) (state : State) : Prop :=
∀ parent data field target, (parent, data) ∈ state.objects →
(field, some target) ∈ data.fields →
∃ declaration fieldType targetData,
(data.className, declaration) ∈ classes ∧
(field, fieldType) ∈ declaration.fields ∧
(target.object, targetData) ∈ state.objects ∧ targetData.className = fieldType.className
abbrev PendingValues := List (Reference × ValueType)
structure Realizes (classes : ClassTable) (environment : Environment) (state : State) (pending : PendingValues) : Prop where
classesWellFormed : classes.WellFormed
environmentWellFormed : environment.WellFormed classes
pendingTypes : ∀ reference ty, (reference, ty) ∈ pending → Admissible classes ty
ownership : WellFormedWith classes.erase state (pending.map Prod.fst)
fields : FieldsMatchClasses classes state
variableDomain : ∀ name,
name ∈ environment.map Prod.fst ↔ name ∈ state.variables.map Prod.fst
emptyVariables : ∀ name, (name, none) ∈ environment → (name, none) ∈ state.variables
initializedVariables : ∀ name ty, (name, some ty) ∈ environment →
∃ reference, (name, some reference) ∈ state.variables ∧ Satisfies classes state reference ty
pendingValues : ∀ reference ty, (reference, ty) ∈ pending →
Satisfies classes state reference ty
For any well-formed \(\Sigma\), if expression typing and storage realization give
then an evaluation exists:
Every such evaluation satisfies \(\href{#claim-shared.typing.realization}{\Sigma;\Gamma'\models(S';R\mathbin{+\!\!+}[(r:T)])}\), where \(+\!\!+\) appends lists. This includes arbitrary pending results of earlier constructor arguments. A copy preserves existing aliases’ views; a move preserves the types of the other owning roots.
theorem expression_soundness
(typed : ExprTyped classes before value ty after)
(realized : Realizes classes before state pending) :
(∃ result object, Eval classes.erase state value result object) ∧
(∀ result object, Eval classes.erase state value result object →
Realizes classes after result (pending ++ [(object, ty)])) := by
have sound := typed.sound state pending realized
refine ⟨sound.1, fun result object evaluated => ?_⟩
exact (sound.2 result object evaluated).perm (by simpa using (List.perm_middle (a := (object, ty)) (l₁ := pending) (l₂ := [])).symm)
A live frame is well typed with final environment \(\Gamma_f\) when its storage realizes an environment under which its remaining statements typecheck:
A configuration with no frame is well typed when its heap is empty. Its counter may be nonzero. The final environment describes the locals before exit; it does not assert that terminal storage still contains those bindings. For a live frame, realization requires a well-formed class table.
Write \(K\longrightarrow_u^k K'\) for exactly \(k\) program steps using unpacking-capable local operations. Finite executions existentially quantify \(k\); stuckness means an unfinished configuration with no successor. The frame-pop step is included in this count.
def ConfigurationTyped (classes : ClassTable) (configuration : Configuration Unpacking.Statement)
(finalEnvironment : Environment) : Prop :=
match configuration.frame with
| none => configuration.objects = []
| some frame => Typing.ConfigurationTyped classes ⟨configuration.state, frame.code⟩ finalEnvironment
inductive StepsExactly (operation : LocalStep Instruction) : Configuration Instruction → Nat → Configuration Instruction → Prop where
| refl (configuration) : StepsExactly operation configuration 0 configuration
| step {before middle after count} :
Step operation before middle → StepsExactly operation middle count after →
StepsExactly operation before (count + 1) after
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after
def ConfigurationTyped (classes : ClassTable) (configuration : Unpacking.Configuration)
(finalEnvironment : Environment) : Prop :=
∃ current, Realizes classes current configuration.state [] ∧
SequenceTyped classes current configuration.code finalEnvironment
Progress and preservation
A well-typed configuration has finished or can take a step:
theorem ConfigurationTyped.progress
(typed : ConfigurationTyped classes configuration finalEnvironment) :
configuration.finished ∨ ∃ after, Step (patternOperation classes.erase) configuration after := by
rcases configuration with ⟨objects, nextId, frame⟩
cases frame with
| none => exact .inl rfl
| some frame =>
rcases frame with ⟨variables, code⟩
have localTyped : Typing.ConfigurationTyped classes ⟨⟨objects, variables, nextId⟩, code⟩ finalEnvironment := typed
rcases localTyped.progress with finished | ⟨after, step⟩
· change code = [] at finished
subst code
exact .inr ⟨_, exit_step ⟨objects, variables, nextId⟩⟩
· exact .inr ⟨_, local_step (operation := patternOperation classes.erase)
(before := ⟨objects, variables, nextId⟩) (code := code) (after := after.state)
(rest := after.code) step (local_wellFormed (localTyped.preservation step))⟩
Every step from a well-typed configuration preserves its final typing:
The current environment changes when a source is moved or a result is bound. A shared give itself preserves the environment even when the final stored reference changes mode; binding its result then adds a fresh variable.
theorem ConfigurationTyped.preservation
(typed : ConfigurationTyped classes before finalEnvironment)
(step : Step (patternOperation classes.erase) before after) :
ConfigurationTyped classes after finalEnvironment := by
cases step with
| «local» operation =>
have next := Typing.ConfigurationTyped.preservation typed operation
rw [collect_running (local_wellFormed next)]
exact next
| exit =>
rw [collect_popped]
rfl
For a well-typed program, no finite execution reaches a stuck configuration. Every execution prefix remains well typed and can be completed.
If the original program has \(n\) statements, every such prefix extends to completion after exactly \(n+1\) steps in total: one per statement, followed by one frame-pop step. A live frame’s remaining work is its statement count plus one; a finished configuration has zero remaining work. Terminal storage has no locals and an empty heap; its allocation counter records the identifiers spent.
theorem program_safety (classesWf : classes.WellFormed)
(typed : SequenceTyped classes [] code finalEnvironment)
(execution : StepsExactly (patternOperation classes.erase) (.initial code) count configuration) :
¬ Stuck (patternOperation classes.erase) configuration ∧
ConfigurationTyped classes configuration finalEnvironment ∧
count + configuration.remaining = code.length + 1 ∧
∃ nextId,
StepsExactly (patternOperation classes.erase) configuration configuration.remaining (.terminal nextId) ∧
StepsExactly (patternOperation classes.erase) (.initial code) (code.length + 1) (.terminal nextId) := by
have current := (ConfigurationTyped.initial classesWf typed).trace execution
have length : count + configuration.remaining = code.length + 1 := by
exact (execution.remaining (fun _ _ _ _ step => step.code_length)).symm
obtain ⟨nextId, rest⟩ := current.finishes
refine ⟨?_, current, length, nextId, rest, length ▸ execution.trans rest⟩
intro stuck
rcases current.progress with finished | next
· exact stuck.1 finished
· exact stuck.2 next
Embed every Given declaration as a class, restrict field declarations and
types to given, and omit give-share
expressions. The typing rules then agree with
Given’s rules, including its
unpacking extension. Embedding every runtime
reference with mode unique preserves and reflects
statement transitions and
exhaustion of the local statement sequence in this fragment. These selected
results concern local-frame observations; program-level steps use the framed
correspondence below.
This extends the earlier correspondence, which covers only single-variable bindings, to local operations with unpacking.
theorem given_fragment (classes : Unique.Typing.ClassTable) :
(∀ before value ty after,
Unique.Typing.ExprTyped classes before value ty after ↔
Shared.Typing.ExprTyped (embedClasses classes) (embedEnvironment before)
(embedValue value) (embedType ty) (embedEnvironment after)) ∧
(∀ before pattern ty after,
Unique.Typing.BindingTyped classes before pattern ty after ↔
Shared.Typing.BindingTyped (embedClasses classes) (embedEnvironment before)
(Unpacking.embedPattern pattern) (embedType ty) (embedEnvironment after)) ∧
(∀ before statement after,
Unique.Typing.StatementTyped classes before statement after ↔
Shared.Typing.StatementTyped (embedClasses classes) (embedEnvironment before)
(Unpacking.embedStatement statement) (embedEnvironment after)) ∧
(∀ before statements after,
Unique.Typing.SequenceTyped classes before statements after ↔
Shared.Typing.SequenceTyped (embedClasses classes) (embedEnvironment before)
(statements.map Unpacking.embedStatement) (embedEnvironment after)) ∧
(∀ statements, Unique.Typing.ProgramTyped classes statements ↔
Shared.Typing.ProgramTyped (embedClasses classes) (statements.map Unpacking.embedStatement)) ∧
(∀ before after,
Shared.Unpacking.Step (embedClasses classes).erase (Unpacking.embedConfiguration before) after ↔
∃ successor, Unique.Unpacking.Step classes.erase before successor ∧
after = Unpacking.embedConfiguration successor) ∧
(∀ before after,
Shared.Unpacking.Steps (embedClasses classes).erase (Unpacking.embedConfiguration before) after ↔
∃ successor, Unique.Unpacking.Steps classes.erase before successor ∧
after = Unpacking.embedConfiguration successor) ∧
(∀ configuration, (Unpacking.embedConfiguration configuration).finished ↔ configuration.finished) ∧
(∀ configuration,
(∃ final, Shared.Unpacking.Steps (embedClasses classes).erase
(Unpacking.embedConfiguration configuration) final ∧ final.finished) ↔
(∃ final, Unique.Unpacking.Steps classes.erase configuration final ∧ final.finished)) := by
refine ⟨fun _ _ _ _ => expression_correspondence,
fun _ _ _ _ => binding_correspondence, fun _ _ _ => statement_correspondence,
fun _ _ _ => sequence_correspondence, program_correspondence classes, ?_, ?_,
Unpacking.finished_correspondence, ?_⟩
· intro before after
simpa using (Unpacking.step_correspondence (classes := classes.erase)
(before := before) (after := after))
· intro before after
simpa using (Unpacking.steps_correspondence (classes := classes.erase)
(before := before) (after := after))
· intro configuration
simpa using (Unpacking.completion_correspondence (classes := classes.erase) configuration)
From a well-typed live frame with \(n\) statements, there is an observation state \(S_f\) after exactly \(n\) program steps. Its frame has no statements left, and its locals still realize the final environment. One further step pops that frame, leaving no roots and an empty heap with counter \(S_f.\nu\). This separates inspection of the computed bindings from program completion.
theorem completion (typed : Typing.ConfigurationTyped classes before finalEnvironment) :
∃ observed,
StepsExactly (patternOperation classes.erase) (.running before.state before.code)
before.code.length (.running observed []) ∧
Realizes classes finalEnvironment observed [] ∧
StepsExactly (patternOperation classes.erase) (.running before.state before.code)
(before.code.length + 1) (.terminal observed.nextId) := by
obtain ⟨last, trace, finished, realized⟩ := typed.finishes
have lifted := lift_local_trace typed trace
change last.code = [] at finished
rw [finished] at lifted
exact ⟨last.state, lifted, realized, lifted.trans (.step (exit_step _) (.refl _))⟩
The program machines with unpacking also preserve and reflect every step of the all-given fragment. From an embedded Given configuration, every Shared successor is the embedding of a Given successor, and every Given successor has that Shared step. This includes eager collection and initial-frame exit, not just local statement operations.
theorem pattern_step_correspondence :
Shared.Framed.Step (Shared.Framed.patternOperation (embedClasses classes))
(embed Unpacking.embedStatement before) after ↔
∃ successor, Unique.Framed.Step (Unique.Framed.patternOperation classes) before successor ∧
after = embed Unpacking.embedStatement successor := by
constructor
· apply step_backward Unpacking.embedStatement
intro state code next rest step
obtain ⟨successor, original, same⟩ := Unpacking.step_backward (before := ⟨state, code⟩) (after := ⟨next, rest⟩) step
exact ⟨successor.state, successor.code, original, congrArg Shared.Unpacking.Configuration.state same,
by simpa [Unpacking.embedConfiguration] using congrArg Shared.Unpacking.Configuration.code same⟩
· rintro ⟨successor, step, rfl⟩
exact step_forward Unpacking.embedStatement (fun state code after rest step => Unpacking.step_forward
(before := ⟨state, code⟩) (after := ⟨after, rest⟩) step) step