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

Shared: typing and soundness

When a give copies

The type of a place tells us whether giving it moves or copies. Consider a box whose field has type Token:

struct Token {}
struct Box { item: Token }

let b = new Box(new Token());
let s = b→share;
let u = s.item→;
let v = s.item→;
StatementResult typeEffect on the source
Construct bBox—
Give-share bshared Boxb becomes empty.
Give s.item into ushared TokenThe field stays initialized.
Give s.item into vshared TokenThe field stays initialized.

The field is declared Token, but access through s makes its effective type shared Token. The first field give changes its stored reference to shared and returns a shared copy; the second copies it again. Neither changes s’s type.

This chapter adds two permissions, given and shared, to Given’s types and views. Token is shorthand for given Token. It also carries Given’s unpacking patterns into Shared, with unpacking restricted to unique results.

Shared/TypingExecutionChecks:copying_through_shared
example : SequenceTyped classes [] copyProgram copyFinal ∧
    Unpacking.StepsExactly classes.erase ⟨State.empty, copyProgram⟩ 4 ⟨boxCopiedTwice, []⟩ ∧
    Eval classes.erase boxShared (.give (field "s" "item"))
      ⟨boxCopied.objects, boxShared.variables, 2⟩ (.shared 0) ∧
    Eval classes.erase boxCopied (.give (field "s" "item")) boxCopied (.shared 0) ∧
    copyFinal.lookup "b" = some none ∧
    copyFinal.lookup "s" = some (some box.shared) ∧
    copyFinal.lookup "u" = some (some token.shared) ∧
    copyFinal.lookup "v" = some (some token.shared) ∧
    (1, ⟨"Box", [("item", some (.owned 0))]⟩) ∈ boxShared.objects ∧
    (1, ⟨"Box", [("item", some (.shared 0))]⟩) ∈ boxCopied.objects ∧
    ("s", some (.shared 1)) ∈ boxCopiedTwice.variables ∧
    ("u", some (.shared 0)) ∈ boxCopiedTwice.variables ∧
    ("v", some (.shared 0)) ∈ boxCopiedTwice.variables := by
  exact ⟨copy_typed, copy_execution, first_copy, second_copy, by decide, by decide, by decide, by decide,
    by decide, by decide, by decide, by decide, by decide⟩

Permissions and field declarations

A permission \(\pi\) describes unique or shared access. A nominal type \(N\) pairs a class name \(C\) with a signed view \(A\). A type \(T\) may apply a permission to another type:

\[ \begin{aligned} \pi &::= \mathsf{given}\mid\mathsf{shared},\\ N &::= C.A,\\ T &::= N\mid\pi\,T. \end{aligned} \]

Bare \(C\) still abbreviates \(C.\{\epsilon\}\). Positive view entries expose initialized subtrees; negative entries describe empty slots; omitted branches are unknown and inaccessible. Views do not assign ownership modes to objects.

Shared/TypingViews:Perm
inductive Perm where
  | given
  | shared
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Shared/TypingViews:Nominal
abbrev Nominal := Unique.Typing.ViewType
Shared/TypingViews:RawType
inductive RawType where
  | nominal (view : Nominal)
  | apply (permission : Perm) (inner : RawType)
  deriving DecidableEq, Repr
Shared/TypingViews:ValueType.whole
def ValueType.whole (name : ClassName) (permission : Perm := .given) : ValueType :=
  ⟨permission, .whole name⟩

Permission composition \(\pi\pi'\) combines an outer permission with an inner one. The result is given only when both are given:

Outer permissionInner givenInner shared
givengivenshared
sharedsharedshared
Shared/TypingViews:Perm.comp
def Perm.comp : Perm → Perm → Perm
  | .given, .given => .given
  | _, _ => .shared

Type normalization combines nested permissions and normalizes the nominal view. Its normalized form has exactly one outer permission:

\[ \pi\,C.A. \]

Combine permissions using composition and these equations:

\[ \mathsf{given}\ T=T, \qquad \pi(\pi'T)=(\href{#claim-shared.typing.composition}{\pi\pi'})T. \]

Normalize the nominal view using Given’s view normalization. For a class or ordinary struct, a bare nominal type supplies the outer permission given; we omit that permission when printing. For a shared struct, the nominal declaration supplies shared instead; applying given does not remove that intrinsic sharing. Thus shared shared Token normalizes to shared Token.

Shared/TypingViews:ValueType
structure ValueType where
  permission : Perm
  nominal : Nominal
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Shared/TypingViews:RawType.normalize
def RawType.normalize (classes : ClassTable) : RawType → ValueType
  | .nominal view =>
      ⟨initialPermission ((classes.lookup view.className).map TypedClass.kind |>.getD .classType),
        Unique.Typing.normalize classes.nominal view⟩
  | .apply permission inner =>
      let result := inner.normalize classes
      { result with permission := permission.comp result.permission }
Shared/TypingViews:normalize
def normalize (classes : ClassTable) (ty : ValueType) : ValueType :=
  { ty with nominal := Unique.Typing.normalize classes.nominal ty.nominal }
Shared/TypingViews:Normalized
def Normalized (classes : ClassTable) (ty : ValueType) : Prop :=
  Unique.Typing.Normalized classes.nominal ty.nominal
Shared/TypingViews:initialPermission
def initialPermission : Kind → Perm
  | .sharedStruct => .shared
  | _ => .given

The permission of a type \(\operatorname{perm}(T)\) is its outer permission in normalized form:

\[ \operatorname{perm}(\pi\,C.A)=\pi. \]

A bare class or ordinary struct type has permission given. A bare shared struct type has permission shared, as specified by normalization.

Shared/TypingViews:ValueType.perm
def ValueType.perm (ty : ValueType) : Perm := ty.permission

The base class \(\operatorname{base}(T)\) is the class named by a type, independent of its permission and view. For a normalized type:

\[ \operatorname{base}(\pi\,C.A)=C. \]
Shared/TypingViews:ValueType.base
def ValueType.base (ty : ValueType) : ClassName := ty.nominal.className

A typed nominal table \(\Sigma\) records each declaration kind and gives each field a permission and a nominal type. Constructor arguments must supply whole values of the declared types:

\[ \begin{aligned} F &::= \pi\,C,\\ k &::= \mathsf{class}\mid\mathsf{struct}\mid\mathsf{shared\ struct},\\ d &::= k\ C\ \{f_1:F_1,\ldots,f_n:F_n\},\\ \Sigma &\in \mathsf{ClassName}\rightharpoonup\mathsf{Kind}\times \mathsf{List}(\mathsf{FieldName}\times F). \end{aligned} \]

Here \(F\) also denotes the set of field types generated by its grammar. The declaration kind belongs to the set Kind generated by the grammar for k. Below, Σ(C) = [f₁:F₁, …, fₙ:Fₙ] abbreviates lookup of just the ordered fields; kindΣ(C) selects the declaration kind. Field permissions are normalized, including the intrinsic sharing of shared struct types. The table records normalized field types, so path permission composition uses those permissions.

Shared/TypingViews:FieldType
structure FieldType where
  permission : Perm
  className : ClassName
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Shared/TypingViews:FieldType.toType
def FieldType.toType (field : FieldType) : ValueType :=
  .whole field.className field.permission
Shared/TypingViews:TypedClass
structure TypedClass where
  fields : List (FieldName × FieldType)
  kind : Kind := .structType
  deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
Shared/TypingViews:ClassTable
abbrev ClassTable := List (ClassName × TypedClass)

A typed class table \(\Sigma\) is well formed when class names are distinct, field names within each class are distinct, and every class named by a field type is declared in \(\Sigma\).

For every struct or shared struct declaration, each field type F must satisfy struct(F). A class declaration has no such restriction. A field with shared permission must have a struct type even when its container is a class. These checks inspect nominal declarations, not field accessibility in a view.

Shared/TypingViews: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.className ∈ classes.map Prod.fst ∧
        KindValid classes field.2.toType ∧
        (entry.2.kind.isStruct = true → StructType classes field.2.toType)

Class-table erasure \(\lfloor\Sigma\rfloor\) supplies the operational class table by removing field types. It retains every nominal name, declaration kind, and field order:

\[ \lfloor\Sigma\rfloor(C)=(\operatorname{kind}_{\Sigma}(C),[f_1,\ldots,f_n]) \quad\text{where }\href{#claim-shared.typing.declarations}{\Sigma(C)}=[f_1:F_1,\ldots,f_n:F_n]. \]
Shared/TypingViews:ClassTable.erase
def ClassTable.erase (classes : ClassTable) : Classes :=
  classes.map fun (name, declaration) => (name, ⟨declaration.fields.map Prod.fst, declaration.kind⟩)

The nominal class table \(\Sigma_{\mathrm{nom}}\) supplies Given’s typed class table by removing declaration kinds and each field’s permission, retaining the nominal names and field order:

\[ \Sigma_{\mathrm{nom}}(C)=[f_1:C_1,\ldots,f_n:C_n] \quad\text{where }\href{#claim-shared.typing.declarations}{\Sigma(C)}=[f_1:\pi_1 C_1,\ldots,f_n:\pi_n C_n]. \]

Use this table for Given’s relative paths and views, view normalization, nominal focusing, and emptying.

Shared/TypingViews:ClassTable.nominal
def ClassTable.nominal (classes : ClassTable) : Unique.Typing.ClassTable :=
  classes.map fun (name, declaration) =>
    (name, ⟨declaration.fields.map fun (field, ty) => (field, ty.className)⟩)

A type is well formed when its base class is declared and its view satisfies Given’s view conditions under the nominal class table: paths are valid, distinct, and pairwise prefix-incomparable. In addition, a shared permission requires struct(T). A shared struct has shared permission after normalization; there is no normalized given type for its instances.

Shared/TypingViews:ValueType.WellFormed
def ValueType.WellFormed (ty : ValueType) (classes : ClassTable) : Prop :=
  ty.nominal.WellFormed classes.nominal ∧ KindValid classes ty
Shared/TypingViews:KindValid
def KindValid (classes : ClassTable) (ty : ValueType) : Prop :=
  (classes.lookup ty.base).any (fun declaration => kindAllows declaration.kind ty.permission) = true
Shared/TypingViews:kindAllows
def kindAllows (kind : Kind) (permission : Perm) : Bool :=
  match kind with
  | .classType => permission == .given
  | .structType => true
  | .sharedStruct => permission == .shared

The known-initialized paths \(\operatorname{pos}_{\Sigma}(T)\) and known-empty paths \(\operatorname{neg}_{\Sigma}(T)\) depend on a type’s nominal view, not its permission. For normalized \(T=\pi N\), use Given’s observations under the nominal class table:

\[ \operatorname{pos}_{\Sigma}(\pi N)=\href{given-typing.html#claim-given.typing.observations}{\operatorname{pos}}_{\href{#claim-shared.typing.nominal_table}{\Sigma_{\mathrm{nom}}}}(N), \qquad \operatorname{neg}_{\Sigma}(\pi N)=\href{given-typing.html#claim-given.typing.observations}{\operatorname{neg}}_{\href{#claim-shared.typing.nominal_table}{\Sigma_{\mathrm{nom}}}}(N). \]

A positive entry exposes a whole declared subtree, including shared fields. A negative entry describes an empty slot; an omitted branch remains unknown and inaccessible.

Shared/TypingViews:Pos
def Pos (classes : ClassTable) (ty : ValueType) (path : Path) : Prop :=
  Unique.Typing.Pos classes.nominal ty.nominal path
Shared/TypingViews:Neg
def Neg (ty : ValueType) (path : Path) : Prop :=
  Unique.Typing.Neg ty.nominal path

Following a path

A shared link may occur anywhere along a path:

struct Token {}
struct Box { item: Token }
class Outer { box: shared Box }
struct Holder { item: shared Token }

Consider initialized variables b: Box, s: shared Box, o: Outer, and h: Holder:

PlaceEffective typeGiving it
b.itemTokenMoves the token.
s.itemshared TokenCopies a shared reference.
o.box.itemshared TokenCopies a shared reference.
h.itemshared TokenCopies a shared reference.

In the third row, o is unique but its box field is shared. In the fourth, the final field itself is declared shared. A unique container can therefore contain a field that is copied when given.

Shared/TypingChecks:permission_paths
example :
    focus classes box ["item"] = some token ∧
    focus classes box.shared ["item"] = some token.shared ∧
    focus classes (.whole "Outer") ["box", "item"] = some token.shared ∧
    focus classes holder ["item"] = some token.shared ∧
    give classes [("b", some box)] (field "b" "item") =
      some (token, [("b", some ⟨.given, ⟨"Box", [.negative ["item"]]⟩⟩)]) ∧
    give classes [("s", some box.shared)] (field "s" "item") =
      some (token.shared, [("s", some box.shared)]) ∧
    give classes [("o", some (.whole "Outer"))] (place :=
      .field (field "o" "box") "item") =
      some (token.shared, [("o", some (.whole "Outer"))]) ∧
    give classes [("h", some holder)] (field "h" "item") =
      some (token.shared, [("h", some holder)]) := by
  exact ⟨by decide, by decide, by decide, by decide,
    by decide, by decide, by decide, by decide⟩

The declared permission \(\operatorname{decl}_{\Sigma}(C,\rho)\) combines the field permissions along a relative path \(\rho\) from class \(C\), using permission composition:

\[ \begin{aligned} \operatorname{decl}_{\Sigma}(C,\epsilon)&=\mathsf{given},\\ \operatorname{decl}_{\Sigma}(C,f\rho)&= \pi_f\operatorname{decl}_{\Sigma}(D,\rho) &&\text{where }(f:\pi_f D)\in\href{#claim-shared.typing.declarations}{\Sigma(C)}. \end{aligned} \]

It is defined exactly on paths valid from \(C\) under the nominal class table.

Shared/TypingViews:declaredPermission
def declaredPermission (classes : ClassTable) (name : ClassName) : Path → Option Perm
  | [] => some .given
  | field :: rest => do
      let declaration ← classes.lookup name
      let target ← declaration.fields.lookup field
      let permission ← declaredPermission classes target.className rest
      return target.permission.comp permission

Focusing \(T\downarrow\rho\) finds the type reached by a path, carrying the enclosing permission into each field. Access to a field declared \(F\) through a whole value of type \(\pi\,C\) has type \(\pi F\).

Using permission composition, extend Given’s focusing operation (\(\href{given-typing.html#claim-given.typing.focus}{N\downarrow\rho}\)) to a type \(T=\pi N\), where the nominal type is \(N=C.A\):

\[ T\downarrow\rho =\bigl(\pi\href{#claim-shared.typing.declared_permission}{\operatorname{decl}_{\Sigma}(C,\rho)}\bigr) (\href{given-typing.html#claim-given.typing.focus}{N\downarrow\rho}), \qquad \rho\in\href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(T)}. \]

The nominal focus uses the nominal class table and preserves the field’s current view, including holes. The new operation \(T\downarrow\rho\) adds the effective permission and normalizes the result. It does not restore moved or hidden fields.

Shared/TypingViews:focus
def focus (classes : ClassTable) (ty : ValueType) (path : Path) : Option ValueType := do
  let nominal ← Unique.Typing.focus classes.nominal ty.nominal path
  let permission ← declaredPermission classes ty.base path
  return ⟨ty.permission.comp permission, nominal⟩

Emptying \(T[-\rho]\) marks a field path as empty while retaining the outer permission and every other branch’s information. For normalized \(T=\pi N\):

\[ (\pi N)[-\rho]=\pi\,(\href{given-typing.html#claim-given.typing.emptying}{N[-\rho]}), \qquad \rho\ne\epsilon,\quad \rho\in\href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(T)}. \]

The right-hand side uses Given’s emptying operation under the nominal class table. Normalize the result.

Shared/TypingViews:emptyPath
def emptyPath (classes : ClassTable) (ty : ValueType) (path : Path) : Option ValueType :=
  (Unique.Typing.emptyPath classes.nominal ty.nominal path).map fun remaining =>
    ⟨ty.permission, remaining⟩

The static give operation

A slot description \(B\) is either \(0\), for an empty variable, or a type. A typing environment \(\Gamma\) describes every variable slot:

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

Types must be well formed and normalized. Empty variables remain in the domain and cannot be reused as fresh names.

Shared/Typing:SlotDescription
abbrev SlotDescription := Option ValueType
Shared/Typing:Environment
abbrev Environment := List (VariableId × SlotDescription)
Shared/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
Shared/Typing:Environment.lookup
def Environment.lookup (environment : Environment) (name : VariableId) :
    Option SlotDescription :=
  (environment.find? fun entry => entry.1 == name).map Prod.snd
Shared/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

The static give operation computes the type produced by giving a place and the environment afterwards. Write \(\mathsf{give}_{\Sigma}(\Gamma,p)=(T,\Gamma')\): the result has type \(T\), and the variable slots have descriptions \(\Gamma'\).

Write a place as \(p=x.\rho\): for o.box.item, the root variable is o and the relative path is box.item; for o, the relative path is \(\epsilon\). The operation is defined exactly when \(\Gamma(x)=U\) and \(\rho\in\href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(U)}\). Its outputs are:

\[ T=\href{#claim-shared.typing.focus}{U\downarrow\rho}, \qquad \Gamma'=\begin{cases} \Gamma & \href{#claim-shared.typing.perm}{\operatorname{perm}(T)}=\mathsf{shared},\\ \Gamma[x\mapsto0] & \href{#claim-shared.typing.perm}{\operatorname{perm}(T)}=\mathsf{given},\ \rho=\epsilon,\\ \Gamma[x\mapsto \href{#claim-shared.typing.emptying}{U[-\rho]}] & \href{#claim-shared.typing.perm}{\operatorname{perm}(T)}=\mathsf{given},\ \rho\ne\epsilon. \end{cases} \]

The last case empties the field path. A given result requires every permission along its route to be given. A shared result leaves the entire environment unchanged. An absent variable, an empty source, or an inaccessible field makes this static give operation undefined. A field hidden by a view may still hold a value at runtime.

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

Weakening a view

As in Given, view weakening can hide initialization facts while preserving the permission. For normalized types \(T=\pi C.A\) and \(U=\pi'C'.A'\), define:

\[ T\preceq_{\Sigma}U \iff \begin{gathered} \pi=\pi'\ \land\ C=C'\\ {}\land\ \href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(U)}\subseteq\href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(T)}\\ {}\land\ \href{#claim-shared.typing.observations}{\operatorname{neg}_{\Sigma}(U)}\subseteq\href{#claim-shared.typing.observations}{\operatorname{neg}_{\Sigma}(T)}. \end{gathered} \]

For example, shared Box can be weakened to shared Box.{}. There is no weakening from Box to shared Box: creating a shared reference requires the runtime give-share operation. Different aliases may expose different views of the same object.

Shared/TypingViews:Subtype
def Subtype (classes : ClassTable) (source target : ValueType) : Prop :=
  source.permission = target.permission ∧
    Unique.Typing.Subtype classes.nominal source.nominal target.nominal

Typing expressions

Expression typing \(\Sigma;\Gamma\vdash e:T\;\triangleright\;\Gamma'\) records the result’s type and the variable descriptions after evaluation. All type expressions in the rules use type normalization. Both Give and Give-share use the static give operation \(\href{#claim-shared.typing.giving}{\mathsf{give}_{\Sigma}(\Gamma,p)=(T,\Gamma')}\) defined above. Give returns its result type. Give-share additionally requires struct(T) and applies shared to that type:

\[ \frac{\href{#claim-shared.typing.giving}{\mathsf{give}_{\Sigma}(\Gamma,p)=(T,\Gamma')}} {\Sigma;\Gamma\vdash p\mathord{\to}:T\;\triangleright\;\Gamma'} \quad\text{Give} \]
\[ \frac{\href{#claim-shared.typing.giving}{\mathsf{give}_{\Sigma}(\Gamma,p)=(T,\Gamma')}\qquad\href{shared.html#claim-shared.struct}{\mathsf{struct}}(T)} {\Sigma;\Gamma\vdash p\mathord{\to}\mathsf{share}:\mathsf{shared}\ T \;\triangleright\;\Gamma'} \quad\text{Give-share} \]

Both rules make the same change to the source. Give-share preserves the result’s view: it changes permission, not initialization.

Construct checks arguments from left to right against the declared field types. Define initΣ(C) to be shared for a shared struct declaration and given for a class or ordinary struct. This permission describes the constructor result; the arguments retain their own permissions:

\[ \frac{ \begin{gathered} \href{#claim-shared.typing.declarations}{\Sigma(C)}=[f_1:F_1,\ldots,f_n:F_n]\\ \Sigma;\Gamma_{i-1}\vdash e_i:F_i\;\triangleright\;\Gamma_i \quad(1\le i\le n) \end{gathered} }{ \Sigma;\Gamma_0\vdash\mathsf{new}\ C(e_1,\ldots,e_n):\operatorname{init}_{\Sigma}(C)\,C \;\triangleright\;\Gamma_n } \quad\text{Construct} \]

The argument count must match the declaration. With no arguments, the environment is unchanged. Arguments still require their whole declared types. A result may expose a weaker view:

\[ \frac{\Sigma;\Gamma\vdash e:T\;\triangleright\;\Gamma' \qquad\href{#claim-shared.typing.weakening}{T\preceq_{\Sigma}U}} {\Sigma;\Gamma\vdash e:U\;\triangleright\;\Gamma'} \quad\text{Weaken} \]
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
Shared/TypingViews:StructType
def StructType (classes : ClassTable) (ty : ValueType) : Prop :=
  (classes.lookup ty.base).any (fun declaration => declaration.kind.isStruct) = true
Shared/TypingViews:initialPermission
def initialPermission : Kind → Perm
  | .sharedStruct => .shared
  | _ => .given

With Token, Box, and Holder declared above:

let t = new Token();
let h = new Holder(t→share);
let a = h.item→;
let b = h.item→;

The constructor rule requires a shared Token, so its argument explicitly shares the token. Afterwards t is empty, h: Holder, and both a and b have type shared Token. Giving h.item does not empty it.

Replacing the constructor argument with t→ is rejected: its type is Token, not the declared shared Token. Conversely, new Box(a→) is rejected because the shared result cannot supply the given Token required by Box.

Shared/TypingExecutionChecks:constructor_permissions
example : SequenceTyped classes [] argumentProgram argumentFinal ∧
    Unpacking.Steps classes.erase ⟨State.empty, argumentProgram⟩ ⟨Unpacking.argumentsFinished, []⟩ ∧
    argumentFinal.lookup "t" = some none ∧
    argumentFinal.lookup "h" = some (some holder) ∧
    argumentFinal.lookup "a" = some (some token.shared) ∧
    argumentFinal.lookup "b" = some (some token.shared) ∧
    (∀ ty after, ¬ ExprTyped classes [("t", some token)]
      (.new "Holder" [.give (.variable "t")]) ty after) ∧
    (∀ ty after, ¬ ExprTyped classes argumentFinal
      (.new "Box" [.give (.variable "a")]) ty after) := by
  exact ⟨arguments_typed, Unpacking.arguments_execution, by decide, by decide, by decide, by decide,
    fun _ _ => holder_requires_sharing, fun _ _ => box_rejects_shared⟩

Sharing also preserves a partially moved value:

struct Token {}
struct Pair { left: Token, right: Token }

let p = new Pair(new Token(), new Token());
let t = p.left→;
let s = p→share;
let a = s.right→;
let b = s.right→;

Moving left leaves p: Pair.{-left, right}. Give-share then empties p and produces s: shared Pair.{-left, right}. The last two statements produce shared tokens and preserve that view of s.

Giving s.left→ is rejected because left is empty. Weakening s’s view could hide that fact, but could not make the field accessible again.

Shared/TypingExecutionChecks:sharing_partial_views
example : SequenceTyped classes [] partialProgram partialFinal ∧
    Unpacking.StepsExactly classes.erase ⟨State.empty, partialProgram⟩ 5 ⟨pairCopiedTwice, []⟩ ∧
    partialFinal.lookup "s" = some (some partialPair.shared) ∧
    partialFinal.lookup "a" = some (some token.shared) ∧
    partialFinal.lookup "b" = some (some token.shared) ∧
    (2, ⟨"Pair", [("left", none), ("right", some (.shared 1))]⟩) ∈ pairCopiedTwice.objects ∧
    ("p", none) ∈ pairCopiedTwice.variables ∧
    ("a", some (.shared 1)) ∈ pairCopiedTwice.variables ∧
    ("b", some (.shared 1)) ∈ pairCopiedTwice.variables ∧
    (∀ ty after, ¬ ExprTyped classes partialFinal (.give (field "s" "left")) ty after) := by
  exact ⟨partial_typed, partial_execution, by decide, by decide, by decide,
    by decide, by decide, by decide, by decide,
    fun _ _ => failed_give_not_typed (by decide)⟩

Binding results

An unpacking pattern consumes a uniquely owned container and transfers its field slots to fresh variables. This extends Shared’s statements with Given’s flat binding patterns \(b\):

\[ \begin{aligned} b&::=x\mid C\mathord{\to}\{f_1:x_1,\ldots,f_n:x_n\},\\ t&::=\mathsf{let}\ b=e. \end{aligned} \]

Each declared field must appear exactly once; destination variables are distinct and fresh in the variable table after expression evaluation. Field order in the pattern is immaterial. f abbreviates f: f; there are no _ or .. patterns here.

Shared/Unpacking:Pattern
inductive Pattern where
  | variable (name : VariableId)
  | unpack (className : ClassName) (fields : List (FieldName × VariableId))
  deriving DecidableEq, Repr
Shared/Unpacking:Statement
structure Statement where
  pattern : Pattern
  value : Value
  deriving Repr

The program configuration keeps its heap and optional initial frame. Its frame now contains pattern-binding statements. A local-frame observation \(\langle S,P\rangle\) pairs the frame’s storage with its remaining statements for local evaluation. It is not a complete program lifetime.

Shared/Frames:Frame
structure Frame (Instruction : Type) where
  variables : List (VariableId × Slot)
  code : List Instruction
  deriving Repr
Shared/Frames:Configuration
structure Configuration (Instruction : Type) where
  objects : List (ObjectId × Object)
  nextId : Nat
  frame : Option (Frame Instruction)
  deriving Repr
Shared/Unpacking:Configuration
structure Configuration where
  state : State
  code : List Statement
  deriving Repr

A local-frame observation pairs storage with the remaining statement sequence. An extended local operation runs one let statement with a binding pattern.

Write \(\href{shared.html#claim-shared.evaluation}{\Delta\vdash\langle S,e\rangle\Downarrow\langle S',r\rangle}\) for Shared’s expression evaluation. It is unchanged. The extended step first evaluates the expression, then binds its result:

  • A variable pattern stores the reference, of either mode, in its fresh slot.
  • A C → { ... } pattern requires \(r=(\mathsf{unique},\alpha)\) and an allocated C object at \(\alpha\). Transfer every field slot to its named destination and remove \(\alpha\) from the object table.

Field references retain their modes and targets; empty fields become empty variables. All other storage and the allocation counter remain as in \(S'\). The statement is removed from the remaining sequence. A shared result has no unpacking transition: consuming its container would invalidate other owners. The program machine applies patternOperation and collects after this local operation; its frame-exit rule is unchanged.

Shared/Unpacking:Configuration
structure Configuration where
  state : State
  code : List Statement
  deriving Repr
Shared/Unpacking:Transfer
inductive Transfer : List (FieldName × VariableId) → List (FieldName × Slot) → List (VariableId × Slot) → Prop where
  | nil : Transfer [] [] []
  | cons {field name slot pattern before after bindings} :
      Transfer pattern (before ++ after) bindings →
      Transfer ((field, name) :: pattern) (before ++ (field, slot) :: after)
        ((name, slot) :: bindings)
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/Unpacking:Step
inductive Step (classes : Classes) : Configuration → Configuration → Prop where
  | letValue {before evaluated after pattern value object rest} :
      Eval classes before value evaluated object →
      Bind classes evaluated object pattern after →
      Step classes ⟨before, ⟨pattern, value⟩ :: rest⟩ ⟨after, rest⟩

A finite execution \(\Delta\vdash K\longrightarrow_u^{*}K'\) consists of zero or more program steps, including collection and frame exit, all using the same class table \(\Delta\).

Shared/Frames:Steps
def Steps (operation : LocalStep Instruction) (before after : Configuration Instruction) : Prop :=
  ∃ count, StepsExactly operation before count after
Shared/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 finished exactly when its initial frame has been popped, as in Shared completion. Exhausted statements alone do not finish the program.

Shared/Frames:Configuration.finished
def Configuration.finished (configuration : Configuration Instruction) : Prop :=
  configuration.frame = none

A configuration is stuck if it is not finished and has no successor. An exhausted live frame can still take its exit step, so it is neither finished nor stuck.

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

The field description \(\mathsf{field}_{\Sigma}(T,f)\) tells an unpacking pattern whether a direct field is empty or which type it transfers:

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

An unknown field has no description.

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

Binding typing \(\Sigma;\Gamma\vdash b:T\Rightarrow\Gamma'\) describes where a result goes in the environment. A fresh variable receives its type unchanged:

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

For unpacking, the container must be given and every direct field’s status must be known. Unpacking transfers its field descriptions:

\[ \frac{ \begin{gathered} \href{#claim-shared.typing.perm}{\operatorname{perm}(T)}=\mathsf{given} \qquad\href{#claim-shared.typing.base}{\operatorname{base}(T)}=C \qquad\href{#claim-shared.typing.declarations}{\Sigma(C)}=[f_1:F_1,\ldots,f_n:F_n]\\ \href{#claim-shared.typing.field}{\mathsf{field}_{\Sigma}(T,f_i)}=B_i\quad(1\le i\le n)\\ x_1,\ldots,x_n\text{ distinct and absent from }\operatorname{dom}(\Gamma) \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 displayed fields are ordered as declared. A transferred field can be shared even though the container must be given. As in Given’s binding rules, a field’s interior may have a partial view; only its direct slot status must be known.

Shared/Typing:FieldBindings
inductive FieldBindings (classes : ClassTable) (ty : ValueType) : 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)
Shared/Typing:BindingTyped
inductive BindingTyped (classes : ClassTable) : Environment → Unpacking.Pattern → ValueType → Environment → Prop where
  | variable {environment : Environment} {name : VariableId} {ty : ValueType} :
      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 : ValueType} {name : ClassName}
      {declaration : TypedClass} {fields : List (FieldName × VariableId)}
      {bindings : Environment} :
      before.WellFormed classes → Admissible classes ty →
      ty.permission = .given → ty.nominal.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)

Continuing the Holder example:

let Holder → { item } = h→;
let c = item→;

The unpacking rule empties h, consumes the holder, and binds item: shared Token. The aliases a and b still own the token. The second copies it again, leaving item initialized.

If s: shared Holder, the pattern let Holder → { item } = s→ is rejected. The result is shared even if this happens to be the only reference to that holder. A type grants the access its permission describes; it does not count aliases to recover unique ownership.

Shared/TypingExecutionChecks:unpacking_shared_fields
example : SequenceTyped classes argumentFinal
    [⟨.unpack "Holder" [("item", "item")], .give (.variable "h")⟩,
     ⟨.variable "c", .give (.variable "item")⟩] unpackFinal ∧
    Unpacking.StepsExactly classes.erase
      ⟨State.empty, Unpacking.unpackingProgram⟩ 6 ⟨Unpacking.unpackingFinished, []⟩ ∧
    unpackFinal.lookup "h" = some none ∧
    unpackFinal.lookup "item" = some (some token.shared) ∧
    unpackFinal.lookup "a" = some (some token.shared) ∧
    unpackFinal.lookup "b" = some (some token.shared) ∧
    unpackFinal.lookup "c" = some (some token.shared) ∧
    ¬ Allocated Unpacking.unpackingFinished 1 ∧
    (∀ after, ¬ BindingTyped classes [("s", some holder.shared)]
      (.unpack "Holder" [("item", "item")]) holder.shared after) := by
  refine ⟨unpack_typed, Unpacking.unpacking_execution, by decide, by decide,
    by decide, by decide, by decide, ?_, ?_⟩
  · change (1 : ObjectId) ∉ [0]; decide
  · intro after typed
    cases typed with
    | unpack _ _ given => cases given

Statement typing \(\Sigma;\Gamma\vdash t\Rightarrow\Gamma'\) threads the environment through expression typing and binding typing:

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

Statement-sequence typing \(\Sigma;\Gamma\vdash P\Rightarrow\Gamma_f\) passes each statement’s resulting environment to the next. Here \(P\) is an ordered sequence of statements:

\[ \frac{}{\Sigma;\Gamma\vdash[]\Rightarrow\Gamma} \qquad \frac{\href{#claim-shared.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}. \]
Shared/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 well-typed program has a well-formed typed class table \(\Sigma\) and a statement sequence \(P\) that typechecks from the empty environment:

\[ \exists\Gamma_f.\;\href{#claim-shared.typing.sequences}{\Sigma;\varnothing\vdash P\Rightarrow\Gamma_f}. \]

The final environment describes locals before frame exit and need not be empty. Completion pops the initial frame and collects the heap.

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

Relating types to storage

The runtime mode \(\operatorname{mode}(\pi)\) maps a type permission to the corresponding reference mode:

\[ \begin{aligned} \operatorname{mode}(\mathsf{given})&=\mathsf{unique},\\ \operatorname{mode}(\mathsf{shared})&=\mathsf{shared}. \end{aligned} \]
Shared/TypingViews:Perm.toMode
def Perm.toMode : Perm → Mode
  | .given => .unique
  | .shared => .shared

For \(r=(\kappa,\alpha)\), the reference-path read \(\mathsf{read}_S(r,\rho)\) follows a relative path \(\rho\) from \(\alpha\), accumulating reference modes starting with \(\kappa\), as in refshared.resolution. The empty path returns \(r\) if its object exists. A missing object or field encountered while following the path, or an empty intermediate slot, makes traversal undefined. The final slot may be empty; if occupied, its reference is returned without dereferencing the target.

Shared/TypingPaths:enter
def enter (permission : Mode) (reference : Reference) : Reference :=
  ⟨permission.join reference.mode, reference.object⟩
Shared/TypingPaths:readPath
def readPath (state : State) (reference : Reference) : List FieldName → Option Slot
  | [] => do
      let _ ← state.objects.lookup reference.object
      return some reference
  | field :: rest => do
      let data ← state.objects.lookup reference.object
      let slot ← data.fields.lookup field
      match rest with
      | [] => return slot.map (enter reference.mode)
      | _ :: _ => do
          let target ← slot
          readPath state (enter reference.mode target) rest

Reference realization \(\Sigma;S\models r:T\) says that a reference’s type describes access from that reference. It does not prescribe one view for the object independent of its aliases.

Using the reference-path read, the relation holds for a normalized type \(T=\pi C.A\), when:

  1. The root reference has mode \(\href{#claim-shared.typing.mode}{\operatorname{mode}(\pi)}\) and targets an allocated object of class \(C\).
  2. Every \(\rho\in\href{#claim-shared.typing.observations}{\operatorname{pos}_{\Sigma}(T)}\) reaches an allocated object of its declared class. Every \(\rho\in\href{#claim-shared.typing.observations}{\operatorname{neg}_{\Sigma}(T)}\) reaches an existing empty slot.
  3. Every valid finite path read from \(C\) that reaches an occupied slot from this root, including paths hidden by the view, has effective mode \(\href{#claim-shared.typing.mode}{\operatorname{mode}}(\pi\href{#claim-shared.typing.declared_permission}{\operatorname{decl}_{\Sigma}(C,\rho)})\).

The third condition composes permissions along the whole route. A field declared given inside a shared container may store a unique reference before copying and a shared one afterwards. Both routes have effective shared mode.

Shared/TypingRealization:Satisfies
structure Satisfies (classes : ClassTable) (state : State) (reference : Reference) (ty : ValueType) : Prop where
  mode : reference.mode = ty.permission.toMode
  root : ∃ data, (reference.object, data) ∈ state.objects ∧ data.className = ty.nominal.className
  positive : ∀ path, Pos classes ty path →
    ∃ target data, readPath state reference path = some (some target) ∧
      (target.object, data) ∈ state.objects ∧
      Unique.Typing.classAt classes.nominal ty.nominal.className path = some data.className
  negative : ∀ path, Neg ty path → readPath state reference path = some none
  modes : ∀ path target permission,
    declaredPermission classes ty.nominal.className path = some permission →
    readPath state reference path = some (some target) →
    target.mode = (ty.permission.comp permission).toMode

Storage realization \(\Sigma;\Gamma\models(S;R)\) relates all variables and pending results to their type descriptions.

Here \(S=\langle O,V,\nu\rangle\) is the storage, and \(R\) is an ordered list of pending values \((r:T)\): expression results not yet stored by a binding or constructor. The relation holds when:

  • The structural clauses of refshared.well_formed hold, counting pending references alongside all stored owning occurrences. The additional declaration-kind invariants are not premises of this relation; the operational preservation result establishes them for executions from the empty initial state.
  • Every occupied field targets an object of its declared class, including fields hidden by views.
  • \(\operatorname{dom}(\Gamma)=\operatorname{dom}(V)\). A description \(\Gamma(x)=0\) means \(V(x)=\bot\); a description \(\Gamma(x)=T\) means \(V(x)=r\) with reference realization \(\href{#claim-shared.typing.reference_realization}{\Sigma;S\models r:T}\).
  • Every pending pair \((r:T)\) satisfies \(\href{#claim-shared.typing.reference_realization}{\Sigma;S\models r:T}\).

The table \(\Sigma\) and all types must be well formed. Shared aliases may carry different views; each must describe the actual storage. Hidden references still contribute to ownership and liveness.

Shared/TypingRealization:FieldsMatchClasses
def FieldsMatchClasses (classes : ClassTable) (state : State) : Prop :=
  ∀ parent data field target, (parent, data) ∈ state.objects →
    (field, some target) ∈ data.fields →
    ∃ declaration fieldType targetData,
      (data.className, declaration) ∈ classes ∧
      (field, fieldType) ∈ declaration.fields ∧
      (target.object, targetData) ∈ state.objects ∧ targetData.className = fieldType.className
Shared/TypingRealization:PendingValues
abbrev PendingValues := List (Reference × ValueType)
Shared/TypingRealization:Realizes
structure Realizes (classes : ClassTable) (environment : Environment) (state : State) (pending : PendingValues) : Prop where
  classesWellFormed : classes.WellFormed
  environmentWellFormed : environment.WellFormed classes
  pendingTypes : ∀ reference ty, (reference, 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 →
    ∃ reference, (name, some reference) ∈ state.variables ∧ Satisfies classes state reference ty
  pendingValues : ∀ reference ty, (reference, ty) ∈ pending →
    Satisfies classes state reference ty

For any well-formed \(\Sigma\), if expression typing and storage realization give

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

then an evaluation exists:

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

Every such evaluation satisfies \(\href{#claim-shared.typing.realization}{\Sigma;\Gamma'\models(S';R\mathbin{+\!\!+}[(r:T)])}\), where \(+\!\!+\) appends lists. This includes arbitrary pending results of earlier constructor arguments. A copy preserves existing aliases’ views; a move preserves the types of the other owning roots.

Shared/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)

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.

Shared/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
Shared/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
Shared/Frames:Stuck
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
  ¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after
Shared/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

A well-typed configuration has finished or can take a step:

\[ \href{#claim-shared.typing.configurations}{\Sigma\vdash K:\Gamma_f} \quad\Longrightarrow\quad \href{#claim-shared.typing.finished}{\mathsf{Finished}(K)}\ \lor\ \exists K'.\;\href{#claim-shared.typing.erasure}{\lfloor\Sigma\rfloor}\vdash K\href{#claim-shared.typing.steps}{\longrightarrow_u} K'. \]
Shared/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 final typing:

\[ \frac{\href{#claim-shared.typing.configurations}{\Sigma\vdash K:\Gamma_f} \qquad\href{#claim-shared.typing.erasure}{\lfloor\Sigma\rfloor}\vdash K\href{#claim-shared.typing.steps}{\longrightarrow_u} K'} {\href{#claim-shared.typing.configurations}{\Sigma\vdash K':\Gamma_f}}. \]

The current environment changes when a source is moved or a result is bound. A shared give itself preserves the environment even when the final stored reference changes mode; binding its result then adds a fresh variable.

Shared/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-typed program, no finite execution reaches 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.

Shared/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

Embed every Given declaration as a class, restrict field declarations and types to given, and omit give-share expressions. The typing rules then agree with Given’s rules, including its unpacking extension. Embedding every runtime reference with mode unique preserves and reflects statement transitions and exhaustion of the local statement sequence in this fragment. These selected results concern local-frame observations; program-level steps use the framed correspondence below.

This extends the earlier correspondence, which covers only single-variable bindings, to local operations with unpacking.

Correspondence/UniqueSharedTyping:given_fragment
theorem given_fragment (classes : Unique.Typing.ClassTable) :
    (∀ before value ty after,
      Unique.Typing.ExprTyped classes before value ty after ↔
        Shared.Typing.ExprTyped (embedClasses classes) (embedEnvironment before)
          (embedValue value) (embedType ty) (embedEnvironment after)) ∧
    (∀ before pattern ty after,
      Unique.Typing.BindingTyped classes before pattern ty after ↔
        Shared.Typing.BindingTyped (embedClasses classes) (embedEnvironment before)
          (Unpacking.embedPattern pattern) (embedType ty) (embedEnvironment after)) ∧
    (∀ before statement after,
      Unique.Typing.StatementTyped classes before statement after ↔
        Shared.Typing.StatementTyped (embedClasses classes) (embedEnvironment before)
          (Unpacking.embedStatement statement) (embedEnvironment after)) ∧
    (∀ before statements after,
      Unique.Typing.SequenceTyped classes before statements after ↔
        Shared.Typing.SequenceTyped (embedClasses classes) (embedEnvironment before)
          (statements.map Unpacking.embedStatement) (embedEnvironment after)) ∧
    (∀ statements, Unique.Typing.ProgramTyped classes statements ↔
      Shared.Typing.ProgramTyped (embedClasses classes) (statements.map Unpacking.embedStatement)) ∧
    (∀ before after,
      Shared.Unpacking.Step (embedClasses classes).erase (Unpacking.embedConfiguration before) after ↔
        ∃ successor, Unique.Unpacking.Step classes.erase before successor ∧
          after = Unpacking.embedConfiguration successor) ∧
    (∀ before after,
      Shared.Unpacking.Steps (embedClasses classes).erase (Unpacking.embedConfiguration before) after ↔
        ∃ successor, Unique.Unpacking.Steps classes.erase before successor ∧
          after = Unpacking.embedConfiguration successor) ∧
    (∀ configuration, (Unpacking.embedConfiguration configuration).finished ↔ configuration.finished) ∧
    (∀ configuration,
      (∃ final, Shared.Unpacking.Steps (embedClasses classes).erase
        (Unpacking.embedConfiguration configuration) final ∧ final.finished) ↔
      (∃ final, Unique.Unpacking.Steps classes.erase configuration final ∧ final.finished)) := by
  refine ⟨fun _ _ _ _ => expression_correspondence,
    fun _ _ _ _ => binding_correspondence, fun _ _ _ => statement_correspondence,
    fun _ _ _ => sequence_correspondence, program_correspondence classes, ?_, ?_,
    Unpacking.finished_correspondence, ?_⟩
  · intro before after
    simpa using (Unpacking.step_correspondence (classes := classes.erase)
      (before := before) (after := after))
  · intro before after
    simpa using (Unpacking.steps_correspondence (classes := classes.erase)
      (before := before) (after := after))
  · intro configuration
    simpa using (Unpacking.completion_correspondence (classes := classes.erase) configuration)

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.

Shared/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 _))⟩

The program machines with unpacking also preserve and reflect every step of the all-given fragment. From an embedded Given configuration, every Shared successor is the embedding of a Given successor, and every Given successor has that Shared step. This includes eager collection and initial-frame exit, not just local statement operations.

Correspondence/UniqueSharedFrames:pattern_step_correspondence
theorem pattern_step_correspondence :
    Shared.Framed.Step (Shared.Framed.patternOperation (embedClasses classes))
      (embed Unpacking.embedStatement before) after ↔
    ∃ successor, Unique.Framed.Step (Unique.Framed.patternOperation classes) before successor ∧
      after = embed Unpacking.embedStatement successor := by
  constructor
  · apply step_backward Unpacking.embedStatement
    intro state code next rest step
    obtain ⟨successor, original, same⟩ := Unpacking.step_backward (before := ⟨state, code⟩) (after := ⟨next, rest⟩) step
    exact ⟨successor.state, successor.code, original, congrArg Shared.Unpacking.Configuration.state same,
      by simpa [Unpacking.embedConfiguration] using congrArg Shared.Unpacking.Configuration.code same⟩
  · rintro ⟨successor, step, rfl⟩
    exact step_forward Unpacking.embedStatement (fun state code after rest step => Unpacking.step_forward
      (before := ⟨state, code⟩) (after := ⟨after, rest⟩) step) step