Destructors
Every owned class value needs an ending
Before a body finishes, it must account for every class value it owns. Unpacking consumes a container and transfers responsibility for its fields to local bindings. Dropping delegates that work to the class’s destructor. Moving a value to another local merely transfers the responsibility.
Start with classes that have no destructors:
class Token {}
class Pair { left: Token, right: Token }
let pair = new Pair(new Token(), new Token());
let Pair → { left, right } = pair→;
let Token → {} = left→;
let Token → {} = right→;
This program checks: unpacking consumes the pair, then each token.
If either of the last two statements is omitted, the body cannot finish. The
corresponding token is still owned by a local binding. Unpacking the outer
container alone does not consume the contents. Since these classes have no
destructors, replacing an unpack with drop is not permitted.
Likewise, ending the body with let other = right→; instead of unpacking
right would leave other responsible for that token. The obligation follows
the value. Struct values are exempt from this requirement; their storage is
treated as garbage collected.
example : ProgramTyped pairProgram ∧
¬ Finished classes [("right",some (.whole "Token")),("left",none),("pair",none)] ∧
¬ Finished classes [("other",some (.whole "Token")),("right",none),("left",none),("pair",none)] ∧
¬ Droppable classes declarations (.whole "Token") := by
refine ⟨pair_typed, ?_, ?_, by decide⟩
· intro h; exact (by decide : ¬ StructType classes (.whole "Token")) (h "right" _ (by simp))
· intro h; exact (by decide : ¬ StructType classes (.whole "Token")) (h "other" _ (by simp))
Delegating consumption to a destructor
A destructor lets a class say how to finish using an instance. This layer makes that work explicit: a class value must be moved, unpacked, or dropped before its frame finishes. Declaring a destructor does not arrange an automatic call.
class Resource {
drop {
let Resource → {} = self→;
}
}
class Wrapper {
resource: Resource
drop {
let Wrapper → { resource } = self→;
drop resource;
}
}
let w = new Wrapper(new Resource());
drop w;
The execution moves w into the wrapper destructor’s self binding.
Unpacking consumes the wrapper container and transfers its field to resource.
Dropping that field invokes the resource destructor, whose unpack consumes the
resource container. Both destructor calls then finish, and w has been emptied by the drop before the initial program frame exits. Nothing implicitly destroys the receiver or its fields.
This chapter introduces the new behavior first. The explicit forward references to the inherited machinery in the appendix keep Shared’s unchanged rules from obscuring that behavior. The appendix states which rules carry over and supplies their definitions in Shared.
example : ProgramTyped wrapperProgram ∧
Steps classes.erase declarations (.initial wrapperProgram) ⟨[],2,[]⟩ :=
⟨wrapper_typed, wrapper_execution⟩
Parameters and locals in a function
Using the preceding Functions chapter, these examples add the
consumption requirement to ordinary function bodies. They use the Wrapper
and Resource declarations above. Both an
owned parameter and a locally created class value must be accounted for before
the function returns.
One version explicitly unpacks everything:
fn finish(w: → Wrapper) {
let extra = new Resource();
let Wrapper → { resource } = w→;
let Resource → {} = resource→;
let Resource → {} = extra→;
}
Another delegates the work to destructors:
fn finish(w: → Wrapper) {
let extra = new Resource();
drop w;
drop extra;
}
Either version can be called with an owned wrapper:
let w = new Wrapper(new Resource());
finish(w→);
These are alternative bodies. In either version, omitting the consumption of
extra would leave an owned class value at return. Merely having a destructor
would not make that omission legal in this explicit core. Likewise, unpacking
w and leaving resource unconsumed would fail to account for its contents.
The requirement applies to program, function, method, and destructor bodies. A function can also transfer ownership to its caller by returning a value; check its remaining locals after evaluating that return expression.
example : BodyTyped classes declarations finish.signature finish.body ∧
BodyTyped classes declarations unpackFinish.signature unpackFinish.body ∧
ProgramTyped finishProgram := by
refine ⟨finish_body,unpackFinish_body,by decide,declarations_typed,[("w",none)],?_,by simp [Finished]⟩
apply SequenceTyped.cons (middle := [("w",some (.whole "Wrapper"))])
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := []) (ty := .whole "Wrapper")
· apply ExprTyped.new (declaration := ⟨[("resource",⟨.given,"Resource"⟩)],.classType⟩) (by decide)
· exact .cons (.new (declaration := ⟨[],.classType⟩) (by decide) (.nil (by decide)) (by decide) (by decide)) (.nil (by decide))
· decide
· decide
· exact .variable (by decide) (by decide) (by decide)
· apply SequenceTyped.cons
· exact .call (declaration := finish) (middle := [("w",none)])
(by simp [finishProgram,declarations]) (by simp)
(.cons (.give (by decide) (by decide) (by decide) (by decide)) (.nil (by decide))) (.none (by decide))
· exact .nil (by decide)
Returning transfers the obligation to the caller
A function can return an owned value instead of destroying it. Using the Resource destructor above:
fn identity(token: → Resource) → Resource {
return token→;
}
let original = new Resource();
let returned = identity(original→);
drop returned;
The call empties original. Returning empties the callee’s token binding,
so the function can finish even though the resource is still alive. The caller
now owns it through returned; the final drop consumes it. Omitting that drop
would leave the caller with an outstanding class value. Returning transfers
responsibility; it does not invoke the destructor.
example : ProgramTyped returningProgram ∧
¬ Finished classes [("returned",some (.whole "Resource")),("original",none)] := by
constructor
· refine ⟨by decide, ?_, [("returned",none),("original",none)], ?_, by simp [Finished]⟩
· constructor
· decide
· intro entry member
simp only [returningProgram,returningTable,List.mem_cons,List.not_mem_nil,or_false] at member
rcases member with rfl | rfl
· refine ⟨⟨by decide,by decide,by decide,by decide⟩, ?_⟩
exact ⟨_,[("token",none)],.nil (by decide),
.some (.give (by decide) (by decide) (by decide) (by decide)),by simp [Finished]⟩
· refine ⟨⟨by decide,by decide,by decide,rfl,⟨⟨[],.classType⟩,by decide,rfl⟩⟩,?_,?_,?_,?_,?_⟩
· exact [("self",none)]
· exact [("self",none)]
· apply SequenceTyped.cons
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := [("self",none)]) (ty := .whole "Resource")
· exact .give (by decide) (by decide) (by decide) (by decide)
· exact .unpack (declaration := ⟨[],.classType⟩) (bindings := [])
(by decide) (by decide) rfl rfl (by decide) (by decide) (by decide) (by decide) .nil (by decide)
· exact .nil (by decide)
· exact .none (by decide)
· simp [Finished]
· apply SequenceTyped.cons (middle := [("original",some (.whole "Resource"))])
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := []) (ty := .whole "Resource")
· exact .new (declaration := ⟨[],.classType⟩) (by decide) (.nil (by decide)) (by decide) (by decide)
· exact .variable (by decide) (by decide) (by decide)
· apply SequenceTyped.cons (middle := [("returned",some (.whole "Resource")),("original",none)])
· exact .call (declaration := returningResource) (middle := [("original",none)])
(by simp [returningProgram,returningTable]) (by decide)
(.cons (.give (by decide) (by decide) (by decide) (by decide)) (.nil (by decide)))
(.some (.variable (by decide) (by decide) (by decide)))
· apply SequenceTyped.cons
· exact .call (declaration := resource) (middle := [("returned",none),("original",none)])
(by simp [returningProgram,returningTable]) (by simp)
(.cons (.give (by decide) (by decide) (by decide) (by decide)) (.nil (by decide)))
(.none (by decide))
· exact .nil (by decide)
· intro h
exact (by decide : ¬ StructType classes (.whole "Resource")) (h "returned" _ (by simp))
Dropping unique and shared structs
Structs do not run destructor code in this layer. An explicit drop uses ordinary give and discards the resulting reference:
struct Point {}
shared struct SharedPoint {}
let p = new Point();
let s = new SharedPoint();
drop p;
drop s;
p starts uniquely owned. Dropping it empties its binding, so a subsequent
p→ would be rejected. s starts shared; dropping it copies and discards a
reference, leaving s initialized. A subsequent s→ is still allowed.
Neither drop removes the local binding or calls user code.
The program may finish with s still initialized. Struct locals need no explicit
consumption, and GC handles their storage.
example : SequenceTyped classes [] [] structProgram.main structFinal ∧
Finished classes structFinal ∧
(∀ ty after, ¬ ExprTyped classes structFinal (.give (.variable "p")) ty after) ∧
ExprTyped classes structFinal (.give (.variable "s")) (.whole "SharedPoint" .shared) structFinal := by
refine ⟨?_,?_,?_,.give (by decide) (by decide) (by decide) (by decide)⟩
· apply SequenceTyped.cons (middle := [("p",some (.whole "Point"))])
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := []) (ty := .whole "Point")
· exact .new (declaration := ⟨[],.structType⟩) (by decide) (.nil (by decide)) (by decide) (by decide)
· exact .variable (by decide) (by decide) (by decide)
· apply SequenceTyped.cons (middle := [("s",some (.whole "SharedPoint" .shared)),("p",some (.whole "Point"))])
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := [("p",some (.whole "Point"))]) (ty := .whole "SharedPoint" .shared)
· exact .new (declaration := ⟨[],.sharedStruct⟩) (by decide) (.nil (by decide)) (by decide) (by decide)
· exact .variable (by decide) (by decide) (by decide)
· exact .cons (middle := structFinal) (.dropStruct (ty := .whole "Point") (.give (by decide) (by decide) (by decide) (by decide)) (by decide))
(.cons (.dropStruct (ty := .whole "SharedPoint" .shared) (.give (by decide) (by decide) (by decide) (by decide)) (by decide)) (.nil (by decide)))
· intro name ty member
have eq : name = "s" ∧ ty = .whole "SharedPoint" .shared := by simpa [structFinal] using member
rcases eq with ⟨rfl,rfl⟩
decide
· intro ty after
exact failed_give_not_typed (by decide)
A class destructor can leave struct locals
The distinction between classes and structs also matters inside a destructor. Using the SharedPoint declaration above:
class Parcel {
point: shared SharedPoint
drop {
let Parcel → { point } = self→;
}
}
Unpacking consumes the class
container and transfers its field into the local point. The destructor may
then finish with point still initialized because it is a struct value. It
needs no drop point. This is different from the Wrapper destructor,
whose unpacked resource is a class and must be consumed.
example : parcelClasses.WellFormed ∧
Signature.WellFormed parcelClasses (.destructor "Parcel") parcel.signature ∧
BodyTyped parcelClasses [(.destructor "Parcel",parcel)] parcel.signature parcel.body := by
refine ⟨by decide,⟨by decide,by decide,by decide,rfl,⟨⟨[("point",⟨.shared,"SharedPoint"⟩)],.classType⟩,by decide,rfl⟩⟩,?_,?_,?_,?_,?_⟩
· exact [("point",some (.whole "SharedPoint" .shared)),("self",none)]
· exact [("point",some (.whole "SharedPoint" .shared)),("self",none)]
· apply SequenceTyped.cons
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := [("self",none)]) (ty := .whole "Parcel")
· exact .give (by decide) (by decide) (by decide) (by decide)
· exact .unpack (declaration := ⟨[("point",⟨.shared,"SharedPoint"⟩)],.classType⟩)
(bindings := [("point",some (.whole "SharedPoint" .shared))])
(by decide) (by decide) rfl rfl (by decide) (by decide) (by decide) (by decide)
(.cons (by decide) .nil) (by decide)
· exact .nil (by decide)
· exact .none (by decide)
· intro name ty member
have eq : name = "point" ∧ ty = .whole "SharedPoint" .shared := by simpa using member
rcases eq with ⟨rfl,rfl⟩
decide
Unpacking after moving a field
A destructor receives a whole instance. Moving out a field of the Wrapper above leaves a partial value, so its destructor can no longer be called. Explicit unpacking can still consume the container:
fn consume(w: → Wrapper) {
let taken = w.resource→;
// drop w; // rejected: resource has been moved out
let Wrapper → { resource } = w→;
drop taken;
}
The move transfers the resource to taken and records an empty field in w.
The unpacking rule transfers
that empty field into an empty resource binding; it does not recreate a value.
Dropping taken consumes the resource itself. All three locals are empty when
the function finishes.
example : BodyTyped classes declarations consumePartial.signature consumePartial.body ∧
Shared.Typing.give classes [("w",some (.whole "Wrapper"))] (.field (.variable "w") "resource") =
some (.whole "Resource",[("w",some partialWrapper)]) ∧
¬ Droppable classes declarations partialWrapper := by
refine ⟨?_,by decide,by decide⟩
refine ⟨[("resource",none),("taken",none),("w",none)],
[("resource",none),("taken",none),("w",none)],?_,.none (by decide),by simp [Finished]⟩
apply SequenceTyped.cons (middle := [("taken",some (.whole "Resource")),("w",some partialWrapper)])
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := [("w",some partialWrapper)]) (ty := .whole "Resource")
· exact .give (by decide) (by decide) (by decide) (by decide)
· exact .variable (by decide) (by decide) (by decide)
· apply SequenceTyped.cons (middle := [("resource",none),("taken",some (.whole "Resource")),("w",none)])
· apply StatementTyped.local
apply Shared.Typing.StatementTyped.letValue (middle := [("taken",some (.whole "Resource")),("w",none)]) (ty := partialWrapper)
· exact .give (by decide) (by decide) (by decide) (by decide)
· exact .unpack (declaration := ⟨[("resource",⟨.given,"Resource"⟩)],.classType⟩)
(bindings := [("resource",none)])
(by decide) (by decide) rfl rfl (by decide) (by decide) (by decide) (by decide)
(.cons (by decide) .nil) (by decide)
· apply SequenceTyped.cons
· exact .call (declaration := resource) (middle := [("resource",none),("taken",none),("w",none)])
(by simp [declarations]) (by simp)
(.cons (.give (by decide) (by decide) (by decide) (by decide)) (.nil (by decide))) (.none (by decide))
· exact .nil (by decide)
Empty and recursive destructor bodies
A destructor must itself account for its receiver. Compare these two bodies:
class Resource {
drop { }
}
This alternative destructor fails: the body leaves self initialized. Even a fieldless
class must unpack its receiver or transfer it to another consuming operation.
class Again {
drop { drop self; }
}
This declaration checks, but dropping an Again instance recurses forever.
Each call moves its receiver into the next frame; none returns.
As with the Token example, a class without a destructor cannot be explicitly dropped, but it can be unpacked.
example :
¬ BodyTyped classes declarations resource.signature ⟨[],none⟩ ∧
ProgramTyped recursionProgram ∧
(∀ depth, Steps classes.erase declarations (.initial recursionProgram) (recursionState depth)) ∧
(∀ depth, Step classes.erase declarations (recursionState depth) (recursionState (depth + 1))) ∧
(∀ depth, ¬ (recursionState depth).finished) ∧
¬ Droppable classes declarations (.whole "Token") ∧
¬ Droppable classes declarations partialWrapper := by
refine ⟨?_,recursion_typed,recursion_reachable,recursive_step,?_,by decide,by decide⟩
· rintro ⟨middle,final,sequence,result,finished⟩
cases sequence
cases result
have impossible := finished "self" (.whole "Resource")
(by simp [resource,Functions.Signature.environment,receiver,FieldType.toType])
exact (by decide : ¬ StructType classes (.whole "Resource")) impossible
· intro depth; simp [recursionState,Configuration.finished,Configuration.running]
Declarations and dropping
A declaration retains Shared’s name, kind, and ordered fields. A class
declaration may additionally contain one destructor, written drop { body },
where body is a sequence of statements. The destructor has no parameters or
result; its initial local binding is self, a uniquely owned whole instance
of the declaring class. A struct or shared struct has no destructor body
in this layer.
The core distinguishes ordinary function names, qualified method names, and
drop(C) destructor names. A destructor is stored as a declaration with exactly
one parameter →self of its owning class and no result. Names must be unique;
ordinary methods cannot collide with destructor names.
Classes without destructors remain legal. Their instances must be consumed through explicit unpacking, possibly after being moved to another owner. Struct fields still have only struct types, and classes still cannot be shared. The inherited declaration restrictions are collected in the appendix.
inductive Name where
| function (name : String)
| method (owner : ClassName) (name : String)
| destructor (owner : ClassName)
deriving DecidableEq, Repr
def Signature.WellFormed (classes : ClassTable) (name : Name)
(signature : Signature) : Prop :=
(signature.parameters.map Functions.Parameter.name).Nodup ∧
(∀ p ∈ signature.parameters, Admissible classes p.type.toType) ∧
(∀ ty ∈ signature.result, Admissible classes ty.toType) ∧
match name with
| .function _ => "self" ∉ signature.parameters.map Functions.Parameter.name
| .destructor owner => signature = ⟨[receiver owner .given], none⟩ ∧
∃ declaration, (owner, declaration) ∈ classes ∧ declaration.kind = .classType
| .method owner _ => match signature.parameters with
| [] => False
| first :: rest => first.name = "self" ∧ first.type.className = owner ∧
"self" ∉ rest.map Functions.Parameter.name
structure Declaration where
signature : Signature
body : Body
deriving Repr
inductive Statement where
| local (statement : Unpacking.Statement)
| call (destination : Option VariableId) (name : Name) (arguments : List Value)
| dropStruct (place : Place)
deriving Repr
def Statement.dropClass (owner : ClassName) (place : Place) : Statement :=
.call none (.destructor owner) [.give place]
structure Body where
statements : List Statement
result : Option Value
deriving Repr
structure Program where
classes : ClassTable
declarations : Declarations
main : List Statement
deriving Repr
The droppability judgment Droppable(T) says that an explicit drop can consume a value of
type T, using a well-formed declaration table. Types retain Shared’s permissions and signed views, summarized in the
appendix.
| Type of value | Condition for Droppable(T) |
|---|---|
| Struct, including shared struct | Any well-formed permission and view allowed for that nominal type. |
| Class | Given permission, a whole declared view, and a declared destructor. |
“Whole” means that view normalization exposes the entire declared value, not merely every currently visible field. A partially moved class cannot invoke its destructor. An omitted field is unknown, not evidence that the field is empty.
def Droppable (classes : ClassTable) (declarations : Declarations) (ty : ValueType) : Prop :=
Admissible classes ty ∧ (StructType classes ty ∨
(ty = .whole ty.base .given ∧ .destructor ty.base ∈ declarations.map Prod.fst))
The new statement is drop p, where p is a place (a local followed by zero or
more field names). An environment Γ maps local names to types or empty slots.
Write Give(Γ, p) = (T, Γ′) for Shared’s static ordinary-give operation,
recalled in the appendix.
The surface statement elaborates to a struct-discard operation or to
drop(C)(p→), a core call to the destructor name
with no destination. The class name comes from the given value’s type. This
elaboration inserts no implicit drops and adds no receiver-call sugar.
The rule is:
- Compute
Give(Γ, p) = (T, Γ′). - Require
Droppable(T). - Check the following statements under
Γ′.
For a class this moves the value out of its source and calls its destructor. For a struct, dropping the resulting value invokes no code and destroys no object. Struct storage is treated as if garbage collected.
For structs, use exactly the ordinary-give effect. A given struct moves out, leaving an empty slot; a shared struct reference is copied, leaving its source initialized. The empty local binding is retained, as for ordinary give. No binding is removed.
inductive DropTyped (classes : ClassTable) (declarations : Declarations) : Environment → Place → Statement → Environment → 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 →
(Name.destructor owner, declaration) ∈ declarations →
declaration.signature = ⟨[receiver owner .given], none⟩ →
DropTyped classes declarations before place (.dropClass owner place) after
inductive StatementTyped (classes : ClassTable) (declarations : Declarations) : Environment → Statement → Environment → Prop where
| local {before after statement} :
Shared.Typing.StatementTyped 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.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
| dropStruct {before after place ty} :
ExprTyped classes before (.give place) ty after → StructType classes ty →
StatementTyped classes declarations before (.dropStruct place) after
Finishing a frame
An environment is finished when each binding is either empty or has a struct type. A class binding is an outstanding obligation even if its class has a destructor, its view is partial, or all of its fields are empty. A frame may finish only when its statement sequence is exhausted and its environment is finished.
A frame owns a local environment and a sequence of statements still to run. There is one program frame and one fresh frame per active function, method, or destructor call. Names are local to their frame; a destructor cannot access its caller’s locals.
Moving a class to another local transfers the obligation. Storing it inside a class transfers the obligation to that owner; unpacking transfers obligations to the resulting field bindings. No class can be hidden inside a struct, because struct fields must themselves have struct types.
Frame completion discards remaining struct bindings without running code. It inserts no drops and performs no implicit unpacking.
def Finished (classes : ClassTable) (environment : Environment) : Prop :=
∀ name ty, (name, some ty) ∈ environment → StructType classes ty
def StoreFinished (classes : Classes) (state : State) : Prop :=
∀ name reference, (name, some reference) ∈ state.variables →
StructReference classes state reference
Check every declared destructor body starting with exactly self: given C,
where C is its declaring class with its whole view. Its statements must type
check and leave a finished environment. Check ordinary functions and methods using their declared parameters and
result types from the Functions signatures,
requiring a finished environment after evaluation of any return expression.
Check the top-level program from the empty environment with the same final
condition.
All declared destructor signatures are available while checking each body.
A call checks droppability, not an inline expansion of the called body. The
whole declaration table is accepted only when every declared body checks.
This permits recursive destructor calls, including drop self.
The inherited rules for declarations, expressions, fresh bindings, and unpacking otherwise apply; the appendix identifies those rules. Assignment is not part of this layer.
def BodyTyped (classes : ClassTable) (declarations : Declarations) (signature : Signature)
(body : Body) : Prop :=
∃ middle after,
SequenceTyped classes declarations signature.environment body.statements middle ∧
ResultTyped classes middle body.result signature.result after ∧ Finished classes after
def DeclarationsTyped (classes : ClassTable) (declarations : Declarations) : Prop :=
(declarations.map Prod.fst).Nodup ∧
∀ entry ∈ declarations,
Signature.WellFormed classes entry.1 entry.2.signature ∧
BodyTyped classes declarations entry.2.signature entry.2.body
def ProgramTyped (program : Program) : Prop :=
program.classes.WellFormed ∧ DeclarationsTyped program.classes program.declarations ∧
∃ finalEnvironment,
SequenceTyped program.classes program.declarations [] program.main finalEnvironment ∧
Finished program.classes finalEnvironment
Calling and returning
A configuration contains a common heap, the allocation counter, an active frame, and a stack of suspended caller frames, including result destinations for ordinary calls as in Functions. This layer strengthens Functions’ frame-exit rule: a returning body must discharge its class obligations, and remaining struct bindings may be discarded. Eager GC still runs after each transition, including popping the initial frame. A runtime frame contains its local store and remaining statements. A local store maps names to empty slots or references. Heap objects, references, and allocation follow the Shared representation; object modes still belong to references.
The caller stack is empty initially. The initial active frame contains the program and an empty local store. Caller frames retain their locals while a destructor runs, but those locals are inaccessible to the callee. Roots used by the heap invariant include references in every frame, not just the active one, together with temporary values during expression evaluation.
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
def Configuration.initial (program : Program) : Configuration :=
.running State.empty ⟨program.main, none⟩
def Configuration.rootState (configuration : Configuration) : State :=
⟨configuration.objects, configuration.frames.flatMap Frame.variables, configuration.nextId⟩
def Configuration.collect (configuration : Configuration) : Configuration := by
exact { configuration with objects := configuration.rootState.collect.objects }
def Configuration.finished (configuration : Configuration) : Prop :=
configuration.frames = []
The transition rules extend Functions’ ordinary call and return machinery with destructor calls and stricter completion:
| Transition | Action |
|---|---|
| Inherited statement | Execute a Shared binding or unpacking statement in the active frame and common heap, then advance that frame. |
| Drop struct | Perform ordinary give from the source place, discard the resulting struct reference, and advance the active frame. No destructor runs; eager GC reclaims the object if it is no longer reachable. |
| Call class destructor | Perform ordinary give as the sole argument to the declared destructor, suspend the updated caller with its following statements, and start the destructor body in a fresh frame containing only self bound to that reference. |
| Return | Evaluate any ordinary function or method result as in Functions, require no initialized class locals remain, discard the remaining struct locals, and resume the caller with its result if any. A destructor returns no value. |
| Finish program | When the program frame has no statements and no initialized class locals, discard its remaining locals and enter a terminal configuration. |
The call transfers the reference directly to self; it does not destroy the
object. Return does not delete a receiver object. Explicit unpacking is what
removes a class container. A destructor’s statements may allocate, unpack, or
call another destructor using the same rules as the program.
The destructor signature requires a uniquely owned whole instance: all declared fields and their declared subtrees are present, with the permissions required by their types. This is checked statically, using the same argument typing as ordinary calls; the machine does not repeat the view check at runtime. An exhausted frame with an initialized class local cannot return or finish; typing must exclude such configurations.
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)
| «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
Safety and relation to Shared
A typed configuration has a well-formed declaration table, a compatible typing of all live frames, and a common heap realizing all of their roots. Its frame typing checks each active body from its current local environment. For a suspended caller it checks the remainder from the environment after result delivery. Every body ends in a finished environment.
The heap realization is Shared’s realization with an empty variable environment and the frame roots as pending values. Roots retain their multiplicity and their types; frame-local names need not be globally unique. Nominal field correctness covers fields hidden by views.
Write RetainsClasses(H, H′) when every non-struct object present in heap H
is still present, unchanged, in heap H′. This is the collection obligation:
GC may reclaim structs, but a class must be consumed explicitly.
The ownership condition still excludes simultaneous unique and shared paths to an object. Class references remain unique, and struct objects cannot contain class references. After the initial frame is popped, collection leaves the terminal heap empty. An explicit unpack removes its class container; a destructor call alone does not discharge that object’s obligation.
Hiding a field in a view does not erase a runtime class obligation.
def BodyFrom (classes : ClassTable) (declarations : Declarations) (environment : Environment)
(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 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 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
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 another typed configuration and retains every class object still present after the raw transition. Explicit unpacking may remove a class container during the raw transition; collection cannot remove it on the program’s behalf.
The proof discards only struct roots. Since struct fields have struct types, those roots cannot be the sole routes to class objects, even when their views omit fields.
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 := by
obtain ⟨classesWf,declarationsWf,roots,shape,heap⟩ := typed
cases step with
| @«local» beforeState afterState statement rest result frames destination operation =>
cases shape with
| active slots envWf body continuation =>
obtain ⟨middle,final,sequence,returned,finished⟩ := body
cases sequence with
| cons first tail =>
cases first with
| «local» localTyped =>
cases localTyped with
| letValue expression binding =>
cases operation with
| letValue evaluation bound =>
have realized := from_heap heap slots envWf
have evaluated := (expression.sound _ _ realized).2 _ _ evaluation
have afterRealized := binding.preserves_realization_pending evaluated bound
have keys := binding_keys binding bound
(expression.keys.trans (slots.keys.trans evaluation.variable_keys.symm))
obtain ⟨afterRoots,afterSlots⟩ := realized_slots afterRealized keys
have afterHeap := to_heap afterRealized afterSlots
apply collect_safely (garbage := []) (by simp) classesWf declarationsWf
(.active (frame := ⟨afterState.variables,⟨rest,result⟩,destination⟩) afterSlots afterRealized.environmentWellFormed ⟨middle,final,tail,returned,finished⟩ continuation)
simpa only [List.append_nil,heapState,Configuration.rootState,Configuration.running] using afterHeap
| @call beforeState evaluated destination name arguments rest result frames returnTo declaration references
declared resultShape fresh evaluation lengths =>
cases shape with
| active slots envWf body continuation =>
obtain ⟨middle,final,sequence,returned,finished⟩ := body
cases sequence with
| cons first tail =>
cases first with
| call expectedMember _ args delivery =>
have same := member_value_unique declarationsWf.1 expectedMember declared
cases same
have realized := from_heap heap slots envWf
have evaluatedRealized := (args.sound _ _ realized).2 _ _ evaluation
have keys := args.keys.trans (slots.keys.trans (evalArgs_keys evaluation).symm)
obtain ⟨callerRoots,callerSlots⟩ := realized_slots evaluatedRealized keys
have callerHeap := to_heap evaluatedRealized callerSlots
obtain ⟨signatureWf,calleeBody⟩ := declarationsWf.2 _ declared
have calleeSlots := parameter_slots (result := declaration.signature.result) declaration.signature.parameters references lengths
have calleeWf := (BodyFrom.of_declaration calleeBody).sequence_wf
apply collect_safely (garbage := []) (by simp) classesWf declarationsWf
(.active (frame := ⟨parameterStore declaration.signature.parameters references,declaration.body,destination⟩) calleeSlots calleeWf calleeBody
(.caller (caller := ⟨evaluated.variables,⟨rest,result⟩,returnTo⟩) callerSlots evaluatedRealized.environmentWellFormed delivery
⟨middle,final,tail,returned,finished⟩ continuation))
apply callerHeap.perm
simp only [List.map_map, Function.comp_def, List.append_nil]
apply List.Perm.trans (List.Perm.of_eq (List.append_assoc _ _ _).symm)
apply List.Perm.trans (List.perm_append_comm.append_right _)
exact List.Perm.of_eq (List.append_assoc _ _ _)
| @dropStruct beforeState evaluated place reference rest result frames destination evaluation _ =>
cases shape with
| active slots envWf body continuation =>
obtain ⟨middle,final,sequence,returned,finished⟩ := body
cases sequence with
| cons first tail =>
cases first with
| dropStruct expression structTy =>
have realized := from_heap heap slots envWf
have evaluatedRealized := (expression.sound _ _ realized).2 _ _ evaluation
have keys := expression.keys.trans (slots.keys.trans evaluation.variable_keys.symm)
obtain ⟨afterRoots,afterSlots⟩ := realized_slots evaluatedRealized keys
have afterHeap := to_heap evaluatedRealized afterSlots
apply collect_safely (garbage := [(reference, _)]) (by
intro ref ty member; cases List.mem_singleton.mp member; exact structTy) classesWf declarationsWf
(.active (frame := ⟨evaluated.variables,⟨rest,result⟩,destination⟩) afterSlots
evaluatedRealized.environmentWellFormed ⟨middle,final,tail,returned,finished⟩ continuation)
apply afterHeap.perm
simpa only [List.append_assoc, List.cons_append, List.nil_append] using
(List.perm_append_comm (l₁ := [(reference, _)])).append_left afterRoots
| @«return» beforeState evaluated result reference caller frames destination variables evaluation delivered _ =>
cases shape with
| active slots envWf body continuation =>
obtain ⟨middle,final,sequence,returned,finished⟩ := body
cases sequence with
| nil _ =>
cases continuation with
| @caller _ _ _ _ callerEnvironment resumed callerRoots laterRoots callerResult callerSlots callerWf delivery callerBody rest =>
have realized := from_heap heap slots envWf
obtain ⟨evaluatedRealized,staticKeys,runtimeKeys⟩ := returned.preserves realized evaluation
obtain ⟨discarded,discardedSlots⟩ := realized_slots evaluatedRealized
(staticKeys.trans (slots.keys.trans runtimeKeys.symm))
have calleeHeap := to_heap evaluatedRealized discardedSlots
have callerHeap := calleeHeap.perm (show
(discarded ++ (resultRoots reference _ ++ (callerRoots ++ laterRoots))).Perm
(callerRoots ++ (resultRoots reference _ ++ (laterRoots ++ discarded))) from by
exact List.perm_append_comm.trans (by
simpa only [List.append_assoc] using
(List.perm_append_comm (l₁ := resultRoots reference _) (l₂ := callerRoots)).append_right (laterRoots ++ discarded)))
have callerRealized := from_heap callerHeap callerSlots callerWf
obtain ⟨resumedRealized,resumedKeys⟩ := delivery.preserves callerRealized callerSlots.keys delivered
obtain ⟨resumedRoots,resumedSlots⟩ := realized_slots resumedRealized resumedKeys
have resumedHeap := to_heap resumedRealized resumedSlots
apply collect_safely (fun ref ty member => by
obtain ⟨name, envMember, _⟩ := discardedSlots.root member
exact finished name ty envMember) classesWf declarationsWf (.active (frame := ⟨variables,caller.body,caller.destination⟩) resumedSlots resumedRealized.environmentWellFormed callerBody rest)
simpa only [List.append_assoc,heapState,Configuration.rootState,Configuration.running] using resumedHeap
| exit _ =>
cases shape with
| active slots envWf body continuation =>
cases continuation with
| done =>
obtain ⟨middle,final,sequence,returned,finished⟩ := body
cases sequence with
| nil _ =>
cases returned with
| none _ =>
apply collect_safely (roots := []) (fun ref ty member => by
obtain ⟨name, envMember, _⟩ := slots.root (by simpa only [List.append_nil] using member)
exact finished name ty envMember) classesWf declarationsWf .done
simpa only [List.append_nil, List.nil_append, heapState, Configuration.rootState, Configuration.running] using heap
A typed configuration with no frames has an empty heap. There are no remaining class or struct objects.
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 prefix ends in a typed configuration. That configuration is terminal or can take a step, and is not stuck. Recursive functions and destructors are allowed; this theorem does not assert termination.
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 := by
have preserved := (ConfigurationTyped.initial typed).trace trace
have progress := preserved.progress
refine ⟨preserved,progress,?_⟩
intro stuck
rcases progress with finished | successor
· exact stuck.1 finished
· exact stuck.2 successor
Embed a Functions program by preserving its classes, ordinary names, signatures, local statements, and calls. Map each body and frame componentwise. The embedded fragment has no destructor declarations or drop statements.
Require an exit condition: if the current body has no statements, every possible result evaluation must leave a store whose initialized locals are structs, as required by frame completion. This condition is vacuous while a local statement or call remains.
Under this condition, a step from an embedded Functions configuration exists exactly when it is the embedding of a Functions step, including its collection. The backward implication quantifies over arbitrary destructor-machine successors. Thus local operations and ordinary calls retain their behavior. Frame exit adds the explicit consumption requirement.
The typing boundary is intentionally stronger. A Functions or Shared program may discard an initialized class local at exit; this layer rejects it. Preservation of all earlier program typings and completions is therefore not claimed.
theorem step_correspondence (allowed : ExitAllowed classes before) :
Destructors.Step classes (declarations ds) (configuration before) after ↔
∃ successor, Functions.Step classes ds before successor ∧ after = configuration successor := by
constructor
· exact step_backward
· rintro ⟨successor, step, rfl⟩
exact step_forward step allowed
Deferred conveniences
Assignment comes after this layer. Inserting explicit drops at scope exits and around control flow is a later desugaring step, rather than behavior supplied implicitly by these rules.
The spelling self → { resource } could eventually abbreviate
let Wrapper → { resource } = self→;, with the nominal type inferred.
This layer uses the explicit pattern.
After borrows are introduced, reconsider whether structs should support a
user-defined drop body receiving a shared borrow of self. This is a tentative
idea, not part of the destructor layer.
Appendix: inherited Shared machinery
The preceding rules use the following Shared machinery unchanged, except for imposing the completion condition defined above; frames already exist in Shared. These links identify the full inherited definitions; this summary fixes their role in this layer.
| Machinery | Inherited meaning |
|---|---|
| Declarations and kinds | Nominal names and ordered named fields; classes, structs, and shared structs. Only structs satisfy struct(T); struct fields have struct types. |
| Syntax | Places start at locals and follow named fields. Expressions give a place, give-share a place, or construct an object from ordered argument expressions. Bindings use fresh local names. |
| Storage | References carry modes and object identifiers. Object fields contain references or empty slots. Allocation uses fresh, monotonically allocated identifiers. |
| Types and views | Given and shared permissions, whole declared types, and signed views. Positive entries expose whole subtrees, negative entries record empty slots, and omissions are unknown. |
| Ordinary give | Move through a unique path, emptying its final slot; copy through shared access, promoting a unique final reference if necessary. Static give computes the result type and source environment. |
| Construction | Evaluate arguments left to right; require whole declared argument types. Shared structs construct shared references immediately. |
| Unpacking | A unique result can be unpacked with C → { fields }, removing the container and transferring its field slots to bindings. Every direct field’s status must be known; transferred objects may themselves be partial. Shared references cannot be unpacked. |
Shared’s completion bound of one step per statement plus initial-frame exit does not carry over. Rootedness now counts all live frames; eager GC removes unreachable struct storage at each transition boundary. Class obligations survive until explicit consumption.
abbrev Parameter := Functions.Parameter
abbrev Signature := Functions.Signature
inductive ResultTyped (classes : ClassTable) : Environment → Option Value → Option FieldType → Environment → 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) : Environment → Option VariableId → Option FieldType → Environment → 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) : Environment → List Statement → Environment → 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