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

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:

\[ d ::= \mathsf{class}\ C\ \{f_1,\ldots,f_n\}. \]

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.

Unique/Syntax:ClassName
abbrev ClassName := String
Unique/Syntax:FieldName
abbrev FieldName := String
Unique/Syntax:Class
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:

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

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:

\[ t ::= \mathsf{let}\ x=e. \]

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.

Unique/Syntax:VariableId
abbrev VariableId := String
Unique/Syntax:Place
inductive Place where
  | variable (name : VariableId)
  | field (base : Place) (name : FieldName)
  deriving DecidableEq, Repr
Unique/Syntax:Value
inductive Value where
  | give (source : Place)
  | new (className : ClassName) (arguments : List Value)
  deriving Repr
Unique/Syntax:Statement
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\).

Common/FiniteMap:FiniteMap
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\):

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

For a declaration \(\mathsf{class}\ C\ \{f_1,\ldots,f_n\}\), the table contains \(\Delta(C)=[f_1,\ldots,f_n]\).

Unique/Syntax:Classes
abbrev Classes := List (ClassName × Class)
Unique/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.

Unique/Soundness:ClassesWellFormed
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:

\[ \alpha,\beta\in\mathsf{ObjectId} =\{\mathsf{obj}(n)\mid n\in\mathbb N\}, \qquad \operatorname{index}(\mathsf{obj}(n))=n. \]
Unique/Syntax:ObjectId
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:

\[ \begin{aligned} s &::= \bot \mid \alpha \\ o &::= C\{f_1:s_1,\ldots,f_n:s_n\}. \end{aligned} \]
Unique/State:Slot
abbrev Slot := Option ObjectId
Unique/State:Object
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\):

\[ \begin{aligned} O &\in \mathsf{ObjectId}\rightharpoonup\mathsf{Object} \\ V &\in \mathsf{VariableId}\rightharpoonup\mathsf{Slot} \\ \nu &\in \mathbb N \\ S &::= \langle O,V,\nu\rangle. \end{aligned} \]

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.

Unique/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 its allocation counter is zero:

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

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

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

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

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

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.

Unique/State:StoragePlace
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:

\[ \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\leq i\leq n. \end{aligned} \]

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\).

Unique/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

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\).

Unique/State:Updated
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:

\[ 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.

Unique/Frames:Frame
structure Frame (Instruction : Type) where
  variables : List (VariableId × Slot)
  code : List Instruction
  deriving Repr
Unique/Frames:Configuration
structure Configuration (Instruction : Type) where
  objects : List (ObjectId × Object)
  nextId : Nat
  frame : Option (Frame Instruction)
  deriving Repr
Unique/Frames:Configuration.running
def Configuration.running (state : State) (code : List Instruction) : Configuration Instruction :=
  ⟨state.objects, state.nextId, some ⟨state.variables, code⟩⟩
Unique/Frames:Configuration.initial
def Configuration.initial (code : List Instruction) : Configuration Instruction :=
  .running State.empty code
Unique/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.

Unique/State:Live
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
Unique/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)) }
Unique/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.

Unique/Frames:Configuration.finished
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:

\[ \frac{\href{#claim-given.lookup}{S[x]}=\alpha}{S\vdash x\Downarrow x:\alpha} \quad\text{Variable} \]
\[ \frac{ S\vdash p\Downarrow q:\beta \qquad \href{#claim-given.lookup}{S[\beta.f]}=\alpha }{S\vdash p.f\Downarrow\beta.f:\alpha} \quad\text{Field} \]

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.

Unique/Step:Resolve
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

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

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:

\[ \frac{\href{#claim-given.resolution}{S\vdash p\Downarrow q:\alpha}}{ \Delta\vdash\langle S,p\mathord{\to}\rangle \Downarrow\langle \href{#claim-given.update}{S[q\leftarrow\bot]},\alpha\rangle } \quad\text{Give} \]

Construct. Evaluate the arguments from left to right, then allocate the object and put their results into its fields in declaration order.

\[ \frac{ \begin{gathered} \href{#claim-given.programs}{\Delta(C)}=[f_1,\ldots,f_n] \\ \Delta\vdash\langle S_{i-1},e_i\rangle \Downarrow\langle S_i,\alpha_i\rangle \quad\text{for each }i=1,\ldots,n \\ \beta\notin\operatorname{dom}(O_n) \end{gathered} }{ \Delta\vdash\langle S_0,\mathsf{new}\ C(e_1,\ldots,e_n)\rangle \Downarrow\langle S',\beta\rangle } \quad\text{Construct} \]

where \(S_0\) is the starting storage and \(S_i\) is the storage after the first \(i\) arguments, with

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

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.

Unique/Step:Eval
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⟩
Unique/Step:EvalArgs
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)
Unique/Step:State.allocate
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:

\[ S'[x\mapsto\alpha]=\langle O',V'[x\mapsto\alpha],\nu'\rangle. \]

The domain \(\operatorname{dom}(V')\) is the set of variable names already present.

The local binding rule is:

\[ \frac{ \begin{gathered} \Delta\vdash\langle S,e\rangle\Downarrow\langle S',\alpha\rangle \\ S'=\langle O',V',\nu'\rangle \qquad x\notin\operatorname{dom}(V') \end{gathered} }{ \Delta\vdash\langle S,(\mathsf{let}\ x=e)::P\rangle \rightsquigarrow\langle S'[x\mapsto\alpha],P\rangle } \quad\text{Let} \]

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:

\[ \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 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.

Unique/Step:State.bind
def State.bind (state : State) (name : VariableId) (object : ObjectId) : State :=
  { state with variables := (name, some object) :: state.variables }
Unique/Step:Step
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⟩
Unique/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
Unique/Frames:baseOperation
def baseOperation (classes : Classes) : LocalStep Statement :=
  fun before code after rest => Dada.Unique.Step classes ⟨before, code⟩ ⟨after, rest⟩
Unique/Frames:patternOperation
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:

\[ \frac{}{\Delta\vdash K\longrightarrow^{*}K} \qquad \frac{ \href{#claim-given.steps}{\Delta\vdash K\longrightarrow K'} \qquad \Delta\vdash K'\longrightarrow^{*}K'' }{\Delta\vdash K\longrightarrow^{*}K''}. \]
Unique/Frames:Steps
def Steps (operation : LocalStep Instruction) (before after : Configuration Instruction) : Prop :=
  ∃ count, StepsExactly operation before count after
Unique/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 next step is possible:

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

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.

Unique/Frames: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.

Unique/FrameChecks:lifetime
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:

  1. Create the token and put its reference in t.
  2. Create a box and move t into its value field, leaving t empty.
  3. Follow b to the box and move the field’s reference into u.

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.

Unique/Examples:give_execution
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.

Unique/Examples:nested_constructor
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:

\[ \neg\exists K'.\; \bigl(\Delta\vdash K_{\mathrm{bad}}\longrightarrow^{*}K'\bigr) \;\land\;\mathsf{Finished}(K'). \]

Zero steps leave the statement pending, and a nonempty execution would need a first step, which does not exist.

Unique/Examples:second_give_fails
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:

\[ \mathsf{Allocated}_S(\alpha)\iff\alpha\in\operatorname{dom}(O). \]
Unique/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. Write \(\mathsf{Live}_S(\alpha)\) for the judgment defined by these two rules:

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

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.

Unique/State:Live
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:

\[ \frac{\alpha\in R}{\mathsf{Live}_{S;R}(\alpha)}. \]

The variable and field rules are otherwise the same. Pending results count as roots even though they are not entries in the variable table.

Unique/State:LiveWith
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.

Unique/State:References
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))
Unique/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
  referencesUnique : (References state).Nodup
  referencesComplete : ∀ id, id ∈ References state ↔ Allocated state id
Unique/Soundness:WellFormedWith
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.

Unique/RootedChecks:younger_child
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.

Unique/RootedChecks:unreachable_cycle
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:

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

Thus every allocated object has an owning path from a variable, and following owning paths cannot reach a missing object.

Unique/Liveness:WellFormed.live_iff_allocated
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.

Unique/Liveness:WellFormed.owner_count
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.

Unique/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 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.

Unique/Frames:base_soundness
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\):

\[ \begin{aligned} b &::= x \mid C\mathord{\to}\{f_1:x_1,\ldots,f_n:x_n\} \\ t &::= \mathsf{let}\ b=e. \end{aligned} \]

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.

Unique/Unpacking:Pattern
inductive Pattern where
  | variable (name : VariableId)
  | unpack (className : ClassName) (fields : List (FieldName × VariableId))
  deriving DecidableEq, Repr
Unique/Unpacking:Statement
structure Statement where
  pattern : Pattern
  value : Value
  deriving Repr
Unique/Unpacking:Configuration
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:

\[ \frac{ \begin{gathered} \Delta\vdash\langle S,e\rangle\Downarrow\langle S',\alpha\rangle \\ \Delta(C)=[f_1,\ldots,f_n] \qquad S'=\langle O',V',\nu'\rangle \\ O'(\alpha)=C\{f_1:s_1,\ldots,f_n:s_n\} \\ x_1,\ldots,x_n\text{ are distinct} \qquad x_i\notin\operatorname{dom}(V')\quad(1\leq i\leq n) \end{gathered} }{ \Delta\vdash \langle S,(\mathsf{let}\ C\mathord{\to}\{f_1:x_1,\ldots,f_n:x_n\}=e)::P\rangle \rightsquigarrow_u\langle S'',P\rangle } \quad\text{Unpack} \]

where

\[ S''=\left\langle O'\setminus\{\alpha\},\; V'[x_1\mapsto s_1,\ldots,x_n\mapsto s_n],\; \nu' \right\rangle. \]

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.

Unique/Unpacking:Transfer
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)
Unique/Unpacking:Bind
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⟩
Unique/Unpacking:Step
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.

Unique/Frames:pattern_preservation
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.

Unique/UnpackingChecks:unpack_after_move
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⟩