Given: operational semantics
This language studies transfer of ownership. Variables and object fields hold references to objects. Giving a reference moves it to its destination and leaves its source empty; constructing an object moves references into its fields.
A class declaration \(d\) names a class and its fields. Write \(C\) for a class name in \(\mathsf{ClassName}\), and \(f\) for a field name in \(\mathsf{FieldName}\). The field count \(n\) is a natural number, including zero:
Fields are distinct and listed in constructor-argument order. They have names but no declared types. An empty class still has objects, so this language needs no primitive values. Subscripts and primes distinguish names in the same category.
abbrev ClassName := String
abbrev FieldName := String
structure Class where
fields : List FieldName
deriving DecidableEq, Repr
Places, expressions, and statements
A place expression \(p\) follows a route from a variable through zero or
more fields. Write \(x\) for a variable name in \(\mathsf{VariableId}\).
A value expression \(e\) produces an owning reference. Giving a place,
p→, is the only way to obtain a value from an existing place. A constructor
creates an object from the values of its argument expressions:
Constructor arguments can themselves be constructors or gives of places.
A statement \(t\) determines what the machine executes next. In this language, the only statement evaluates an expression and binds its result to a fresh variable:
Expressions evaluate within a statement; they do not choose the next statement.
Each let introduces a distinct runtime variable. This fragment has no shadowing,
scopes, function calls, assignment, or destruction.
abbrev VariableId := String
inductive Place where
| variable (name : VariableId)
| field (base : Place) (name : FieldName)
deriving DecidableEq, Repr
inductive Value where
| give (source : Place)
| new (className : ClassName) (arguments : List Value)
deriving Repr
structure Statement where
letValue ::
destination : VariableId
value : Value
deriving Repr
Programs
Write \(A\rightharpoonup B\) for finite partial maps from domain \(A\) to codomain \(B\), and \(\mathsf{List}(A)\) for finite ordered sequences of elements of \(A\).
structure FiniteMap (Key Value : Type) where
entries : List (Key × Value)
uniqueKeys : (entries.map Prod.fst).Nodup
A program \(\Pi\) supplies class declarations and an ordered sequence of statements. Its class table \(\Delta\) maps each declared class name to its field names in declaration order. Each class name is declared once.
A statement sequence \(P\) is empty, written \([]\), or has a first statement \(t\) followed by a sequence \(P\), written \(t::P\):
For a declaration \(\mathsf{class}\ C\ \{f_1,\ldots,f_n\}\), the table contains \(\Delta(C)=[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
Objects and slots
An object identity \(\alpha\) is a tagged natural number. The tag keeps identities distinct from ordinary numbers. We also use \(\beta\) for an object identity; \(\operatorname{index}\) extracts its number:
structure ObjectId where
index : Nat
deriving DecidableEq, Repr
A slot is a variable or object field. Its contents \(s\), in the category \(\mathsf{Slot}\), are empty, written \(\bot\), or hold an owning reference, represented by an object identity. An object \(o\), in the category \(\mathsf{Object}\), has a class name and an ordered list of named field slots. All references in this language are owners:
abbrev Slot := Option ObjectId
structure Object where
className : ClassName
fields : List (FieldName × Slot)
deriving DecidableEq, Repr
A storage state \(S\) has an object table \(O\), a variable table \(V\), and an allocation counter \(\nu\):
The counter supplies \(\mathsf{obj}(\nu)\) for the next allocation, then increases by one. Finite-map notation assumes distinct keys. The tables and field lists record empty slots as well as occupied ones.
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 its allocation counter is zero:
Here \(\varnothing\) denotes the empty map.
def State.empty : State := ⟨[], [], 0⟩
A storage place \(q\) selects one slot directly: either a variable or a field of a particular object:
A place expression such as b.value describes a route to a slot; a storage place
such as \(\mathsf{obj}(1).\mathsf{value}\) identifies the slot itself.
inductive StoragePlace where
| variable (name : VariableId)
| field (object : ObjectId) (name : FieldName)
deriving DecidableEq, Repr
For \(S=\langle O,V,\nu\rangle\), write \(S[q]=s\) for slot lookup at a storage place. It is a partial operation, defined by:
Lookup has no result for an absent variable, object, or field. An existing empty slot has the defined result \(\bot\). An occupied slot contains an object identity, not that object’s data; the data is in \(O\).
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
For a slot with defined lookup, \(S[q\leftarrow s]\) replaces its contents and leaves all other slots, object identities, class names, and the counter unchanged. This update preserves the slot even when its new contents are \(\bot\).
inductive Updated : State → StoragePlace → Slot → State → Prop where
| variable (objects : List (ObjectId × Object)) (nextId : Nat)
(leading suffix : List (VariableId × Slot)) (name : VariableId) (old new : Slot) :
Updated ⟨objects, leading ++ (name, old) :: suffix, nextId⟩ (.variable name) new
⟨objects, leading ++ (name, new) :: 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) (old new : Slot) :
Updated ⟨before ++ (parent, ⟨className, leading ++ (name, old) :: suffix⟩) :: after,
variables, nextId⟩ (.field parent name) new
⟨before ++ (parent, ⟨className, leading ++ (name, new) :: suffix⟩) :: after,
variables, nextId⟩
The machine
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 object} : (name, some object) ∈ state.variables → Live state object
| field {parent object data name} :
Live state parent → (parent, data) ∈ state.objects →
(name, some object) ∈ data.fields → Live state 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
Operational semantics
Resolving a place
Place resolution, written \(S\vdash p\Downarrow q:\alpha\), follows route \(p\) to a storage place \(q\) holding reference \(\alpha\). These two rules define it:
Each slot along the route must hold a reference. Undefined lookup and the empty contents \(\bot\) satisfy neither rule’s lookup premise. Resolution itself changes nothing.
inductive Resolve (state : State) : Place → StoragePlace → ObjectId → Prop where
| variable {name object} :
(name, some object) ∈ state.variables →
Resolve state (.variable name) (.variable name) object
| field {base source parent data name object} :
Resolve state base source parent →
(parent, data) ∈ state.objects →
(name, some object) ∈ data.fields →
Resolve state (.field base name) (.field parent name) object
Evaluating an expression
Expression evaluation, written
produces an owning reference \(\alpha\) and updated storage \(S'\). The following rules define successful evaluation, including nested expressions.
Give. Resolve the place and empty its slot. Return the reference taken:
Construct. Evaluate the arguments from left to right, then allocate the object and put their results into its fields in declaration order.
where \(S_0\) is the starting storage and \(S_i\) is the storage after the first \(i\) arguments, with
Here \(\operatorname{dom}(O_n)\) is the set of allocated identities, and \(O_n[\beta\mapsto o]\) adds the fresh object’s entry.
With no arguments, there are no argument premises and allocation uses \(S_n=S_0\). Argument results remain owned by the ongoing evaluation until placed in the new object’s fields; they are not copied.
An empty slot, a missing field, or an unknown class has no successful evaluation. Giving the same slot twice as constructor arguments fails on the second give. An expression runs within one statement transition, but it can still fail.
inductive Eval (classes : Classes) : State → Value → State → ObjectId → Prop where
| give {state cleared : State} {path : Place} {source : StoragePlace} {object : ObjectId} :
Resolve state path source object →
Take state source object cleared →
Eval classes state (.give path) cleared object
| new {state evaluated : State} {className : ClassName} {declaration : Class}
{arguments : List Value} {objects : List ObjectId} :
(className, declaration) ∈ classes →
EvalArgs classes state arguments evaluated objects →
objects.length = declaration.fields.length →
ObjectId.mk evaluated.nextId ∉ evaluated.objects.map Prod.fst →
Eval classes state (.new className arguments)
(evaluated.allocate className declaration.fields objects) ⟨evaluated.nextId⟩
inductive EvalArgs (classes : Classes) : State → List Value → State → List ObjectId → Prop where
| nil (state : State) : EvalArgs classes state [] state []
| cons {before middle after : State} {argument : Value} {arguments : List Value}
{object : ObjectId} {objects : List ObjectId} :
Eval classes before argument middle object →
EvalArgs classes middle arguments after objects →
EvalArgs classes before (argument :: arguments) after (object :: objects)
def State.allocate (state : State) (className : ClassName) (fields : List FieldName)
(arguments : List ObjectId) : State :=
⟨(⟨state.nextId⟩, ⟨className, fields.zip (arguments.map some)⟩) :: state.objects,
state.variables, state.nextId + 1⟩
Executing a statement
To execute let x = e, evaluate the expression completely, then put its result
in the new variable x. For the resulting storage
\(S'=\langle O',V',\nu'\rangle\), write \(V'[x\mapsto\alpha]\) for the
variable table extended with that binding, and abbreviate the updated state as:
The domain \(\operatorname{dom}(V')\) is the set of variable names already present.
The local binding rule is:
The remaining statements keep their order. If evaluation fails or the variable already exists, the statement has no transition. There is no recovery transition or separately observable state partway through a failed expression.
The local rule above is auxiliary. 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 Unique/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) (object : ObjectId) : State :=
{ state with variables := (name, some object) :: state.variables }
inductive Step (classes : Classes) : Configuration → Configuration → Prop where
| letValue {state evaluated : State} {destination : VariableId} {value : Value}
{object : ObjectId} {rest : List Statement} :
destination ∉ evaluated.variables.map Prod.fst →
Eval classes state value evaluated object →
Step classes ⟨state, ⟨destination, value⟩ :: rest⟩
⟨evaluated.bind destination object, 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.Unique.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⟩
Finite executions and failure
A finite execution, written \(\Delta\vdash K\longrightarrow^{*}K'\), consists of zero or more statement steps. These rules define it:
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 next step is possible:
This is how execution goes wrong. For example, trying to give through an absent variable or an empty field yields no expression evaluation and therefore no statement step. Undefined lookup alone is a property of storage; attempting an operation that requires that lookup is what leaves the machine stuck.
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after
Worked executions
An empty class provides a value we can move:
class Token {}
let t = new Token();
Starting with empty storage, one step creates a Token object and puts its
reference in t. No statements remain, but the initial frame is still live.
The second step pops it and collects the object, leaving an empty heap and
counter one. The check also covers the single exit step of an empty program.
example :
Step (baseOperation classes) (.initial []) (Configuration.terminal (Instruction := Statement) 0) ∧
Step (baseOperation classes) (.initial code) (.running observed []) ∧
("t", some 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 _))
A field can receive a reference and later give it away:
class Token {}
class Box { value }
let t = new Token();
let b = new Box(t→);
let u = b.value→;
Starting with empty storage, the machine takes three steps:
- Create the token and put its reference in
t. - Create a box and move
tinto itsvaluefield, leavingtempty. - Follow
bto the box and move the field’s reference intou.
At this pre-exit observation, the statements are exhausted. Variable b owns the box and u
owns the token; t and the box’s value field are empty. Giving the field moves
its contents; the containing box remains in place.
example : Framed.StepsExactly (Framed.baseOperation exampleClasses)
(.initial (tokenProgram ++ boxProgram ++ moveProgram)) 3 (.running movedState []) := by
have classesWf : ClassesWellFormed exampleClasses := by simp [ClassesWellFormed, exampleClasses, or_imp, and_imp, forall_and]
have tokenWf : WellFormed exampleClasses tokenState := (createToken []).preserves_wellFormed classesWf (WellFormed.empty _)
have boxWf : WellFormed exampleClasses boxState := (createBox []).preserves_wellFormed classesWf tokenWf
have movedWf : WellFormed exampleClasses movedState := (giveField []).preserves_wellFormed classesWf boxWf
exact .step (Framed.local_step (createToken _) tokenWf)
(.step (Framed.local_step (createBox _) boxWf)
(.step (Framed.local_step (giveField []) movedWf) (.refl _)))
Constructor arguments can create their own objects:
class Token {}
class Box { value }
let b = new Box(new Token());
Starting with empty storage, this is one statement step. Evaluate new Token()
first, then put its reference in the newly created box’s value field. Bind the
box’s reference to b. The pre-exit observation contains both objects, with
no temporary source variable needed in the program.
example : Framed.Step (Framed.baseOperation exampleClasses)
(.initial [⟨"b", .new "Box" [.new "Token" []]⟩]) (.running nestedState []) :=
Framed.local_step nested_operation (nested_operation.preserves_wellFormed
(by simp [ClassesWellFormed, exampleClasses, or_imp, and_imp, forall_and]) (WellFormed.empty _))
Starting with the pre-exit storage of refgiven.example.field, try:
let v = b.value→;
Let \(\Delta\) be that example’s class table, and let \(K_{\mathrm{bad}}\)
put that storage in a live frame with this one remaining statement.
It is stuck: b still holds the box’s reference, but its value field is empty.
The give cannot evaluate, so the statement cannot execute. Giving once leaves
no reference behind for a second give.
Execution from this configuration cannot finish:
Zero steps leave the statement pending, and a nonempty execution would need a first step, which does not exist.
example : Framed.Stuck (Framed.baseOperation exampleClasses)
(.running badConfiguration.state badConfiguration.code) ∧
¬ ∃ after, Framed.Steps (Framed.baseOperation exampleClasses)
(.running badConfiguration.state badConfiguration.code) after ∧ after.finished := by
refine ⟨framed_second_give_stuck, ?_⟩
rintro ⟨after, ⟨_, execution⟩, finished⟩
cases execution with
| refl => exact framed_second_give_stuck.1 finished
| step first _ => exact framed_second_give_stuck.2 ⟨_, first⟩
Liveness and well-formedness
For \(S=\langle O,V,\nu\rangle\), an object is allocated when its identity occurs 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. Write \(\mathsf{Live}_S(\alpha)\) for the judgment defined by these two rules:
An empty slot contributes no edge to such a path. Allocation and liveness are properties of the object graph, independent of how the state was produced.
inductive Live (state : State) : ObjectId → Prop where
| variable {name object} : (name, some object) ∈ state.variables → Live state object
| field {parent object data name} :
Live state parent → (parent, data) ∈ state.objects →
(name, some object) ∈ data.fields → Live state object
During expression evaluation, a result may have left its source slot without yet entering a constructor or local binding. Such a result is a pending root. Let \(R\) be the list of object identities held by these pending results.
An object is live with pending roots, written \(\mathsf{Live}_{S;R}(\alpha)\), when it can be reached from a variable or an identity in \(R\), following initialized fields. This extends ordinary liveness with one additional starting rule:
The variable and field rules are otherwise the same. Pending results count as roots even though they are not entries in the variable table.
inductive LiveWith (state : State) (pending : List ObjectId) : ObjectId → Prop where
| pending {object} : object ∈ pending → LiveWith state pending object
| variable {name object} : (name, some object) ∈ state.variables → LiveWith state pending object
| field {parent object data name} :
LiveWith state pending parent → (parent, data) ∈ state.objects →
(name, some object) ∈ data.fields → LiveWith state pending object
The following conditions describe storage between statements, including before the first statement. Write \(\mathsf{WF}_{\Delta}(S)\) when the state meets all these conditions:
- Object-table keys and variable names are each distinct.
- Every object’s class is declared. Its field names occur exactly in declaration order, without duplicates, including fields whose slots are empty.
- Every allocated identity \(\alpha\) satisfies \(\href{#claim-given.identities}{\operatorname{index}(\alpha)}<\nu\). This bounds the identities already used, so the next allocation is fresh.
- Every allocated object is live: a path from a variable reaches it through initialized fields.
- The references in all variable slots and all object fields, counted by occurrence, contain each allocated object identity exactly once and contain no other identity.
The last condition excludes both duplicate ownership and references to missing objects. Two slots containing the same identity count as two references even though their contents are equal. Rootedness is a separate condition: a cycle with no variable root does not become valid merely because each object has one incoming reference. Object identities do not impose an ordering on field edges.
Within an expression, write \(\mathsf{WF}_{\Delta}(S;R)\) for the version with pending roots. Rootedness uses \(\mathsf{Live}_{S;R}\), and reference counting includes every occurrence in \(R\) as well as the variable slots and object fields. The other conditions are unchanged. Thus moving an owner out of a field can leave that slot empty while the returned object remains rooted in the ongoing evaluation.
def References (state : State) : List ObjectId :=
state.variables.filterMap (fun binding => binding.2) ++
state.objects.flatMap (fun entry => entry.2.fields.filterMap (fun field => field.2))
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
referencesUnique : (References state).Nodup
referencesComplete : ∀ id, id ∈ References state ↔ Allocated state id
structure WellFormedWith (classes : Classes) (state : State) (pending : List ObjectId) : 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
referencesUnique : (pending ++ References state).Nodup
referencesComplete : ∀ id, id ∈ pending ++ References state ↔ Allocated state id
The well-formedness invariant accepts this storage, with allocation counter 3:
variables: b → Box#1
objects: Box#1.value → Token#2
Token#2 has no fields
Each object has exactly one incoming reference and is reached from b.
The field points from identity 1 to identity 2; the target’s index is larger.
This is an example of admissible storage, not a claim that the constructor-only
Given language produces it from an empty state.
Taking b.value empties that field and returns identity 2.
The checked preservation result establishes well-formedness with identity 2
as a pending root; identity 1 remains rooted at b.
No allocation-order comparison is needed to preserve this state.
example : WellFormed classes youngerChild ∧
¬ ((2 : ObjectId).index < (1 : ObjectId).index) ∧
WellFormedWith classes takenChild [2] := by
exact ⟨youngerChild_wellFormed, by decide, take_younger.preserves_pending youngerChild_wellFormed.with_empty⟩
A single allocated Box#1 with value pointing back to itself and no variables
fails well-formedness, even with allocation counter 2.
Its one field supplies exactly one incoming reference to the allocated object,
but no path starts at a variable. It is not live.
This separates ownership counting from rootedness: the former does not imply the latter, even when all references are unique.
example : ¬ WellFormed classes unreachableCycle := by
intro wf
have noLive : ∀ id, ¬ Live unreachableCycle id := by
intro id live
induction live with
| «variable» member => exact List.not_mem_nil member
| field _ _ _ ih => exact ih
exact noLive 1 (wf.rooted 1 (by simp [Allocated, unreachableCycle]))
In every well-formed state, an object is live exactly when it is allocated:
Thus every allocated object has an owning path from a variable, and following owning paths cannot reach a missing object.
theorem WellFormed.live_iff_allocated (wf : WellFormed classes state) :
Live state object ↔ Allocated state object :=
⟨wf.live_allocated, wf.allocated_live⟩
In every well-formed state, each allocated object has exactly one owning reference across all variable slots and object fields. This counts the slot that immediately holds its reference: a path through several enclosing objects does not add extra owners of its final target.
theorem WellFormed.owner_count (wf : WellFormed classes state)
(allocated : Allocated state object) : (References state).count object = 1 := by
exact wf.referencesUnique.count_of_mem ((wf.referencesComplete object).mpr 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 its empty initial state has a well-formed state. This includes zero steps, intermediate configurations, and completed executions.
Consequently, every allocated object remains live and has exactly one owning reference. The theorem covers successful execution; it does not promise that a program can always take another step.
theorem base_soundness (classesWf : ClassesWellFormed classes)
(trace : StepsExactly (baseOperation classes) (.initial code) count after) :
WellFormed classes after.state :=
trace.preserves (fun _ _ _ _ wf operation => operation.preserves_wellFormed classesWf wf)
(WellFormed.empty _)
Unpacking
An unpacking pattern consumes an object and transfers its field slots into new variables. This extends the statement syntax with a binding pattern \(b\):
In a pattern, f: x names the field f and its new variable x; f alone is
shorthand for f: f. The pattern must name every declared field exactly once,
and its variable names must be distinct. Fields may be listed in any order.
This first version has flat patterns, with no _ or .. entries.
The expression p→ transfers the reference out of p. The pattern
C → { ... } then removes the enclosing object and transfers its components.
An ordinary field give leaves the enclosing object in place. An empty class
can be consumed with C → {}.
This extension adds patterns while keeping expression evaluation unchanged. The preceding results concern single-variable bindings.
inductive Pattern where
| variable (name : VariableId)
| unpack (className : ClassName) (fields : List (FieldName × VariableId))
deriving DecidableEq, Repr
structure Statement where
pattern : Pattern
value : Value
deriving Repr
structure Configuration where
state : State
code : List Statement
deriving Repr
To execute let C → { ... } = e, evaluate e, check that its result names a
C object, and transfer that object’s slots into fresh variables. An initialized
field becomes an initialized variable; an empty field becomes an empty variable.
The consumed object’s entry is removed from the object table.
Write \(\Delta\vdash K\rightsquigarrow_u K'\) for the extended transition relation. It has the earlier Let rule, read over the extended statement syntax, and the following Unpack rule. We display the pattern fields in declaration order:
where
Here \(O'\setminus\{\alpha\}\) removes the object-table entry for \(\alpha\). The variable-map extension adds exactly the displayed slots, including those containing \(\bot\). All other objects and variables, and the allocation counter, retain their values from \(S'\).
The slots move together within one statement step. No object stored in a field is removed by unpacking its container. A class mismatch or an already allocated destination variable gives this rule no transition, even when that variable’s slot is empty.
These are local-frame operations. The program machine uses patternOperation
in the same collection and exit rules as single-variable bindings.
inductive Transfer : List (FieldName × VariableId) → List (FieldName × Slot) → List (VariableId × Slot) → Prop where
| nil : Transfer [] [] []
| cons {field name slot pattern before after bindings} :
Transfer pattern (before ++ after) bindings →
Transfer ((field, name) :: pattern) (before ++ (field, slot) :: after)
((name, slot) :: bindings)
inductive Bind (classes : Classes) : State → ObjectId → Pattern → State → Prop where
| variable {state object name} :
name ∉ state.variables.map Prod.fst →
Bind classes state object (.variable name) (state.bind name object)
| unpack {before after variables nextId object className fields pattern bindings declaration} :
(className, declaration) ∈ classes →
fields.map Prod.fst = declaration.fields →
(pattern.map Prod.fst).Nodup →
(pattern.map Prod.snd).Nodup →
(∀ name ∈ pattern.map Prod.snd, name ∉ variables.map Prod.fst) →
Transfer pattern fields bindings →
Bind classes ⟨before ++ (object, ⟨className, fields⟩) :: after, variables, nextId⟩
object (.unpack className pattern)
⟨before ++ after, bindings ++ variables, nextId⟩
inductive Step (classes : Classes) : Configuration → Configuration → Prop where
| letValue {before evaluated after pattern value object rest} :
Eval classes before value evaluated object →
Bind classes evaluated object pattern after →
Step classes ⟨before, ⟨pattern, value⟩ :: rest⟩ ⟨after, rest⟩
For a well-formed class table, every extended step from well-formed storage preserves well-formedness. Unpacking transfers every field slot and removes only the consumed container, so its children retain their owners.
theorem pattern_preservation (classesWf : ClassesWellFormed classes)
(wf : WellFormed classes before.state) (step : Step (patternOperation classes) before after) :
WellFormed classes after.state :=
step.preserves (fun _ _ _ _ wf operation => operation.preserves_wellFormed classesWf wf) wf
Unpacking also works after a field has been moved:
class Token {}
class Pair { left, right }
let p = new Pair(new Token(), new Token());
let taken = p.left→;
let Pair → { left, right } = p→;
After the three-step execution, taken owns the first token and
right owns the second. Variables p and left have empty slots. The pair
object has been removed; both token objects remain. The configuration is finished.
The empty field does not produce a value: its new binding left is empty too.
Trying to evaluate left→ afterward would have no result.
example : Steps exampleClasses ⟨State.empty, unpackingProgram⟩ ⟨unpacked, []⟩ ∧
(Configuration.mk unpacked []).finished ∧
¬ ∃ after object, Eval exampleClasses unpacked (.give (.variable "left")) after object := by
exact ⟨unpacking_execution, rfl, moved_field_has_no_value⟩