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:
Object identities are tagged natural numbers, written \(\mathsf{obj}(n)\), with \(\operatorname{index}(\mathsf{obj}(n))=n\).
structure ObjectId where
index : Nat
deriving DecidableEq, Repr
inductive Mode where
| unique
| shared
deriving DecidableEq, Repr
structure Reference where
reference ::
mode : Mode
object : ObjectId
deriving DecidableEq, Repr
def Reference.owned (object : ObjectId) : Reference := ⟨.unique, object⟩
def Reference.shared (object : ObjectId) : Reference := ⟨.shared, object⟩
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 access | Stored mode | Result mode | Source slot afterwards |
|---|---|---|---|
| Unique | Unique | Unique | Empty |
| Shared | Shared | Shared | Unchanged |
| Shared | Unique | Shared | Stored 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.
inductive Place where
| variable (name : VariableId)
| field (base : Place) (name : FieldName)
deriving DecidableEq, Repr
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)
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⟩
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⟩
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:
| Declaration | May be shared | Constructor result |
|---|---|---|
class C { ... } | No | Given C |
struct C { ... } | Yes | Given C |
shared struct C { ... } | Yes | shared C |
These three forms describe nominal types; they do not introduce three different kinds of runtime object representation. Modes still belong to references.
inductive Kind where
| classType
| structType
| sharedStruct
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
structure Class where
fields : List FieldName
kind : Kind := .structType
deriving DecidableEq, Repr
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.
def Kind.isStruct : Kind → Bool
| .classType => false
| _ => true
def StructType (classes : ClassTable) (ty : ValueType) : Prop :=
(classes.lookup ty.base).any (fun declaration => declaration.kind.isStruct) = true
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)
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.
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.
abbrev ClassName := String
abbrev FieldName := String
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:
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.
abbrev VariableId := String
inductive Place where
| variable (name : VariableId)
| field (base : Place) (name : FieldName)
deriving DecidableEq, Repr
inductive Value where
| give (source : Place)
| giveShare (source : Place)
| new (className : ClassName) (arguments : List Value)
deriving Repr
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:
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])\).
abbrev Classes := List (ClassName × Class)
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.
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.
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:
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:
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:
Here \(\varnothing\) denotes the empty map.
def State.empty : State := ⟨[], [], 0⟩
A storage place \(q\) selects one slot directly: a variable or a field of a particular object:
A place expression follows a route to a slot; a storage place identifies the slot itself.
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\):
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.
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:
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:
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.
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:
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.
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
def Configuration.running (state : State) (code : List Instruction) : Configuration Instruction :=
⟨state.objects, state.nextId, some ⟨state.variables, code⟩⟩
def Configuration.initial (code : List Instruction) : Configuration Instruction :=
.running State.empty code
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:
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.
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
def State.collect (state : State) : State := by
classical
exact { state with objects := state.objects.filter (fun entry => decide (Live state entry.1)) }
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:
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.
def Configuration.finished (configuration : Configuration Instruction) : Prop :=
configuration.frame = none
Expression evaluation, written
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→shareby 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:
where
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.
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⟩⟩)
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)
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⟩
def StructReference (classes : Classes) (state : State) (reference : Reference) : Prop :=
∃ data declaration, (reference.object, data) ∈ state.objects ∧
(data.className, declaration) ∈ classes ∧ declaration.kind.isStruct = true
def StructArguments (classes : Classes) (state : State) (kind : Kind)
(references : List Reference) : Prop :=
kind.isStruct = true → ∀ reference ∈ references, StructReference classes state reference
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:
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:
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.
def State.bind (state : State) (name : VariableId) (reference : Reference) : State :=
{ state with variables := (name, some reference) :: state.variables }
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⟩
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
def baseOperation (classes : Classes) : LocalStep Statement :=
fun before code after rest => Dada.Shared.Step classes ⟨before, code⟩ ⟨after, rest⟩
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.
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.
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.
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:
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 stuck when its frame remains but no step is available:
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.
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after
A shared link inside a path
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\):
| Slot | Contents |
|---|---|
b | Unique owner of box \(\mathsf{obj}(1)\) |
t | Empty |
Box \(\mathsf{obj}(1)\), field value | Unique 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.
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\).
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:
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:
Empty slots contribute no edge.
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.
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.
def Allocated (state : State) (object : ObjectId) : Prop :=
object ∈ state.objects.map Prod.fst
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
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))
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))
def Compatible (first second : Reference) : Prop :=
first.object ≠ second.object ∨ first.mode = .shared ∧ second.mode = .shared
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
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
def HasKind (classes : Classes) (state : State) (object : ObjectId) (kind : Kind) : Prop :=
∃ name declaration, (object, name) ∈ objectNames state ∧
(name, declaration) ∈ classes ∧ declaration.kind = kind
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)
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
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.
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.
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.
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.
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.
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.
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:
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.
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:
Every allocated object therefore has an owning path from a variable. Sharing allows several such paths without making missing objects reachable.
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.
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.
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.
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⟩⟩
def embedId (object : Unique.ObjectId) : Shared.ObjectId := ⟨object.index⟩
def embedReference (object : Unique.ObjectId) : Shared.Reference := .owned (embedId object)
def embedSlots {Key : Type} (slots : List (Key × Unique.Slot)) : List (Key × Shared.Slot) :=
slots.map (fun entry => (entry.1, entry.2.map embedReference))
def embedObject (object : Unique.Object) : Shared.Object :=
⟨object.className, embedSlots object.fields⟩
def embedState (state : Unique.State) : Shared.State :=
⟨state.objects.map (fun entry => (embedId entry.1, embedObject entry.2)),
embedSlots state.variables, state.nextId⟩
def embedPlace : Unique.Place → Shared.Place
| .variable name => .variable name
| .field base name => .field (embedPlace base) name
def embedValue : Unique.Value → Shared.Value
| .give source => .give (embedPlace source)
| .new name arguments => .new name (arguments.map embedValue)
def embedStatement (statement : Unique.Statement) : Shared.Statement :=
⟨statement.destination, embedValue statement.value⟩
def embedClasses (classes : Unique.Classes) : Shared.Classes :=
classes.map (fun entry => (entry.1, ⟨entry.2.fields, .classType⟩))
def embedProgram (program : Unique.Program) : Shared.Program :=
⟨embedClasses program.classes, program.body.map embedStatement⟩
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.
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.
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⟩