Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Shared: operational semantics

Shared ownership lets several references own the same object. A reference \(r\) pairs a mode \(\kappa\) with an object identity \(\alpha\). The object itself has no ownership mode. Variables and object fields are slots; their contents \(s\) are empty or hold one reference:

\[ \begin{aligned} \kappa &::= \mathsf{unique}\mid\mathsf{shared} \\ r &::= (\kappa,\alpha) \\ s &::= \bot\mid r. \end{aligned} \]

Object identities are tagged natural numbers, written \(\mathsf{obj}(n)\), with \(\operatorname{index}(\mathsf{obj}(n))=n\).

Shared/Syntax:ObjectId
structure ObjectId where
  index : Nat
  deriving DecidableEq, Repr
Shared/State:Mode
inductive Mode where
  | unique
  | shared
  deriving DecidableEq, Repr
Shared/State:Reference
structure Reference where
  reference ::
  mode : Mode
  object : ObjectId
  deriving DecidableEq, Repr
Shared/State:Reference.owned
def Reference.owned (object : ObjectId) : Reference := ⟨.unique, object⟩
Shared/State:Reference.shared
def Reference.shared (object : ObjectId) : Reference := ⟨.shared, object⟩
Shared/State:Slot
abbrev Slot := Option Reference

A place expression \(p\) follows fields from a variable to select a slot. Giving it, p→, requires every slot and intermediate object on the route to exist, and every slot to hold a reference. It moves the reference when every reference along that route is unique. If any is shared, it returns a shared copy and keeps the source initialized:

Path accessStored modeResult modeSource slot afterwards
UniqueUniqueUniqueEmpty
SharedSharedSharedUnchanged
SharedUniqueSharedStored reference becomes shared

In every case, the result refers to the source reference’s object. When copying a unique reference through shared access, the stored reference becomes shared too. Only the reference in that final slot changes; every other reference and object identity stay unchanged.

Sharing a container leaves its field references’ modes alone. Those fields are already reached through a shared path, even if their own references are unique. Copying one of those references later makes the final stored reference shared as well.

Shared/Syntax:Place
inductive Place where
  | variable (name : VariableId)
  | field (base : Place) (name : FieldName)
  deriving DecidableEq, Repr
Shared/Step:Resolve
inductive Resolve (state : State) : Place → StoragePlace → ObjectId → Mode → Prop where
  | variable {name reference} :
      (name, some reference) ∈ state.variables →
      Resolve state (.variable name) (.variable name) reference.object reference.mode
  | field {base source parent permission data name reference} :
      Resolve state base source parent permission →
      (parent, data) ∈ state.objects →
      (name, some reference) ∈ data.fields →
      Resolve state (.field base name) (.field parent name) reference.object
        (permission.join reference.mode)
Shared/Step:Take
inductive Take : State → StoragePlace → ObjectId → State → Prop where
  | variable (objects : List (ObjectId × Object)) (nextId : Nat)
      (leading suffix : List (VariableId × Slot)) (name : VariableId) (object : ObjectId) :
      Take ⟨objects, leading ++ (name, some (.owned object)) :: suffix, nextId⟩
        (.variable name) object
        ⟨objects, leading ++ (name, none) :: suffix, nextId⟩
  | field (variables : List (VariableId × Slot)) (nextId : Nat)
      (before after : List (ObjectId × Object)) (parent : ObjectId) (className : ClassName)
      (leading suffix : List (FieldName × Slot)) (name : FieldName) (object : ObjectId) :
      Take ⟨before ++ (parent, ⟨className, leading ++ (name, some (.owned object)) :: suffix⟩) :: after,
          variables, nextId⟩
        (.field parent name) object
        ⟨before ++ (parent, ⟨className, leading ++ (name, none) :: suffix⟩) :: after,
          variables, nextId⟩
Shared/Step:Promote
inductive Promote : State → StoragePlace → ObjectId → State → Prop where
  | variable (objects : List (ObjectId × Object)) (nextId : Nat)
      (leading suffix : List (VariableId × Slot)) (name : VariableId) (object : ObjectId) :
      Promote ⟨objects, leading ++ (name, some (.owned object)) :: suffix, nextId⟩
        (.variable name) object
        ⟨objects, leading ++ (name, some (.shared object)) :: suffix, nextId⟩
  | field (variables : List (VariableId × Slot)) (nextId : Nat)
      (before after : List (ObjectId × Object)) (parent : ObjectId) (className : ClassName)
      (leading suffix : List (FieldName × Slot)) (name : FieldName) (object : ObjectId) :
      Promote ⟨before ++ (parent, ⟨className, leading ++ (name, some (.owned object)) :: suffix⟩) :: after,
          variables, nextId⟩
        (.field parent name) object
        ⟨before ++ (parent, ⟨className, leading ++ (name, some (.shared object)) :: suffix⟩) :: after,
          variables, nextId⟩
Shared/Step:Give
inductive Give : State → Place → Reference → State → Prop where
  | move {state cleared : State} {path : Place} {source : StoragePlace} {object : ObjectId} :
      Resolve state path source object .unique →
      Take state source object cleared →
      Give state path (.owned object) cleared
  | copy {state : State} {path : Place} {source : StoragePlace} {object : ObjectId} :
      Resolve state path source object .shared →
      Stored state source (some (.shared object)) →
      Give state path (.shared object) state
  | promote {state promoted : State} {path : Place} {source : StoragePlace} {object : ObjectId} :
      Resolve state path source object .shared →
      Promote state source object promoted →
      Give state path (.shared object) promoted

A nominal type has a name and an ordered list of fields. Its declaration chooses whether its values can be shared and whether construction makes them shared immediately:

DeclarationMay be sharedConstructor result
class C { ... }NoGiven C
struct C { ... }YesGiven C
shared struct C { ... }Yesshared C

These three forms describe nominal types; they do not introduce three different kinds of runtime object representation. Modes still belong to references.

Shared/Syntax:Kind
inductive Kind where
  | classType
  | structType
  | sharedStruct
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Shared/Syntax:Class
structure Class where
  fields : List FieldName
  kind : Kind := .structType
  deriving DecidableEq, Repr
Shared/State:Kind.mode
def Kind.mode : Kind → Mode
  | .sharedStruct => .shared
  | _ => .unique

The predicate struct(T) means that the nominal type underlying T is declared as either struct or shared struct. It does not depend on the reference’s current permission or on which fields its view exposes. It is false for a class.

Every field of a struct, including a shared struct, must itself have a struct type. This restriction applies to all declared fields, including ones hidden by a view or currently empty. Classes may contain either classes or structs. Thus sharing a container cannot expose a class through shared field access. A shared C type is permitted only when struct(C) holds.

This layer checks struct(T) directly from nominal declarations. Generic type parameters, user-written predicates, and predicate where-clauses are not part of this language. Destructors and assignment belong to later layers.

Shared/Syntax:Kind.isStruct
def Kind.isStruct : Kind → Bool
  | .classType => false
  | _ => true
Shared/TypingViews:StructType
def StructType (classes : ClassTable) (ty : ValueType) : Prop :=
  (classes.lookup ty.base).any (fun declaration => declaration.kind.isStruct) = true
Shared/TypingViews:ClassTable.WellFormed
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)
Shared/TypingViews:KindValid
def KindValid (classes : ClassTable) (ty : ValueType) : Prop :=
  (classes.lookup ty.base).any (fun declaration => kindAllows declaration.kind ty.permission) = true

These declarations distinguish the three forms without requiring primitive types:

struct Token {}
struct Box { value: Token }
shared struct SharedBox { value: Token }
class Resource { token: Token }
class Owner { resource: Resource, box: Box }

Box and SharedBox satisfy the struct-only field restriction. Owner may contain a Resource because Owner is a class. In contrast, both of the following declarations are rejected:

struct BadBox { resource: Resource }
shared struct BadSharedBox { resource: Resource }

An empty view of Resource would not make either declaration valid: hiding its fields does not make the nominal type a struct.

Shared/KindChecks:declarations
example : classes.WellFormed ∧
    StructType classes (.whole "Token") ∧ StructType classes (.whole "Box") ∧
    StructType classes (.whole "SharedBox" .shared) ∧
    ¬ StructType classes (.whole "Resource") ∧
    ¬ StructType classes ⟨.given, ⟨"Resource", []⟩⟩ ∧
    ¬ ClassTable.WellFormed (("BadBox", badBox) :: classes) ∧
    ¬ ClassTable.WellFormed (("BadSharedBox", badSharedBox) :: classes) := by
  decide

Places, values, and programs

A nominal declaration named \(C\), in \(\mathsf{ClassName}\), declares an ordered list of \(n\) fields, where \(n\) is a natural number including zero. A field name \(f\) belongs to \(\mathsf{FieldName}\). Constructor arguments supply the fields in order. Source fields have types checked by the type system. The operational declaration retains its kind and ordered field names; all values are objects.

Shared/Syntax:ClassName
abbrev ClassName := String
Shared/Syntax:FieldName
abbrev FieldName := String
Shared/Syntax:Class
structure Class where
  fields : List FieldName
  kind : Kind := .structType
  deriving DecidableEq, Repr

A variable name \(x\) belongs to \(\mathsf{VariableId}\). A place expression \(p\) starts at a variable and follows fields. A value expression \(e\) gives from a place, gives and shares the result, or constructs an object. A statement \(t\) binds an expression’s result:

\[ \begin{aligned} p &::= x\mid p.f \\ e &::= p\mathord{\to} \\ &\phantom{{}::={}}\mid p\mathord{\to}\mathsf{share} \\ &\phantom{{}::={}}\mid\mathsf{new}\ C(e_1,\ldots,e_n) \\ t &::= \mathsf{let}\ x=e \end{aligned} \]

The expression p→share performs the give, requires a struct result, then makes that result a shared owner. A class result cannot be shared. Giving along a unique route empties the source. To share a newly constructed object, first construct it in a variable, then give-share that variable.

Each let names a fresh runtime variable. Constructor arguments are value expressions, evaluated from left to right; they may themselves construct objects. There is no shadowing, scope, call, assignment, destruction, or borrowing in this fragment.

Shared/Syntax:VariableId
abbrev VariableId := String
Shared/Syntax:Place
inductive Place where
  | variable (name : VariableId)
  | field (base : Place) (name : FieldName)
  deriving DecidableEq, Repr
Shared/Syntax:Value
inductive Value where
  | give (source : Place)
  | giveShare (source : Place)
  | new (className : ClassName) (arguments : List Value)
  deriving Repr
Shared/Syntax:Statement
structure Statement where
  letValue ::
  destination : VariableId
  value : Value
  deriving Repr

A program \(\Pi=\langle\Delta,P\rangle\) has a class table \(\Delta\) and a finite ordered sequence \(P\) of statements:

\[ \begin{aligned} \Delta &\in \mathsf{ClassName}\rightharpoonup(\mathsf{Kind}\times\mathsf{List}(\mathsf{FieldName})),\\ P &::= []\mid t::P. \end{aligned} \]

The finite-map and list notation is unchanged. For a nominal declaration of kind \(k\) listing \(f_1,\ldots,f_n\), \(\Delta(C)=(k,[f_1,\ldots,f_n])\).

Shared/Syntax:Classes
abbrev Classes := List (ClassName × Class)
Shared/Syntax:Program
structure Program where
  classes : Classes
  body : List Statement
  deriving Repr

A class table is well formed when class names are distinct and each declaration lists distinct field names.

Shared/Soundness:ClassesWellFormed
def ClassesWellFormed (classes : Classes) : Prop :=
  (classes.map Prod.fst).Nodup ∧
    ∀ name declaration, (name, declaration) ∈ classes → declaration.fields.Nodup

Copying a field

Start with no objects or variables and execute:

struct Token {}
struct Box { value: Token }

let t = new Token();
let b = new Box(t→);
let s = b→share;
let u = s.value→;
let v = s.value→;

The first two statements construct a token and put its reference in a box, leaving t empty. The third moves the box’s reference out of b and makes it shared in s. The box’s field still holds a unique reference to the token.

The fourth statement reaches the token through shared variable s. It changes the reference in the box’s value field to shared and gives u a shared copy. The fifth copies the already-shared reference into v.

After these statements, before frame exit, there are still two objects. Variable s is a shared owner of the box. The box’s field, u, and v are three shared owners of the token. Variables t and b are empty. Both field gives succeed because neither empties the field.

Shared/Examples:sharing_execution
example : Steps exampleClasses ⟨State.empty, sharingCode⟩ ⟨twiceCopiedState, []⟩ := by
  exact .step (example_create_token _)
    (.step (example_create_box _) (.step (example_share_box _)
      (.step (example_copy_field _) (.step (example_copy_again _) (.refl _)))))

Objects and slots

An object \(o\) has a class name and named field slots, whose contents can be empty:

\[ o::=C\{f_1:s_1,\ldots,f_n:s_n\}. \]
Shared/State:Object
structure Object where
  className : ClassName
  fields : List (FieldName × Slot)
  deriving DecidableEq, Repr

A storage state \(S=\langle O,V,\nu\rangle\) consists of the object table, variable table, and allocation counter \(\nu\). Object identities are tagged numbers. Creation uses \(\mathsf{obj}(\nu)\), then increments the counter.

We use finite-map notation for tables with distinct keys:

\[ O\in\mathsf{ObjectId}\rightharpoonup\mathsf{Object},\qquad V\in\mathsf{VariableId}\rightharpoonup\mathsf{Slot},\qquad \nu\in\mathbb N. \]
Shared/State:State
structure State where
  objects : List (ObjectId × Object)
  variables : List (VariableId × Slot)
  nextId : Nat
  deriving DecidableEq, Repr

The empty storage state has no objects or variables, and counter zero:

\[S_{\emptyset}=\langle\varnothing,\varnothing,0\rangle.\]

Here \(\varnothing\) denotes the empty map.

Shared/State:State.empty
def State.empty : State := ⟨[], [], 0⟩

A storage place \(q\) selects one slot directly: a variable or a field of a particular object:

\[ q::=x\mid\alpha.f. \]

A place expression follows a route to a slot; a storage place identifies the slot itself.

Shared/State:StoragePlace
inductive StoragePlace where
  | variable (name : VariableId)
  | field (object : ObjectId) (name : FieldName)
  deriving DecidableEq, Repr

Slot lookup \(S[q]=s\) reads the contents at a storage place. For storage \(S=\langle O,V,\nu\rangle\):

\[ \begin{aligned} S[x]&=V(x)&&\text{when }V(x)\text{ is defined},\\ S[\alpha.f_i]&=s_i&&\text{when }O(\alpha)=C\{f_1:s_1,\ldots,f_n:s_n\},\ 1\le i\le n. \end{aligned} \]

An empty slot still exists; lookup at an absent variable, object, or field is undefined. A reference identifies an object in \(O\); the slot does not contain that object’s data.

Shared/State:Stored
def Stored (state : State) (place : StoragePlace) (slot : Slot) : Prop :=
  match place with
  | .variable name => (name, slot) ∈ state.variables
  | .field object name =>
      ∃ data, (object, data) ∈ state.objects ∧ (name, slot) ∈ data.fields

Reading a route

Mode combination \(\kappa_0\sqcup\kappa_1\) combines the access to a containing object with the mode of a field’s reference. The result is unique only when both are unique:

\[ \kappa_0\sqcup\kappa_1 = \begin{cases} \mathsf{unique} & \kappa_0=\mathsf{unique}\ \land\ \kappa_1=\mathsf{unique},\\ \mathsf{shared} & \text{otherwise}. \end{cases} \]
Shared/State:Mode.join
def Mode.join : Mode → Mode → Mode
  | .unique, .unique => .unique
  | _, _ => .shared

Resolving a place reads its route without changing the state. Write \(S\vdash p\Downarrow q:\alpha@\kappa\) when the route selects a storage place \(q\) and object \(\alpha\), with effective access mode \(\kappa\). The effective mode describes the entire route, not just the last stored reference.

A variable starts with its stored reference’s mode. A field combines the mode of its prefix with its own using mode combination:

\[ \frac{\href{#claim-shared.lookup}{S[x]}=(\kappa,\alpha)} {S\vdash x\Downarrow x:\alpha@\kappa} \qquad \frac{S\vdash p\Downarrow q:\beta@\kappa_0\quad \href{#claim-shared.lookup}{S[\beta.f]}=(\kappa_1,\alpha)} {S\vdash p.f\Downarrow\beta.f:\alpha@\href{#claim-shared.mode_join}{(\kappa_0\sqcup\kappa_1)}}. \]

Thus once a shared reference occurs along a path, the rest of that path has shared access. An absent variable, a missing field or intermediate object, or an empty slot prevents resolution.

Shared/Step:Resolve
inductive Resolve (state : State) : Place → StoragePlace → ObjectId → Mode → Prop where
  | variable {name reference} :
      (name, some reference) ∈ state.variables →
      Resolve state (.variable name) (.variable name) reference.object reference.mode
  | field {base source parent permission data name reference} :
      Resolve state base source parent permission →
      (parent, data) ∈ state.objects →
      (name, some reference) ∈ data.fields →
      Resolve state (.field base name) (.field parent name) reference.object
        (permission.join reference.mode)

Executing statements

A frame \(f=(V,P)\) owns its local variable store \(V\) and remaining statements \(P\). The program has one initial frame; after its exit there is no frame. Heap objects \(O\) and the allocation counter \(\nu\) live outside it:

\[ K=\langle O,\nu,F\rangle,\qquad F::=\mathsf{none}\mid\mathsf{some}(V,P). \]

For expression evaluation, combine the live frame’s locals with the heap and counter as the storage \(S=\langle O,V,\nu\rangle\). Write \(\operatorname{run}(S,P)=\langle O,\nu,\mathsf{some}(V,P)\rangle\). The pair \(\langle S,P\rangle\) used by local statement rules is an observation of that live frame, not a terminal program state.

Initially \(K=\operatorname{run}(S_{\emptyset},P)\), including when \(P=[]\). Exhausting the statements leaves a live frame whose bindings can still be inspected. A separate exit step pops it. There are no nested scopes or calls in this layer; Functions will extend this single-frame lifetime to a stack.

Shared/Frames:Frame
structure Frame (Instruction : Type) where
  variables : List (VariableId × Slot)
  code : List Instruction
  deriving Repr
Shared/Frames:Configuration
structure Configuration (Instruction : Type) where
  objects : List (ObjectId × Object)
  nextId : Nat
  frame : Option (Frame Instruction)
  deriving Repr
Shared/Frames:Configuration.running
def Configuration.running (state : State) (code : List Instruction) : Configuration Instruction :=
  ⟨state.objects, state.nextId, some ⟨state.variables, code⟩⟩
Shared/Frames:Configuration.initial
def Configuration.initial (code : List Instruction) : Configuration Instruction :=
  .running State.empty code
Shared/Frames:Configuration.state
def Configuration.state (configuration : Configuration Instruction) : State :=
  ⟨configuration.objects, configuration.frame.map Frame.variables |>.getD [], configuration.nextId⟩

Reachability starts at an initialized slot of the live frame and follows initialized object fields. Write \(\mathsf{Live}_S(\alpha)\) when this reaches object \(\alpha\). An absent frame has no roots.

Eager collection retains exactly reachable object entries. For object data \(D\) (its class tag and field slots), define:

\[ \operatorname{gc}(K)=\langle [(\alpha,D)\in O\mid\mathsf{Live}_{S_K}(\alpha)],\nu,F\rangle. \]

Here \(S_K\) uses the frame’s locals, or an empty variable store if the frame is absent. Collection preserves surviving objects and their identifiers, the allocation counter, and the frame. It invokes no user code. With no frame, it removes the entire heap.

The Lean definition is a mathematical reachability filter, not an executable traversal. Collection runs after whole statements and frame exit, never between constructor operands or while an expression result awaits binding.

Shared/State:Live
inductive Live (state : State) : ObjectId → Prop where
  | variable {name reference} :
      (name, some reference) ∈ state.variables → Live state reference.object
  | field {parent reference data name} :
      Live state parent → (parent, data) ∈ state.objects →
      (name, some reference) ∈ data.fields → Live state reference.object
Shared/Frames:State.collect
def State.collect (state : State) : State := by
  classical
  exact { state with objects := state.objects.filter (fun entry => decide (Live state entry.1)) }
Shared/Frames:Configuration.collect
def Configuration.collect (configuration : Configuration Instruction) : Configuration Instruction :=
  { configuration with objects := configuration.state.collect.objects }

A configuration is finished exactly when its initial frame has been popped:

\[ \mathsf{Finished}(\langle O,\nu,F\rangle)\iff F=\mathsf{none}. \]

An empty statement sequence still has a live frame and can take its exit step. Completion discards the frame’s locals and collects its unreachable objects.

Shared/Frames:Configuration.finished
def Configuration.finished (configuration : Configuration Instruction) : Prop :=
  configuration.frame = none

Expression evaluation, written

\[ \Delta\vdash\langle S,e\rangle\Downarrow\langle S',r\rangle, \]

produces a reference and updated storage. These clauses define successful evaluation:

  • Give. Evaluate p→ by giving from its route. The result is unique when it moves and shared when it copies.
  • Give-share. Evaluate p→share by the same give, require that its result targets a struct, then replace the result’s mode with shared, preserving its object identity. This last conversion changes no stored slot.
  • Construct. Evaluate arguments from left to right, then create an object containing their results in declaration order:
\[ \frac{ \begin{gathered} \href{#claim-shared.programs}{\Delta(C)}=(k,[f_1,\ldots,f_n])\\ \Delta\vdash\langle S_{i-1},e_i\rangle\Downarrow\langle S_i,r_i\rangle \quad(1\le i\le n)\\ \beta\notin\operatorname{dom}(O_n)\\ \mathsf{isStruct}(k)\Rightarrow\forall i.\;\mathsf{StructReference}_{\Delta,S_n}(r_i) \end{gathered} }{ \Delta\vdash\langle S_0,\mathsf{new}\ C(e_1,\ldots,e_n)\rangle \Downarrow\langle S',(\mathsf{mode}(k),\beta)\rangle } \quad\text{Construct} \]

where

\[ \begin{aligned} S_n&=\langle O_n,V_n,\nu_n\rangle,\\ \beta&=\href{#claim-shared.references}{\mathsf{obj}(\nu_n)},\\ O'&=O_n[\beta\mapsto C\{f_1:r_1,\ldots,f_n:r_n\}],\\ S'&=\langle O',V_n,\nu_n+1\rangle. \end{aligned} \]

Here mode(k) is shared for a shared struct and unique otherwise, as specified by the declaration kinds. StructReference means that the reference targets an allocated object whose declaration is a struct. The argument guard applies to both struct kinds and prevents constructing a struct containing a class even in an untyped program.

Here \(S_i\) is the storage after the first \(i\) arguments; \(\operatorname{dom}(O_n)\) is its set of allocated identities and the map update adds the fresh object’s entry. An empty class takes no arguments and uses \(S_n=S_0\). Argument results remain owned by the evaluation until placed in the new object’s fields. An unknown class, wrong argument count, or failed argument evaluation gives no successful construction.

Shared/Step:Eval
inductive Eval (classes : Classes) : State → Value → State → Reference → Prop where
  | give {state evaluated : State} {path : Place} {reference : Reference} :
      Give state path reference evaluated →
      Eval classes state (.give path) evaluated reference
  | giveShare {state evaluated : State} {path : Place} {reference : Reference} :
      Give state path reference evaluated →
      StructReference classes evaluated reference →
      Eval classes state (.giveShare path) evaluated (.shared reference.object)
  | new {state evaluated : State} {className : ClassName} {declaration : Class}
      {arguments : List Value} {references : List Reference} :
      (className, declaration) ∈ classes →
      EvalArgs classes state arguments evaluated references →
      references.length = declaration.fields.length →
      ObjectId.mk evaluated.nextId ∉ evaluated.objects.map Prod.fst →
      StructArguments classes evaluated declaration.kind references →
      Eval classes state (.new className arguments)
        (evaluated.allocate className declaration.fields references) (⟨declaration.kind.mode, ⟨evaluated.nextId⟩⟩)
Shared/Step:EvalArgs
inductive EvalArgs (classes : Classes) : State → List Value → State → List Reference → Prop where
  | nil (state : State) : EvalArgs classes state [] state []
  | cons {before middle after : State} {argument : Value} {arguments : List Value}
      {reference : Reference} {references : List Reference} :
      Eval classes before argument middle reference →
      EvalArgs classes middle arguments after references →
      EvalArgs classes before (argument :: arguments) after (reference :: references)
Shared/Step:State.allocate
def State.allocate (state : State) (className : ClassName) (fields : List FieldName)
    (references : List Reference) : State :=
  ⟨(⟨state.nextId⟩, ⟨className, fields.zip (references.map some)⟩) :: state.objects,
    state.variables, state.nextId + 1⟩
Shared/Step:StructReference
def StructReference (classes : Classes) (state : State) (reference : Reference) : Prop :=
  ∃ data declaration, (reference.object, data) ∈ state.objects ∧
    (data.className, declaration) ∈ classes ∧ declaration.kind.isStruct = true
Shared/Step:StructArguments
def StructArguments (classes : Classes) (state : State) (kind : Kind)
    (references : List Reference) : Prop :=
  kind.isStruct = true → ∀ reference ∈ references, StructReference classes state reference
Shared/State:Kind.mode
def Kind.mode : Kind → Mode
  | .sharedStruct => .shared
  | _ => .unique

An auxiliary local statement operation \(\Delta\vdash K\rightsquigarrow K'\) executes the first statement in a local observation of the frame. It completes expression evaluation, stores the result in a fresh variable, and removes the statement:

\[ \frac{ \href{#claim-shared.evaluation}{\Delta\vdash\langle S,e\rangle\Downarrow\langle S',r\rangle} \quad x\notin\operatorname{dom}(V') }{ \Delta\vdash\langle S,(\mathsf{let}\ x=e)::P\rangle \rightsquigarrow\langle\langle O',V'[x\mapsto r],\nu'\rangle,P\rangle } \quad\text{Let} \]

where \(S'=\langle O',V',\nu'\rangle\), and \(V'[x\mapsto r]\) adds variable \(x\) holding \(r\). The remaining statements keep their order. If evaluation fails or the variable already exists, there is no transition. All argument evaluations belong to this one step; there is no separately observable state partway through a failed expression. Write \(\rightsquigarrow\) for that local operation. The program machine collects after it and has a separate exit rule:

\[ \frac{\Delta\vdash\langle S,P\rangle\rightsquigarrow\langle S',P'\rangle} {\Delta\vdash\operatorname{run}(S,P)\longrightarrow \operatorname{gc}(\operatorname{run}(S',P'))} \qquad \Delta\vdash\operatorname{run}(\langle O,V,\nu\rangle,[]) \longrightarrow\operatorname{gc}(\langle O,\nu,\mathsf{none}\rangle). \]

The exit target has no frame and an empty heap, retaining counter \(\nu\). Even an empty program takes one exit step. A finished configuration has no successor. The Lean Step in Shared/Step is the auxiliary local relation; Framed.Step is this program machine. baseOperation selects the single-variable binding relation; later patternOperation selects the unpacking relation.

Shared/Step:State.bind
def State.bind (state : State) (name : VariableId) (reference : Reference) : State :=
  { state with variables := (name, some reference) :: state.variables }
Shared/Step:Step
inductive Step (classes : Classes) : Configuration → Configuration → Prop where
  | letValue {state evaluated : State} {destination : VariableId} {value : Value}
      {reference : Reference} {rest : List Statement} :
      destination ∉ evaluated.variables.map Prod.fst →
      Eval classes state value evaluated reference →
      Step classes ⟨state, ⟨destination, value⟩ :: rest⟩
        ⟨evaluated.bind destination reference, rest⟩
Shared/Frames:Step
inductive Step (operation : LocalStep Instruction) : Configuration Instruction → Configuration Instruction → Prop where
  | «local» {before after code rest} :
      operation before code after rest →
      Step operation (.running before code) (Configuration.running after rest).collect
  | exit {state} :
      Step operation (.running state []) (Configuration.mk state.objects state.nextId none).collect
Shared/Frames:baseOperation
def baseOperation (classes : Classes) : LocalStep Statement :=
  fun before code after rest => Dada.Shared.Step classes ⟨before, code⟩ ⟨after, rest⟩
Shared/Frames:patternOperation
def patternOperation (classes : Classes) : LocalStep Unpacking.Statement :=
  fun before code after rest => Unpacking.Step classes ⟨before, code⟩ ⟨after, rest⟩
class Token {}
let t = new Token();

The first step binds the token in the initial frame. That frame is still live even though its statements are exhausted. The second step pops it and collects the token, leaving an empty heap and allocation counter one. An empty program has no statements but still takes its initial-frame exit step.

Shared/FrameChecks:lifetime
example :
    Step (baseOperation classes) (.initial []) (Configuration.terminal (Instruction := Statement) 0) ∧
    Step (baseOperation classes) (.initial code) (.running observed []) ∧
    ("t", some (.owned 0)) ∈ observed.variables ∧
    ¬ (Configuration.running observed ([] : List Statement)).finished ∧
    StepsExactly (baseOperation classes) (.initial code) 2 (.terminal 1) ∧
    (Configuration.terminal (Instruction := Statement) 1).finished := by
  refine ⟨exit_step State.empty, local_step allocated observed_wellFormed, by decide,
    by simp [Configuration.running, Configuration.finished], ?_, rfl⟩
  exact .step (local_step allocated observed_wellFormed) (.step (exit_step observed) (.refl _))

Using the declarations above:

let b = new SharedBox(new Token());
let c = b→;
let t = b.value→;

Construction gives b a shared reference immediately. Giving b copies that reference into c, leaving b initialized. The token field initially holds a unique reference; giving it through shared b promotes that stored reference and produces a shared token in t. Immediate sharing of the container does not require its fields to have been stored with shared modes.

Shared/KindChecks:immediately_shared
example : SequenceTyped classes [] program finalEnvironment ∧
    Unpacking.Steps classes.erase ⟨State.empty, program⟩ ⟨finalState, []⟩ ∧
    RawType.normalize classes (.nominal (.whole "SharedBox")) = sharedBox ∧
    ¬ Admissible classes (.whole "SharedBox") ∧
    ¬ Admissible classes (.whole "Resource" .shared) ∧
    ("b", some (.shared 1)) ∈ finalState.variables ∧
    ("c", some (.shared 1)) ∈ finalState.variables ∧
    ("t", some (.shared 0)) ∈ finalState.variables := by
  exact ⟨program_typed, execution, by decide, by decide, by decide,
    by decide, by decide, by decide⟩

new Resource(new Token()) produces a unique class reference. Binding it to r and then evaluating r→share is rejected. Plain r→ remains a move; a class may contain structs without becoming shareable itself.

Shared/KindChecks:class_boundary
example : ExprTyped classes [] (.new "Resource" [.new "Token" []]) (.whole "Resource") [] ∧
    (∀ ty after, ¬ ExprTyped classes [("r", some (.whole "Resource"))]
      (.giveShare (.variable "r")) ty after) ∧
    (∀ after, ¬ Unpacking.Bind classes.erase constructed (.shared 1)
      (.unpack "SharedBox" [("value", "v")]) after) ∧
    give classes [("r", some (.whole "Resource"))] (.variable "r") =
      some (.whole "Resource", [("r", none)]) := by
  exact ⟨class_construction, fun _ _ => class_sharing_rejected,
    (fun _ => Unpacking.shared_cannot_unpack), by decide⟩

A finite execution \(\Delta\vdash K\longrightarrow^{*}K'\) consists of zero or more statement steps:

\[ \frac{}{\Delta\vdash K\longrightarrow^{*}K} \qquad \frac{\href{#claim-shared.steps}{\Delta\vdash K\longrightarrow K'} \quad\Delta\vdash K'\longrightarrow^{*}K''} {\Delta\vdash K\longrightarrow^{*}K''}. \]
Shared/Frames:Steps
def Steps (operation : LocalStep Instruction) (before after : Configuration Instruction) : Prop :=
  ∃ count, StepsExactly operation before count after
Shared/Frames:StepsExactly
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 stuck when its frame remains but no step is available:

\[ \mathsf{Stuck}_{\Delta}(K)\iff \neg\href{#claim-shared.finished}{\mathsf{Finished}(K)}\ \land\ \neg\exists K'.\;\href{#claim-shared.steps}{\Delta\vdash K\longrightarrow K'}. \]

For example, giving through an entirely unique path empties its slot, so giving it again cannot evaluate and leaves the machine stuck. Repeated gives through shared access leave the source initialized.

Shared/Frames:Stuck
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
  ¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after

Use struct Token {} and struct Box { value: Token }. Let object \(\mathsf{obj}(0)\) be a token and object \(\mathsf{obj}(1)\) a box, with these slots and allocation counter \(2\):

SlotContents
bUnique owner of box \(\mathsf{obj}(1)\)
tEmpty
Box \(\mathsf{obj}(1)\), field valueUnique owner of token \(\mathsf{obj}(0)\)

Execute:

let s = b→share;

Variable s receives a shared owner of box \(\mathsf{obj}(1)\), and b becomes empty. The field remains a unique owner of token \(\mathsf{obj}(0)\). The objects, empty t, and allocation counter are unchanged.

Shared/Examples:share_value
example : Step exampleClasses
    ⟨boxState, [⟨"s", .giveShare (.variable "b")⟩]⟩ ⟨sharedBoxState, []⟩ := by
  exact example_share_box []

Start again from the pre-exit storage of refshared.example.share_value, before copying its field. Execute:

class Outer { value: shared Box }
let outer = new Outer(s→);
let u = outer.value.value→;

The constructor copies shared variable s into the new outer object \(\mathsf{obj}(2)\); s remains initialized. Variable outer uniquely owns the outer object \(\mathsf{obj}(2)\). The give then traverses three references: unique outer, shared outer.value to box \(\mathsf{obj}(1)\), and the unique value field of box \(\mathsf{obj}(1)\) to token \(\mathsf{obj}(0)\).

The shared middle link makes this a shared access even though the first and last stored references are unique. The give changes only the reference in box \(\mathsf{obj}(1)\)’s value field to shared, and u receives a shared owner of token \(\mathsf{obj}(0)\). outer stays unique; its field stays shared; s still refers to box \(\mathsf{obj}(1)\). All three objects remain allocated and the allocation counter is \(3\).

Shared/Examples:nested_shared_path
example : Steps nestedClasses
    ⟨sharedBoxState, [⟨"outer", .new "Outer" [.give (.variable "s")]⟩,
      ⟨"u", .give (.field (.field (.variable "outer") "value") "value")⟩]⟩
    ⟨nestedCopiedState, []⟩ := by
  apply Steps.step (middle := ⟨nestedSharedState,
    [⟨"u", .give (.field (.field (.variable "outer") "value") "value")⟩]⟩)
  · apply Step.letValue (reference := .owned 2)
      (evaluated := sharedBoxState.allocate "Outer" ["value"] [.shared 1])
    · simp [State.allocate, sharedBoxState]
    · apply Eval.new (declaration := ⟨["value"], .classType⟩) (references := [.shared 1])
      · simp [nestedClasses]
      · apply EvalArgs.cons (reference := .shared 1)
        · apply Eval.give
          apply Give.copy (source := .variable "s")
          · exact Resolve.variable (reference := .shared 1) (by simp [sharedBoxState])
          · simp [Stored, sharedBoxState]
        · exact EvalArgs.nil _
      · rfl
      · decide
      · simp [StructArguments, Kind.isStruct]
  apply Steps.step (middle := ⟨nestedCopiedState, []⟩)
  · apply Step.letValue (reference := .shared 0)
      (evaluated := ⟨nestedCopiedState.objects, nestedSharedState.variables, 3⟩)
    · simp [nestedSharedState, sharedBoxState]
    · apply Eval.give
      apply Give.promote (source := .field 1 "value")
      · apply Resolve.field (permission := .shared) (reference := .owned 0)
          (data := ⟨"Box", [("value", some (.owned 0))]⟩)
        · apply Resolve.field (permission := .unique) (reference := .shared 1)
            (data := ⟨"Outer", [("value", some (.shared 1))]⟩)
          · exact Resolve.variable (reference := .owned 2) (by simp [nestedSharedState])
          · simp [nestedSharedState, Reference.owned]
          · simp
        · simp [nestedSharedState, boxState]
        · simp
      · exact Promote.field nestedSharedState.variables 3
          [(2, ⟨"Outer", [("value", some (.shared 1))]⟩)] [(0, ⟨"Token", []⟩)]
          1 "Box" [] [] "value" 0
  exact Steps.refl _

Liveness and well-formedness

An object is allocated when its identity appears in the object table:

\[ \mathsf{Allocated}_S(\alpha)\iff\alpha\in\operatorname{dom}(O). \]
Shared/State:Allocated
def Allocated (state : State) (object : ObjectId) : Prop :=
  object ∈ state.objects.map Prod.fst

An object is live when an owning path reaches it from a variable, following occupied slots. Both unique and shared references contribute owning edges:

\[ \frac{\href{#claim-shared.lookup}{S[x]}=(\kappa,\alpha)}{\mathsf{Live}_S(\alpha)} \qquad \frac{\mathsf{Live}_S(\beta)\quad\href{#claim-shared.lookup}{S[\beta.f]}=(\kappa,\alpha)} {\mathsf{Live}_S(\alpha)}. \]

Empty slots contribute no edge.

Shared/State:Live
inductive Live (state : State) : ObjectId → Prop where
  | variable {name reference} :
      (name, some reference) ∈ state.variables → Live state reference.object
  | field {parent reference data name} :
      Live state parent → (parent, data) ∈ state.objects →
      (name, some reference) ∈ data.fields → Live state reference.object

During expression evaluation, an object can be live with pending values even when no variable points to it. A list of pending references supplies additional roots alongside the variable roots of ordinary liveness. An object is live with pending values when a finite sequence of occupied field slots reaches it from either kind of root. Both unique and shared references contribute edges, and a pending reference reaches its own target directly.

Shared/Reachability:LiveWith
inductive LiveWith (state : State) (pending : List Reference) : ObjectId → Prop where
  | pending {reference} : reference ∈ pending → LiveWith state pending reference.object
  | variable {name reference} : (name, some reference) ∈ state.variables →
      LiveWith state pending reference.object
  | field {parent data name reference} : LiveWith state pending parent →
      (parent, data) ∈ state.objects → (name, some reference) ∈ data.fields →
      LiveWith state pending reference.object

Allocated objects and live objects are distinguished by presence in storage and reachability from roots.

A state is well formed, written \(\mathsf{WF}_{\Delta}(S)\), when:

  • Object identities and variable names are each distinct.
  • Every object’s class is declared, and its distinct field names match the declaration’s order, including fields whose slots are empty.
  • Every allocated identity has an index below the allocation counter.
  • Every allocated object is live: some finite owning path reaches it from a variable root. Field edges need not follow allocation order.
  • Every stored reference targets an allocated object, and every allocated object has at least one stored owning reference.
  • Any two distinct owning occurrences targeting the same object are both shared.
  • Every occupied field of a struct targets another struct object.
  • Every shared reference targets a struct, and every reference to an instance of a shared struct is shared.

The first six clauses are structural well-formedness. The final two are the declaration-kind invariants. Structural well-formedness also has a form that counts pending expression results as additional owning occurrences and uses liveness with pending values for its rootedness condition. This lets expression soundness describe values not yet placed in a slot.

Owning occurrences are counted across all variable slots and all object fields. The ownership-compatibility condition permits several shared references to an object, but a stored unique reference must be its only incoming owning reference. That local condition does not by itself give a path unique access: every preceding reference must also be unique. Rootedness excludes an unreachable component even when its objects reference one another. It permits cycles reachable through shared access; the allocation counter is a freshness bound, not a ranking of heap edges.

Shared/State:Allocated
def Allocated (state : State) (object : ObjectId) : Prop :=
  object ∈ state.objects.map Prod.fst
Shared/State:Live
inductive Live (state : State) : ObjectId → Prop where
  | variable {name reference} :
      (name, some reference) ∈ state.variables → Live state reference.object
  | field {parent reference data name} :
      Live state parent → (parent, data) ∈ state.objects →
      (name, some reference) ∈ data.fields → Live state reference.object
Shared/State:References
def References (state : State) : List ObjectId :=
  state.variables.filterMap (fun binding => binding.2.map Reference.object) ++
    state.objects.flatMap (fun entry => entry.2.fields.filterMap
      (fun field => field.2.map Reference.object))
Shared/Soundness:Owners
def Owners (state : State) : List Reference :=
  state.variables.filterMap (fun binding => binding.2) ++
    state.objects.flatMap (fun entry => entry.2.fields.filterMap (fun field => field.2))
Shared/Soundness:Compatible
def Compatible (first second : Reference) : Prop :=
  first.object ≠ second.object ∨ first.mode = .shared ∧ second.mode = .shared
Shared/Soundness:WellFormed
structure WellFormed (classes : Classes) (state : State) : Prop where
  objectKeys : (state.objects.map Prod.fst).Nodup
  variableKeys : (state.variables.map Prod.fst).Nodup
  shapes : ∀ id data, (id, data) ∈ state.objects →
    ∃ declaration, (data.className, declaration) ∈ classes ∧
      data.fields.map Prod.fst = declaration.fields ∧ declaration.fields.Nodup
  bounds : ∀ id data, (id, data) ∈ state.objects → id.index < state.nextId
  rooted : ∀ object, Allocated state object → Live state object
  ownersCompatible : (Owners state).Pairwise Compatible
  referencesComplete : ∀ id, id ∈ References state ↔ Allocated state id
Shared/Soundness:WellFormedWith
structure WellFormedWith (classes : Classes) (state : State) (pending : List Reference) : Prop where
  objectKeys : (state.objects.map Prod.fst).Nodup
  variableKeys : (state.variables.map Prod.fst).Nodup
  shapes : ∀ id data, (id, data) ∈ state.objects →
    ∃ declaration, (data.className, declaration) ∈ classes ∧
      data.fields.map Prod.fst = declaration.fields ∧ declaration.fields.Nodup
  bounds : ∀ id data, (id, data) ∈ state.objects → id.index < state.nextId
  rooted : ∀ object, Allocated state object → LiveWith state pending object
  ownersCompatible : (pending ++ Owners state).Pairwise Compatible
  referencesComplete : ∀ id, id ∈ (pending.map Reference.object ++ References state) ↔ Allocated state id
Shared/KindSafety:HasKind
def HasKind (classes : Classes) (state : State) (object : ObjectId) (kind : Kind) : Prop :=
  ∃ name declaration, (object, name) ∈ objectNames state ∧
    (name, declaration) ∈ classes ∧ declaration.kind = kind
Shared/KindSafety:ReferenceAllowed
def ReferenceAllowed (classes : Classes) (state : State) (reference : Reference) : Prop :=
  ∃ kind, HasKind classes state reference.object kind ∧
    (reference.mode = .shared → kind.isStruct = true) ∧
    (kind = .sharedStruct → reference.mode = .shared)
Shared/KindSafety:KindCorrect
structure KindCorrect (classes : Classes) (state : State) (pending : List Reference) : Prop where
  references : ∀ reference ∈ pending ++ Owners state, ReferenceAllowed classes state reference
  fields : ∀ object data declaration, (object, data) ∈ state.objects →
    (data.className, declaration) ∈ classes → declaration.kind.isStruct = true →
    ∀ name reference, (name, some reference) ∈ data.fields →
      StructReference classes state reference
Shared/KindSafety:WellFormedState
def WellFormedState (classes : Classes) (state : State) : Prop :=
  WellFormed classes state ∧ KindCorrect classes state []

Structural well-formedness accepts a parent whose child was allocated later. The checked heap contains class Parent object 0, class Leaf object 1, and allocation counter 2. Variable p uniquely owns object 0; its child field uniquely owns object 1. Both objects are reachable, and each has exactly one owning occurrence. The field edge from 0 to 1 is permitted independently of their allocation indices.

Shared/RootedChecks:newer_child
example : WellFormed classes newerChild := by
  refine ⟨by decide, by decide, ?_, ?_, ?_, ?_, ?_⟩
  · intro id data member
    simp only [newerChild, List.mem_cons, List.not_mem_nil, or_false] at member
    rcases member with h | h <;> cases h
    · exact ⟨⟨["child"], .classType⟩, by decide, rfl, by decide⟩
    · exact ⟨⟨[], .classType⟩, by decide, rfl, by decide⟩
  · intro id data member
    simp only [newerChild, List.mem_cons, List.not_mem_nil, or_false] at member
    rcases member with h | h <;> cases h <;> decide
  · intro object allocated
    have cases : object = ⟨0⟩ ∨ object = ⟨1⟩ := by simpa [Allocated, newerChild] using allocated
    rcases cases with rfl | rfl
    · exact .variable (name := "p") (reference := .owned ⟨0⟩) (by decide)
    · exact .field (parent := ⟨0⟩) (name := "child") (reference := .owned ⟨1⟩)
        (.variable (name := "p") (reference := .owned ⟨0⟩) (by decide))
        (data := ⟨"Parent", [("child", some (.owned ⟨1⟩))]⟩) (by decide) (by decide)
  · simp [Owners, newerChild, Compatible, Reference.owned]
  · intro object
    simp [References, Allocated, newerChild, Reference.owned]

Consider two struct Node objects, 0 and 1, each with a next field. Variable root holds a shared reference to object 0; object 0’s next holds a shared reference to object 1, and object 1’s next holds a shared reference back to 0. With allocation counter 2, this heap satisfies structural well-formedness. Both objects have finite paths from root, despite the cycle. This is a check of an arbitrary heap, not a claim that this layer’s constructor-only operations can create the cycle.

Shared/RootedChecks:shared_cycle
example : WellFormed classes sharedCycle := by
  refine ⟨by decide, by decide, ?_, ?_, ?_, ?_, ?_⟩
  · intro id data member
    simp only [sharedCycle, List.mem_cons, List.not_mem_nil, or_false] at member
    rcases member with h | h <;> cases h
    all_goals exact ⟨⟨["next"], .structType⟩, by decide, rfl, by decide⟩
  · intro id data member
    simp only [sharedCycle, List.mem_cons, List.not_mem_nil, or_false] at member
    rcases member with h | h <;> cases h <;> decide
  · intro object allocated
    have cases : object = ⟨0⟩ ∨ object = ⟨1⟩ := by simpa [Allocated, sharedCycle] using allocated
    rcases cases with rfl | rfl
    · exact .variable (name := "root") (reference := .shared ⟨0⟩) (by decide)
    · exact .field (parent := ⟨0⟩) (name := "next") (reference := .shared ⟨1⟩)
        (.variable (name := "root") (reference := .shared ⟨0⟩) (by decide))
        (data := ⟨"Node", [("next", some (.shared ⟨1⟩))]⟩) (by decide) (by decide)
  · simp [Owners, sharedCycle, Compatible, Reference.shared]
  · intro object
    simp [References, Allocated, sharedCycle, Reference.shared, or_comm]

In the preceding cycle, change only object 0’s next reference to unique. The heap still satisfies structural well-formedness: that field is the sole owning occurrence of object 1. Access from variable root still traverses a shared reference first. Thus a unique stored edge may occur inside a cycle whose access from roots is shared; stored uniqueness alone is not unique access.

Shared/RootedChecks:mixed_cycle
example : WellFormed classes mixedCycle := by
  refine ⟨by decide, by decide, ?_, ?_, ?_, ?_, ?_⟩
  · intro id data member
    simp only [mixedCycle, List.mem_cons, List.not_mem_nil, or_false] at member
    rcases member with h | h <;> cases h
    all_goals exact ⟨⟨["next"], .structType⟩, by decide, rfl, by decide⟩
  · intro id data member
    simp only [mixedCycle, List.mem_cons, List.not_mem_nil, or_false] at member
    rcases member with h | h <;> cases h <;> decide
  · intro object allocated
    have cases : object = ⟨0⟩ ∨ object = ⟨1⟩ := by simpa [Allocated, mixedCycle] using allocated
    rcases cases with rfl | rfl
    · exact .variable (name := "root") (reference := .shared ⟨0⟩) (by decide)
    · exact .field (parent := ⟨0⟩) (name := "next") (reference := .owned ⟨1⟩)
        (.variable (name := "root") (reference := .shared ⟨0⟩) (by decide))
        (data := ⟨"Node", [("next", some (.owned ⟨1⟩))]⟩) (by decide) (by decide)
  · simp [Owners, mixedCycle, Compatible, Reference.shared, Reference.owned]
  · intro object
    simp [References, Allocated, mixedCycle, Reference.shared, Reference.owned, or_comm]

The distinction between stored uniqueness and unique access matters when moving an object. Use the mixed cycle shape with these concrete names: variable a shares object 0 of struct A; its field f uniquely owns object 1 of struct B; field g of object 1 shares object 0.

Starting at object 1, the path g.f leads back to object 1 with shared access. The low-level slot-removal operation used by give can clear object 0’s f slot. Afterwards, following g.f from object 1 reaches an empty slot. Thus removing an incoming reference does not, by itself, preserve all observations inside its target.

This is an abstract-heap check of the storage helper, not an execution of a.f→. A valid move also requires unique access along the entire source path.

Shared/RootedPathChecks:raw_take_changes_interior
example :
    Take cyclic (.field ⟨0⟩ "f") ⟨1⟩ removed ∧
    readPath cyclic (.owned ⟨1⟩) ["g", "f"] = some (some (.shared ⟨1⟩)) ∧
    readPath removed (.owned ⟨1⟩) ["g", "f"] = some none := by
  exact ⟨.field _ _ [] [(⟨1⟩, ⟨"B", [("g", some (.shared ⟨0⟩))]⟩)]
    ⟨0⟩ "A" [] [] "f" ⟨1⟩, by decide, by decide⟩

In the preceding heap, a.f→ has shared access. The checked transition uses give’s promotion case: it changes object 0’s f reference to shared and returns a shared reference to object 1. There is no unique resolution of a.f, so this access cannot select the move case.

Every finite field-path observation starting from the returned shared reference to object 1 is unchanged by the promotion. This includes the shared g.f backedge, empty slots, and failed lookups. The cycle remains present; no allocation ordering or global acyclicity is required for this result. As above, the example starts from an abstract heap rather than constructing the cycle with this layer’s source operations.

Shared/RootedPathChecks:give_preserves_shared_cycle
example :
    Give cyclic fieldPlace (.shared ⟨1⟩) promoted ∧
    (¬ ∃ source, Resolve cyclic fieldPlace source ⟨1⟩ .unique) ∧
    (∀ path, readPath promoted (.shared ⟨1⟩) path = readPath cyclic (.shared ⟨1⟩) path) := by
  have given : Give cyclic fieldPlace (.shared ⟨1⟩) promoted := .promote resolves_shared promotes
  have afterWf := given.preserves_pending cyclic_wellFormed.with_pending
  refine ⟨given, ?_, ?_⟩
  · rintro ⟨source, unique⟩
    have impossible := (resolve_deterministic cyclic_wellFormed.with_pending resolves_shared unique).2.2
    cases impossible
  · intro path
    exact promote_readPath_eq cyclic_wellFormed.with_pending afterWf promotes
      (route_of_resolve resolves_shared) (route_of_resolve resolves_shared) path

Remove variable root from the two-shared-edge cycle. Each object still has an incoming shared reference, but neither has a path from a variable. The resulting heap fails structural well-formedness. Incoming-reference coverage does not replace rootedness.

Shared/RootedChecks:unrooted_cycle
example : ¬ WellFormed classes { sharedCycle with variables := [] } := by
  intro wf
  have noLive : ∀ object, ¬ Live { sharedCycle with variables := [] } object := by
    intro object live
    induction live with
    | «variable» member => simp at member
    | field _ _ _ ih => exact ih
  exact noLive ⟨0⟩ (wf.rooted ⟨0⟩ (by simp [Allocated, sharedCycle]))

In a well-formed state, no object can be reached both by an entirely unique path and by a path containing a shared reference:

\[ \begin{aligned} &\mathsf{WF}_{\Delta}(S)\;\land\; (\href{#claim-shared.resolution}{S\vdash p\Downarrow q:\alpha@\mathsf{unique}})\\ &\quad\Longrightarrow\quad \neg\exists p',q'.\ \href{#claim-shared.resolution}{S\vdash p'\Downarrow q':\alpha@\mathsf{shared}}. \end{aligned} \]

The paths start at variables. A unique reference stored inside a shared container does not contradict this property: the path through that container already contains a shared reference.

Shared/KindSafety:WellFormedState.path_mode_exclusive
theorem WellFormedState.path_mode_exclusive (wf : WellFormedState classes state)
    (unique : Resolve state uniquePath uniquePlace object .unique)
    (shared : Resolve state sharedPath sharedPlace object .shared) : False :=
  wf.1.path_mode_exclusive unique shared

In a well-formed state, an object is live exactly when it is allocated:

\[ \mathsf{WF}_{\Delta}(S) \quad\Longrightarrow\quad \bigl(\href{#claim-shared.live}{\mathsf{Live}_S(\alpha)}\iff\href{#claim-shared.allocated}{\mathsf{Allocated}_S(\alpha)}\bigr). \]

Every allocated object therefore has an owning path from a variable. Sharing allows several such paths without making missing objects reachable.

Shared/KindSafety:WellFormedState.live_iff_allocated
theorem WellFormedState.live_iff_allocated (wf : WellFormedState classes state) :
    Live state object ↔ Allocated state object := wf.1.live_iff_allocated

Collection leaves structurally well-formed evaluation storage unchanged: every allocated object is already reachable. Ordinary statements preserve this property, so their following collection is inert. Popping the frame removes its roots; collection at that boundary empties the heap instead.

Shared/Frames:State.collect_eq_self
theorem State.collect_eq_self (wf : WellFormed classes state) : state.collect = state := by
  classical
  have keep : state.objects.filter (fun entry => decide (Live state entry.1)) = state.objects :=
    List.filter_eq_self.mpr (by
      intro entry member
      simpa using wf.allocated_live (List.mem_map.mpr ⟨entry, member, rfl⟩))
  simp [State.collect, keep]

For any program with a well-formed class table, every configuration reached by a finite execution from the empty initial state has a well-formed state. This includes intermediate configurations and the state after the final statement.

Consequently, every allocated object remains live. In each such state, a unique stored reference is the only incoming owner of its object; when an object has several incoming owners, all those references are shared. No object has both a unique path and a shared path from variables. This covers both explicit give-share and copying through a shared path, including the change to the path’s final stored reference.

Shared/FrameInvariants:base_soundness
theorem base_soundness (classesWf : ClassesWellFormed classes)
    (trace : StepsExactly (baseOperation classes) (.initial code) count after) :
    WellFormedState classes after.state := by
  have preserve : ∀ start n finish, WellFormedState classes start.state →
      StepsExactly (baseOperation classes) start n finish → WellFormedState classes finish.state := by
    intro start n finish wf execution
    induction execution with
    | refl => exact wf
    | step next _ rest => exact rest (base_kind_preservation classesWf wf next)
  exact preserve _ _ _ ⟨WellFormed.empty _, KindCorrect.empty _⟩ trace

The Given fragment inside Shared

The Shared language contains a translation of the Given fragment with single-variable bindings. This section restricts the correspondence to that fragment. Write \(E\) for this translation, applied to programs, configurations, and their components.

For a state, \(E\) replaces every reference \(\alpha\) with the unique reference \((\mathsf{unique},\alpha)\). Empty slots remain empty. Class names, field names, variable names, object identities, table order, and the next-identity counter are preserved.

For a program, \(E\) preserves its class declarations, places, constructors, gives, and statement order. Every Given declaration becomes a class, never a struct or shared struct. It introduces no give-share expression. For a configuration, it translates the heap and any live frame, preserving the counter and the distinction between a live frame and no frame. Thus a related pair describes the same point in the same computation, with explicit unique mode tags in the Shared state.

Correspondence/UniqueSharedFrames:embed
def embed (instruction : I → J) (configuration : Unique.Framed.Configuration I) : Shared.Framed.Configuration J :=
  ⟨(embedState configuration.state).objects, configuration.nextId,
    configuration.frame.map fun frame => ⟨embedSlots frame.variables, frame.code.map instruction⟩⟩
Correspondence/UniqueShared:embedId
def embedId (object : Unique.ObjectId) : Shared.ObjectId := ⟨object.index⟩
Correspondence/UniqueShared:embedReference
def embedReference (object : Unique.ObjectId) : Shared.Reference := .owned (embedId object)
Correspondence/UniqueShared:embedSlots
def embedSlots {Key : Type} (slots : List (Key × Unique.Slot)) : List (Key × Shared.Slot) :=
  slots.map (fun entry => (entry.1, entry.2.map embedReference))
Correspondence/UniqueShared:embedObject
def embedObject (object : Unique.Object) : Shared.Object :=
  ⟨object.className, embedSlots object.fields⟩
Correspondence/UniqueShared:embedState
def embedState (state : Unique.State) : Shared.State :=
  ⟨state.objects.map (fun entry => (embedId entry.1, embedObject entry.2)),
    embedSlots state.variables, state.nextId⟩
Correspondence/UniqueShared:embedPlace
def embedPlace : Unique.Place → Shared.Place
  | .variable name => .variable name
  | .field base name => .field (embedPlace base) name
Correspondence/UniqueShared:embedValue
def embedValue : Unique.Value → Shared.Value
  | .give source => .give (embedPlace source)
  | .new name arguments => .new name (arguments.map embedValue)
Correspondence/UniqueShared:embedStatement
def embedStatement (statement : Unique.Statement) : Shared.Statement :=
  ⟨statement.destination, embedValue statement.value⟩
Correspondence/UniqueShared:embedClasses
def embedClasses (classes : Unique.Classes) : Shared.Classes :=
  classes.map (fun entry => (entry.1, ⟨entry.2.fields, .classType⟩))
Correspondence/UniqueShared:embedProgram
def embedProgram (program : Unique.Program) : Shared.Program :=
  ⟨embedClasses program.classes, program.body.map embedStatement⟩
Correspondence/UniqueShared:embedConfiguration
def embedConfiguration (configuration : Unique.Configuration) : Shared.Configuration :=
  ⟨embedState configuration.state, configuration.code.map embedStatement⟩

For every class table \(\Delta\) and configuration \(c\) of this Given fragment, the embedding matches steps in both directions:

  • If \(\href{given.html#claim-given.steps}{\Delta\vdash c\longrightarrow c'}\), then \(\href{#claim-shared.steps}{E(\Delta)\vdash E(c)\longrightarrow E(c')}\).
  • If \(\href{#claim-shared.steps}{E(\Delta)\vdash E(c)\longrightarrow d}\), then there is a Given successor \(c'\) with \(\href{given.html#claim-given.steps}{\Delta\vdash c\longrightarrow c'}\) and \(d=E(c')\).

The second statement covers every Shared successor \(d\); it does not assume in advance that \(d\) is a translated state. These statements give a one-step bisimulation between Given and its embedded fragment: Shared adds no behavior to translated Given computations, and loses none of their steps.

Correspondence/UniqueSharedFrames:base_step_correspondence
theorem base_step_correspondence :
    Shared.Framed.Step (Shared.Framed.baseOperation (embedClasses classes))
      (embed embedStatement before) after ↔
    ∃ successor, Unique.Framed.Step (Unique.Framed.baseOperation classes) before successor ∧
      after = embed embedStatement successor := by
  constructor
  · apply step_backward embedStatement
    intro state code next rest step
    obtain ⟨successor, original, same⟩ := Dada.Correspondence.step_backward (before := ⟨state, code⟩) (after := ⟨next, rest⟩) step
    have states := congrArg Shared.Configuration.state same
    exact ⟨successor.state, successor.code, original, states, by simpa [Dada.Correspondence.embedConfiguration] using congrArg (fun c => c.code) same⟩
  · rintro ⟨successor, step, rfl⟩
    exact step_forward embedStatement (fun state code after rest step => Dada.Correspondence.step_forward
      (before := ⟨state, code⟩) (after := ⟨after, rest⟩) step) step

For every program in the Given fragment with single-variable bindings, translating its initial configuration gives exactly the initial configuration of its translated Shared program.

For every configuration in this fragment, the translated configuration is finished exactly when the original is finished. Using the program’s class table, the translated configuration is stuck exactly when the original is stuck. The correspondence therefore agrees on how execution starts, on successful completion, and on the absence of an available step before completion.

Correspondence/UniqueSharedFrames:base_boundary_correspondence
theorem base_boundary_correspondence (classes : Unique.Classes)
    (code : List Unique.Statement) (configuration : Unique.Framed.Configuration Unique.Statement) :
    embed embedStatement (.initial code) = .initial (code.map embedStatement) ∧
    ((embed embedStatement configuration).finished ↔ configuration.finished) ∧
    (Shared.Framed.Stuck (Shared.Framed.baseOperation (embedClasses classes)) (embed embedStatement configuration) ↔
      Unique.Framed.Stuck (Unique.Framed.baseOperation classes) configuration) :=
  ⟨initial_correspondence _ _, finished_correspondence _ _, base_stuck_correspondence⟩