Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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.

Functions/Checks:identity
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.

Functions/Checks:shared
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:

BoundaryFramesHeap
After allocating temporarywork, initial callerbox, child, temporary
After returning from workinitial callerbox, child
After popping the initial framenoneempty

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.

Functions/Checks:gc
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.

Functions/Checks:methods
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.

\[ \begin{aligned} a &::= f \mid C.m, & Q &::= {\to} \mid \mathsf{shared}, \\ T &::= Q\ C, & P &::= x:T, \\ R &::= \mathsf{none} \mid T, & \sigma &::= ({\overline P})\;R. \end{aligned} \]

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.

Functions/Syntax:Name
inductive Name where
  | function (name : String)
  | method (owner : ClassName) (name : String)
  deriving DecidableEq, Repr
Functions/Syntax:Parameter
structure Parameter where
  name : VariableId
  type : FieldType
  deriving DecidableEq, Repr
Functions/Syntax:Signature
structure Signature where
  parameters : List Parameter
  result : Option FieldType
  deriving DecidableEq, Repr
Functions/Syntax:receiver
def receiver (owner : ClassName) (permission : Perm) : Parameter :=
  ⟨"self", ⟨permission, owner⟩⟩
Functions/Syntax:Signature.WellFormed
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:

\[ \begin{aligned} d &::= \mathsf{none}\mid x, \\ t &::= \mathsf{let}\ b=e \mid d\mathrel{:=}\mathsf{call}\ a({\overline e}), \\ r &::= \mathsf{none}\mid e, \\ B &::= ({\overline t};\ \mathsf{return}\ r), \\ D &::= (\sigma,B). \end{aligned} \]

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.

Functions/Syntax:Statement
inductive Statement where
  | local (statement : Unpacking.Statement)
  | call (destination : Option VariableId) (name : Name) (arguments : List Value)
  deriving Repr
Functions/Syntax:Body
structure Body where
  statements : List Statement
  result : Option Value
  deriving Repr
Functions/Syntax:Declaration
structure Declaration where
  signature : Signature
  body : Body
  deriving Repr
Functions/Syntax:Program
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.

Functions/Syntax:Signature.environment
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'\).

\[ \frac{\operatorname{WF}_{\Delta}(\Gamma)} {\Delta\vdash\Gamma;\mathsf{none}:\mathsf{none}\Rightarrow\Gamma} \qquad \frac{\Delta\vdash\Gamma;x:T\Rightarrow_{\mathrm{bind}}\Gamma'} {\Delta\vdash\Gamma;x:T\Rightarrow\Gamma'} \]

A value-returning call cannot silently discard its result. The binding premise also checks admissibility and freshness.

Functions/Typing:DestinationTyped
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.

\[ \frac{ \begin{gathered} (a,(\sigma,B))\in F \quad d\notin\operatorname{dom}(\Gamma) \\ \Delta\vdash\Gamma;{\overline e}:\operatorname{params}(\sigma)\Rightarrow\Gamma_e \quad \Delta\vdash\Gamma_e;d:\operatorname{result}(\sigma)\Rightarrow\Gamma' \end{gathered} }{\Delta;F\vdash\Gamma\mathrel{\xrightarrow{d:=\mathsf{call}\ a({\overline e})}}\Gamma'} \]

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:

\[ \frac{\Delta\vdash\Gamma\mathrel{\xrightarrow{t}_{\mathrm{Shared}}}\Gamma'} {\Delta;F\vdash\Gamma\mathrel{\xrightarrow{t}}\Gamma'} \qquad \frac{\operatorname{WF}_{\Delta}(\Gamma)} {\Delta;F\vdash\Gamma\mathrel{\xrightarrow{[]}}\Gamma} \qquad \frac{\Delta;F\vdash\Gamma\mathrel{\xrightarrow{t}}\Gamma_1\quad \Delta;F\vdash\Gamma_1\mathrel{\xrightarrow{{\overline t}}}\Gamma'} {\Delta;F\vdash\Gamma\mathrel{\xrightarrow{t::{\overline t}}}\Gamma'} \]
Functions/Typing:StatementTyped
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
Functions/Typing:SequenceTyped
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:

\[ \frac{\operatorname{WF}_{\Delta}(\Gamma)} {\Delta\vdash\Gamma;\mathsf{none}:\mathsf{none}\Rightarrow_{\mathrm{return}}\Gamma} \qquad \frac{\Delta\vdash\Gamma;e:T\Rightarrow\Gamma'} {\Delta\vdash\Gamma;e:T\Rightarrow_{\mathrm{return}}\Gamma'} \]

The expression judgment in the second rule is Shared’s.

Functions/Typing:ResultTyped
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:

\[ \frac{ \Delta;F\vdash\operatorname{env}(\sigma)\mathrel{\xrightarrow{{\overline t}}}\Gamma_m \quad \Delta\vdash\Gamma_m;r:\operatorname{result}(\sigma)\Rightarrow_{\mathrm{return}}\Gamma_f }{\Delta;F\vdash({\overline t};\mathsf{return}\ r):\sigma} \]

There is no consumption condition on \(\Gamma_f\) in this layer.

Functions/Typing:BodyTyped
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.

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

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

Functions/Typing:call_arity
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:

AttemptReason
fn bad(x: shared Token) with class TokenClasses cannot be shared.
A Point method with a receiver of nominal type Token in the core signatureA 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.
Functions/Checks:rejection
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:

\[ \phi=(V,B,d),\qquad K=[\phi_0,\ldots,\phi_j],\qquad M=\langle H,n,K\rangle. \]

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.

Functions/Step:Store
abbrev Store := List (VariableId × Slot)
Functions/Step:Frame
structure Frame where
  variables : Store
  body : Body
  destination : Option VariableId
  deriving Repr
Functions/Step:Configuration
structure Configuration where
  objects : List (ObjectId × Object)
  nextId : Nat
  frames : List Frame
  deriving Repr
Functions/Step:Configuration.running
def Configuration.running (state : State) (body : Body)
    (frames : List Frame := []) (destination : Option VariableId := none) : Configuration :=
  ⟨state.objects, state.nextId, ⟨state.variables, body, destination⟩ :: frames⟩
Functions/Step:Configuration.initial
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.

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

Functions/Step:Configuration.rootState
def Configuration.rootState (configuration : Configuration) : State :=
  ⟨configuration.objects, configuration.frames.flatMap Frame.variables, configuration.nextId⟩
Functions/Step:Configuration.roots
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:

\[ \operatorname{gc}(\langle H,n,K\rangle) =\langle [(o,h)\in H\mid\operatorname{live}_M(o)],n,K\rangle. \]

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.

Functions/Step:Configuration.collect
def Configuration.collect (configuration : Configuration) : Configuration := by
  exact { configuration with objects := configuration.rootState.collect.objects }
Shared/Frames:State.collect
def State.collect (state : State) : State := by
  classical
  exact { state with objects := state.objects.filter (fun entry => decide (Live state entry.1)) }

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.

\[ \operatorname{bind}((x_1:T_1,\ldots,x_j:T_j)\,R,[v_1,\ldots,v_j]) =[x_1\mapsto v_1,\ldots,x_j\mapsto v_j]. \]

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.

Functions/Step:parameterStore
def parameterStore (parameters : List Parameter) (references : List Reference) : Store :=
  (parameters.map Parameter.name).zip (references.map some)
Functions/Step:DestinationMatches
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:

\[ V;\mathsf{none};\mathsf{none}\Rightarrow V \qquad \frac{x\notin\operatorname{dom}(V)}{V;x;v\Rightarrow(x\mapsto v)::V}. \]
Functions/Step:ResultEval
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)
Functions/Step:Deliver
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:

\[ \frac{M\rightsquigarrow M_r}{M\longrightarrow\operatorname{gc}(M_r)}. \]

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

\[ \frac{S\vdash t\Downarrow S_e} {\langle H,n,(V,(t::{\overline t};\mathsf{return}\ r),d_0)::K\rangle \rightsquigarrow\langle H_e,n_e,(V_e,B_r,d_0)::K\rangle} \]

Call

\[ \frac{ \begin{gathered} (a,(\sigma,B_c))\in F\quad d\sim\operatorname{result}(\sigma)\quad d\notin\operatorname{dom}(V) \\ S\vdash{\overline e}\Downarrow S_e;{\overline v}\quad |{\overline v}|=|\operatorname{params}(\sigma)| \end{gathered} }{ \begin{gathered} \langle H,n,(V,(d:=\mathsf{call}\ a({\overline e})::{\overline t};\mathsf{return}\ r),d_0)::K\rangle \\ \rightsquigarrow \langle H_e,n_e,(\operatorname{bind}(\sigma,{\overline v}),B_c,d)::(V_e,B_r,d_0)::K\rangle \end{gathered} } \]

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

\[ \frac{S\vdash r\Downarrow S_e;u\quad V_c;d;u\Rightarrow V'} {\langle H,n,(V,([];\mathsf{return}\ r),d)::(V_c,B_c,d_c)::K\rangle \rightsquigarrow\langle H_e,n_e,(V',B_c,d_c)::K\rangle}. \]

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

\[ \langle H,n,[(V,([];\mathsf{return}\ \mathsf{none}),\mathsf{none})]\rangle \rightsquigarrow\langle H,n,[]\rangle. \]

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.

Functions/Step:RawStep
inductive RawStep (classes : Classes) (declarations : Declarations) : Configuration → Configuration → Prop where
  | local {before after statement rest result frames destination} :
      Unpacking.Step classes ⟨before, [statement]⟩ ⟨after, []⟩ →
      RawStep classes declarations
        (.running before ⟨.local statement :: rest, result⟩ frames destination)
        (.running after ⟨rest, result⟩ frames destination)
  | call {before evaluated destination name arguments rest result frames returnTo
      declaration references} :
      (name, declaration) ∈ declarations →
      DestinationMatches destination declaration.signature.result →
      (∀ x ∈ destination, x ∉ before.variables.map Prod.fst) →
      EvalArgs classes before arguments evaluated references →
      references.length = declaration.signature.parameters.length →
      RawStep classes declarations
        (.running before ⟨.call destination name arguments :: rest, result⟩ frames returnTo)
        (.running { evaluated with variables := parameterStore declaration.signature.parameters references }
          declaration.body (⟨evaluated.variables, ⟨rest, result⟩, returnTo⟩ :: frames) destination)
  | «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, []⟩
Functions/Step:Step
inductive Step (classes : Classes) (declarations : Declarations) : Configuration → Configuration → Prop where
  | collect {before raw} : RawStep classes declarations before raw →
      Step classes declarations before raw.collect

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.

Functions/Checks:nested
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.

Functions/Checks:completion
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.

Functions/Step:Steps
inductive Steps (classes : Classes) (declarations : Declarations) : Configuration → Configuration → Prop where
  | refl (configuration : Configuration) : Steps classes declarations configuration configuration
  | step {before middle after} :
      Step classes declarations before middle → Steps classes declarations middle after →
      Steps classes declarations before after

A configuration is stuck when it is not finished and has no successor.

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

Functions/Checks:recursion
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.

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

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

Correspondence/SharedFunctionsFrames:framed_step_correspondence
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.

Correspondence/SharedFunctionsFrames:framed_steps_backward
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.

Correspondence/SharedFunctions:typing_correspondence
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.

Correspondence/SharedFunctionsFrames:framed_finished_correspondence
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.

Correspondence/SharedFunctionsFrames:framed_stuck_correspondence
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.

Functions/SafetyChecks:nested_safety
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.

Functions/Realization:Slots
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:

ComponentRequirement
Active frameIts locals form a typed store; its remaining statements and return expression check from that environment to its promised optional result type.
Suspended callerIts 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 callersThe same condition repeats down the stack, using each caller’s own result destination and promised result type.
Initial frameIts result and destination are absent; there is no caller below it.
Common heapShared 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.

Functions/StackTyping:BodyFrom
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
Functions/StackTyping:ContinuationTyped
inductive ContinuationTyped (classes : ClassTable) (declarations : Declarations) : Option VariableId → Option FieldType → List Frame → PendingValues → Prop where
  | done : ContinuationTyped classes declarations none none [] []
  | caller {destination result caller rest environment resumed roots laterRoots callerResult} :
      Slots environment 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)
Functions/StackTyping:StackShape
inductive StackShape (classes : ClassTable) (declarations : Declarations) : List Frame → PendingValues → Prop where
  | done : StackShape classes declarations [] []
  | active {frame rest environment roots laterRoots result} :
      Slots environment 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)
Functions/StackTyping:ConfigurationTyped
def ConfigurationTyped (classes : ClassTable) (declarations : Declarations) (configuration : Configuration) : Prop :=
  classes.WellFormed ∧ DeclarationsTyped classes declarations ∧
  ∃ roots, StackShape classes declarations configuration.frames roots ∧
    Realizes classes [] (heapState configuration.rootState) roots
Functions/Realization:heapState
def heapState (state : State) : State := ⟨state.objects,[],state.nextId⟩

A well-typed machine is finished or has a successor:

\[ \Delta;F\vdash M\ \mathsf{ok} \quad\Longrightarrow\quad \mathsf{Finished}(M)\ \lor\ \exists M'.\ M\longrightarrow M'. \]

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.

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

\[ \frac{\Delta;F\vdash M\ \mathsf{ok}\qquad M\longrightarrow M'} {\Delta;F\vdash M'\ \mathsf{ok}}. \]

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.

Functions/Safety:ConfigurationTyped.preservation
theorem ConfigurationTyped.preservation {before after : Configuration}
    (typed : ConfigurationTyped classes declarations before)
    (step : Step classes.erase declarations before after) :
    ConfigurationTyped classes declarations after := 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.

Functions/Safety:ConfigurationTyped.ownership
theorem ConfigurationTyped.ownership {configuration : Configuration}
    (typed : ConfigurationTyped classes declarations configuration) :
    (Owners configuration.rootState).Pairwise Compatible ∧
    (∀ id, id ∈ References configuration.rootState ↔ Allocated configuration.rootState id) := by
  obtain ⟨_,_,roots,shape,heap⟩ := typed
  have refs := shape.references
  constructor
  · simpa only [Owners,heapState,List.filterMap_nil,List.nil_append,refs,
      Configuration.rootState] using heap.ownership.ownersCompatible
  · intro id
    have complete := heap.ownership.referencesComplete id
    simpa only [heapState,References,List.filterMap_nil,List.nil_append,refs,
      Configuration.rootState,Allocated,List.map_append,List.map_filterMap,Function.comp_def] using complete

A 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.

Functions/Safety:ConfigurationTyped.finished_heap_empty
theorem ConfigurationTyped.finished_heap_empty {configuration : Configuration}
    (typed : ConfigurationTyped classes declarations configuration)
    (finished : configuration.finished) : configuration.objects = [] := by
  rcases configuration with ⟨objects,nextId,frames⟩
  change frames = [] at finished
  subst frames
  obtain ⟨_,_,roots,shape,heap⟩ := typed
  cases shape
  have same := State.collect_eq_self heap.ownership.no_pending
  rw [heapState,State.collect_no_variables] at same
  exact (congrArg State.objects same).symm

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.

Functions/Safety:program_safety
theorem program_safety (typed : ProgramTyped program)
    (trace : Steps program.classes.erase program.declarations (.initial program) configuration) :
    ConfigurationTyped program.classes program.declarations configuration ∧
    (configuration.finished ∨ ∃ after, Step program.classes.erase program.declarations configuration after) ∧
    ¬ Stuck program.classes.erase program.declarations configuration := 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.

Functions/SafetyChecks:recursion_safety
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:

UniqueShared
Ownedgiven, spelled → in signaturesshared[], abbreviated shared
Leasedmut[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:

MachineryInherited behavior
Nominal kindsClasses cannot be shared; struct fields have struct types.
StorageReferences carry modes; slots hold a reference or are empty; allocation is monotonic.
ViewsPositive entries expose whole subtrees, negative entries record empty slots, and omissions are unknown.
GivingUnique access moves; shared access copies, promoting a unique final stored reference when necessary.
ExpressionsConstructor arguments are evaluated left to right and require whole declared types. Shared structs construct shared references immediately.
UnpackingUnpacking 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.

Shared/Syntax:Value
inductive Value where
  | give (source : Place)
  | giveShare (source : Place)
  | new (className : ClassName) (arguments : List Value)
  deriving Repr
Shared/State:State
structure State where
  objects : List (ObjectId × Object)
  variables : List (VariableId × Slot)
  nextId : Nat
  deriving DecidableEq, Repr
Shared/Step:Give
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
Shared/Step:Eval
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⟩⟩)
Shared/Step:EvalArgs
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)
Shared/Unpacking:Pattern
inductive Pattern where
  | variable (name : VariableId)
  | unpack (className : ClassName) (fields : List (FieldName × VariableId))
  deriving DecidableEq, Repr
Shared/Unpacking:Bind
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⟩
Shared/Typing:ExprTyped
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
Shared/Typing:ArgsTyped
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