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:
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.
structure TypedClass where
fields : List (FieldName × ClassName)
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
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\).
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]\).
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\).
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\).
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:
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.
inductive Entry where
| positive (path : Path)
| negative (path : Path)
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
structure ViewType where
className : ClassName
entries : List Entry
deriving DecidableEq, BEq, ReflBEq, LawfulBEq, Repr
def ViewType.whole (name : ClassName) : ViewType :=
⟨name, [.positive []]⟩
The base class is \(\operatorname{base}(C.A)=C\).
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.
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
def entriesDisjoint : List Entry → Bool
| [] => true
| entry :: rest =>
rest.all (fun other =>
!entry.path.isPrefixOf other.path && !other.path.isPrefixOf entry.path) &&
entriesDisjoint rest
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 }
| Type | Information available |
|---|---|
Pair | Both 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.
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.
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))
def negative (ty : ViewType) (path : Path) : Bool :=
ty.entries.contains (.negative path)
def Pos (classes : ClassTable) (ty : ViewType) (path : Path) : Prop :=
positive classes ty path = true
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:
A full view may contain empty slots; being full does not mean being fully initialized.
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:
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.
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:
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.
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
def Entry.prepend (initialPath : Path) : Entry → Entry
| .positive path => .positive (initialPath ++ path)
| .negative path => .negative (initialPath ++ path)
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
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 }
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:
Reordering a view’s entries gives the same normalized type. Once normalized, a second pass makes no further change.
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:
This operation does not restore fields that have been moved or hidden.
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:
- Normalize the input type.
- 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\).
- 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:
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.
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]]
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:
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.
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:
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.
abbrev SlotDescription := Option ViewType
abbrev Environment := List (VariableId × SlotDescription)
def Admissible (classes : ClassTable) (ty : ViewType) : Prop :=
ty.WellFormed classes ∧ Normalized classes ty
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
def Environment.lookup (environment : Environment) (name : VariableId) :
Option SlotDescription :=
(environment.find? fun entry => entry.1 == name).map Prod.snd
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:
All other variables keep their descriptions. Taking an absent variable, an empty slot, or an unknown field is undefined.
def splitPlace : Place → VariableId × Path
| .variable name => (name, [])
| .field base name =>
let (root, path) := splitPlace base
(root, path ++ [name])
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:
| Give | Root and relative place | Result type | Updated description of b |
|---|---|---|---|
b→ | \(b,\epsilon\) | Box | 0 |
b.item.left→ | \(b,\mathsf{item.left}\) | Token | Box.{-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.
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:
The Give rule uses the current view of the source:
Construct checks arguments from left to right, passing each updated environment to the next argument:
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:
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.
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
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:
It is undefined if that field is unknown.
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:
An unpacking pattern must name every declared field, and each field’s description must be defined:
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.
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)
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:
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:
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.
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.
| Statement | Updated binding | New bindings |
|---|---|---|
| Construct | — | b: Box |
Give left | b: Box.{-item.left, item.right} | taken: Token |
Give item | b: Box.{-item} | p: Pair.{-left, right} |
| Unpack | p: 0 | left: 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.
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 becauseleftis unknown. It might exist and be initialized at runtime. - From
p: Pair.{-left, right}, givingp→succeeds statically with that same viewed type. It does not produce a wholePair. - 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 hiddenleftfield.
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.
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.
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.
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:
- 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.
- Every occupied object field targets an object of its declared nominal class in \(\Sigma\). This condition applies even to fields hidden by views.
- \(\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}\).
- 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.
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
abbrev PendingValues := List (ObjectId × ViewType)
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.
def Steps (operation : LocalStep Instruction) (before after : Configuration Instruction) : Prop :=
∃ count, StepsExactly operation before count after
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.
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:
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.
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
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
def Stuck (operation : LocalStep Instruction) (configuration : Configuration Instruction) : Prop :=
¬ configuration.finished ∧ ¬ ∃ after, Step operation configuration after
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:
Then an evaluation exists:
Moreover, every such evaluation satisfies:
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.
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:
This is a claim about the operational rules: typing does not add a transition for an otherwise failing operation.
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:
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.
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.
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.
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 _))⟩