Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Caller storage footprints for reusable mutable calls

Definition
Algo2LeanLib_Footprint

by lunjia · Oct 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsdata-structuresrunning-timetextbook

Heap.Footprint before after sequences objects collections records monotone allocation and preservation of every previously allocated location outside the listed writable references, together with the required object/collection shape guarantees. An empty writable footprint preserves every location allocated before the call while allowing fresh output/internal allocations.

Kruskal's public call has an empty footprint. Union-find methods list only their parent/rank arrays, and the scan additionally lists its chosen-flag array. These distinctions let clients compose mutations without assuming that entire heaps remain identical.

<!-- algo2lean-provenance-v0.1.4 -->

Algo2Lean provenance and reproduction. These definitions target Algo2Lean v0.1.4, using the compiler source at public commit 0f79d5e4242e6477531c9ee4410409f5b1c92f76, and Lean 4.33.1. The versioned compiler location is Algo2Lean v0.1.4. Compile all supplied .algo files and imports to reproduce the raw generated definitions. Release publication and exact website parity require their separately recorded checks; this metadata alone does not assert them. Prove2Me imports and declaration packaging are mechanically adapted, with original hashes, compiler-reported source ranges, and adaptations recorded in transplant provenance. Exact reproduction does not prove the compiler correct.

Definition code
import Definitions.Def_Algo2LeanLib_HeapFrame

set_option autoImplicit true
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true



set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true

namespace Algo2LeanGenerated

/-- Allocation-aware framing. Every previously allocated location outside the
    listed footprint keeps its contents; all existing object and collection
    type tags survive. Fresh locations may be allocated and initialized.
    Clocks have a separate contract and are intentionally unconstrained here. -/
structure Heap.Footprint (before after : Heap) (sequences : List SeqRef)
    (objects : List ObjectRef) (collections : List CollectionRef) : Prop where
  nextRef : before.nextRef ≤ after.nextRef
  nextObject : before.nextObject ≤ after.nextObject
  nextCollection : before.nextCollection ≤ after.nextCollection
  classes : ∀ ref, ref < before.nextObject → after.objectClass ref = before.objectClass ref
  types : ∀ ref, ref < before.nextCollection → after.sequenceType ref = before.sequenceType ref
  otherSequences : ∀ ref, ref < before.nextRef → ref ∉ sequences → after.store ref = before.store ref
  otherObjects : ∀ ref, ref < before.nextObject → ref ∉ objects → after.objects ref = before.objects ref
  otherCollections : ∀ ref, ref < before.nextCollection → ref ∉ collections →
    after.collections ref = before.collections ref

namespace Heap.Footprint

variable {before middle after : Heap} {sequences : List SeqRef}
  {objects : List ObjectRef} {collections : List CollectionRef}

theorem refl (heap : Heap) (sequences : List SeqRef) (objects : List ObjectRef)
    (collections : List CollectionRef) : heap.Footprint heap sequences objects collections :=
  ⟨Nat.le_refl _, Nat.le_refl _, Nat.le_refl _, fun _ _ => rfl,
    fun _ _ => rfl, fun _ _ _ => rfl, fun _ _ _ => rfl, fun _ _ _ => rfl⟩

theorem trans (first : before.Footprint middle sequences objects collections)
    (second : middle.Footprint after sequences objects collections) :
    before.Footprint after sequences objects collections :=
  ⟨Nat.le_trans first.nextRef second.nextRef,
    Nat.le_trans first.nextObject second.nextObject,
    Nat.le_trans first.nextCollection second.nextCollection,
    fun ref old => (second.classes ref (Nat.lt_of_lt_of_le old first.nextObject)).trans
      (first.classes ref old),
    fun ref old => (second.types ref (Nat.lt_of_lt_of_le old first.nextCollection)).trans
      (first.types ref old),
    fun ref old outside =>
      (second.otherSequences ref (Nat.lt_of_lt_of_le old first.nextRef) outside).trans
        (first.otherSequences ref old outside),
    fun ref old outside =>
      (second.otherObjects ref (Nat.lt_of_lt_of_le old first.nextObject) outside).trans
        (first.otherObjects ref old outside),
    fun ref old outside =>
      (second.otherCollections ref (Nat.lt_of_lt_of_le old first.nextCollection) outside).trans
        (first.otherCollections ref old outside)⟩

/-- A callee may mutate private storage created after a caller snapshot while
    preserving every location that already existed in that snapshot. -/
theorem trans_fresh {caller : Heap}
    (preserved : caller.Footprint before [] [] [])
    (changed : before.Footprint after sequences objects collections)
    (freshSequences : ∀ ref ∈ sequences, caller.nextRef ≤ ref)
    (freshObjects : ∀ ref ∈ objects, caller.nextObject ≤ ref)
    (freshCollections : ∀ ref ∈ collections, caller.nextCollection ≤ ref) :
    caller.Footprint after [] [] [] := by
  refine ⟨Nat.le_trans preserved.nextRef changed.nextRef,
    Nat.le_trans preserved.nextObject changed.nextObject,
    Nat.le_trans preserved.nextCollection changed.nextCollection, ?_, ?_, ?_, ?_, ?_⟩
  · intro ref old
    exact (changed.classes ref (Nat.lt_of_lt_of_le old preserved.nextObject)).trans
      (preserved.classes ref old)
  · intro ref old
    exact (changed.types ref (Nat.lt_of_lt_of_le old preserved.nextCollection)).trans
      (preserved.types ref old)
  · intro ref old outside
    have absent : ref ∉ sequences := by
      intro member
      have fresh := freshSequences ref member
      omega
    exact (changed.otherSequences ref (Nat.lt_of_lt_of_le old preserved.nextRef) absent).trans
      (preserved.otherSequences ref old outside)
  · intro ref old outside
    have absent : ref ∉ objects := by
      intro member
      have fresh := freshObjects ref member
      omega
    exact (changed.otherObjects ref (Nat.lt_of_lt_of_le old preserved.nextObject) absent).trans
      (preserved.otherObjects ref old outside)
  · intro ref old outside
    have absent : ref ∉ collections := by
      intro member
      have fresh := freshCollections ref member
      omega
    exact (changed.otherCollections ref (Nat.lt_of_lt_of_le old preserved.nextCollection) absent).trans
      (preserved.otherCollections ref old outside)

/-- A caller may reserve more locations than a callee actually changes. -/
theorem weaken (frame : before.Footprint after sequences objects collections)
    {moreSequences : List SeqRef} {moreObjects : List ObjectRef}
    {moreCollections : List CollectionRef}
    (seqs : ∀ ref ∈ sequences, ref ∈ moreSequences)
    (objs : ∀ ref ∈ objects, ref ∈ moreObjects)
    (colls : ∀ ref ∈ collections, ref ∈ moreCollections) :
    before.Footprint after moreSequences moreObjects moreCollections :=
  ⟨frame.nextRef, frame.nextObject, frame.nextCollection, frame.classes, frame.types,
    fun ref old outside => frame.otherSequences ref old (fun member => outside (seqs ref member)),
    fun ref old outside => frame.otherObjects ref old (fun member => outside (objs ref member)),
    fun ref old outside => frame.otherCollections ref old (fun member => outside (colls ref member))⟩

theorem tick (frame : before.Footprint after sequences objects collections)
    (clock : String) (amount : Nat := 1) :
    before.Footprint (after.tick clock amount) sequences objects collections :=
  ⟨frame.nextRef, frame.nextObject, frame.nextCollection, frame.classes, frame.types,
    frame.otherSequences, frame.otherObjects, frame.otherCollections⟩

theorem charge (frame : before.Footprint after sequences objects collections) (costs : Clocks) :
    before.Footprint (after.charge costs) sequences objects collections :=
  ⟨frame.nextRef, frame.nextObject, frame.nextCollection, frame.classes, frame.types,
    frame.otherSequences, frame.otherObjects, frame.otherCollections⟩

/-- A write may target owned storage or storage allocated during this segment. -/
theorem write (frame : before.Footprint after sequences objects collections)
    (ref : SeqRef) (index value : Int) (allowed : ref ∈ sequences ∨ before.nextRef ≤ ref) :
    before.Footprint (after.write ref index value) sequences objects collections := by
  refine ⟨frame.nextRef, frame.nextObject, frame.nextCollection, frame.classes, frame.types,
    ?_, frame.otherObjects, frame.otherCollections⟩
  intro other old outside
  have different : other ≠ ref := by
    intro same
    subst other
    rcases allowed with owned | fresh
    · exact outside owned
    · omega
  simpa only [Heap.write, different, false_and, if_false] using frame.otherSequences other old outside

theorem writeField (frame : before.Footprint after sequences objects collections)
    (ref : ObjectRef) (field : String) (value : ObjectValue)
    (allowed : ref ∈ objects ∨ before.nextObject ≤ ref) :
    before.Footprint (after.writeField ref field value) sequences objects collections := by
  refine ⟨frame.nextRef, frame.nextObject, frame.nextCollection, ?_, frame.types,
    frame.otherSequences, ?_, frame.otherCollections⟩
  · intro other old
    rw [Heap.objectClass_writeField]
    exact frame.classes other old
  · intro other old outside
    have different : other ≠ ref := by
      intro same
      subst other
      rcases allowed with owned | fresh
      · exact outside owned
      · omega
    simpa only [Heap.writeField, if_neg different] using frame.otherObjects other old outside

theorem writeElement (frame : before.Footprint after sequences objects collections)
    (ref : CollectionRef) (index : Int) (value : ObjectValue)
    (allowed : ref ∈ collections ∨ before.nextCollection ≤ ref) :
    before.Footprint (after.writeElement ref index value) sequences objects collections := by
  refine ⟨frame.nextRef, frame.nextObject, frame.nextCollection, frame.classes, ?_,
    frame.otherSequences, frame.otherObjects, ?_⟩
  · intro other old
    rw [Heap.sequenceType_writeElement]
    exact frame.types other old
  · intro other old outside
    have different : other ≠ ref := by
      intro same
      subst other
      rcases allowed with owned | fresh
      · exact outside owned
      · omega
    simpa only [Heap.writeElement, if_neg different] using frame.otherCollections other old outside

theorem allocate (frame : before.Footprint after sequences objects collections) (contents : Seq) :
    before.Footprint (after.allocate contents) sequences objects collections := by
  refine ⟨Nat.le_trans frame.nextRef (Nat.le_succ _), frame.nextObject,
    frame.nextCollection, frame.classes, frame.types, ?_, frame.otherObjects, frame.otherCollections⟩
  intro ref old outside
  have different := Nat.ne_of_lt (Nat.lt_of_lt_of_le old frame.nextRef)
  simpa only [Heap.allocate, if_neg different] using frame.otherSequences ref old outside

theorem allocateObject (frame : before.Footprint after sequences objects collections)
    (className : String) :
    before.Footprint (after.allocateObject className) sequences objects collections := by
  refine ⟨frame.nextRef, Nat.le_trans frame.nextObject (Nat.le_succ _),
    frame.nextCollection, ?_, frame.types, frame.otherSequences, ?_, frame.otherCollections⟩
  · intro ref old
    have preserved := Heap.objects_allocateObject_old after className ref
      (Nat.lt_of_lt_of_le old frame.nextObject)
    simpa only [Heap.objectClass, preserved] using frame.classes ref old
  · intro ref old outside
    rw [Heap.objects_allocateObject_old after className ref
      (Nat.lt_of_lt_of_le old frame.nextObject)]
    exact frame.otherObjects ref old outside

theorem allocateSequence (frame : before.Footprint after sequences objects collections)
    (elementType : String) (values : Int → ObjectValue) :
    before.Footprint (after.allocateSequence elementType values) sequences objects collections := by
  refine ⟨frame.nextRef, frame.nextObject, Nat.le_trans frame.nextCollection (Nat.le_succ _),
    frame.classes, ?_, frame.otherSequences, frame.otherObjects, ?_⟩
  · intro ref old
    have preserved := Heap.collections_allocateSequence_old after elementType values ref
      (Nat.lt_of_lt_of_le old frame.nextCollection)
    simpa only [Heap.sequenceType, preserved] using frame.types ref old
  · intro ref old outside
    rw [Heap.collections_allocateSequence_old after elementType values ref
      (Nat.lt_of_lt_of_le old frame.nextCollection)]
    exact frame.otherCollections ref old outside

theorem read (frame : before.Footprint after sequences objects collections)
    (ref : SeqRef) (old : ref < before.nextRef) (outside : ref ∉ sequences) :
    after.read ref = before.read ref := frame.otherSequences ref old outside

theorem readField (frame : before.Footprint after sequences objects collections)
    (ref : ObjectRef) (old : ref < before.nextObject) (outside : ref ∉ objects) (field : String) :
    after.readField ref field = before.readField ref field := by
  simp only [Heap.readField, frame.otherObjects ref old outside]

theorem readElement (frame : before.Footprint after sequences objects collections)
    (ref : CollectionRef) (old : ref < before.nextCollection) (outside : ref ∉ collections)
    (index : Int) : after.readElement ref index = before.readElement ref index := by
  simp only [Heap.readElement, frame.otherCollections ref old outside]

theorem validSequence (frame : before.Footprint after sequences objects collections)
    (ref : CollectionRef) (elementType : String) (valid : before.validSequence ref elementType) :
    after.validSequence ref elementType :=
  ⟨Nat.lt_of_lt_of_le valid.1 frame.nextCollection, (frame.types ref valid.1).trans valid.2⟩

end Heap.Footprint

/-- Existing allocation-free frame contracts can be reused without reproving
    the implementation when a caller accepts an allocation-aware footprint. -/
theorem Heap.Modifies.footprint {before after : Heap} {sequences : List SeqRef}
    {objects : List ObjectRef} (frame : before.Modifies after sequences objects) :
    before.Footprint after sequences objects [] := by
  refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  · exact Nat.le_of_eq frame.nextRef.symm
  · exact Nat.le_of_eq frame.nextObject.symm
  · exact Nat.le_of_eq frame.nextCollection.symm
  · intro ref _
    exact congrFun frame.classes ref
  · intro ref _
    simp only [Heap.sequenceType, frame.collections]
  · intro ref _ outside
    exact frame.otherSequences ref outside
  · intro ref _ outside
    exact frame.otherObjects ref outside
  · intro ref _ _
    exact congrFun frame.collections ref

end Algo2LeanGenerated
Source
https://github.com/lunjiah/algo2lean/blob/0f79d5e4242e6477531c9ee4410409f5b1c92f76/Algo2LeanLib/Footprint.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me