Assignment
Refill a field
An empty field can receive a new value. Suppose w has type
given Wrapper.{-resource}, with these declarations:
class Resource {}
class Wrapper { resource: Resource }
w.resource = new Resource();
The statement checks, and w has the whole type given Wrapper afterwards.
The assignment p = e installs the value of e into the slot p.
It does not call a destructor
for the previous contents.
The negative view entry
records that resource exists and is empty.
example :
store classes partialContext (.field (.variable "w") "resource") (.whole "Resource") = some wrapper ∧
StatementTyped classes [] partialContext
(.store (.field (.variable "w") "resource") (.new "Resource" [])) wrapper := by
constructor
· decide
· apply StatementTyped.store (middle := partialContext) (ty := .whole "Resource")
· exact .lift (by decide)
(.new (declaration := ⟨[], .classType⟩) (by decide) (.nil (by decide)) (by decide) (by decide))
(by decide)
· decide
A complete replacement lifetime
The same frame can retain a partial wrapper across a destructor call, refill its field, and then consume both the wrapper and the replacement:
class Resource {
drop { let Resource → {} = self→; }
}
class Wrapper { resource: Resource }
let w = new Wrapper(new Resource());
drop w.resource;
w.resource = new Resource();
let Wrapper → { resource: r } = w→;
drop r;
This checks as a complete program, including the destructor body and the
initial frame’s consumption obligation.
Wrapper needs no destructor because the program explicitly
unpacks it. Every finite
execution, defined below, is safe: each reached
state either has no frames or can take another step. If all frames have exited,
the heap is empty.
example : ProgramTyped refillProgram ∧
∀ configuration,
Steps classes.erase declarations (.initial refillProgram) configuration →
ConfigurationTyped classes declarations configuration ∧
¬ Stuck classes.erase declarations configuration ∧
(configuration.finished → configuration.objects = []) := by
refine ⟨refill_typed, ?_⟩
intro configuration trace
have safe := program_safety refill_typed trace
exact ⟨safe.1, safe.2.2, safe.1.finished_heap_empty⟩
Replace a class explicitly
Use explicit destruction
before storing over an owned class. With an initialized r: given Resource
and replacement: given Resource, this sequence checks:
class Resource {
drop { let Resource → {} = self→; }
}
drop r;
r = replacement→;
The destructor consumes the old resource. The store then moves the replacement
into the empty r slot, leaving replacement empty. During the destructor
call, the replacement remains rooted in the
suspended caller frame.
The example checks the destructor declaration and the two-statement sequence;
it assumes the two initial bindings.
example :
DeclarationsTyped classes declarations ∧
SequenceTyped classes declarations replacementBefore
[.dropClass "Resource" (.variable "r"), .store (.variable "r") (.give (.variable "replacement"))]
replacementAfter := by
constructor
· refine ⟨by decide, ?_⟩
intro entry member
have eq : entry = (.destructor "Resource", resourceDestructor) := by simpa [declarations] using member
cases eq
exact ⟨⟨by decide, by decide, by decide, rfl, ⟨⟨[], .classType⟩, by decide, rfl⟩⟩, resource_body⟩
· apply SequenceTyped.cons (middle := replacementMiddle)
· apply StatementTyped.call (declaration := resourceDestructor) (middle := replacementMiddle)
· simp [declarations]
· simp
· exact .lift (by decide)
(.cons (.give (by decide) (by decide) (by decide) (by decide)) (.nil (by decide))) (by decide)
· exact .none (by decide)
· apply SequenceTyped.cons (middle := replacementAfter)
· apply StatementTyped.store
(middle := replacementBefore.withCurrent [("r", none), ("replacement", none)])
(ty := .whole "Resource")
· exact .lift (by decide) (.give (by decide) (by decide) (by decide) (by decide)) (by decide)
· decide
· exact .nil (by decide)
An occupied class field cannot be overwritten, even when its class declares a
destructor. Given whole w: given Wrapper, this store is rejected:
w.resource = new Resource();
An empty local retains its declared storage type. An empty r that previously
held a Resource accepts another Resource, but rejects a Token:
class Token {}
r = new Resource(); // accepted from the empty-r state
r = new Token(); // rejected even from the empty-r state
These are separate checks from the same initial state.
example :
store classes wrapper (.field (.variable "w") "resource") (.whole "Resource") = none ∧
store classes emptyResource (.variable "r") (.whole "Resource") =
some (emptyResource.withCurrent [("r", some (.whole "Resource"))]) ∧
store classes emptyResource (.variable "r") (.whole "Token") = none := by decide
Structs and shared references
Struct replacement needs no destructor call. Consider these declarations:
struct Point {}
shared struct SharedPoint {}
struct Box { point: Point }
The following cases check independently:
| Destination’s current type | Assignment | Result |
|---|---|---|
p: given Point | p = new Point() | accepted |
s: shared SharedPoint | s = new SharedPoint() | accepted |
b: given Box | b.point = new Point() | accepted |
b: shared Box | store a shared Point into b.point | rejected |
A local slot holding a shared reference is writable. A field reached through shared access is not. Overwriting a struct reference does not run user code; collection reclaims its object only if no frame can still reach it.
This layer fixes a local’s permission as well as its nominal type: a local
inferred as given Point does not accept a shared Point. This is a typing
restriction, not a layout requirement. Both permissions have the same nominal
layout key.
example :
store classes point (.variable "p") (.whole "Point") = some point ∧
store classes sharedPoint (.variable "s") (.whole "SharedPoint" .shared) = some sharedPoint ∧
store classes (box .given) (.field (.variable "b") "point") (.whole "Point") = some (box .given) ∧
store classes (box .shared) (.field (.variable "b") "point") (.whole "Point" .shared) = none ∧
store classes point (.variable "p") (.whole "Point" .shared) = none ∧
layoutKey ⟨.given, "Point"⟩ = layoutKey ⟨.shared, "Point"⟩ := by decide
A shared-struct local can instead be overwritten and left for collection:
shared struct SharedPoint {}
let s = new SharedPoint();
s = new SharedPoint();
This also checks as a complete program. For every finite
execution, defined below, each reached state
either has no frames or can take another step; no frames means an empty heap.
The completion obligation
permits s to remain initialized, so it needs no explicit drop.
example : ProgramTyped overwriteProgram ∧
∀ configuration,
Steps classes.erase [] (.initial overwriteProgram) configuration →
ConfigurationTyped classes [] configuration ∧
¬ Stuck classes.erase [] configuration ∧
(configuration.finished → configuration.objects = []) := by
refine ⟨overwrite_typed, ?_⟩
intro configuration trace
have safe := program_safety overwrite_typed trace
exact ⟨safe.1, safe.2.2, safe.1.finished_heap_empty⟩
Partial values keep their views
Storing a partial value does not repair its missing fields. An empty local w
with fixed storage type given Wrapper can receive a
given Wrapper.{-resource} value; afterwards its current type is still
given Wrapper.{-resource}. It cannot be left behind when the frame finishes:
the class-consumption obligation
also applies to partial classes.
Unpacking remains an alternative
to repairing the container. The pattern Wrapper → { resource: r } gives the
empty r binding a fixed storage type given Resource, obtained from the
field declaration. Its current slot is empty, but it has not become untyped.
example :
store classes (wrapper.withCurrent [("w", none)]) (.variable "w") partialWrapper = some partialContext ∧
¬ Finished classes partialContext ∧
bindingTypes classes (.unpack "Wrapper" [("resource", "r")]) partialWrapper =
some [("r", ⟨.given, "Resource"⟩)] := by
refine ⟨by decide, ?_, by decide⟩
intro finished
exact (by decide : ¬ StructType classes partialWrapper)
(finished "w" partialWrapper (by simp [partialContext, wrapper, Context.withCurrent]))
The right-hand side runs before the destination is checked. For whole
w: given Wrapper, giving moves
w out, then the store refills the same local:
w = w→;
It checks and leaves w whole. Conversely, an empty w does not provide a
writable w.resource slot: a field store needs an initialized parent after
right-hand-side evaluation. Nominal knowledge of the field name is insufficient.
example :
StatementTyped classes [] wrapper (.store (.variable "w") (.give (.variable "w"))) wrapper ∧
store classes (wrapper.withCurrent [("w", none)])
(.field (.variable "w") "resource") (.whole "Resource") = none := by
constructor
· apply StatementTyped.store (middle := wrapper.withCurrent [("w", none)]) (ty := .whole "Wrapper")
· exact .lift (by decide) (.give (by decide) (by decide) (by decide) (by decide)) (by decide)
· decide
· decide
Syntax and fixed binding types
Assignment adds the statement p = e; to the Destructor statements.
Here p is a place and e is a
Shared value expression. Calls remain
statements with fresh result bindings; a call is not an assignment expression.
Bodies, declarations, and programs have the same components as in Destructors,
with statement lists drawn from this extended syntax.
inductive Statement where
| local (statement : Unpacking.Statement)
| call (destination : Option VariableId) (name : Name) (arguments : List Value)
| store (place : Place) (value : Value)
| dropStruct (place : Place)
deriving Repr
structure Body where
statements : List Statement
result : Option Value
deriving Repr
structure Declaration where
signature : Signature
body : Body
deriving Repr
structure Program where
classes : ClassTable
declarations : Declarations
main : List Statement
deriving Repr
A storage type is a nominal type name paired with a
permission. Taking the storage type
of a current value type forgets its view. Its layout key forgets
the permission too; given Foo and shared Foo have the same key.
A typing context contains two ordered maps with the same local names:
- Fixed binding types retain each local’s nominal type and permission.
- Current descriptions record either an empty slot or its present value type, including the view.
The current environment must be well formed. Each fixed type must be well formed and normalized as a whole type. Every initialized current description must agree with its binding’s fixed nominal type and permission. Empty descriptions carry no value view, but their fixed binding types remain.
Parameters begin with their declared fixed types and whole current types. A fresh variable binding infers its fixed type from its initializer’s type. Unpacking obtains fixed types from the nominal field declarations in pattern order, including for fields that are currently empty.
abbrev StorageType := FieldType
def storageType (ty : ValueType) : StorageType := ⟨ty.permission, ty.base⟩
def layoutKey (ty : StorageType) : ClassName := ty.className
structure Context where
bindings : List (VariableId × StorageType)
current : Environment
deriving DecidableEq, Repr
def Context.WellFormed (context : Context) (classes : ClassTable) : Prop :=
context.current.WellFormed classes ∧
context.bindings.map Prod.fst = context.current.map Prod.fst ∧
(∀ entry ∈ context.bindings, Admissible classes entry.2.toType) ∧
(∀ entry ∈ context.current, ∀ ty ∈ entry.2,
context.bindings.lookup entry.1 = some (storageType ty))
def initialContext (signature : Signature) : Context :=
⟨signature.parameters.map (fun p => (p.name, p.type)), signature.environment⟩
def bindingTypes (classes : ClassTable) (pattern : Unpacking.Pattern)
(ty : ValueType) : Option (List (VariableId × StorageType)) := do
match pattern with
| .variable name => some [(name, storageType ty)]
| .unpack name fields =>
let declaration ← classes.lookup name
fields.mapM fun (field, destination) => do
let fixed ← declaration.fields.lookup field
some (destination, fixed)
Static store operation
Replacing the view at a field path keeps all entries outside that subtree. A positive ancestor is expanded along the destination path so its unaffected siblings remain exposed. Entries beneath the overwritten path are removed; the incoming value’s entries are prefixed by that path and inserted. Finally, the result is normalized. The root nominal type and permission do not change. Incoming negative entries stay negative; an omitted interior does not become whole.
def replaceView (classes : ClassTable) (source incoming : ValueType) (path : Path) : ValueType :=
let retained := source.nominal.entries.flatMap fun entry =>
if path.isPrefixOf entry.path then []
else match entry with
| .negative _ => [entry]
| .positive initialPath =>
if initialPath.isPrefixOf path then
match Unique.Typing.classAt classes.nominal source.base initialPath with
| none => []
| some target =>
(Unique.Typing.remainingAfterMove classes.nominal target (path.drop initialPath.length)).map
(Unique.Typing.Entry.prepend initialPath)
else [entry]
normalize classes ⟨source.permission, ⟨source.base,
retained ++ incoming.nominal.entries.map (Unique.Typing.Entry.prepend path)⟩⟩
The static store operation takes a context after expression evaluation, a destination place, and an incoming value type. It returns an updated context, or fails. The input context must be well formed. The incoming type must be well formed and normalized.
For a local destination, its fixed type must match the incoming nominal type and permission. Its current slot must be empty or have a struct type.
For a field destination, the root must be initialized and the parent path must
focus to a type with given permission. The declared field type must match the
incoming nominal type and permission. The current field description must be
known and either empty or a struct. An omitted, inaccessible field cannot be
written merely because its declaration is known. The root’s view is updated
using view replacement.
The operation preserves the fixed binding map and requires the resulting context to be well formed. It accepts partial incoming views. It never implicitly consumes an occupied class, including a partial class.
def replaceable (classes : ClassTable) : SlotDescription → Bool
| none => true
| some ty => decide (StructType classes ty)
def storeCurrent (classes : ClassTable) (context : Context) (place : Place) (incoming : ValueType) : Option Environment := do
if !decide (context.WellFormed classes) || !decide (Admissible classes incoming) then none else do
let (root,path) := splitPlace place
let fixed ← context.bindings.lookup root
let slot ← context.current.lookup root
let result ← if path.isEmpty then do
if storageType incoming != fixed || !replaceable classes slot then none
else some (context.current.replace root (some incoming))
else do
let source ← slot
let parentPath := path.take (path.length - 1)
let field ← path.getLast?
let parent ← focus classes source parentPath
if parent.permission != .given then none else do
let declaration ← classes.lookup parent.base
let fieldType ← declaration.fields.lookup field
let previous ← fieldDescription classes parent field
if storageType incoming != fieldType || !replaceable classes previous then none
else some (context.current.replace root (some (replaceView classes source incoming path)))
some result
def store (classes : ClassTable) (context : Context) (place : Place)
(incoming : ValueType) : Option Context := do
let current ← storeCurrent classes context place incoming
let after := context.withCurrent current
if decide (after.WellFormed classes) then some after else none
Expression and argument typing use the existing Shared judgments on the current environment, retaining fixed bindings and requiring the resulting context to be well formed. Binding typing uses Shared’s binding judgment and extends the fixed map with the binding types. A local statement evaluates its initializer, then binds it.
A store statement first types its expression, producing an incoming type and an intermediate context. It then applies the static store operation to that intermediate context. The operation’s output is the statement’s output context. Thus an expression may empty the destination before the store, but cannot leave a missing ancestor along a field destination.
Calls and struct drops retain their Destructor rules, using these extended contexts. A call still requires a declared callee, correctly typed arguments, and a fresh destination matching its result signature.
inductive ExprTyped (classes : ClassTable) : Context → Value → ValueType → Context → Prop where
| lift {before after value ty} :
before.WellFormed classes →
Shared.Typing.ExprTyped classes before.current value ty after →
(before.withCurrent after).WellFormed classes →
ExprTyped classes before value ty (before.withCurrent after)
inductive ArgsTyped (classes : ClassTable) : Context → List Value → List FieldType → Context → Prop where
| lift {before after values types} :
before.WellFormed classes →
Shared.Typing.ArgsTyped classes before.current values types after →
(before.withCurrent after).WellFormed classes →
ArgsTyped classes before values types (before.withCurrent after)
inductive BindingTyped (classes : ClassTable) : Context → Unpacking.Pattern → ValueType → Context → Prop where
| lift {before after pattern ty fixed} :
before.WellFormed classes →
Shared.Typing.BindingTyped classes before.current pattern ty after →
bindingTypes classes pattern ty = some fixed →
(Context.mk (fixed ++ before.bindings) after).WellFormed classes →
BindingTyped classes before pattern ty ⟨fixed ++ before.bindings, after⟩
inductive LocalTyped (classes : ClassTable) : Context → Unpacking.Statement → Context → Prop where
| letValue {before middle after pattern value ty} :
ExprTyped classes before value ty middle →
BindingTyped classes middle pattern ty after →
LocalTyped classes before ⟨pattern, value⟩ after
inductive StatementTyped (classes : ClassTable) (declarations : Declarations) : Context → Statement → Context → Prop where
| local {before after statement} :
LocalTyped classes before statement after →
StatementTyped classes declarations before (.local statement) after
| call {before middle after destination name arguments declaration} :
(name, declaration) ∈ declarations →
(∀ x ∈ destination, x ∉ before.current.map Prod.fst) →
ArgsTyped classes before arguments (declaration.signature.parameters.map Functions.Parameter.type) middle →
DestinationTyped classes middle destination declaration.signature.result after →
StatementTyped classes declarations before (.call destination name arguments) after
| store {before middle after place value ty} :
ExprTyped classes before value ty middle →
store classes middle place ty = some after →
StatementTyped classes declarations before (.store place value) after
| dropStruct {before after place ty} :
ExprTyped classes before (.give place) ty after → StructType classes ty →
StatementTyped classes declarations before (.dropStruct place) after
Every successful static store preserves the entire fixed binding map.
theorem store_preserves_bindings (stored : store classes before place ty = some after) :
after.bindings = before.bindings := by
unfold store at stored
cases h : storeCurrent classes before place ty <;> simp [h] at stored
rw [← stored.2]
rfl
Execution
A writable slot is either a local entry (initialized or empty), or a field of an object reached through a uniquely accessible parent place. Resolving a field destination resolves the parent, not the field’s previous contents.
Runtime contents are replaceable if the slot is empty or holds a reference to a struct. Writing installs the incoming reference into the selected slot; it preserves object identities, field names, other slots, and the allocation counter. In particular, it does not reallocate the parent object.
inductive Writable (state : State) : Place → StoragePlace → Slot → Prop where
| variable {name slot} :
(name, slot) ∈ state.variables →
Writable state (.variable name) (.variable name) slot
| field {base source parent data name slot} :
Resolve state base source parent .unique →
(parent, data) ∈ state.objects →
(name, slot) ∈ data.fields →
Writable state (.field base name) (.field parent name) slot
def Replaceable (classes : Classes) (state : State) : Slot → Prop
| none => True
| some reference => StructReference classes state reference
inductive Write : State → StoragePlace → Reference → State → Prop where
| variable (objects : List (ObjectId × Object)) (nextId : Nat)
(leading suffix : List (VariableId × Slot)) (name : VariableId)
(previous : Slot) (reference : Reference) :
Write ⟨objects, leading ++ (name, previous) :: suffix, nextId⟩
(.variable name) reference
⟨objects, leading ++ (name, some reference) :: 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)
(previous : Slot) (reference : Reference) :
Write ⟨before ++ (parent, ⟨className, leading ++ (name, previous) :: suffix⟩) :: after,
variables, nextId⟩
(.field parent name) reference
⟨before ++ (parent, ⟨className, leading ++ (name, some reference) :: suffix⟩) :: after,
variables, nextId⟩
The machine retains the explicit stack and eager collector. Each frame owns its locals, remaining body, and result destination. Expressions run against the top frame; collection uses the roots of all frames.
For a raw store transition:
- Evaluate the right-hand-side expression to a reference and intermediate state.
- Resolve a writable destination slot in that intermediate state.
- Check that its previous contents are replaceable.
- Write the incoming reference into that slot and advance the statement list.
The resulting configuration is then collected. There is no collection between evaluation and installation of the incoming reference. Explicit drops remain separate statements, with their own calls and collection steps. Return and initial-frame exit retain the requirement that no class root remains in the completed frame.
structure Frame where
variables : Store
body : Body
destination : Option VariableId
deriving Repr
structure Configuration where
objects : List (ObjectId × Object)
nextId : Nat
frames : List Frame
deriving Repr
inductive RawStep (classes : Classes) (declarations : Declarations) : Configuration → Configuration → Prop where
| local {before after statement rest result frames destination} :
Unpacking.Step classes ⟨before, [statement]⟩ ⟨after, []⟩ →
RawStep classes declarations
(.running before ⟨.local statement :: rest, result⟩ frames destination)
(.running after ⟨rest, result⟩ frames destination)
| call {before evaluated destination name arguments rest result frames returnTo
declaration references} :
(name, declaration) ∈ declarations →
DestinationMatches destination declaration.signature.result →
(∀ x ∈ destination, x ∉ before.variables.map Prod.fst) →
EvalArgs classes before arguments evaluated references →
references.length = declaration.signature.parameters.length →
RawStep classes declarations
(.running before ⟨.call destination name arguments :: rest, result⟩ frames returnTo)
(.running { evaluated with variables := parameterStore declaration.signature.parameters references }
declaration.body (⟨evaluated.variables, ⟨rest, result⟩, returnTo⟩ :: frames) destination)
| dropStruct {before evaluated place reference rest result frames destination} :
Eval classes before (.give place) evaluated reference →
StructReference classes evaluated reference →
RawStep classes declarations
(.running before ⟨.dropStruct place :: rest, result⟩ frames destination)
(.running evaluated ⟨rest, result⟩ frames destination)
| store {before evaluated after place value reference target previous rest result frames destination} :
Eval classes before value evaluated reference →
Writable evaluated place target previous →
Replaceable classes evaluated previous →
Write evaluated target reference after →
RawStep classes declarations
(.running before ⟨.store place value :: rest, result⟩ frames destination)
(.running after ⟨rest, result⟩ frames destination)
| «return» {before evaluated result reference caller frames destination variables} :
ResultEval classes before result evaluated reference →
Deliver caller.variables destination reference variables →
StoreFinished classes evaluated →
RawStep classes declarations
(.running before ⟨[], result⟩ (caller :: frames) destination)
(.running { evaluated with variables := variables } caller.body frames caller.destination)
| exit {objects nextId variables} :
StoreFinished classes ⟨objects, variables, nextId⟩ →
RawStep classes declarations
(.running ⟨objects, variables, nextId⟩ ⟨[], none⟩) ⟨objects, nextId, []⟩
inductive Step (classes : Classes) (declarations : Declarations) : Configuration → Configuration → Prop where
| collect {before raw} : RawStep classes declarations before raw →
Step classes declarations before raw.collect
def Configuration.collect (configuration : Configuration) : Configuration := by
exact { configuration with objects := configuration.rootState.collect.objects }
A finite execution is zero or more machine steps. A program starts with an empty heap and one initial frame containing its main statements and no locals or result destination.
def Configuration.initial (program : Program) : Configuration :=
.running State.empty ⟨program.main, none⟩
inductive Steps (classes : Classes) (declarations : Declarations) : Configuration → Configuration → Prop where
| refl (configuration : Configuration) : Steps classes declarations configuration configuration
| step {before middle after} :
Step classes declarations before middle → Steps classes declarations middle after →
Steps classes declarations before after
A configuration is finished when its frame stack is empty.
def Configuration.finished (configuration : Configuration) : Prop :=
configuration.frames = []
A configuration is stuck when it is not finished and has no possible next machine step. A finished configuration is therefore not stuck.
def Stuck (classes : Classes) (declarations : Declarations) (configuration : Configuration) : Prop :=
¬ configuration.finished ∧ ¬ ∃ after, Step classes declarations configuration after
Replacing a local shared-struct reference
can make the old object unreachable.
The checked transition begins with s referencing SharedPoint object 0,
constructs object 1, and stores its reference in s. In the resulting raw
configuration, object 0 is unreachable and object 1 is reachable. The eager
collector therefore discards object 0 and retains object 1.
example :
RawStep classes.erase []
(.running beforeStructStore ⟨[.store (.variable "s") (.new "SharedPoint" [])], none⟩)
(.running afterStructStore ⟨[], none⟩) ∧
¬ Live (Configuration.running afterStructStore ⟨[], none⟩).rootState ⟨0⟩ ∧
Live (Configuration.running afterStructStore ⟨[], none⟩).rootState ⟨1⟩ := by
refine ⟨?_, ?_, .variable (name := "s") (reference := .shared ⟨1⟩) (by decide)⟩
· apply RawStep.store (evaluated := beforeStructStore.allocate "SharedPoint" [] [])
(reference := .shared ⟨1⟩) (target := .variable "s") (previous := some (.shared ⟨0⟩))
· exact .new (declaration := ⟨[], .sharedStruct⟩) (by decide) (.nil _) rfl (by decide)
(by simp [StructArguments])
· exact .variable (by decide)
· exact ⟨⟨"SharedPoint", []⟩, ⟨[], .sharedStruct⟩, by decide, by decide, rfl⟩
· exact .variable _ _ [] [] "s" _ _
· have onlyOne : ∀ id, Live (Configuration.running afterStructStore ⟨[], none⟩).rootState id → id = ⟨1⟩ := by
intro id live
induction live with
| «variable» member =>
simp only [Configuration.rootState, Configuration.running, afterStructStore,
List.flatMap_cons, List.flatMap_nil, List.append_nil, List.mem_cons,
List.not_mem_nil, or_false, Prod.mk.injEq, Option.some.injEq] at member
rw [member.2]
rfl
| field _ obj field _ =>
simp only [Configuration.rootState, Configuration.running, afterStructStore,
List.mem_cons, List.not_mem_nil, or_false] at obj
rcases obj with h | h <;> cases h <;> contradiction
intro live
have impossible := onlyOne _ live
cases impossible
Refilling a field can reverse allocation-age order. In the checked step,
w owns wrapper object 1 with an empty resource field. The store constructs
resource object 2 and installs it in object 1. Both objects survive collection,
and their identities remain 1 and 2.
This resulting heap satisfies the structural heap invariant: its objects are rooted and its owning references are compatible. It does not satisfy the stronger requirement that every field target have a smaller allocation index than its parent. The foundation deliberately does not require that ordering.
example :
Step classes.erase []
(.running beforeRefill ⟨[.store (.field (.variable "w") "resource") (.new "Resource" [])], none⟩)
(.running afterRefill ⟨[], none⟩) ∧
Shared.WellFormed classes.erase afterRefill ∧
¬ (∀ id data name reference, (id, data) ∈ afterRefill.objects →
(name, some reference) ∈ data.fields → reference.object.index < id.index) := by
refine ⟨?_, ?_, ?_⟩
· have collected : (Configuration.running afterRefill ⟨[], none⟩).collect =
Configuration.running afterRefill ⟨[], none⟩ := by
apply Configuration.collect_eq_self
intro id data member
simp only [Configuration.running, afterRefill, List.mem_cons, List.not_mem_nil, or_false] at member
rcases member with h | h
· cases h
exact .field (parent := ⟨1⟩) (reference := .owned ⟨2⟩) (name := "resource") (data := ⟨"Wrapper", [("resource", some (.owned ⟨2⟩))]⟩) (.variable (name := "w") (reference := .owned ⟨1⟩) (by decide)) (by decide) (by decide)
· cases h
exact .variable (name := "w") (reference := .owned ⟨1⟩) (by decide)
rw [← collected]
exact .collect refill_raw
· refine ⟨by decide, by decide, ?_, ?_, ?_, ?_, ?_⟩
· intro id data member
simp only [afterRefill, List.mem_cons, List.not_mem_nil, or_false] at member
rcases member with h | h <;> cases h
· exact ⟨⟨[], .classType⟩, by decide, rfl, by decide⟩
· exact ⟨⟨["resource"], .classType⟩, by decide, rfl, by decide⟩
· intro id data member
simp only [afterRefill, 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 = ⟨2⟩ ∨ object = ⟨1⟩ := by simpa [Allocated, afterRefill] using allocated
rcases cases with rfl | rfl
· exact .field (parent := ⟨1⟩) (reference := .owned ⟨2⟩) (name := "resource")
(data := ⟨"Wrapper", [("resource", some (.owned ⟨2⟩))]⟩)
(.variable (name := "w") (reference := .owned ⟨1⟩) (by decide)) (by decide) (by decide)
· exact .variable (name := "w") (reference := .owned ⟨1⟩) (by decide)
· simp [Owners, afterRefill, Compatible, Reference.owned]
· intro object
simp [References, Allocated, afterRefill, Reference.owned, or_comm]
· intro older
have impossible := older ⟨1⟩ ⟨"Wrapper", [("resource", some (.owned ⟨2⟩))]⟩ "resource" (.owned ⟨2⟩) (by decide) (by decide)
contradiction
Correspondence
Embedding Destructors into Assignment maps statements, bodies, and declarations, and frames componentwise. It adds no store statements. Heap objects, allocation counters, local slots, call names, and value expressions remain unchanged.
def statement : Destructors.Statement → Assignment.Statement
| .local s => .local s
| .call destination name arguments => .call destination name arguments
| .dropStruct place => .dropStruct place
def body (source : Destructors.Body) : Assignment.Body :=
⟨source.statements.map statement, source.result⟩
def declaration (source : Destructors.Declaration) : Assignment.Declaration :=
⟨source.signature, body source.body⟩
def declarations (source : Destructors.Declarations) : Assignment.Declarations :=
source.map fun (name, decl) => (name, declaration decl)
def frame (source : Destructors.Frame) : Assignment.Frame :=
⟨source.variables, body source.body, source.destination⟩
def configuration (source : Destructors.Configuration) : Assignment.Configuration :=
⟨source.objects, source.nextId, source.frames.map frame⟩
Every Destructor execution step is preserved by this embedding, including collection and frame transitions, with the declaration table embedded as well. This is an operational correspondence result; it does not assert preservation of typing with the new fixed binding metadata.
theorem step_forward (h : Destructors.Step classes decls before after) :
Assignment.Step classes (declarations decls) (configuration before) (configuration after) := by
cases h with
| collect raw => rw [collect]; exact .collect (raw_forward raw)
Reverse execution correspondence and preservation of Destructor typing with the new fixed binding metadata remain separate proof obligations. The forward execution theorem does not establish either.
Automatic destructor insertion remains deferred. Mutable leases and their different representation also remain outside this layer.
Appendix: inherited calls and completion
Result typing evaluates an optional result against the signature. Destination typing either accepts no result and no destination, or introduces a fresh local with the result’s declared fixed type. Sequence typing composes statement contexts in order.
inductive ResultTyped (classes : ClassTable) : Context → Option Value → Option FieldType → Context → Prop where
| none {environment} :
environment.WellFormed classes → ResultTyped classes environment none none environment
| some {before after value type} :
ExprTyped classes before value type.toType after →
ResultTyped classes before (some value) (some type) after
inductive DestinationTyped (classes : ClassTable) : Context → Option VariableId → Option FieldType → Context → Prop where
| none {environment} :
environment.WellFormed classes → DestinationTyped classes environment none none environment
| some {before after name type} :
BindingTyped classes before (.variable name) type.toType after →
DestinationTyped classes before (some name) (some type) after
inductive SequenceTyped (classes : ClassTable) (declarations : Declarations) : Context → List Statement → Context → Prop where
| nil {environment} :
environment.WellFormed classes → SequenceTyped classes declarations environment [] environment
| cons {before middle after statement rest} :
StatementTyped classes declarations before statement middle →
SequenceTyped classes declarations middle rest after →
SequenceTyped classes declarations before (statement :: rest) after
A well-typed body starts in its parameter context, checks its statements and result using sequence and result typing, and must satisfy the completion obligation: only empty or struct locals remain. This condition uses current descriptions, so an empty class slot is permitted while an initialized partial class is not.
Class drops use whole given receivers and the dedicated destructor name; struct drops give and discard without invoking user code.
def Finished (classes : ClassTable) (context : Context) : Prop :=
Destructors.Finished classes context.current
inductive DropTyped (classes : ClassTable) (declarations : Declarations) : Context → Place → Statement → Context → Prop where
| struct {before after place ty} :
ExprTyped classes before (.give place) ty after → StructType classes ty →
DropTyped classes declarations before place (.dropStruct place) after
| class {before after place owner declaration} :
ExprTyped classes before (.give place) (.whole owner .given) after →
(Destructors.Name.destructor owner, declaration) ∈ declarations →
declaration.signature = ⟨[receiver owner .given], none⟩ →
DropTyped classes declarations before place (.dropClass owner place) after
def BodyTyped (classes : ClassTable) (declarations : Declarations) (signature : Signature)
(body : Body) : Prop :=
∃ middle after,
SequenceTyped classes declarations (initialContext signature) body.statements middle ∧
ResultTyped classes middle body.result signature.result after ∧ Finished classes after
A well-typed declaration table has distinct callable names. Each declaration has a signature obeying the ordinary call restrictions and destructor restrictions, and a well-typed body checked against the entire table. Signatures are therefore available recursively; there is no termination requirement.
def DeclarationsTyped (classes : ClassTable) (declarations : Declarations) : Prop :=
(declarations.map Prod.fst).Nodup ∧
∀ entry ∈ declarations,
Destructors.Signature.WellFormed classes entry.1 entry.2.signature ∧
BodyTyped classes declarations entry.2.signature entry.2.body
A well-typed program has a well-formed class table and a well-typed declaration table. Its main sequence checks from the empty context and satisfies the same completion obligation as a function body.
def ProgramTyped (program : Program) : Prop :=
program.classes.WellFormed ∧ DeclarationsTyped program.classes program.declarations ∧
∃ finalEnvironment,
SequenceTyped program.classes program.declarations Context.empty program.main finalEnvironment ∧
Finished program.classes finalEnvironment
Appendix: store and stack safety
Suppose the input state is structurally well formed, counting the incoming reference and any other pending references as roots. A write to a writable slot preserves that invariant when the incoming reference leaves the pending roots and the displaced reference, if any, joins them instead.
This is an ownership exchange before collection. The displaced reference remains a temporary root even when no local or field reaches it after the write. The theorem assumes neither allocation-age order nor global acyclicity.
theorem Write.preserves_pending {previous : Slot} (wf : WellFormedWith classes before (incoming :: pending))
(writable : Writable before place source previous)
(written : Write before source incoming after) :
WellFormedWith classes after (previous.toList ++ pending) := by
have owners := written.owners_pending wf writable pending
constructor
· simpa only [written.objectKeys] using wf.objectKeys
· simpa only [written.variableKeys] using wf.variableKeys
· intro id data stored
obtain ⟨oldData, oldStored, sameClass, sameFields⟩ := written.new_object_data stored
obtain ⟨declaration, declared, shape, unique⟩ := wf.shapes id oldData oldStored
exact ⟨declaration, sameClass ▸ declared, sameFields ▸ shape, unique⟩
· intro id data stored
obtain ⟨oldData, oldStored, _, _⟩ := written.new_object_data stored
simpa only [written.nextId] using wf.bounds id oldData oldStored
· intro id allocated
have oldAllocated : Allocated before id := by
simpa only [Allocated, written.objectKeys] using allocated
exact written.liveWith wf writable (wf.rooted id oldAllocated)
· exact owners.pairwise wf.ownersCompatible compatible_symm
· intro id
have targets := (owners.map Reference.object).mem_iff (a := id)
simp only [List.map_append, owners_targets] at targets
have allocation : Allocated before id ↔ Allocated after id := by
simp only [Allocated, written.objectKeys]
simpa only [List.map_append] using
targets.symm.trans ((wf.referencesComplete id).trans allocation)
Suppose the static store operation succeeds and the input state realizes its current environment, with the incoming value and any other pending values as roots. A writable, replaceable runtime destination and write then exist.
For every such runtime write, the resulting state realizes the output current environment and all the original pending values except the installed incoming value. Any additional pending values needed to retain displaced storage have struct types, so they can be discarded by the statement’s collector. For a field destination, the output type uses view replacement; incoming negative entries still describe empty fields.
theorem store_sound
{classes : ClassTable} {before after : Context} {place : Place}
{ty : ValueType} {state : State} {reference : Reference} {pending : PendingValues}
(stored : store classes before place ty = some after)
(realized : Realizes classes before.current state ((reference, ty) :: pending)) :
(∃ target previous result, Writable state place target previous ∧
Replaceable classes.erase state previous ∧ Write state target reference result) ∧
(∀ target previous result, Writable state place target previous →
Replaceable classes.erase state previous → Write state target reference result →
∃ garbage, (∀ ref ty, (ref, ty) ∈ garbage → StructType classes ty) ∧
Realizes classes after.current result (pending ++ garbage)) := by
refine ⟨store_exists stored realized, ?_⟩
intro target previous result writable replaceable written
exact store_preserves stored realized writable replaceable written
A typed configuration has well-formed nominal declarations, typed callable declarations, and a compatible stack. Each frame’s locals form a typed store for the current descriptions in its context.
The active body’s remainder checks from that context. A suspended caller’s remainder checks from the context after result delivery. Every body satisfies the completion obligation. The empty stack has no result destination and no roots.
The common heap has Shared realization with an empty local environment and all frame references as pending values. Their multiplicities and types are retained, so equal shared references in two slots still contribute two roots. Frame-local names need not be globally unique.
def BodyFrom (classes : ClassTable) (declarations : Declarations) (environment : Context)
(body : Body) (result : Option FieldType) : Prop :=
∃ middle final, SequenceTyped classes declarations environment body.statements middle ∧
ResultTyped classes middle body.result result final ∧ Finished classes final
inductive ContinuationTyped (classes : ClassTable) (declarations : Declarations) : Option VariableId → Option FieldType → List Frame → PendingValues → Prop where
| done : ContinuationTyped classes declarations none none [] []
| caller {destination result caller rest environment resumed roots laterRoots callerResult} :
Slots environment.current caller.variables roots → environment.WellFormed classes →
DestinationTyped classes environment destination result resumed →
BodyFrom classes declarations resumed caller.body callerResult →
ContinuationTyped classes declarations caller.destination callerResult rest laterRoots →
ContinuationTyped classes declarations destination result (caller :: rest) (roots ++ laterRoots)
inductive StackShape (classes : ClassTable) (declarations : Declarations) : List Frame → PendingValues → Prop where
| done : StackShape classes declarations [] []
| active {frame rest environment roots laterRoots result} :
Slots environment.current frame.variables roots → environment.WellFormed classes →
BodyFrom classes declarations environment frame.body result →
ContinuationTyped classes declarations frame.destination result rest laterRoots →
StackShape classes declarations (frame :: rest) (roots ++ laterRoots)
def ConfigurationTyped (classes : ClassTable) (declarations : Declarations) (configuration : Configuration) : Prop :=
classes.WellFormed ∧ DeclarationsTyped classes declarations ∧
∃ roots, StackShape classes declarations configuration.frames roots ∧
Realizes classes [] (heapState configuration.rootState) roots
Every typed configuration has no remaining frames—that is, it is finished—or can take a machine step. This covers stores, calls, returns, explicit drops, and the initial-frame exit.
theorem ConfigurationTyped.progress {configuration : Configuration}
(typed : ConfigurationTyped classes declarations configuration) :
configuration.finished ∨ ∃ after, Step classes.erase declarations configuration after :=
ConfigurationTyped.progress_of_store store_sound typed
Every machine step from a typed configuration produces another typed configuration. The result quantifies over every operational successor and includes eager collection after the raw transition.
theorem ConfigurationTyped.preservation {before after : Configuration}
(typed : ConfigurationTyped classes declarations before)
(step : Step classes.erase declarations before after) :
ConfigurationTyped classes declarations after :=
ConfigurationTyped.preservation_of_store store_sound typed step
A collection retains classes when every object whose nominal type is not a struct remains present with the same identity and contents. The comparison uses the heap immediately before collection and the heap after it.
def RetainsClasses (classes : ClassTable) (before after : Configuration) : Prop :=
∀ id data, (id, data) ∈ before.objects →
¬ StructType classes (.whole data.className) → (id, data) ∈ after.objects
For every raw transition from a typed configuration, collection produces a typed configuration and retains every class object still present after that transition. An explicit unpack can remove a class container during the raw transition; collection cannot consume it on the program’s behalf.
Overwriting a struct reference can discard its entire unreachable subgraph. Since struct fields have struct types, this cannot hide an unconsumed class, including behind a view omission.
theorem RawStep.sound {before after : Configuration}
(typed : ConfigurationTyped classes declarations before)
(step : RawStep classes.erase declarations before after) :
ConfigurationTyped classes declarations after.collect ∧ RetainsClasses classes after after.collect :=
RawStep.sound_of_store store_sound typed step
In a typed configuration, references in all frame slots and object fields are pairwise compatible. Distinct owning occurrences can target the same object only when both are shared. Every referenced object is allocated, and every allocated object has an incoming reference from a frame or field.
theorem ConfigurationTyped.ownership {configuration : Configuration}
(typed : ConfigurationTyped classes declarations configuration) :
(Owners configuration.rootState).Pairwise Compatible ∧
(∀ id, id ∈ References configuration.rootState ↔ Allocated configuration.rootState id) := by
obtain ⟨_,_,roots,shape,heap⟩ := typed
have refs := shape.references
constructor
· simpa only [Owners,heapState,List.filterMap_nil,List.nil_append,refs,
Configuration.rootState] using heap.ownership.ownersCompatible
· intro id
have complete := heap.ownership.referencesComplete id
simpa only [heapState,References,List.filterMap_nil,List.nil_append,refs,
Configuration.rootState,Allocated,List.map_append,List.map_filterMap,Function.comp_def] using complete
A typed configuration with no frames has an empty heap. No class or struct objects remain after completion.
theorem ConfigurationTyped.finished_heap_empty {configuration : Configuration}
(typed : ConfigurationTyped classes declarations configuration)
(finished : configuration.finished) : configuration.objects = [] := by
rcases configuration with ⟨objects,nextId,frames⟩
change frames = [] at finished
subst frames
obtain ⟨_,_,roots,shape,heap⟩ := typed
cases shape
have same := State.collect_eq_self heap.ownership.no_pending
rw [heapState,State.collect_no_variables] at same
exact (congrArg State.objects same).symm
Starting from a well-typed program, every finite execution ends in a typed configuration. It is finished or can take another machine step, and is not stuck. This includes stores within recursive functions and destructors; the theorem makes no termination claim.
theorem program_safety (typed : ProgramTyped program)
(trace : Steps program.classes.erase program.declarations (.initial program) configuration) :
ConfigurationTyped program.classes program.declarations configuration ∧
(configuration.finished ∨ ∃ after, Step program.classes.erase program.declarations configuration after) ∧
¬ Stuck program.classes.erase program.declarations configuration :=
program_safety_of_store store_sound typed trace