Functions and methods
Moving a value into a call and back
A function gives a sequence of statements its own parameters and locals. A call transfers argument values into those parameters; a return transfers a result back to the caller.
class Token {}
fn identity(token: → Token) → Token {
return token→;
}
let original = new Token();
let result = identity(original→);
Here → Token in a signature means uniquely owned Token, called given Token in the model. The argument expression original→ empties original.
The function receives that reference in token, then moves it into its return
value. The caller binds the same reference to result. No object is copied or
reconstructed.
The arrow after the parameter list introduces a uniquely owned
result type: fn identity(...) → Token. A shared result instead uses
fn copy(...) shared Point. This chapter uses
the same permission-prefixed type syntax as parameters, without an additional
return-type separator.
This layer adds functions and methods to Shared. The examples check typing and execution in Lean. The new rules come first; the explicit forward reference to the inherited machinery in the appendix keeps the call rules together without repeating Shared’s expression calculus here.
example : ProgramTyped identityProgram ∧
Steps classes.erase declarations (.initial identityProgram) identityReturned ∧
Step classes.erase declarations identityReturned ⟨[], 1, []⟩ ∧
("original", none) ∈ identityReturned.rootState.variables ∧
("result", some (.owned 0)) ∈ identityReturned.rootState.variables :=
⟨⟨by decide, declarations_typed, _, identity_main⟩, identity_execution,
by exact collected_step .exit (by simp), by decide, by decide⟩
A shared parameter receives an owned shared reference. It does not borrow
from the caller, and returning it does not create a dependency on the callee’s
locals.
struct Point {}
fn copy(point: shared Point) shared Point {
return point→;
}
let p = new Point();
let s = p→share;
let t = copy(s→);
Sharing empties the uniquely owned p and produces the shared reference s.
Giving s copies it, and giving the shared parameter point copies it again.
Both s and t remain initialized and refer to the same object.
shared Point means shared[] Point: shared ownership with no lease
dependency. The empty brackets may be omitted. Classes cannot be shared, so a
parameter of type shared Token for the class in the preceding example is
invalid.
example : ProgramTyped sharedProgram ∧
Steps classes.erase declarations (.initial sharedProgram) sharedReturned ∧
Step classes.erase declarations sharedReturned ⟨[], 1, []⟩ ∧
("p", none) ∈ sharedReturned.rootState.variables ∧
("s", some (.shared 0)) ∈ sharedReturned.rootState.variables ∧
("t", some (.shared 0)) ∈ sharedReturned.rootState.variables ∧
¬ Admissible classes (ValueType.whole "Token" .shared) :=
⟨⟨by decide, declarations_typed, _, shared_main⟩, shared_execution,
by exact collected_step .exit (by simp), by decide, by decide, by decide, by decide⟩
Locals live in frames
A suspended caller keeps its locals alive while another function runs:
class Token {}
class Box { child: Token }
fn work() {
let temporary = new Token();
}
let box = new Box(new Token());
work();
The focused runtime check starts inside work, with the caller’s box and its
child already allocated. It checks these transitions:
| Boundary | Frames | Heap |
|---|---|---|
After allocating temporary | work, initial caller | box, child, temporary |
After returning from work | initial caller | box, child |
| After popping the initial frame | none | empty |
The box is rooted only by the suspended caller during work; its child is
reachable through a field. Both survive collection. The temporary is reclaimed
as soon as work returns. All three object identifiers remain spent: the final
allocation counter is three. The check also covers the single exit step of an
empty program.
These examples observe returned values before the final frame exits. The frame rules and collector definition below make this lifetime explicit. The later Destructors layer will require consuming class values before a frame can exit; this layer permits them to become unreachable.
example : Step classes.erase declarations gcBefore gcDuring ∧
gcDuring.objects.length = 3 ∧
Step classes.erase declarations gcDuring gcAfter ∧
gcAfter.objects = callerHeap ∧
Step classes.erase declarations gcAfter ⟨[], 3, []⟩ ∧
(Configuration.mk [] 3 []).finished ∧
Step classes.erase declarations (.initial ⟨classes, declarations, []⟩) ⟨[], 0, []⟩ :=
⟨gc_local, rfl, gc_return, rfl, collected_step .exit (by simp), rfl,
collected_step .exit (by simp)⟩
Methods choose a receiver permission
A method belongs to a nominal declaration. Its first parameter names the
permission it requires for self; the enclosing declaration fixes the nominal
type of the receiver.
struct Point {
fn take(→self) → Point {
return self→;
}
fn copy(shared self) shared Point {
return self→;
}
}
let p = new Point();
let q = Point.take(p→);
let s = q→share;
let t = Point.copy(s→);
The take call gives p to an owned receiver. The copy call gives s, which
produces a shared copy, to a shared receiver. p becomes empty; s remains
initialized. Both receiver permissions use prefix syntax in declarations.
There is no general self: Type receiver form.
Each call names the enclosing type and method explicitly, with the receiver as the first argument. The give operation moves or copies according to the receiver’s permission. Method-call sugar is deferred to a later layer.
example : ProgramTyped methodProgram ∧
Steps classes.erase declarations (.initial methodProgram) methodReturned ∧
Step classes.erase declarations methodReturned ⟨[], 1, []⟩ ∧
("p", none) ∈ methodReturned.rootState.variables ∧
("s", some (.shared 0)) ∈ methodReturned.rootState.variables ∧
("t", some (.shared 0)) ∈ methodReturned.rootState.variables :=
⟨⟨by decide, declarations_typed, _, method_main⟩, method_execution,
by exact collected_step .exit (by simp), by decide, by decide, by decide⟩
Syntax
A callable name \(a\) identifies either a global function \(f\) or a method named \(m\) of nominal type \(C\). Parameter names \(x\) are local variables. A signature type \(T\) is a whole nominal type with an explicit permission \(Q\); it carries no partial view.
Here \(P\) is a parameter, \(R\) an optional result type, and \(\sigma\) a signature.
shared[] abbreviates the same permission as shared. The model calls →
permission given. A result annotation follows the parameter list directly;
its absence denotes no result. There is no implicit parameter permission.
A method’s first parameter is written →self or shared self. These elaborate
to the parameter named self with type → C or shared C, respectively,
where C is the enclosing nominal type. No self: Type surface form is
provided. Ordinary function parameters cannot be named self.
A well-formed signature has distinct parameter names and admissible parameter and result types. A method must have its correctly named and typed receiver first. In particular, classes admit only given access, shared structs admit only shared access, and ordinary structs admit either.
inductive Name where
| function (name : String)
| method (owner : ClassName) (name : String)
deriving DecidableEq, Repr
structure Parameter where
name : VariableId
type : FieldType
deriving DecidableEq, Repr
structure Signature where
parameters : List Parameter
result : Option FieldType
deriving DecidableEq, Repr
def receiver (owner : ClassName) (permission : Perm) : Parameter :=
⟨"self", ⟨permission, owner⟩⟩
def Signature.WellFormed (classes : ClassTable) (name : Name)
(signature : Signature) : Prop :=
(signature.parameters.map 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 Parameter.name
| .method owner _ => match signature.parameters with
| [] => False
| first :: rest => first.name = "self" ∧ first.type.className = owner ∧
"self" ∉ rest.map Parameter.name
A value expression \(e\) and binding pattern \(b\) are inherited from Shared (see the appendix). An optional call destination \(d\) is either a fresh local name or absent. The core syntax is:
Here \(t\) is a statement, \(r\) an optional return expression, \(B\) a
body, and \(D\) a declaration pairing a signature with its body. The call notation above is metasyntax:
let x = f(args); supplies destination x, while f(args); supplies none.
A method call is C.method(receiver, args), with its receiver as argument zero.
There is no receiver-based call sugar.
A body stores its final return separately from its statement list. return;
and falling off the end both mean no return expression. There are no early
returns. Receivers, arguments, and returned values use call-free expressions;
write nested calls as successive statements.
A program contains a nominal class table \(\Delta\), a declaration table \(F\) listing callable-name/declaration pairs, and a top-level statement list. Method lookup uses the qualified name, not runtime dispatch. There is no overloading. These are abstract syntax definitions, not a source parser.
inductive Statement where
| local (statement : Unpacking.Statement)
| call (destination : Option VariableId) (name : Name) (arguments : List Value)
deriving Repr
structure Body where
statements : List Statement
result : Option Value
deriving Repr
structure Declaration where
signature : Signature
body : Body
deriving Repr
structure Program where
classes : ClassTable
declarations : Declarations
main : List Statement
deriving Repr
Typing calls and bodies
An environment \(\Gamma\) maps local names to types or empty slots. Write \(\operatorname{WF}_{\Delta}(\Gamma)\) for the inherited check of distinct names and normalized, admissible types. Write \(\operatorname{env}(\sigma)\) for a signature’s parameter environment: each parameter is initially present at its declared whole type. Write \(\operatorname{params}(\sigma)\) for its ordered parameter types and \(\operatorname{result}(\sigma)\) for its optional result type.
def Signature.environment (signature : Signature) : Environment :=
signature.parameters.map fun p => (p.name, some p.type.toType)
The judgment \(\Delta\vdash\Gamma;d:R\Rightarrow\Gamma'\) installs a call’s result in a well-formed environment. An absent destination requires an absent result; a present one uses Shared’s fresh-variable binding judgment, written \(\Delta\vdash\Gamma;x:T\Rightarrow_{\mathrm{bind}}\Gamma'\).
A value-returning call cannot silently discard its result. The binding premise also checks admissibility and freshness.
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
Write \(\Delta;F\vdash\Gamma\mathrel{\xrightarrow{t}}\Gamma'\) for statement typing. Shared’s argument judgment \(\Delta\vdash\Gamma;{\overline e}:{\overline T}\Rightarrow\Gamma_e\) checks arguments left to right and threads their effects through the environment. The receiver, when present, is the first argument.
The destination judgment installs the result after argument evaluation.
The freshness premise is vacuous when \(d=\mathsf{none}\). Arguments must match the declared whole types; there is no automatic sharing at the boundary. The rule consults a signature, not a body expansion.
Shared bindings and unpacking retain their typing rule. Sequence typing chains statement environments; an empty sequence requires a well-formed environment:
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 Parameter.type) middle →
DestinationTyped classes middle destination declaration.signature.result after →
StatementTyped classes declarations before (.call destination name arguments) 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
The judgment \(\Delta\vdash\Gamma;r:R\Rightarrow_{\mathrm{return}}\Gamma'\) checks the final return. The environment condition is inherited. It has two cases:
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
A body checks against its signature by typing its statements from the parameter environment, then checking its return expression:
There is no consumption condition on \(\Gamma_f\) in 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
A declaration table checks when callable names are distinct and every signature is well formed and every body checks against its signature, using the complete table. This permits mutual recursion.
def DeclarationsTyped (classes : ClassTable) (declarations : Declarations) : Prop :=
(declarations.map Prod.fst).Nodup ∧
∀ entry ∈ declarations,
entry.2.signature.WellFormed classes entry.1 ∧
BodyTyped classes declarations entry.2.signature entry.2.body
A program checks when its nominal table and declaration table check, and its top-level statements check from the empty environment to some final environment.
def ProgramTyped (program : Program) : Prop :=
program.classes.WellFormed ∧ DeclarationsTyped program.classes program.declarations ∧
∃ finalEnvironment,
SequenceTyped program.classes program.declarations [] program.main finalEnvironment
Every typed call names a declaration in its table, supplies exactly as many arguments as that declaration has parameters, and supplies a destination exactly when the declaration has a result.
theorem call_arity
(typed : StatementTyped classes declarations before (.call destination name arguments) after) :
∃ declaration, (name, declaration) ∈ declarations ∧
arguments.length = declaration.signature.parameters.length ∧
DestinationMatches destination declaration.signature.result := by
cases typed with
| call declared _ args dest =>
exact ⟨_, declared, by simpa using args.length, dest.shape⟩
The formal checks reject each of these boundaries:
| Attempt | Reason |
|---|---|
fn bad(x: shared Token) with class Token | Classes cannot be shared. |
A Point method with a receiver of nominal type Token in the core signature | A method’s receiver must have its enclosing nominal type. |
let x = identity(); | The owned parameter is missing. |
identity(new Token()); | The call omits the destination for its result. |
example :
¬ Signature.WellFormed classes (.function "bad") ⟨[⟨"x", ⟨.shared, "Token"⟩⟩], none⟩ ∧
¬ Signature.WellFormed classes (.method "Point" "bad")
⟨[⟨"self", ownedToken⟩], none⟩ ∧
(∀ after, ¬ StatementTyped classes [(.function "identity", identity)] []
(.call (some "x") (.function "identity") []) after) ∧
(∀ after, ¬ StatementTyped classes [(.function "identity", identity)] []
(.call none (.function "identity") [.new "Token" []]) after) := by
refine ⟨by decide, by decide, ?_, ?_⟩
· intro after typed
obtain ⟨declaration, member, arity, _⟩ := call_arity typed
simp only [List.mem_singleton, Prod.mk.injEq] at member
rcases member with ⟨_, rfl⟩
cases arity
· intro after typed
obtain ⟨declaration, member, _, shape⟩ := call_arity typed
simp only [List.mem_singleton, Prod.mk.injEq] at member
rcases member with ⟨_, rfl⟩
cases shape
Stores, frames, and calls
Each call has a frame \(\phi\) containing its local store \(V\), remaining body \(B\), and destination \(d\) for its result in the caller. A store maps local names to references or empty slots. The frame stack \(K\) lists the active frame first, followed by suspended callers. The heap \(H\) and next object identifier \(n\) belong to the whole machine:
Only the active frame’s locals are accessible to expressions. For evaluation,
combine them with the heap and counter to form Shared’s state \(S=(H,V,n)\).
The Lean helper Configuration.running constructs a configuration from such a
state, an active body, a caller stack, and a result destination.
The initial configuration has an empty heap, counter zero, and one frame: empty locals, the program’s statements, no return expression, and no destination.
abbrev Store := List (VariableId × Slot)
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.running (state : State) (body : Body)
(frames : List Frame := []) (destination : Option VariableId := none) : Configuration :=
⟨state.objects, state.nextId, ⟨state.variables, body, destination⟩ :: frames⟩
def Configuration.initial (program : Program) : Configuration :=
.running State.empty ⟨program.main, none⟩
A configuration is finished exactly when its frame stack is empty. Exhausting the initial body’s statements still leaves its frame to be popped.
def Configuration.finished (configuration : Configuration) : Prop :=
configuration.frames = []
Roots are initialized local slots in all live frames, including suspended
callers. rootState concatenates their stores solely to reuse Shared’s
reachability relation; identical local names in different frames remain distinct
slots. There are no retained stores from completed calls.
def Configuration.rootState (configuration : Configuration) : State :=
⟨configuration.objects, configuration.frames.flatMap Frame.variables, configuration.nextId⟩
def Configuration.roots (configuration : Configuration) : List Reference :=
configuration.rootState.variables.filterMap Prod.snd
As in Shared, eager garbage collection, written \(\operatorname{gc}(M)\), retains exactly
the heap entries reachable from the live frames’ roots. Here \(o\) is an
object identifier and \(h\) its class tag and field store. Reachability follows
zero or more initialized object fields, regardless of reference permission.
Write \(\operatorname{live}_M(o)\) for Shared’s Live relation with all frame
stores as its variable store. Then:
Collection preserves surviving objects, their identifiers and fields, the allocation counter, and every frame. It invokes no destructor. With no frames, there are no roots and collection removes the entire heap.
This is a mathematical definition of the resulting heap. Its Lean definition reuses Shared’s noncomputable reachability filter; it does not prescribe an executable graph-traversal algorithm.
def Configuration.collect (configuration : Configuration) : Configuration := by
exact { configuration with objects := configuration.rootState.collect.objects }
def State.collect (state : State) : State := by
classical
exact { state with objects := state.objects.filter (fun entry => decide (Live state entry.1)) }
For equally long parameter and reference lists, \(\operatorname{bind}(\sigma, {\overline v})\) pairs each parameter name with its argument reference, in order. Here \(v\) denotes a runtime reference. The call rule checks lengths before using this operation.
Write \(d\sim R\) when destination and result are either both present or both absent. This is an operational shape check, not runtime type checking.
def parameterStore (parameters : List Parameter) (references : List Reference) : Store :=
(parameters.map Parameter.name).zip (references.map some)
def DestinationMatches (destination : Option VariableId)
(result : Option Shared.Typing.FieldType) : Prop :=
destination.isSome = result.isSome
Let \(u\) be an optional reference. Write \(S\vdash r\Downarrow S_e;u\) for optional-result evaluation. An absent expression produces no reference and leaves the state unchanged; a present one uses Shared’s value evaluation.
Delivery, written \(V;d;u\Rightarrow V'\), has just two cases:
inductive ResultEval (classes : Classes) : State → Option Value → State → Option Reference → Prop where
| none (state : State) : ResultEval classes state none state none
| some {before after value reference} :
Eval classes before value after reference →
ResultEval classes before (some value) after (some reference)
inductive Deliver : Store → Option VariableId → Option Reference → Store → Prop where
| none (variables : Store) : Deliver variables none none variables
| some {variables name reference} :
name ∉ variables.map Prod.fst →
Deliver variables (some name) (some reference) ((name, some reference) :: variables)
Every transition first performs a raw step \(M\rightsquigarrow M_r\), then collects. Raw steps are auxiliary rules, not observable machine steps:
In the rules below, \(S=(H,V,n)\) is the active frame’s evaluation state, and \(S_e=(H_e,V_e,n_e)\) is its result. Write \(S\vdash{\overline e}\Downarrow S_e;{\overline v}\) for Shared’s left-to-right argument evaluation, and \(S\vdash t\Downarrow S_e\) for one Shared binding or unpacking statement. Write \(B_r=({\overline t};\mathsf{return}\ r)\) for the remaining body and \(d_0\) for the current frame’s own return destination.
The parameter operations define \(d\sim R\) and \(\operatorname{bind}\). The return premises use optional-result evaluation and delivery.
Local statement
Call
Freshness is vacuous for an absent destination. The caller retains its updated locals and continuation; the callee receives a new frame. Arguments are transferred to parameters before collection. Qualified methods use this same rule.
Return
Evaluate the result, deliver it to the caller, and pop the callee. Collection then uses the resumed caller and remaining frames as roots. A returned object survives even when its last callee reference has just disappeared. Other objects reachable only from the departed frame are reclaimed.
Initial frame exit
Collection makes this step’s target \(\langle\varnothing,n,[]\rangle\). Even an empty program takes this exit step. No rule steps from an empty stack.
No collection occurs midway through expression evaluation: constructor arguments, call arguments, and returned values remain available until the raw transition finishes transferring them. Collection runs after local statements, calls, returns, and initial-frame exit.
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)
| «return» {before evaluated result reference caller frames destination variables} :
ResultEval classes before result evaluated reference →
Deliver caller.variables destination reference variables →
RawStep classes declarations
(.running before ⟨[], result⟩ (caller :: frames) destination)
(.running { evaluated with variables := variables } caller.body frames caller.destination)
| exit {objects nextId variables} :
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
A nested call suspends the current function just as the outer call suspended the program. Reusing a local name in different frames does not identify their storage slots:
class Token {}
fn identity(token: → Token) → Token {
return token→;
}
fn relay(token: → Token) → Token {
let answer = identity(token→);
return answer→;
}
let token = new Token();
let result = relay(token→);
All three frames have a local named token. After both returns, the program’s
token is empty and result owns the original object. Only the initial
frame remains. The example checks typing, these observations after the calls,
and the final exit step that pops this frame and empties the heap.
example : ProgramTyped nestedProgram ∧
Steps classes.erase nestedTable (.initial nestedProgram) nestedReturned ∧
Step classes.erase nestedTable nestedReturned ⟨[], 1, []⟩ ∧
nestedReturned.rootState.variables = [("result", some (.owned 0)), ("token", none)] ∧
nestedReturned.frames.length = 1 :=
⟨nested_typed, nested_execution, by exact collected_step .exit (by simp), rfl, rfl⟩
Completion and recursion
This layer accepts a function that leaves its owned parameter initialized:
class Token {}
fn leave(token: → Token) { }
let t = new Token();
leave(t→);
Returning from leave pops its frame. The caller’s t is empty, so eager GC
immediately reclaims the token, before the initial frame exits. Nothing invokes
a destructor. Explicit unpacking is also accepted:
fn consume(token: → Token) {
let Token → {} = token→;
}
The checks cover the first program’s typing and full execution, and the second function’s body typing. Mandatory consumption is added in the next layer; it is not a premise of these Functions rules.
example : ProgramTyped leaveProgram ∧
Steps classes.erase declarations (.initial leaveProgram) leaveReturned ∧
Step classes.erase declarations leaveReturned ⟨[], 1, []⟩ ∧ leaveReturned.objects = [] ∧
BodyTyped classes declarations consume.signature consume.body :=
⟨⟨by decide, declarations_typed, _, leave_main⟩, leave_execution,
by exact collected_step .exit (by simp), rfl, consume_body⟩
The relation \(M\longrightarrow^{*}M'\) is the reflexive, transitive closure of steps, represented by zero steps or one step followed by a trace.
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 stuck when it is not finished and has no successor.
def Stuck (classes : Classes) (declarations : Declarations) (configuration : Configuration) : Prop :=
¬ configuration.finished ∧ ¬ ∃ after, Step classes declarations configuration after
fn recur() {
recur();
}
recur();
This program checks. After any number of calls it can call again, adding one suspended caller. The formal example supplies an infinite sequence of adjacent steps, all reachable from the initial configuration and none finished. The Shared completion bound therefore does not extend to Functions.
example : ProgramTyped recursionProgram ∧
(∀ depth, Steps classes.erase recursionTable (.initial recursionProgram) (recursionState depth)) ∧
(∀ depth, Step classes.erase recursionTable (recursionState depth) (recursionState (depth + 1))) ∧
(∀ depth, ¬ (recursionState depth).finished) := by
refine ⟨⟨by decide, ?_, [], .cons recursive_statement (.nil (by decide))⟩,
recursion_reachable, recursive_step, ?_⟩
· refine ⟨by decide, ?_⟩
intro entry member
have : entry = (.function "recur", recur) := by simpa [recursionProgram, recursionTable] using member
subst entry
exact ⟨by decide, [], [], .cons recursive_statement (.nil (by decide)), .none (by decide)⟩
· intro depth
simp [recursionState, Configuration.finished, Configuration.running]
A finished configuration has no successor, for any declaration table.
theorem finished_no_step (finished : configuration.finished) :
¬ Step classes declarations configuration after := by
intro step
cases step with
| collect raw => cases raw <;> simp_all [Configuration.finished, Configuration.running]
If a machine step reaches a finished configuration, its heap is empty. The allocation counter need not be zero. This theorem concerns the targets of steps; an arbitrary hand-written configuration with no frames need not already have been collected.
theorem terminal_heap_empty (step : Step classes declarations before after)
(finished : after.finished) : after.objects = [] := by
cases step with
| collect raw =>
cases raw <;> simp_all [Configuration.finished, Configuration.running,
Configuration.collect_frames, Configuration.collect_empty_frames]
Embed a Shared program configuration with the same heap and allocation counter. Its live frame becomes a one-element Functions stack with no result or return destination; its absent frame becomes an empty stack. Wrap each statement as a local statement.
Under any callable table, every Shared step has its corresponding Functions step. Conversely, every Functions successor of an embedded configuration is exactly the embedding of a Shared successor. This includes collection and the initial-frame exit, and quantifies over arbitrary successors and starting states. There is no extra Functions-only completion step: both layers pop their initial frame and collect at the same boundary.
theorem framed_step_correspondence :
Functions.Step classes declarations (embedFramed before) after ↔
∃ successor, Framed.Step (Framed.patternOperation classes) before successor ∧ after = embedFramed successor := by
constructor
· exact framed_step_backward
· rintro ⟨successor, step, rfl⟩
exact framed_step_forward step
Every finite Functions trace from an embedded Shared program configuration has a Shared trace to a configuration whose embedding is exactly the Functions endpoint. This includes finished configurations with no frames or heap objects; no well-formedness restriction is needed for this correspondence.
theorem framed_steps_backward (steps : Functions.Steps classes declarations start after) :
∀ before, start = embedFramed before →
∃ successor, Framed.Steps (Framed.patternOperation classes) before successor ∧ after = embedFramed successor := by
induction steps with
| refl => intro before equality; exact ⟨before, ⟨0, .refl _⟩, equality⟩
| step first _ ih =>
intro before equality
subst equality
obtain ⟨middle, original, rfl⟩ := framed_step_backward first
obtain ⟨last, ⟨count, rest⟩, equality⟩ := ih middle rfl
exact ⟨last, ⟨count + 1, .step original rest⟩, equality⟩
For any initial and final environments, nominal table, and callable table, a sequence containing only embedded Shared statements checks in Functions if and only if the original sequence checks in Shared.
theorem typing_correspondence :
Functions.SequenceTyped classes declarations before (code.map Functions.Statement.local) after ↔
Typing.SequenceTyped classes before code after :=
⟨fun typed => typing_backward typed code rfl, typing_forward⟩
A Shared program configuration is finished exactly when its Functions embedding is finished. Both conditions mean the initial frame has been popped.
theorem framed_finished_correspondence :
(embedFramed configuration).finished ↔ configuration.finished := by
rcases configuration with ⟨objects, nextId, frame⟩
cases frame <;> simp [embedFramed, Functions.Configuration.finished, Framed.Configuration.finished]
A Shared program configuration is stuck exactly when its Functions embedding is stuck, for any nominal and callable tables. An exhausted live frame can take its exit step in both layers; an absent frame is finished in both.
theorem framed_stuck_correspondence :
Functions.Stuck classes declarations (embedFramed configuration) ↔
Framed.Stuck (Framed.patternOperation classes) configuration := by
simp only [Functions.Stuck, Framed.Stuck, framed_finished_correspondence]
constructor
· rintro ⟨unfinished, noStep⟩
exact ⟨unfinished, fun ⟨after, step⟩ => noStep ⟨_, framed_step_forward step⟩⟩
· rintro ⟨unfinished, noStep⟩
refine ⟨unfinished, ?_⟩
rintro ⟨after, step⟩
obtain ⟨successor, original, _⟩ := framed_step_backward step
exact noStep ⟨successor, original⟩
Safety across calls
The nested relay/identity example uses token in three different frames.
The safety check now covers every finite execution prefix of that program:
the whole stack remains well typed, and execution cannot get stuck. It also
checks the returned initial frame and the empty terminal state after its exit.
The following stack-typing definition explains what being well typed means for a suspended
caller whose result has not arrived yet.
example :
(∀ configuration, Steps classes.erase nestedTable (.initial nestedProgram) configuration →
ConfigurationTyped classes nestedTable configuration ∧ ¬ Stuck classes.erase nestedTable configuration) ∧
ConfigurationTyped classes nestedTable nestedReturned ∧
ConfigurationTyped classes nestedTable ⟨[],1,[]⟩ := by
refine ⟨fun configuration trace => ?_, ?_, ?_⟩
· have safe := program_safety nested_typed trace
exact ⟨safe.1,safe.2.2⟩
· exact (program_safety nested_typed nested_execution).1
· have exit : RawStep classes.erase nestedTable nestedReturned ⟨nestedReturned.objects,1,[]⟩ := .exit
have collected := Step.collect exit
simp only [Configuration.collect_empty_frames] at collected
exact (program_safety nested_typed nested_execution).1.preservation collected
A typed store pairs a frame’s environment with its runtime locals, in order. Their names agree, empty descriptions have empty slots, and each initialized slot pairs a reference with its type. Write \(\mathcal R\) for the resulting list of reference/type pairs. These are the frame’s typed roots.
The list retains occurrences: two shared aliases contribute two roots even when their references are equal. This relation only pairs names, slots, and types; it does not itself require distinct names or check the heap.
inductive Slots : Environment → Store → PendingValues → Prop where
| nil : Slots [] [] []
| empty {environment variables roots} (name) : Slots environment variables roots →
Slots ((name, none) :: environment) ((name, none) :: variables) roots
| value {environment variables roots} (name reference ty) : Slots environment variables roots →
Slots ((name, some ty) :: environment) ((name, some reference) :: variables) ((reference, ty) :: roots)
Write \(\Delta;F\vdash M\ \mathsf{ok}\) when the machine is well typed. Its nominal and callable tables must check. The remaining requirements are:
| Component | Requirement |
|---|---|
| Active frame | Its locals form a typed store; its remaining statements and return expression check from that environment to its promised optional result type. |
| Suspended caller | Its stored locals form a typed store before delivery. The delivery typing judgment checks the destination against the callee’s promised result type. Its remaining body checks from the environment after delivery. |
| Outer callers | The same condition repeats down the stack, using each caller’s own result destination and promised result type. |
| Initial frame | Its result and destination are absent; there is no caller below it. |
| Common heap | Shared realization holds with an empty variable environment and all frames’ typed roots as pending values. |
Thus the heap counts every owner, including those in suspended callers, while expression evaluation sees only the active frame’s locals. Realization checks reference modes and views, nominal field types, object layouts, allocation bounds, and compatibility of owning occurrences. A finished stack has no roots.
The Lean BodyFrom judgment checks a remaining body from a given environment.
ContinuationTyped checks the suspended callers, StackShape adds the active
frame (or an empty stack), and ConfigurationTyped joins those checks to heap
realization. None assumes a future execution or successful runtime operation.
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
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 heapState (state : State) : State := ⟨state.objects,[],state.nextId⟩
A well-typed machine is finished or has a successor:
This includes calls, returns, and the initial-frame exit. The transition uses the erased nominal table and the same callable table as the typing judgment.
theorem ConfigurationTyped.progress {configuration : Configuration}
(typed : ConfigurationTyped classes declarations configuration) :
configuration.finished ∨ ∃ after, Step classes.erase declarations configuration after := by
rcases configuration with ⟨objects,nextId,frames⟩
obtain ⟨classesWf,declarationsWf,roots,shape,heap⟩ := typed
cases shape with
| done => exact .inl rfl
| @active frame rest environment localRoots laterRoots result slots envWf body continuation =>
have realized := from_heap heap slots envWf
rcases frame with ⟨variables,frameBody,destination⟩
rcases frameBody with ⟨code,returnValue⟩
obtain ⟨middle,final,sequence,returned⟩ := body
right
cases code with
| cons first restCode =>
cases sequence with
| cons firstTyped tail =>
cases firstTyped with
| «local» localTyped =>
cases localTyped with
| letValue expression binding =>
obtain ⟨evaluated,reference,evaluation⟩ := (expression.sound _ _ realized).1
have evaluatedRealized := (expression.sound _ _ realized).2 _ _ evaluation
obtain ⟨after,operation⟩ := binding.exists_bind_pending evaluatedRealized
exact ⟨_,.collect (.local (.letValue evaluation operation))⟩
| call declared fresh args dest =>
obtain ⟨evaluated,references,evaluation⟩ := (args.sound _ _ realized).1
exact ⟨_,.collect (.call declared dest.shape
(fun x member occupied => fresh x member ((realized.variableDomain x).mpr occupied))
evaluation (by simpa using evaluation.length.trans args.length))⟩
| nil =>
cases sequence with
| nil _ =>
obtain ⟨evaluated,reference,evaluation,resultShape⟩ := returned.exists_eval realized
cases continuation with
| done =>
cases returned with
| none _ => exact ⟨_,.collect .exit⟩
| caller callerSlots _ delivery _ _ =>
obtain ⟨variables,delivered⟩ := delivery.exists_deliver callerSlots resultShape
exact ⟨_,.collect (.return evaluation delivered)⟩
Every machine step preserves machine typing:
This quantifies over every operational successor. Calls transfer argument roots to a new frame; returns deliver the result and remove the callee. Eager collection is part of the step. Objects reachable only from discarded locals can disappear, while the returned value and surviving callers retain their views and ownership guarantees.
theorem ConfigurationTyped.preservation {before after : Configuration}
(typed : ConfigurationTyped classes declarations before)
(step : Step classes.erase declarations before after) :
ConfigurationTyped classes declarations after := by
cases step with
| collect raw => exact raw.preserves typed
In a well-typed machine, the references in all live 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. These statements count all frames without requiring their local names to be globally distinct.
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 well-typed finished configuration has an empty heap. Its initial frame has been popped, so no locals remain. The allocation counter is retained. This strengthens the earlier step-target result to every configuration satisfying the stack typing judgment.
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
For a well-typed program, every configuration reached by a finite execution from its initial configuration remains well typed and is finished or can step. Consequently no such execution reaches a stuck configuration.
The theorem permits recursion and does not assert termination or a step bound. It starts from ordinary program typing; there is no operational-success premise added to function or method declarations.
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
For the earlier recur() program, the machine remains well typed and is not
stuck at every recursion depth. Each such state takes the next recursive-call
step. Safety therefore holds along the infinite execution already exhibited
by the example, despite the growing stack.
example : ∀ depth,
ConfigurationTyped classes recursionTable (recursionState depth) ∧
¬ Stuck classes.erase recursionTable (recursionState depth) ∧
Step classes.erase recursionTable (recursionState depth) (recursionState (depth+1)) := by
intro depth
have safe := program_safety recursion_typed (recursion_reachable depth)
exact ⟨safe.1,safe.2.2,recursive_step depth⟩
Later permissions and defaults
The intended permission design extends the current owned permissions with two independent distinctions:
| Unique | Shared | |
|---|---|---|
| Owned | given, spelled → in signatures | shared[], abbreviated shared |
| Leased | mut[places...] | shared[places...] |
The eventual mutable access expression is p!, including p!method(...).
A bare place expression p will abbreviate p.share, producing
shared[p]; p.method(...) will use that borrowed receiver. Applying share
to a value, as in p→share, instead produces owned shared[] access.
Receiver declarations keep permissions in prefix position:
fn method(→self, arg: → Foo)
fn method(!self, arg: !Foo)
fn method(shared self, arg: shared Foo)
fn method(self, arg: Foo)
fn method[perm P](P self, arg: P Foo)
Bare argument types and bare self are intended to introduce generic
permissions constrained to support reading, rather than assume unique
ownership. The constraint’s name and exact meaning remain to be designed;
readable(P) is a candidate, not an established predicate. These defaults,
leases, permission parameters, where-clauses, and permission-based method
overloading are outside the initial Functions layer.
Appendix: inherited Shared machinery
The call machine and its typing judgments live in Functions/. They explicitly
use Shared’s call-free expressions, storage, and binding judgments. There is
no change to those definitions in this layer:
| Machinery | Inherited behavior |
|---|---|
| Nominal kinds | Classes cannot be shared; struct fields have struct types. |
| Storage | References carry modes; slots hold a reference or are empty; allocation is monotonic. |
| Views | Positive entries expose whole subtrees, negative entries record empty slots, and omissions are unknown. |
| Giving | Unique access moves; shared access copies, promoting a unique final stored reference when necessary. |
| Expressions | Constructor arguments are evaluated left to right and require whole declared types. Shared structs construct shared references immediately. |
| Unpacking | Unpacking requires unique access and known status for every direct field, removes the container, and transfers its field slots to fresh bindings. |
The call syntax, frame stores, and call/return judgments are defined separately in Functions. Assignments, destructors, branches, loops, and borrowing remain outside this layer.
inductive Value where
| give (source : Place)
| giveShare (source : Place)
| new (className : ClassName) (arguments : List Value)
deriving Repr
structure State where
objects : List (ObjectId × Object)
variables : List (VariableId × Slot)
nextId : Nat
deriving DecidableEq, Repr
inductive Give : State → Place → Reference → State → Prop where
| move {state cleared : State} {path : Place} {source : StoragePlace} {object : ObjectId} :
Resolve state path source object .unique →
Take state source object cleared →
Give state path (.owned object) cleared
| copy {state : State} {path : Place} {source : StoragePlace} {object : ObjectId} :
Resolve state path source object .shared →
Stored state source (some (.shared object)) →
Give state path (.shared object) state
| promote {state promoted : State} {path : Place} {source : StoragePlace} {object : ObjectId} :
Resolve state path source object .shared →
Promote state source object promoted →
Give state path (.shared object) promoted
inductive Eval (classes : Classes) : State → Value → State → Reference → Prop where
| give {state evaluated : State} {path : Place} {reference : Reference} :
Give state path reference evaluated →
Eval classes state (.give path) evaluated reference
| giveShare {state evaluated : State} {path : Place} {reference : Reference} :
Give state path reference evaluated →
StructReference classes evaluated reference →
Eval classes state (.giveShare path) evaluated (.shared reference.object)
| new {state evaluated : State} {className : ClassName} {declaration : Class}
{arguments : List Value} {references : List Reference} :
(className, declaration) ∈ classes →
EvalArgs classes state arguments evaluated references →
references.length = declaration.fields.length →
ObjectId.mk evaluated.nextId ∉ evaluated.objects.map Prod.fst →
StructArguments classes evaluated declaration.kind references →
Eval classes state (.new className arguments)
(evaluated.allocate className declaration.fields references) (⟨declaration.kind.mode, ⟨evaluated.nextId⟩⟩)
inductive EvalArgs (classes : Classes) : State → List Value → State → List Reference → Prop where
| nil (state : State) : EvalArgs classes state [] state []
| cons {before middle after : State} {argument : Value} {arguments : List Value}
{reference : Reference} {references : List Reference} :
Eval classes before argument middle reference →
EvalArgs classes middle arguments after references →
EvalArgs classes before (argument :: arguments) after (reference :: references)
inductive Pattern where
| variable (name : VariableId)
| unpack (className : ClassName) (fields : List (FieldName × VariableId))
deriving DecidableEq, Repr
inductive Bind (classes : Classes) : State → Reference → Pattern → State → Prop where
| variable {state object name} :
name ∉ state.variables.map Prod.fst →
Bind classes state object (.variable name) (state.bind name object)
| unpack {before after variables nextId object className fields pattern bindings declaration} :
(className, declaration) ∈ classes →
fields.map Prod.fst = declaration.fields →
(pattern.map Prod.fst).Nodup →
(pattern.map Prod.snd).Nodup →
(∀ name ∈ pattern.map Prod.snd, name ∉ variables.map Prod.fst) →
Transfer pattern fields bindings →
Bind classes ⟨before ++ (object, ⟨className, fields⟩) :: after, variables, nextId⟩
(.owned object) (.unpack className pattern)
⟨before ++ after, bindings ++ variables, nextId⟩
inductive ExprTyped (classes : ClassTable) : Environment → Value → ValueType → Environment → Prop where
| give {before after : Environment} {place : Place} {ty : ValueType} :
before.WellFormed classes →
Typing.give classes before place = some (ty, after) →
Admissible classes ty → after.WellFormed classes →
ExprTyped classes before (.give place) ty after
| giveShare {before after : Environment} {place : Place} {ty : ValueType} :
before.WellFormed classes →
Typing.give classes before place = some (ty, after) →
Admissible classes ty → after.WellFormed classes →
StructType classes ty →
ExprTyped classes before (.giveShare place) ty.shared after
| new {before after : Environment} {name : ClassName} {declaration : TypedClass}
{arguments : List Value} :
(name, declaration) ∈ classes →
ArgsTyped classes before arguments (declaration.fields.map Prod.snd) after →
Admissible classes (ValueType.whole name (initialPermission declaration.kind)) →
(declaration.kind.isStruct = true →
∀ field ∈ declaration.fields, StructType classes field.2.toType) →
ExprTyped classes before (.new name arguments)
(ValueType.whole name (initialPermission declaration.kind)) after
| weaken {before after : Environment} {value : Value} {ty other : ValueType} :
ExprTyped classes before value ty after →
Admissible classes other → Subtype classes ty other →
ExprTyped classes before value other after
inductive ArgsTyped (classes : ClassTable) : Environment → List Value → List FieldType → Environment → Prop where
| nil {environment : Environment} :
environment.WellFormed classes → ArgsTyped classes environment [] [] environment
| cons {before middle after : Environment} {value : Value} {values : List Value}
{field : FieldType} {fields : List FieldType} :
ExprTyped classes before value field.toType middle →
ArgsTyped classes middle values fields after →
ArgsTyped classes before (value :: values) (field :: fields) after