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

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.

Assignment/Checks:refill
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.

Assignment/SafetyChecks:refill_safety
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.

Assignment/Checks:explicit_replacement
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.

Assignment/Checks:class_replacement
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 typeAssignmentResult
p: given Pointp = new Point()accepted
s: shared SharedPoints = new SharedPoint()accepted
b: given Boxb.point = new Point()accepted
b: shared Boxstore a shared Point into b.pointrejected

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.

Assignment/Checks:structs
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.

Assignment/SafetyChecks:overwrite_safety
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.

Assignment/Checks:partial_value
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.

Assignment/Checks:rhs_first
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.

Assignment/Syntax:Statement
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
Assignment/Syntax:Body
structure Body where
  statements : List Statement
  result : Option Value
  deriving Repr
Assignment/Syntax:Declaration
structure Declaration where
  signature : Signature
  body : Body
  deriving Repr
Assignment/Syntax:Program
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.

Assignment/StorageTypes:StorageType
abbrev StorageType := FieldType
Assignment/StorageTypes:storageType
def storageType (ty : ValueType) : StorageType := ⟨ty.permission, ty.base⟩
Assignment/StorageTypes:layoutKey
def layoutKey (ty : StorageType) : ClassName := ty.className
Assignment/StorageTypes:Context
structure Context where
  bindings : List (VariableId × StorageType)
  current : Environment
  deriving DecidableEq, Repr
Assignment/StorageTypes:Context.WellFormed
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))
Assignment/Typing:initialContext
def initialContext (signature : Signature) : Context :=
  ⟨signature.parameters.map (fun p => (p.name, p.type)), signature.environment⟩
Assignment/Typing:bindingTypes
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.

Assignment/StorageTypes:replaceView
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.

Assignment/StorageTypes:replaceable
def replaceable (classes : ClassTable) : SlotDescription → Bool
  | none => true
  | some ty => decide (StructType classes ty)
Assignment/StorageTypes:storeCurrent
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
Assignment/StorageTypes:store
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.

Assignment/Typing:ExprTyped
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)
Assignment/Typing:ArgsTyped
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)
Assignment/Typing:BindingTyped
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⟩
Assignment/Typing:LocalTyped
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
Assignment/Typing:StatementTyped
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.

Assignment/StorageTypes:store_preserves_bindings
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.

Assignment/Write:Writable
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
Assignment/Write:Replaceable
def Replaceable (classes : Classes) (state : State) : Slot → Prop
  | none => True
  | some reference => StructReference classes state reference
Assignment/Write:Write
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:

  1. Evaluate the right-hand-side expression to a reference and intermediate state.
  2. Resolve a writable destination slot in that intermediate state.
  3. Check that its previous contents are replaceable.
  4. 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.

Assignment/Step:Frame
structure Frame where
  variables : Store
  body : Body
  destination : Option VariableId
  deriving Repr
Assignment/Step:Configuration
structure Configuration where
  objects : List (ObjectId × Object)
  nextId : Nat
  frames : List Frame
  deriving Repr
Assignment/Step:RawStep
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, []⟩
Assignment/Step:Step
inductive Step (classes : Classes) (declarations : Declarations) : Configuration → Configuration → Prop where
  | collect {before raw} : RawStep classes declarations before raw →
      Step classes declarations before raw.collect
Assignment/Step:Configuration.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.

Assignment/Step:Configuration.initial
def Configuration.initial (program : Program) : Configuration :=
  .running State.empty ⟨program.main, none⟩
Assignment/Step:Steps
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.

Assignment/Step:Configuration.finished
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.

Assignment/Step: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.

Assignment/ExecutionChecks:struct_collection
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.

Assignment/ExecutionChecks:younger_child
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.

Correspondence/DestructorsAssignment:statement
def statement : Destructors.Statement → Assignment.Statement
  | .local s => .local s
  | .call destination name arguments => .call destination name arguments
  | .dropStruct place => .dropStruct place
Correspondence/DestructorsAssignment:body
def body (source : Destructors.Body) : Assignment.Body :=
  ⟨source.statements.map statement, source.result⟩
Correspondence/DestructorsAssignment:declaration
def declaration (source : Destructors.Declaration) : Assignment.Declaration :=
  ⟨source.signature, body source.body⟩
Correspondence/DestructorsAssignment:declarations
def declarations (source : Destructors.Declarations) : Assignment.Declarations :=
  source.map fun (name, decl) => (name, declaration decl)
Correspondence/DestructorsAssignment:frame
def frame (source : Destructors.Frame) : Assignment.Frame :=
  ⟨source.variables, body source.body, source.destination⟩
Correspondence/DestructorsAssignment:configuration
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.

Correspondence/DestructorsAssignment:step_forward
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.

Assignment/Typing:ResultTyped
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
Assignment/Typing:DestinationTyped
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
Assignment/Typing:SequenceTyped
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.

Assignment/Typing:Finished
def Finished (classes : ClassTable) (context : Context) : Prop :=
  Destructors.Finished classes context.current
Assignment/Typing:DropTyped
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
Assignment/Typing:BodyTyped
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.

Assignment/Typing:DeclarationsTyped
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.

Assignment/Typing:ProgramTyped
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.

Assignment/WriteOwnership:Write.preserves_pending
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.

Assignment/StoreSoundness:store_sound
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.

Assignment/StackTyping:BodyFrom
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
Assignment/StackTyping:ContinuationTyped
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)
Assignment/StackTyping:StackShape
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)
Assignment/StackTyping:ConfigurationTyped
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.

Assignment/Safety:ConfigurationTyped.progress
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.

Assignment/Safety:ConfigurationTyped.preservation
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.

Assignment/Safety:RetainsClasses
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.

Assignment/Safety:RawStep.sound
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.

Assignment/Safety:ConfigurationTyped.ownership
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.

Assignment/Safety:ConfigurationTyped.finished_heap_empty
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.

Assignment/Safety:program_safety
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