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

Given: typing and soundness

The type system checks that each give finds a value and that each binding can receive its result. A move changes the source’s type description as well as its contents.

This chapter uses the unpacking extension refgiven.unpacking; expression evaluation is unchanged.

A typed class table \(\Sigma\) gives each field a declared class:

\[ \begin{aligned} d &::= \mathsf{class}\ C\ \{f_1:C_1,\ldots,f_n:C_n\},\\ \Sigma &\in \mathsf{ClassName}\rightharpoonup \mathsf{List}(\mathsf{FieldName}\times\mathsf{ClassName}). \end{aligned} \]

Fields retain their constructor-argument order.

Field declarations constrain the class of an object stored there. They do not require its slot to remain initialized after a move. All value types in this chapter are nominal types; ownership is unique.

Unique/Views:TypedClass
structure TypedClass where
  fields : List (FieldName × ClassName)
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Unique/Views:ClassTable
abbrev ClassTable := List (ClassName × TypedClass)

A typed class table is well formed when each class name has one declaration, field names within each declaration are distinct, and every field’s declared class occurs in \(\Sigma\).

Unique/Views:ClassTable.WellFormed
def ClassTable.WellFormed (classes : ClassTable) : Prop :=
  (classes.map Prod.fst).Nodup ∧
    ∀ entry ∈ classes, (entry.2.fields.map Prod.fst).Nodup ∧
      ∀ field ∈ entry.2.fields, field.2 ∈ classes.map Prod.fst

Class-table erasure removes field types to recover the operational class table: if \(\href{#claim-given.typing.declarations}{\Sigma(C)}=[f_1:C_1,\ldots,f_n:C_n]\), then \(\lfloor\Sigma\rfloor(C)=[f_1,\ldots,f_n]\).

Unique/Views:ClassTable.erase
def ClassTable.erase (classes : ClassTable) : Classes :=
  classes.map fun (name, declaration) => (name, ⟨declaration.fields.map Prod.fst⟩)

Types describe accessible places

A relative place \(\rho\) is a finite sequence of field names. The empty sequence \(\epsilon\) denotes the value itself; concatenation is written \(\rho\cdot\sigma\); \(\rho f\) appends the single field \(f\).

\[\rho ::= \epsilon \mid f\cdot\rho.\]
Unique/Views:Path
abbrev Path := List FieldName

A relative path is valid from \(C\) when its fields can be followed through the declarations in \(\Sigma\). Write \(\operatorname{class}_{\Sigma}(C,\rho)\) for its final declared class; in particular, \(\operatorname{class}_{\Sigma}(C,\epsilon)=C\).

Unique/Views:classAt
def classAt (classes : ClassTable) (base : ClassName) : Path → Option ClassName
  | [] => some base
  | field :: rest => do
      let declaration ← classes.lookup base
      let target ← declaration.fields.lookup field
      classAt classes target rest

A view entry \(a\), in the category \(\mathsf{ViewEntry}\), is a positive relative place or a negative nonempty relative place. A view \(A\) is a finite set of entries. A type \(T\) always pairs a nominal class with a view:

\[ \begin{aligned} a &::= \rho \mid -\rho \qquad(\text{negative entries require }\rho\ne\epsilon),\\ A &\subseteq_{\mathrm{fin}}\mathsf{ViewEntry},\\ T &::= C.A. \end{aligned} \]

The surface notation uses braces: Point.{x, -y}. A positive entry exposes an initialized value of the path’s declared class, including its fully initialized fields. A negative entry exposes an existing empty slot. Every proper prefix of either kind of entry must hold an object. A branch not covered by an entry is unknown and cannot be accessed through this type.

We write bare \(C\) as shorthand for \(C.\{\epsilon\}\): the whole value, including all fields reachable from it, is initialized. It is not a separate form of type. By contrast, \(C.\{\}\) exposes the object itself but none of its fields. The empty path \(\epsilon\) and the empty set \(\{\}\) have different meanings.

Unique/Views:Entry
inductive Entry where
  | positive (path : Path)
  | negative (path : Path)
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Unique/Views:ViewType
structure ViewType where
  className : ClassName
  entries : List Entry
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Unique/Views:ViewType.whole
def ViewType.whole (name : ClassName) : ViewType :=
  ⟨name, [.positive []]⟩

The base class is \(\operatorname{base}(C.A)=C\).

Unique/Views:ViewType
structure ViewType where
  className : ClassName
  entries : List Entry
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr

A type is well formed when its base class is declared and its view satisfies the following condition.

Entries do not overlap. Their paths must be valid from \(C\), distinct, and pairwise prefix-incomparable: no entry’s path is a prefix of another’s. Thus C.{f, -f.g} is not a valid view. Exposing all of f would claim initialization that -f.g denies. To describe such a hole, first expand f into its fields.

Unique/Views:Entry.valid
def Entry.valid (classes : ClassTable) (base : ClassName) (entry : Entry) : Bool :=
  (classAt classes base entry.path).isSome &&
    match entry with
    | .positive _ => true
    | .negative path => !path.isEmpty
Unique/Views:entriesDisjoint
def entriesDisjoint : List Entry → Bool
  | [] => true
  | entry :: rest =>
    rest.all (fun other =>
      !entry.path.isPrefixOf other.path && !other.path.isPrefixOf entry.path) &&
    entriesDisjoint rest
Unique/Views:ViewType.WellFormed
def ViewType.WellFormed (ty : ViewType) (classes : ClassTable) : Prop :=
  (classes.lookup ty.className).isSome = true ∧
    ty.entries.all (Entry.valid classes ty.className) = true ∧
    entriesDisjoint ty.entries = true

A full view accounts for every field recursively, including fields known to be empty. A partial view leaves some statuses unknown. The formal fullness predicate comes after this example; only this distinction is needed to read the table.

Consider these declarations:

class Token {}
class Pair { left: Token, right: Token }
class Box { item: Pair }
TypeInformation available
PairBoth fields contain tokens.
Pair.{left}left contains a token; right is unknown.
Pair.{-left, right}left is empty and right contains a token: a full view.
Box.{-item.left}item contains a pair whose left is empty; its right is unknown.
Box.{-item.left, item.right}item contains a pair whose left is empty and right contains a token: a full view.

In the last two types, item itself remains initialized. Its negative child does not make the containing field empty.

Unique/ViewChecks:view_information
example :
    (Pos viewClasses ⟨"Pair", [.positive ["left"]]⟩ ["left"] ∧
    ¬ Pos viewClasses ⟨"Pair", [.positive ["left"]]⟩ ["right"] ∧
    ¬ Neg ⟨"Pair", [.positive ["left"]]⟩ ["right"] ∧
    Pos viewClasses ⟨"Box", [.negative ["item", "left"]]⟩ ["item"] ∧
    Neg ⟨"Box", [.negative ["item", "left"]]⟩ ["item", "left"] ∧
    ¬ Pos viewClasses ⟨"Box", [.negative ["item", "left"]]⟩ ["item", "right"]) ∧
    (Full viewClasses (.whole "Pair") ∧
    ¬ Full viewClasses ⟨"Pair", [.positive ["left"]]⟩ ∧
    Full viewClasses ⟨"Pair", [.negative ["left"], .positive ["right"]]⟩ ∧
    ¬ Full viewClasses ⟨"Box", [.negative ["item", "left"]]⟩ ∧
    Full viewClasses ⟨"Box", [.negative ["item", "left"], .positive ["item", "right"]]⟩) := by
  exact ⟨by decide, view_fullness⟩

Each type determines a set of known-initialized paths \(\operatorname{pos}_{\Sigma}(T)\) and known-empty paths \(\operatorname{neg}_{\Sigma}(T)\). These sets give precise meanings to the view notation.

For \(T=C.A\):

  • \(\epsilon\) is positive: the described value is an object.
  • Every proper prefix of an entry’s path is positive.
  • A positive entry’s path and all its valid descendants are positive.
  • Exactly the paths of negative entries are negative.

No other path is known. In particular, a negative path does not say that its descendants are empty: there is no object in that slot whose fields could be examined. The shorthand \(C=C.\{\epsilon\}\) makes every valid path positive.

Unique/Views:positive
def positive (classes : ClassTable) (ty : ViewType) (path : Path) : Bool :=
  (classAt classes ty.className path).isSome &&
    (path.isEmpty || ty.entries.any (fun entry =>
      (path.length < entry.path.length && path.isPrefixOf entry.path) ||
      match entry with
      | .positive initialPath => initialPath.isPrefixOf path
      | .negative _ => false))
Unique/Views:negative
def negative (ty : ViewType) (path : Path) : Bool :=
  ty.entries.contains (.negative path)
Unique/Views:Pos
def Pos (classes : ClassTable) (ty : ViewType) (path : Path) : Prop :=
  positive classes ty path = true
Unique/Views:Neg
def Neg (ty : ViewType) (path : Path) : Prop :=
  negative ty path = true

A view is full when every direct field of every known-initialized object has a known status:

\[ \mathsf{Full}_{\Sigma}(T)\iff \begin{gathered} \forall\rho\in\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T).\\ \forall(f:D)\in\Sigma(\href{#claim-given.typing.class_at}{\operatorname{class}}_{\Sigma}(\href{#claim-given.typing.base}{\operatorname{base}}(T),\rho)).\\ \rho f\in\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T)\cup\href{#claim-given.typing.observations}{\operatorname{neg}}_{\Sigma}(T). \end{gathered} \]

A full view may contain empty slots; being full does not mean being fully initialized.

Unique/Views:Full
def Full (classes : ClassTable) (ty : ViewType) : Prop :=
  ∀ path, Pos classes ty path →
    ∀ name declaration, classAt classes ty.className path = some name →
      classes.lookup name = some declaration →
      ∀ field ∈ declaration.fields,
        Pos classes ty (path ++ [field.1]) ∨ Neg ty (path ++ [field.1])

Normalizing a view

Several spellings can describe the same accessible fields:

class Foo { bar: Bar }
class Bar { baz: Baz }
class Baz {}

In Foo.{bar.baz}, bar must contain an object, and its only field, baz, is fully initialized. We can therefore write bar instead. The same reasoning then applies to the whole Foo:

\[ \mathsf{Foo}.\{\mathsf{bar.baz}\} \;\leadsto\;\mathsf{Foo}.\{\mathsf{bar}\} \;\leadsto\;\mathsf{Foo}.\{\epsilon\} \;=\;\mathsf{Foo}. \]

All these spellings are well formed. The normalization procedure defined next chooses the last one; this example illustrates only the collapses it performs. If Bar also declared another field, an unknown or empty sibling would prevent the first collapse. A deeper path remains when it describes only part of an intermediate object.

Unique/ViewChecks:normalize_nested_whole
example :
    normalize viewClasses ⟨"Foo", [.positive ["bar", "baz"]]⟩ = .whole "Foo" ∧
    normalize viewClasses ⟨"Foo", [.positive ["bar"]]⟩ = .whole "Foo" := by
  decide

Normalization \(\mathsf{N}_{\Sigma}(T)\) replaces a completely exposed subtree with its shortest positive entry. Work from the deepest entries toward the root. If the class at \(\rho\) declares exactly the nonempty list of fields \(f_1,\ldots,f_n\), replace all their positive entries together:

\[ A\cup\{\rho f_1,\ldots,\rho f_n\} \;\leadsto\; A\cup\{\rho\} \qquad(n>0). \]

Here none of the replaced entries occurs in \(A\). Repeat until no such replacement is possible. A negative or unknown child prevents a collapse. The procedure shortens the finite paths in the view; it does not unfold recursive class declarations.

Keep a positive entry for an empty-class object: it records that the object exists. Do not create an entry for an unknown field merely because its declared class is empty. The root is already known to exist, so for an empty class \(C\), normalize \(C.\{\}\) to \(C.\{\epsilon\}\).

Print \(C.\{\epsilon\}\) as \(C\). Expanded spellings remain valid input. The typing rules use normalized types throughout, including when comparing constructor arguments with their declared types.

Unique/Views:Entry.dropPrefix
def Entry.dropPrefix (initialPath : Path) (entry : Entry) : Option Entry :=
  if initialPath.isPrefixOf entry.path then
    some (match entry with
      | .positive path => .positive (path.drop initialPath.length)
      | .negative path => .negative (path.drop initialPath.length))
  else none
Unique/Views:Entry.prepend
def Entry.prepend (initialPath : Path) : Entry → Entry
  | .positive path => .positive (initialPath ++ path)
  | .negative path => .negative (initialPath ++ path)
Unique/Views:normalizeEntries
def normalizeEntries (classes : ClassTable) : Nat → ClassName → List Entry → List Entry
  | fuel, name, entries =>
    if entries.contains (.positive []) then [.positive []]
    else match classes.lookup name with
    | none => entries
    | some declaration =>
      if declaration.fields.isEmpty && entries.isEmpty then [.positive []]
      else match fuel with
      | 0 => entries
      | fuel + 1 =>
        let children := declaration.fields.flatMap fun (field, target) =>
          let selected := entries.filterMap (Entry.dropPrefix [field])
          if selected.isEmpty then []
          else if selected.contains (.negative []) then [.negative [field]]
          else (normalizeEntries classes fuel target selected).map (Entry.prepend [field])
        if !declaration.fields.isEmpty && declaration.fields.all
            (fun field => children.contains (.positive [field.1])) then
          [.positive []]
        else children
Unique/Views:normalize
def normalize (classes : ClassTable) (ty : ViewType) : ViewType :=
  let depth := ty.entries.foldl (fun depth entry => max depth entry.path.length) 0
  { ty with entries := normalizeEntries classes (depth + 1) ty.className ty.entries }
Unique/Views:Normalized
def Normalized (classes : ClassTable) (ty : ViewType) : Prop :=
  normalize classes ty = ty

For a well-formed class table \(\Sigma\) and well-formed type \(T\), normalization preserves the base class, well-formedness, and every initialization fact:

\[ \begin{aligned} \href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(\href{#claim-given.typing.normalization}{\mathsf N}_{\Sigma}(T)) &= \href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T),\\ \href{#claim-given.typing.observations}{\operatorname{neg}}_{\Sigma}(\href{#claim-given.typing.normalization}{\mathsf N}_{\Sigma}(T)) &= \href{#claim-given.typing.observations}{\operatorname{neg}}_{\Sigma}(T),\\ \href{#claim-given.typing.normalization}{\mathsf N}_{\Sigma}(\href{#claim-given.typing.normalization}{\mathsf N}_{\Sigma}(T)) &= \href{#claim-given.typing.normalization}{\mathsf N}_{\Sigma}(T). \end{aligned} \]

Reordering a view’s entries gives the same normalized type. Once normalized, a second pass makes no further change.

Unique/Normalization:normalization_correct
theorem normalization_correct {classes : ClassTable} (classesWf : classes.WellFormed)
    {ty : ViewType} (wf : ty.WellFormed classes) :
    (normalize classes ty).WellFormed classes ∧
    (normalize classes ty).className = ty.className ∧
    (∀ path, Pos classes (normalize classes ty) path ↔ Pos classes ty path) ∧
    (∀ path, Neg (normalize classes ty) path ↔ Neg ty path) ∧
    normalize classes (normalize classes ty) = normalize classes ty ∧
    (∀ entries, ty.entries.Perm entries →
      normalize classes ⟨ty.className, entries⟩ = normalize classes ty) := by
  refine ⟨normalize_wellFormed classesWf wf, rfl,
    normalize_pos_iff classesWf wf, normalize_neg_iff classesWf wf,
    normalize_idempotent classesWf wf, ?_⟩
  intro entries permutation
  exact (normalize_permutation classesWf wf.1 permutation).symm

Reading and updating a view

Focusing a type at an initialized relative place returns the current type of the value stored there, including any holes. Write \(T\downarrow\rho\); it is defined only when \(\rho\in\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T)\).

Start from \(\href{#claim-given.typing.normalization}{\mathsf{N}}_{\Sigma}(T)\). Focusing at \(\epsilon\) returns that type. For a nonempty path, let \(D=\href{#claim-given.typing.class_at}{\operatorname{class}}_{\Sigma}(\href{#claim-given.typing.base}{\operatorname{base}}(T),\rho)\).

  • If a positive entry’s path is a prefix of \(\rho\), including an entry at \(\epsilon\), the result is \(D\), the whole-type shorthand.
  • Otherwise, retain the entries below \(\rho\), remove their common prefix \(\rho\), and attach the resulting view to \(D\). Normalize the result.

For example, under the example declarations:

\[ \mathsf{Box}.\{-\mathsf{item.left},\mathsf{item.right}\} \downarrow\mathsf{item} = \mathsf{Pair}.\{-\mathsf{left},\mathsf{right}\}. \]

This operation does not restore fields that have been moved or hidden.

Unique/Views:focus
def focus (classes : ClassTable) (ty : ViewType) (path : Path) : Option ViewType := do
  if !decide (ty.WellFormed classes) then none else do
    let source := normalize classes ty
    if !positive classes source path then none else do
      let target ← classAt classes source.className path
      if path.isEmpty then some source
      else if source.entries.any (fun entry => match entry with
          | .positive initialPath => initialPath.isPrefixOf path
          | .negative _ => false) then
        some (.whole target)
      else some (normalize classes ⟨target, source.entries.filterMap (Entry.dropPrefix path)⟩)

Emptying an initialized nonempty path updates its enclosing type. Write \(T[-\rho]\), where \(\rho\in\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T)\). The result records that this slot is now empty and preserves the information about every other branch.

Compute the update as follows:

  1. Normalize the input type.
  2. Expand any positive entry that is a strict prefix of \(\rho\) into its declared fields, including an entry at \(\epsilon\). Continue only along the finite path to \(\rho\).
  3. Remove all entries at or below \(\rho\), then insert \(-\rho\). Normalize the result.

An expansion cannot pass through an empty class, because no longer valid path exists there. This procedure also handles a target that is already the common prefix of several view entries.

For the example’s Box, moving item.left yields:

\[ \mathsf{Box}[-\mathsf{item.left}] = \mathsf{Box}.\{-\mathsf{item.left},\mathsf{item.right}\}. \]

The preserved sibling is essential. Replacing the result with Box.{-item.left} would also forget access to item.right. An empty or unknown target has no emptying operation.

Unique/Views:remainingAfterMove
def remainingAfterMove (classes : ClassTable) (name : ClassName) : Path → List Entry
  | [] => []
  | field :: rest =>
    match classes.lookup name with
    | none => []
    | some declaration => declaration.fields.flatMap fun (other, target) =>
        if other == field then
          (remainingAfterMove classes target rest).map (Entry.prepend [other])
        else [.positive [other]]
Unique/Views:emptyPath
def emptyPath (classes : ClassTable) (ty : ViewType) (path : Path) : Option ViewType :=
  if !decide (ty.WellFormed classes) || path.isEmpty then none
  else
    let source := normalize classes ty
    if !positive classes source path then none
    else
      let retained := source.entries.flatMap fun entry =>
        if path.isPrefixOf entry.path then []
        else match entry with
        | .negative _ => [entry]
        | .positive initialPath =>
          if initialPath.isPrefixOf path then
            match classAt classes source.className initialPath with
            | none => []
            | some target =>
              (remainingAfterMove classes target (path.drop initialPath.length)).map
                (Entry.prepend initialPath)
          else [entry]
      some (normalize classes ⟨source.className, retained ++ [.negative path]⟩)

A value can be used through a view that provides less information. To compare types, first normalize them. For the normalized types \(T\) and \(U\), write \(T\preceq_{\Sigma}U\) when they have the same base class and:

\[ \href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(U)\subseteq\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T), \qquad \href{#claim-given.typing.observations}{\operatorname{neg}}_{\Sigma}(U)\subseteq\href{#claim-given.typing.observations}{\operatorname{neg}}_{\Sigma}(T). \]

This view weakening can forget initialization facts and access. It cannot invent them. For the example declarations, Pair can be weakened to Pair.{left}, but neither Pair.{left} nor Pair.{} can be strengthened to Pair. Unknown does not imply empty. Compare the known paths, not just the written entries: the single root entry in Pair includes both of its fields.

Weakening does not change storage, copy a reference, or abandon an object’s ownership. Hidden fields remain part of the owned object graph.

Unique/Views:Subtype
def Subtype (classes : ClassTable) (source target : ViewType) : Prop :=
  source.className = target.className ∧
    (∀ path, Pos classes (normalize classes target) path →
      Pos classes (normalize classes source) path) ∧
    (∀ path, Neg (normalize classes target) path → Neg (normalize classes source) path)

Typing expressions

A slot description \(B\) says that a slot is empty or contains a value of a particular type. A typing environment \(\Gamma\) describes every allocated variable slot:

\[ B ::= 0 \mid T, \qquad \Gamma\in\mathsf{VariableId}\rightharpoonup B. \]

Here \(B\) also denotes the set of slot descriptions generated by its grammar. The marker \(0\) describes an empty slot; it is not a value type. All types in an environment must be well formed and normalized under \(\Sigma\). An empty variable remains in \(\operatorname{dom}(\Gamma)\); its name cannot be reused by a fresh binding. An absent variable has no description.

Unique/Typing:SlotDescription
abbrev SlotDescription := Option ViewType
Unique/Typing:Environment
abbrev Environment := List (VariableId × SlotDescription)
Unique/Typing:Admissible
def Admissible (classes : ClassTable) (ty : ViewType) : Prop :=
  ty.WellFormed classes ∧ Normalized classes ty
Unique/Typing:Environment.WellFormed
def Environment.WellFormed (environment : Environment) (classes : ClassTable) : Prop :=
  (environment.map Prod.fst).Nodup ∧
    environment.all (fun entry => match entry.2 with
      | none => true
      | some ty => decide (Admissible classes ty)) = true
Unique/Typing:Environment.lookup
def Environment.lookup (environment : Environment) (name : VariableId) :
    Option SlotDescription :=
  (environment.find? fun entry => entry.1 == name).map Prod.snd
Unique/Typing:Environment.replace
def Environment.replace (environment : Environment) (name : VariableId)
    (description : SlotDescription) : Environment :=
  environment.map fun entry => if entry.1 = name then (name, description) else entry

To check a give, find the variable where the path starts, then follow its fields inside that variable’s type. For b.item.left, the variable is b and the relative place is item.left. Giving b itself has no field suffix.

Thus every place expression has a unique decomposition \(p=x.\rho\), with \(x.\epsilon=x\). Taking a place returns its current type and updates that variable’s environment description. Define \(\mathsf{take}_{\Sigma}(\Gamma,p)=(T,\Gamma')\) when \(\Gamma(x)=U\), \(\rho\in\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(U)\), and:

\[ T=U\href{#claim-given.typing.focus}{\downarrow}\rho, \qquad \Gamma'= \begin{cases} \Gamma[x\mapsto 0] & \rho=\epsilon,\\ \Gamma[x\mapsto \href{#claim-given.typing.emptying}{U[-\rho]}] & \rho\ne\epsilon. \end{cases} \]

All other variables keep their descriptions. Taking an absent variable, an empty slot, or an unknown field is undefined.

Unique/Typing:splitPlace
def splitPlace : Place → VariableId × Path
  | .variable name => (name, [])
  | .field base name =>
      let (root, path) := splitPlace base
      (root, path ++ [name])
Unique/Typing:take
def take (classes : ClassTable) (environment : Environment) (place : Place) :
    Option (ViewType × Environment) := do
  let (root, path) := splitPlace place
  let source ← environment.lookup root
  let source ← source
  let result ← focus classes source path
  if path = [] then
    return (result, environment.replace root none)
  else
    let remaining ← emptyPath classes source path
    return (result, environment.replace root (some remaining))

Suppose \(\Gamma(b)=\mathsf{Box}\), using the Box, Pair, and Token declarations above. The following are two separate takes from that starting environment:

GiveRoot and relative placeResult typeUpdated description of b
b→\(b,\epsilon\)Box0
b.item.left→\(b,\mathsf{item.left}\)TokenBox.{-item.left, item.right}

The first takes the whole box. The second takes one token, leaving the box, the pair, and its other token accessible through b. Both leave every other variable’s description unchanged.

Unique/TypingChecks:take_root_and_field
example :
    splitPlace (.variable "b") = ("b", []) ∧
    splitPlace leftPlace = ("b", ["item", "left"]) ∧
    take classes afterConstruct (.variable "b") = some (box, [("b", none)]) ∧
    take classes afterConstruct leftPlace = some (token, [("b", some partialBox)]) := by
  decide

Expression typing records both the value produced and the environment after its moves:

\[ \Sigma;\Gamma\vdash e:T\;\triangleright\;\Gamma'. \]

The Give rule uses the current view of the source:

\[ \frac{\href{#claim-given.typing.take}{\mathsf{take}}_{\Sigma}(\Gamma,p)=(T,\Gamma')} {\Sigma;\Gamma\vdash p\mathord{\to}:T\;\triangleright\;\Gamma'} \quad\text{Give} \]

Construct checks arguments from left to right, passing each updated environment to the next argument:

\[ \frac{ \begin{gathered} \href{#claim-given.typing.declarations}{\Sigma(C)}=[f_1:C_1,\ldots,f_n:C_n]\\ \Sigma;\Gamma_{i-1}\vdash e_i:C_i\;\triangleright\;\Gamma_i \quad(1\leq i\leq n) \end{gathered} }{ \Sigma;\Gamma_0\vdash\mathsf{new}\ C(e_1,\ldots,e_n):C \;\triangleright\;\Gamma_n } \quad\text{Construct} \]

For no arguments, the environment is unchanged. The argument count must match the declaration. Each argument supplies an owning value, so the new object has fully initialized fields.

A result may expose less information:

\[ \frac{ \Sigma;\Gamma\vdash e:T\;\triangleright\;\Gamma' \qquad T\href{#claim-given.typing.forgetting}{\preceq}_{\Sigma}U }{ \Sigma;\Gamma\vdash e:U\;\triangleright\;\Gamma' } \quad\text{Weaken} \]

First-pass restriction. Constructor arguments must have their whole declared class types. A partially moved object can be transferred to another variable or unpacked, but cannot be passed to a constructor requiring its whole class. This rejects some dynamically safe programs. The Future extensions chapter records the proposed generic-view constructor signatures.

Unique/Typing:ExprTyped
inductive ExprTyped (classes : ClassTable) : Environment → Value → ViewType → Environment → Prop where
  | give {before after : Environment} {place : Place} {ty : ViewType} :
      before.WellFormed classes →
      take classes before place = some (ty, after) →
      Admissible classes ty → after.WellFormed classes →
      ExprTyped classes before (.give place) ty 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 (ViewType.whole name) →
      ExprTyped classes before (.new name arguments) (ViewType.whole name) after
  | weaken {before after : Environment} {value : Value} {ty other : ViewType} :
      ExprTyped classes before value ty after →
      Admissible classes other → Subtype classes ty other →
      ExprTyped classes before value other after
Unique/Typing:ArgsTyped
inductive ArgsTyped (classes : ClassTable) : Environment → List Value → List ClassName → Environment → Prop where
  | nil {environment : Environment} :
      environment.WellFormed classes → ArgsTyped classes environment [] [] environment
  | cons {before middle after : Environment} {value : Value} {values : List Value}
      {name : ClassName} {names : List ClassName} :
      ExprTyped classes before value (ViewType.whole name) middle →
      ArgsTyped classes middle values names after →
      ArgsTyped classes before (value :: values) (name :: names) after

Typing bindings and statements

The direct-field description records whether a field has the empty-slot description or gives its current type:

\[ \mathsf{field}_{\Sigma}(T,f)= \begin{cases} 0 & f\in\href{#claim-given.typing.observations}{\operatorname{neg}}_{\Sigma}(T),\\ T\href{#claim-given.typing.focus}{\downarrow} f & f\in\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T). \end{cases} \]

It is undefined if that field is unknown.

Unique/Typing:fieldDescription
def fieldDescription (classes : ClassTable) (ty : ViewType) (name : FieldName) :
    Option SlotDescription :=
  if negative ty [name] then some none
  else (focus classes ty [name]).map some

Binding typing, written \(\Sigma;\Gamma\vdash b:T\Rightarrow\Gamma'\), describes where an expression’s result goes. A variable pattern transfers its current type unchanged:

\[ \frac{x\notin\operatorname{dom}(\Gamma)} {\Sigma;\Gamma\vdash x:T\Rightarrow\Gamma[x\mapsto T]} \quad\text{Bind} \]

An unpacking pattern must name every declared field, and each field’s description must be defined:

\[ \frac{ \begin{gathered} \href{#claim-given.typing.base}{\operatorname{base}}(T)=C \qquad\href{#claim-given.typing.declarations}{\Sigma(C)}=[f_1:C_1,\ldots,f_n:C_n]\\ \href{#claim-given.typing.field}{\mathsf{field}}_{\Sigma}(T,f_i)=B_i\quad(1\leq i\leq n)\\ x_1,\ldots,x_n\text{ are distinct} \qquad x_i\notin\operatorname{dom}(\Gamma)\quad(1\leq i\leq n) \end{gathered} }{ \Sigma;\Gamma\vdash C\mathord{\to}\{f_1:x_1,\ldots,f_n:x_n\}:T \Rightarrow\Gamma[x_1\mapsto B_1,\ldots,x_n\mapsto B_n] } \quad\text{Unpack} \]

The rule displays fields in declaration order; named patterns can be reordered to that order. A known-empty field produces an empty binding. An initialized field transfers its current type, which may itself be a partial view.

Knowing every direct field’s status is sufficient: unpacking does not inspect the interiors of the objects transferred. An unknown direct field prevents this rule from applying. It cannot be silently dropped or assigned an invented initialization status.

Unique/Typing:FieldBindings
inductive FieldBindings (classes : ClassTable) (ty : ViewType) : List (FieldName × VariableId) → Environment → Prop where
  | nil : FieldBindings classes ty [] []
  | cons {field : FieldName} {destination : VariableId} {description : SlotDescription}
      {fields : List (FieldName × VariableId)} {bindings : Environment} :
      fieldDescription classes ty field = some description →
      FieldBindings classes ty fields bindings →
      FieldBindings classes ty ((field, destination) :: fields)
        ((destination, description) :: bindings)
Unique/Typing:BindingTyped
inductive BindingTyped (classes : ClassTable) : Environment → Unpacking.Pattern → ViewType → Environment → Prop where
  | variable {environment : Environment} {name : VariableId} {ty : ViewType} :
      environment.WellFormed classes → Admissible classes ty →
      name ∉ environment.map Prod.fst →
      BindingTyped classes environment (.variable name) ty ((name, some ty) :: environment)
  | unpack {before : Environment} {ty : ViewType} {name : ClassName}
      {declaration : TypedClass} {fields : List (FieldName × VariableId)}
      {bindings : Environment} :
      before.WellFormed classes → Admissible classes ty →
      ty.className = name → (name, declaration) ∈ classes →
      (fields.map Prod.fst).Perm (declaration.fields.map Prod.fst) →
      (fields.map Prod.snd).Nodup →
      (∀ destination ∈ fields.map Prod.snd, destination ∉ before.map Prod.fst) →
      FieldBindings classes ty fields bindings →
      (bindings ++ before).WellFormed classes →
      BindingTyped classes before (.unpack name fields) ty (bindings ++ before)

Statement typing, written \(\Sigma;\Gamma\vdash t\Rightarrow\Gamma'\), first types the expression and then its binding pattern:

\[ \frac{ \Sigma;\Gamma\vdash e:T\;\href{#claim-given.typing.expressions}{\triangleright}\;\Gamma_1 \qquad \href{#claim-given.typing.bindings}{\Sigma;\Gamma_1\vdash b:T\Rightarrow\Gamma_2} }{ \Sigma;\Gamma\vdash\mathsf{let}\ b=e\Rightarrow\Gamma_2 } \quad\text{Let} \]
Unique/Typing:StatementTyped
inductive StatementTyped (classes : ClassTable) : Environment → Unpacking.Statement → Environment → Prop where
  | letValue {before middle after : Environment} {pattern : Unpacking.Pattern}
      {value : Value} {ty : ViewType} :
      ExprTyped classes before value ty middle →
      BindingTyped classes middle pattern ty after →
      StatementTyped classes before ⟨pattern, value⟩ after

A statement-sequence typing \(\Sigma;\Gamma\vdash P\Rightarrow\Gamma_f\) threads statement typings through the remaining code:

\[ \frac{}{\Sigma;\Gamma\vdash []\Rightarrow\Gamma} \qquad \frac{ \href{#claim-given.typing.statements}{\Sigma;\Gamma\vdash t\Rightarrow\Gamma_1} \qquad\Sigma;\Gamma_1\vdash P\Rightarrow\Gamma_f }{ \Sigma;\Gamma\vdash t::P\Rightarrow\Gamma_f }. \]
Unique/Typing:SequenceTyped
inductive SequenceTyped (classes : ClassTable) : Environment → List Unpacking.Statement → Environment → Prop where
  | nil {environment : Environment} :
      environment.WellFormed classes → SequenceTyped classes environment [] environment
  | cons {before middle after : Environment} {statement : Unpacking.Statement}
      {rest : List Unpacking.Statement} :
      StatementTyped classes before statement middle →
      SequenceTyped classes middle rest after →
      SequenceTyped classes before (statement :: rest) after

A program is well typed when \(\Sigma\) is well formed and \(\href{#claim-given.typing.sequences}{\Sigma;\varnothing\vdash P\Rightarrow\Gamma_f}\) for some final environment \(\Gamma_f\). The final environment describes locals before initial-frame exit and need not be empty. Frame exit discards those locals and collects the heap; user-defined destruction is not part of this language.

Unique/Typing:ProgramTyped
def ProgramTyped (classes : ClassTable) (code : List Unpacking.Statement) : Prop :=
  classes.WellFormed ∧ ∃ finalEnvironment, SequenceTyped classes [] code finalEnvironment

A nested move followed by unpacking

With the Token, Pair, and Box declarations above:

let b = new Box(new Pair(new Token(), new Token()));
let taken = b.item.left→;
let p = b.item→;
let Pair → { left, right } = p→;

The statement rules change the following entries; all others keep their descriptions. The marker 0 means that a variable exists with an empty slot.

StatementUpdated bindingNew bindings
Construct—b: Box
Give leftb: Box.{-item.left, item.right}taken: Token
Give itemb: Box.{-item}p: Pair.{-left, right}
Unpackp: 0left: 0, right: Token

Unpacking consumes the pair object; the box and both tokens remain. A subsequent left→ has no typing derivation, because left is empty. Nor can p→ be repeated.

Unique/TypingExecutionChecks:moves_and_unpacking
example :
    StatementTyped classes [] (program[0]'(by decide)) afterConstruct ∧
    StatementTyped classes afterConstruct (program[1]'(by decide)) afterLeft ∧
    StatementTyped classes afterLeft (program[2]'(by decide)) afterItem ∧
    StatementTyped classes afterItem (program[3]'(by decide)) afterUnpack ∧
    SequenceTyped classes [] program afterUnpack ∧
    Unpacking.Steps classes.erase ⟨State.empty, program⟩ ⟨runtimeFinal, []⟩ ∧
    (Unpacking.Configuration.mk runtimeFinal []).finished ∧
    (∀ ty after, ¬ ExprTyped classes afterUnpack (.give (.variable "left")) ty after) ∧
    (∀ ty after, ¬ ExprTyped classes afterUnpack (.give (.variable "p")) ty after) := by
  exact ⟨construct_typed, left_typed, item_typed, unpack_typed, program_typed,
    program_executes, rfl, fun _ _ => failed_take_not_typed (by decide),
    fun _ _ => failed_take_not_typed (by decide)⟩

The expression and binding rules distinguish failure from lack of knowledge:

  • From p: Pair.{-left, right}, p.left→ is rejected because the field is known empty.
  • From p: Pair.{right}, the same expression is rejected because left is unknown. It might exist and be initialized at runtime.
  • From p: Pair.{-left, right}, giving p→ succeeds statically with that same viewed type. It does not produce a whole Pair.
  • Passing that result to new Box(p→) is rejected by this first constructor rule, even though the untyped machine could put the partial pair in the box.
  • Unpacking Pair.{right} is rejected because it would need a description for the hidden left field.

Constructor argument order also matters:

class Two { a: Token, b: Token }
let t = new Token();
let bad = new Two(t→, t→);

The first argument leaves t: 0. The second argument therefore has no typing derivation. Constructor arguments are checked in the same order as evaluation.

Unique/TypingRejectionChecks:rejected_moves
example :
    (∀ ty after, ¬ ExprTyped classes partialEnvironment (.give left) ty after) ∧
    (∀ ty after, ¬ ExprTyped classes hiddenEnvironment (.give left) ty after) ∧
    Satisfies classes runtimeFull 2 hiddenPair ∧
    Eval classes.erase runtimeFull (.give left) runtimeGivenLeft 0 ∧
    ExprTyped classes partialEnvironment (.give root) partialPair [("p", none)] ∧
    (∀ after, ¬ ExprTyped classes partialEnvironment (.give root) pair after) ∧
    (∀ ty after, ¬ ExprTyped classes partialEnvironment (.new "Box" [.give root]) ty after) ∧
    Eval classes.erase runtimePartial (.new "Box" [.give root])
      (runtimeAfterTake.allocate "Box" ["item"] [2]) 3 ∧
    (∀ before pattern after, ¬ BindingTyped classes before
      (.unpack "Pair" pattern) hiddenPair after) ∧
    ExprTyped twoClasses tokenEnvironment tokenGive token [("t", none)] ∧
    (∀ ty after, ¬ ExprTyped twoClasses [("t", none)] tokenGive ty after) ∧
    (∀ ty after, ¬ ExprTyped twoClasses tokenEnvironment
      (.new "Two" [tokenGive, tokenGive]) ty after) := by
  exact ⟨fun _ _ => failed_take_not_typed (by decide),
    fun _ _ => failed_take_not_typed (by decide), initialized_hidden_field.1,
    initialized_hidden_field.2, partial_give, fun _ => partial_not_whole,
    fun _ _ => partial_constructor_rejected, partial_constructor_executes,
    fun _ _ _ => hidden_unpack_rejected, first_argument_moves,
    fun _ _ => failed_take_not_typed (by decide), fun _ _ => repeated_argument_rejected⟩

Relating types to storage

Reading a relative path, written \(\mathsf{read}_S(\alpha,\rho)\), starts at object \(\alpha\) and follows the fields of the relative path \(\rho\). At \(\epsilon\), it returns \(\alpha\) if the object exists. At a nonempty path, every intermediate slot must contain an existing object; the final slot may contain an object identity or \(\bot\). A missing object or field encountered while following the path, or an empty intermediate slot, makes the read undefined. The final identity is not dereferenced.

Unique/TypingRealization:readPath
def readPath (state : State) (object : ObjectId) : Path → Option Slot
  | [] => do
      let _ ← state.objects.lookup object
      return some object
  | field :: rest => do
      let data ← state.objects.lookup object
      let slot ← data.fields.lookup field
      match rest with
      | [] => return slot
      | _ :: _ => do
          let target ← slot
          readPath state target rest

An object satisfies a type, written \(\Sigma;S\models\alpha:T\), when:

  • \(O(\alpha)\) exists and has class \(\href{#claim-given.typing.base}{\operatorname{base}}(T)\).
  • For every \(\rho\in\href{#claim-given.typing.observations}{\operatorname{pos}}_{\Sigma}(T)\), \(\href{#claim-given.typing.read}{\mathsf{read}}_S(\alpha,\rho)=\beta\) for an allocated object \(\beta\) of class \(\href{#claim-given.typing.class_at}{\operatorname{class}}_{\Sigma}(\href{#claim-given.typing.base}{\operatorname{base}}(T),\rho)\).
  • For every \(\rho\in\href{#claim-given.typing.observations}{\operatorname{neg}}_{\Sigma}(T)\), \(\href{#claim-given.typing.read}{\mathsf{read}}_S(\alpha,\rho)=\bot\).

Omitted branches impose no local initialization requirement. The definition ranges over finite paths; recursive class declarations need no infinite syntactic unfolding.

Unique/TypingRealization:Satisfies
structure Satisfies (classes : ClassTable) (state : State) (object : ObjectId) (ty : ViewType) : Prop where
  root : ∃ data, (object, data) ∈ state.objects ∧ data.className = ty.className
  positive : ∀ path, Pos classes ty path →
    ∃ target data, readPath state object path = some (some target) ∧
      (target, data) ∈ state.objects ∧
      classAt classes ty.className path = some data.className
  negative : ∀ path, Neg ty path → readPath state object path = some none

Expression results can temporarily own objects before binding or construction. Let \(R\) be a finite ordered list of pairs \((\alpha:T)\) for these pending values. Write \(\Sigma;\Gamma\models(S;R)\) when all of the following hold:

  1. Storage satisfies refgiven.well_formed, with the references in \(R\) counted alongside stored references in the ownership condition. Thus every allocated object has exactly one owner, including hidden fields and pending values.
  2. Every occupied object field targets an object of its declared nominal class in \(\Sigma\). This condition applies even to fields hidden by views.
  3. \(\operatorname{dom}(\Gamma)=\operatorname{dom}(V)\). If \(\Gamma(x)=0\), then \(V(x)=\bot\). If \(\Gamma(x)=T\), then \(V(x)=\alpha\) and \(\href{#claim-given.typing.satisfaction}{\Sigma;S\models\alpha:T}\).
  4. Each \((\alpha:T)\) in \(R\) satisfies \(\href{#claim-given.typing.satisfaction}{\Sigma;S\models\alpha:T}\).

Here \(\Sigma\) is a well-formed typed class table, \(S=\langle O,V,\nu\rangle\), and the operational class table is \(\href{#claim-given.typing.erasure}{\lfloor\Sigma\rfloor}\). Types must be well formed and normalized throughout. Empty pending lists are written \([]\).

This relation does not require every allocated object to satisfy its whole class type. That would rule out the very field moves the views describe.

Unique/TypingRealization:FieldsMatchClasses
def FieldsMatchClasses (classes : ClassTable) (state : State) : Prop :=
  ∀ parent data field target, (parent, data) ∈ state.objects →
    (field, some target) ∈ data.fields →
    ∃ declaration targetClass targetData,
      (data.className, declaration) ∈ classes ∧
      (field, targetClass) ∈ declaration.fields ∧
      (target, targetData) ∈ state.objects ∧ targetData.className = targetClass
Unique/TypingRealization:PendingValues
abbrev PendingValues := List (ObjectId × ViewType)
Unique/TypingRealization:Realizes
structure Realizes (classes : ClassTable) (environment : Environment) (state : State) (pending : PendingValues) : Prop where
  classesWellFormed : classes.WellFormed
  environmentWellFormed : environment.WellFormed classes
  pendingTypes : ∀ object ty, (object, ty) ∈ pending → Admissible classes ty
  ownership : WellFormedWith classes.erase state (pending.map Prod.fst)
  fields : FieldsMatchClasses classes state
  variableDomain : ∀ name,
    name ∈ environment.map Prod.fst ↔ name ∈ state.variables.map Prod.fst
  emptyVariables : ∀ name, (name, none) ∈ environment → (name, none) ∈ state.variables
  initializedVariables : ∀ name ty, (name, some ty) ∈ environment →
    ∃ object, (name, some object) ∈ state.variables ∧ Satisfies classes state object ty
  pendingValues : ∀ object ty, (object, ty) ∈ pending → Satisfies classes state object ty

Write \(\longrightarrow_u^{*}\) for zero or more extended steps, using the reflexive and transitive rules of refgiven.executions with \(\longrightarrow_u\) in place of \(\longrightarrow\). Write \(K\longrightarrow_u^k K'\) for exactly \(k\) program steps, including collection and initial-frame exit. The local operation is the unpacking-capable relation.

Unique/Frames:Steps
def Steps (operation : LocalStep Instruction) (before after : Configuration Instruction) : Prop :=
  ∃ count, StepsExactly operation before count after
Unique/Frames:StepsExactly
inductive StepsExactly (operation : LocalStep Instruction) : Configuration Instruction → Nat → Configuration Instruction → Prop where
  | refl (configuration) : StepsExactly operation configuration 0 configuration
  | step {before middle after count} :
      Step operation before middle → StepsExactly operation middle count after →
      StepsExactly operation before (count + 1) after

A configuration is stuck in the extended language when it is not finished and has no \(\href{given.html#claim-given.unpacking}{\longrightarrow_u}\) successor. Finishing means that the initial frame has been popped.

Unique/Frames:Stuck
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
  ¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after

A live frame is well typed with final environment \(\Gamma_f\) when its storage realizes an environment under which its remaining statements typecheck:

\[ \Sigma\vdash\operatorname{run}(S,P):\Gamma_f \iff \exists\Gamma.\;\Sigma;\Gamma\models(S;[]) \land \Sigma;\Gamma\vdash P\Rightarrow\Gamma_f. \]

A configuration with no frame is well typed when its heap is empty. Its counter may be nonzero. The final environment describes the locals before exit; it does not assert that terminal storage still contains those bindings. For a live frame, realization requires a well-formed class table.

Write \(K\longrightarrow_u^k K'\) for exactly \(k\) program steps using unpacking-capable local operations. Finite executions existentially quantify \(k\); stuckness means an unfinished configuration with no successor. The frame-pop step is included in this count.

Unique/FrameSafety:ConfigurationTyped
def ConfigurationTyped (classes : ClassTable) (configuration : Configuration Unpacking.Statement)
    (finalEnvironment : Environment) : Prop :=
  match configuration.frame with
  | none => configuration.objects = []
  | some frame => Typing.ConfigurationTyped classes ⟨configuration.state, frame.code⟩ finalEnvironment
Unique/Frames:StepsExactly
inductive StepsExactly (operation : LocalStep Instruction) : Configuration Instruction → Nat → Configuration Instruction → Prop where
  | refl (configuration) : StepsExactly operation configuration 0 configuration
  | step {before middle after count} :
      Step operation before middle → StepsExactly operation middle count after →
      StepsExactly operation before (count + 1) after
Unique/Frames:Stuck
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
  ¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after
Unique/TypedConfigurations:ConfigurationTyped
def ConfigurationTyped (classes : ClassTable) (configuration : Unpacking.Configuration)
    (finalEnvironment : Environment) : Prop :=
  ∃ current, Realizes classes current configuration.state [] ∧
    SequenceTyped classes current configuration.code finalEnvironment

Progress and preservation

Expression typing guarantees both successful evaluation and the description of its result. For every well-formed \(\Sigma\), environment \(\Gamma\), storage \(S\), and pending-value list \(R\), assume:

\[ \Sigma;\Gamma\vdash e:T\;\href{#claim-given.typing.expressions}{\triangleright}\;\Gamma', \qquad \href{#claim-given.typing.realization}{\Sigma;\Gamma\models(S;R)}. \]

Then an evaluation exists:

\[ \exists S',\alpha.\; \href{#claim-given.typing.erasure}{\lfloor\Sigma\rfloor}\vdash\langle S,e\rangle \href{given.html#claim-given.evaluation}{\Downarrow}\langle S',\alpha\rangle. \]

Moreover, every such evaluation satisfies:

\[ \href{#claim-given.typing.realization}{\Sigma;\Gamma'\models(S';R\mathbin{+\!\!+}[(\alpha:T)])}. \]

Here \(+\!\!+\) appends lists. Earlier constructor arguments are included in \(R\) while later arguments run. The lemma preserves their types as well as the variables’ types. Evaluation leaves the variable domain unchanged, so the typing rules’ freshness checks also hold at the point of runtime binding.

Unique/TypingSafety:expression_soundness
theorem expression_soundness
    (typed : ExprTyped classes before value ty after)
    (realized : Realizes classes before state pending) :
    (∃ result object, Eval classes.erase state value result object) ∧
    (∀ result object, Eval classes.erase state value result object →
      Realizes classes after result (pending ++ [(object, ty)])) := by
  have sound := typed.sound state pending realized
  refine ⟨sound.1, fun result object evaluated => ?_⟩
  exact (sound.2 result object evaluated).perm (by simpa using (List.perm_middle (a := (object, ty)) (l₁ := pending) (l₂ := [])).symm)

For every well-typed configuration, either execution has finished or a next step is possible:

\[ \Sigma\vdash K:\Gamma_f \quad\Longrightarrow\quad \mathsf{Finished}(K) \;\lor\; \exists K'.\;\lfloor\Sigma\rfloor\vdash K\longrightarrow_u K'. \]

This is a claim about the operational rules: typing does not add a transition for an otherwise failing operation.

Unique/FrameSafety:ConfigurationTyped.progress
theorem ConfigurationTyped.progress
    (typed : ConfigurationTyped classes configuration finalEnvironment) :
    configuration.finished ∨ ∃ after, Step (patternOperation classes.erase) configuration after := by
  rcases configuration with ⟨objects, nextId, frame⟩
  cases frame with
  | none => exact .inl rfl
  | some frame =>
    rcases frame with ⟨variables, code⟩
    have localTyped : Typing.ConfigurationTyped classes ⟨⟨objects, variables, nextId⟩, code⟩ finalEnvironment := typed
    rcases localTyped.progress with finished | ⟨after, step⟩
    · change code = [] at finished
      subst code
      exact .inr ⟨_, exit_step ⟨objects, variables, nextId⟩⟩
    · exact .inr ⟨_, local_step (operation := patternOperation classes.erase)
        (before := ⟨objects, variables, nextId⟩) (code := code) (after := after.state)
        (rest := after.code) step (local_wellFormed (localTyped.preservation step))⟩

Every step from a well-typed configuration preserves its typing:

\[ \frac{ \Sigma\vdash K:\Gamma_f \qquad \lfloor\Sigma\rfloor\vdash K\longrightarrow_u K' }{ \Sigma\vdash K':\Gamma_f }. \]

The existential current environment changes to reflect moved slots and new bindings. The final environment stays the same. This theorem quantifies over every operational successor, including unpacking an object with empty fields.

Unique/FrameSafety:ConfigurationTyped.preservation
theorem ConfigurationTyped.preservation
    (typed : ConfigurationTyped classes before finalEnvironment)
    (step : Step (patternOperation classes.erase) before after) :
    ConfigurationTyped classes after finalEnvironment := by
  cases step with
  | «local» operation =>
    have next := Typing.ConfigurationTyped.preservation typed operation
    rw [collect_running (local_wellFormed next)]
    exact next
  | exit =>
    rw [collect_popped]
    rfl

For a well-formed class table, a program whose statements check from the empty environment cannot reach a stuck configuration. Every execution prefix remains well typed and can be completed.

If the original program has \(n\) statements, every such prefix extends to completion after exactly \(n+1\) steps in total: one per statement, followed by one frame-pop step. A live frame’s remaining work is its statement count plus one; a finished configuration has zero remaining work. Terminal storage has no locals and an empty heap; its allocation counter records the identifiers spent.

Unique/FrameSafety:program_safety
theorem program_safety (classesWf : classes.WellFormed)
    (typed : SequenceTyped classes [] code finalEnvironment)
    (execution : StepsExactly (patternOperation classes.erase) (.initial code) count configuration) :
    ¬ Stuck (patternOperation classes.erase) configuration ∧
    ConfigurationTyped classes configuration finalEnvironment ∧
    count + configuration.remaining = code.length + 1 ∧
    ∃ nextId,
      StepsExactly (patternOperation classes.erase) configuration configuration.remaining (.terminal nextId) ∧
      StepsExactly (patternOperation classes.erase) (.initial code) (code.length + 1) (.terminal nextId) := by
  have current := (ConfigurationTyped.initial classesWf typed).trace execution
  have length : count + configuration.remaining = code.length + 1 := by
    exact (execution.remaining (fun _ _ _ _ step => step.code_length)).symm
  obtain ⟨nextId, rest⟩ := current.finishes
  refine ⟨?_, current, length, nextId, rest, length ▸ execution.trans rest⟩
  intro stuck
  rcases current.progress with finished | next
  · exact stuck.1 finished
  · exact stuck.2 next

From a well-typed live frame with \(n\) statements, there is an observation state \(S_f\) after exactly \(n\) program steps. Its frame has no statements left, and its locals still realize the final environment. One further step pops that frame, leaving no roots and an empty heap with counter \(S_f.\nu\). This separates inspection of the computed bindings from program completion.

Unique/FrameSafety:completion
theorem completion (typed : Typing.ConfigurationTyped classes before finalEnvironment) :
    ∃ observed,
      StepsExactly (patternOperation classes.erase) (.running before.state before.code)
        before.code.length (.running observed []) ∧
      Realizes classes finalEnvironment observed [] ∧
      StepsExactly (patternOperation classes.erase) (.running before.state before.code)
        (before.code.length + 1) (.terminal observed.nextId) := by
  obtain ⟨last, trace, finished, realized⟩ := typed.finishes
  have lifted := lift_local_trace typed trace
  change last.code = [] at finished
  rw [finished] at lifted
  exact ⟨last.state, lifted, realized, lifted.trans (.step (exit_step _) (.refl _))⟩