Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Graded typing derivations in the positive AARA fragment of Giralf

Definition
Grodin2026_AARADerivations

by kmehltretter82 · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

amortized-analysisprogram-semanticstype-theory

The inductive typing derivations for the terminating positive fragment. A derivation gives a cost and a value on each input environment and is interpreted by a lax Calf homomorphism from its credited context to the result type. The abstract homomorphism preserves the input cost and introduces no new cost.

Definition code
import Definitions.Def_Grodin2026_AARATypes

/-!
# Graded derivations for the positive fragment of Giralf

This module interprets syntax for terminating AARA programs over the positive types of
Grodin, Chu, Li, Hoffmann, and Harper (2026), Sections 5.1–5.2. Linear contexts are
represented by their tensor, with `top` for the empty context. Pure values in the
structural context are represented by Lean values. Computation costs are introduced
by the spend rule and composed by evaluating the immediate subderivations.
-/

namespace Grodin2026.Revised

/-- A derivation of a linear program taking context `Γ` to result type `A` with grade `q`.
Positive sums, tensors and units have their usual linear rules. Linear list elimination
uses a right fold, and quadratic list elimination uses the indexed fold from §5.1.4. -/
inductive AARADerivation : AARAType → AARAType → Nat → Type 1 where
  | var {A : AARAType} (q : Nat) : AARADerivation A A q
  | letBind {Γ₁ Γ₂ A B : AARAType} {q q₁ q₂ : Nat} (h : q₁ + q₂ ≤ q)
      (value : AARADerivation Γ₁ A q₁) (body : AARADerivation (.tensor Γ₂ A) B q₂) :
      AARADerivation (.tensor Γ₁ Γ₂) B q
  | spend {Γ A : AARAType} {q p q' : Nat} (h : p + q' ≤ q)
      (body : AARADerivation Γ A q') : AARADerivation Γ A q
  | weaken {Γ A : AARAType} {q q' : Nat} (h : q' ≤ q)
      (body : AARADerivation Γ A q') : AARADerivation Γ A q
  | ret {X : Type} (x : X) (q : Nat) : AARADerivation .top (.free X) q
  | read {X : Type} {Γ A : AARAType} {q : Nat}
      (body : X → AARADerivation Γ A q) : AARADerivation (.tensor (.free X) Γ) A q
  | tensorIntro {Γ₁ Γ₂ A B : AARAType} {q q₁ q₂ : Nat} (h : q₁ + q₂ ≤ q)
      (left : AARADerivation Γ₁ A q₁) (right : AARADerivation Γ₂ B q₂) :
      AARADerivation (.tensor Γ₁ Γ₂) (.tensor A B) q
  | swap {Γ₁ Γ₂ A : AARAType} {q : Nat} (body : AARADerivation (.tensor Γ₂ Γ₁) A q) :
      AARADerivation (.tensor Γ₁ Γ₂) A q
  | assocLeft {Γ₁ Γ₂ Γ₃ A : AARAType} {q : Nat}
      (body : AARADerivation (.tensor (.tensor Γ₁ Γ₂) Γ₃) A q) :
      AARADerivation (.tensor Γ₁ (.tensor Γ₂ Γ₃)) A q
  | assocRight {Γ₁ Γ₂ Γ₃ A : AARAType} {q : Nat}
      (body : AARADerivation (.tensor Γ₁ (.tensor Γ₂ Γ₃)) A q) :
      AARADerivation (.tensor (.tensor Γ₁ Γ₂) Γ₃) A q
  | unitLeft {Γ A : AARAType} {q : Nat} (body : AARADerivation Γ A q) :
      AARADerivation (.tensor .top Γ) A q
  | insertUnitLeft {Γ A : AARAType} {q : Nat} (body : AARADerivation (.tensor .top Γ) A q) :
      AARADerivation Γ A q
  | inl {Γ A B : AARAType} {q : Nat} (body : AARADerivation Γ A q) :
      AARADerivation Γ (.sum A B) q
  | inr {Γ A B : AARAType} {q : Nat} (body : AARADerivation Γ B q) :
      AARADerivation Γ (.sum A B) q
  | caseSum {Γ A B C : AARAType} {q : Nat}
      (left : AARADerivation (.tensor Γ A) C q) (right : AARADerivation (.tensor Γ B) C q) :
      AARADerivation (.tensor Γ (.sum A B)) C q
  | store {Γ A : AARAType} {q p q' : Nat} (h : p + q' ≤ q)
      (body : AARADerivation Γ A q') : AARADerivation Γ (.credit p A) q
  | release {Γ₁ Γ₂ A B : AARAType} {q p q₁ q₂ : Nat} (h : q₁ + q₂ ≤ q)
      (value : AARADerivation Γ₁ (.credit p A) q₁)
      (body : AARADerivation (.tensor Γ₂ A) B (p + q₂)) :
      AARADerivation (.tensor Γ₁ Γ₂) B q
  | nil1 {A : AARAType} (p q : Nat) : AARADerivation .top (.clist1 p A) q
  | cons1 {Γ₁ Γ₂ A : AARAType} {q p q₁ q₂ : Nat} (h : p + q₁ + q₂ ≤ q)
      (head : AARADerivation Γ₁ A q₁) (tail : AARADerivation Γ₂ (.clist1 p A) q₂) :
      AARADerivation (.tensor Γ₁ Γ₂) (.clist1 p A) q
  | fold1 {Γ A B : AARAType} {q p : Nat} (base : AARADerivation .top B 0)
      (step : AARADerivation (.tensor A B) B p) (list : AARADerivation Γ (.clist1 p A) q) :
      AARADerivation Γ B q
  | nil2 {A : AARAType} (p₁ p₂ q : Nat) : AARADerivation .top (.clist2 p₁ p₂ A) q
  | cons2 {Γ₁ Γ₂ A : AARAType} {q p₁ p₂ q₁ q₂ : Nat} (h : p₁ + q₁ + q₂ ≤ q)
      (head : AARADerivation Γ₁ A q₁)
      (tail : AARADerivation Γ₂ (.clist2 (p₂ + p₁) p₂ A) q₂) :
      AARADerivation (.tensor Γ₁ Γ₂) (.clist2 p₁ p₂ A) q
  | fold2 {Γ A : AARAType} {B : Nat → AARAType} {q p₁ p₂ : Nat}
      (base : (r : Nat) → AARADerivation .top (B r) 0)
      (step : (r : Nat) → AARADerivation (.tensor A (B (p₂ + r))) (B r) r)
      (list : AARADerivation Γ (.clist2 p₁ p₂ A) q) : AARADerivation Γ (B p₁) q

namespace AARADerivation

private def evalListFold {X : Type} {Y : Nat → Type} (next : Nat → Nat)
    (base : (r : Nat) → Nat × Y r) (step : (r : Nat) → X × Y (next r) → Nat × Y r) :
    (r : Nat) → List X → Nat × Y r
  | r, [] => base r
  | r, x :: xs =>
      let tail := evalListFold next base step (next r) xs
      let result := step r (x, tail.2)
      (tail.1 + result.1, result.2)

/-- Evaluate a derivation on a linear environment, returning concrete cost and value. -/
def eval {Γ A : AARAType} {q : Nat} (d : AARADerivation Γ A q) :
    aaraValues Γ → Nat × aaraValues A :=
  match d with
  | .var _ => fun x ↦ (0, x)
  | .letBind _ value body => fun (x, y) ↦
      let v := value.eval x
      let result := body.eval (y, v.2)
      (v.1 + result.1, result.2)
  | .spend (p := p) _ body => fun x ↦
      let result := body.eval x
      (p + result.1, result.2)
  | .weaken _ body => body.eval
  | .ret x _ => fun _ ↦ (0, x)
  | .read body => fun (x, δ) ↦ (body x).eval δ
  | .tensorIntro _ left right => fun (x, y) ↦
      let a := left.eval x
      let b := right.eval y
      (a.1 + b.1, (a.2, b.2))
  | .swap body => fun (x, y) ↦ body.eval (y, x)
  | .assocLeft body => fun (x, y, z) ↦ body.eval ((x, y), z)
  | .assocRight body => fun ((x, y), z) ↦ body.eval (x, y, z)
  | .unitLeft body => fun (_, x) ↦ body.eval x
  | .insertUnitLeft body => fun x ↦ body.eval (PUnit.unit, x)
  | .inl body => fun x ↦
      let result := body.eval x
      (result.1, .inl result.2)
  | .inr body => fun x ↦
      let result := body.eval x
      (result.1, .inr result.2)
  | .caseSum left right => fun (δ, s) ↦
      match s with
      | .inl x => left.eval (δ, x)
      | .inr y => right.eval (δ, y)
  | .store _ body => body.eval
  | .release _ value body => fun (x, y) ↦
      let v := value.eval x
      let result := body.eval (y, v.2)
      (v.1 + result.1, result.2)
  | .nil1 _ _ => fun _ ↦ (0, [])
  | .cons1 _ head tail => fun (x, y) ↦
      let h := head.eval x
      let t := tail.eval y
      (h.1 + t.1, h.2 :: t.2)
  | .fold1 (B := B) (p := p) base step list => fun x ↦
      let v := list.eval x
      let result := evalListFold (Y := fun _ ↦ aaraValues B) id
        (fun _ ↦ base.eval PUnit.unit) (fun _ ↦ step.eval) p v.2
      (v.1 + result.1, result.2)
  | .nil2 _ _ _ => fun _ ↦ (0, [])
  | .cons2 _ head tail => fun (x, y) ↦
      let h := head.eval x
      let t := tail.eval y
      (h.1 + t.1, h.2 :: t.2)
  | .fold2 (B := B) (p₁ := p₁) (p₂ := p₂) base step list => fun x ↦
      let v := list.eval x
      let result := evalListFold (Y := fun r ↦ aaraValues (B r)) (p₂ + ·)
        (fun r ↦ (base r).eval PUnit.unit) (fun r ↦ (step r).eval) p₁ v.2
      (v.1 + result.1, result.2)
termination_by structural d

private theorem evalListFold_bound {X : Type} {Y : Nat → Type} (next : Nat → Nat)
    (base : (r : Nat) → Nat × Y r) (step : (r : Nat) → X × Y (next r) → Nat × Y r)
    (credit : Nat → Nat) (inputPotential : X → Nat) (listPotential : Nat → List X → Nat)
    (outputPotential : (r : Nat) → Y r → Nat)
    (hCons : ∀ r x xs, listPotential r (x :: xs) =
      credit r + inputPotential x + listPotential (next r) xs)
    (hBase : ∀ r, (base r).1 + outputPotential r (base r).2 ≤ listPotential r [])
    (hStep : ∀ r x y, (step r (x, y)).1 + outputPotential r (step r (x, y)).2 ≤
      inputPotential x + outputPotential (next r) y + credit r)
    (r : Nat) (xs : List X) :
    (evalListFold next base step r xs).1 +
      outputPotential r (evalListFold next base step r xs).2 ≤ listPotential r xs := by
  induction xs generalizing r with
  | nil => exact hBase r
  | cons x xs ih =>
      rw [hCons]
      let tail := evalListFold next base step (next r) xs
      change tail.1 + (step r (x, tail.2)).1 + outputPotential r (step r (x, tail.2)).2 ≤ _
      have hTail : tail.1 + outputPotential (next r) tail.2 ≤ listPotential (next r) xs :=
        ih (next r)
      have hHead := hStep r x tail.2
      omega

/-- Every rule preserves the available credits, accounting for the evaluated subterms and
for the transfer of credits into and out of the value. -/
private theorem eval_bound {Γ A : AARAType} {q : Nat} (d : AARADerivation Γ A q)
    (x : aaraValues Γ) : (d.eval x).1 + aaraPotential A (d.eval x).2 ≤ aaraPotential Γ x + q := by
  induction d with
  | var => simp [eval]
  | letBind _ value body ihValue ihBody =>
      rcases x with ⟨x, y⟩
      have hValue := ihValue x
      have hBody := ihBody (y, (value.eval x).2)
      simp only [eval, aaraPotential] at hBody ⊢
      omega
  | spend _ body ih =>
      have hBody := ih x
      simp only [eval]
      omega
  | weaken h _ ih => exact Nat.le_trans (ih x) (Nat.add_le_add_left h _)
  | ret => simp [eval, aaraPotential]
  | read body ih =>
      rcases x with ⟨x, y⟩
      simpa only [eval, aaraPotential, Nat.zero_add] using ih x y
  | tensorIntro _ _ _ ihLeft ihRight =>
      rcases x with ⟨x, y⟩
      have hLeft := ihLeft x
      have hRight := ihRight y
      simp only [eval, aaraPotential]
      omega
  | swap _ ih =>
      rcases x with ⟨x, y⟩
      have h := ih (y, x)
      simp only [eval, aaraPotential] at h ⊢
      omega
  | assocLeft _ ih =>
      rcases x with ⟨x, y, z⟩
      simpa only [eval, aaraPotential, Nat.add_assoc] using ih ((x, y), z)
  | assocRight _ ih =>
      rcases x with ⟨⟨x, y⟩, z⟩
      simpa only [eval, aaraPotential, Nat.add_assoc] using ih (x, y, z)
  | unitLeft _ ih =>
      rcases x with ⟨_, x⟩
      simpa only [eval, aaraPotential, Nat.zero_add] using ih x
  | insertUnitLeft _ ih =>
      simpa only [eval, aaraPotential, Nat.zero_add] using ih (PUnit.unit, x)
  | inl _ ih => simpa only [eval, aaraPotential] using ih x
  | inr _ ih => simpa only [eval, aaraPotential] using ih x
  | caseSum _ _ ihLeft ihRight =>
      rcases x with ⟨δ, a | b⟩
      · simpa only [eval, aaraPotential] using ihLeft (δ, a)
      · simpa only [eval, aaraPotential] using ihRight (δ, b)
  | store _ body ih =>
      have hBody := ih x
      simp only [eval, aaraPotential]
      omega
  | release _ value body ihValue ihBody =>
      rcases x with ⟨x, y⟩
      have hValue := ihValue x
      have hBody := ihBody (y, (value.eval x).2)
      simp only [aaraPotential] at hValue hBody
      simp only [eval, aaraPotential]
      omega
  | nil1 => simp [eval, aaraPotential, listPotentialSum]
  | cons1 _ _ _ ihHead ihTail =>
      rcases x with ⟨x, y⟩
      have hHead := ihHead x
      have hTail := ihTail y
      simp only [eval]
      erw [aaraPotential_clist1_cons]
      simp only [aaraPotential] at hTail ⊢
      omega
  | @fold1 Γ A B q p base step list ihBase ihStep ihList =>
      have hFold := evalListFold_bound (Y := fun _ ↦ aaraValues B) id
        (fun _ ↦ base.eval PUnit.unit) (fun _ ↦ step.eval) (fun _ ↦ p) (aaraPotential A)
        (fun _ ↦ aaraPotential (.clist1 p A)) (fun _ ↦ aaraPotential B)
        (fun _ y ys ↦ aaraPotential_clist1_cons p A y ys)
        (fun _ ↦ by simpa [aaraPotential, listPotentialSum] using ihBase PUnit.unit)
        (fun _ y z ↦ by simpa only [aaraPotential] using ihStep (y, z)) p (list.eval x).2
      have hList := ihList x
      simp only [eval]
      omega
  | nil2 => simp [eval, aaraPotential, listPotentialSum, binom2]
  | cons2 _ _ _ ihHead ihTail =>
      rcases x with ⟨x, y⟩
      have hHead := ihHead x
      have hTail := ihTail y
      simp only [eval]
      erw [aaraPotential_clist2_cons]
      simp only [aaraPotential] at hTail ⊢
      omega
  | @fold2 Γ A B q p₁ p₂ base step list ihBase ihStep ihList =>
      have hFold := evalListFold_bound (Y := fun r ↦ aaraValues (B r)) (p₂ + ·)
        (fun r ↦ (base r).eval PUnit.unit) (fun r ↦ (step r).eval) (fun r ↦ r) (aaraPotential A)
        (fun r ↦ aaraPotential (.clist2 r p₂ A)) (fun r ↦ aaraPotential (B r))
        (fun r y ys ↦ aaraPotential_clist2_cons r p₂ A y ys)
        (fun r ↦ by simpa [aaraPotential, listPotentialSum, binom2] using ihBase r PUnit.unit)
        (fun r y z ↦ by simpa only [aaraPotential] using ihStep r (y, z)) p₁ (list.eval x).2
      have hList := ihList x
      simp only [eval]
      omega

private def evalFreeHom {X Y : Type} (f : X → Nat × Y) :
    CostHom (FreeCostAlg X) (FreeCostAlg Y) where
  fn := fun (c, x) ↦ (c + (f x).1, (f x).2)
  map_charge := fun c (c', x) ↦ Prod.ext (Nat.add_assoc c c' (f x).1) rfl
  mono := by
    rintro ⟨a, x⟩ ⟨b, y⟩ ⟨h, rfl⟩
    exact ⟨Nat.add_le_add_right h _, rfl⟩

/-- Interpret a derivation as a Calf program from its credited tensor context.
Its abstract homomorphism runs the same program on values with zero added cost. -/
def interpret {Γ A : AARAType} {q : Nat} (d : AARADerivation Γ A q) :
    LaxCompHom (CreditComp q (interpPositiveAARA Γ)) (interpPositiveAARA A) where
  hom_top := evalFreeHom d.eval
  hom_abs := evalFreeHom (fun x ↦ (0, (d.eval x).2))
  lax_comm := by
    rintro ⟨c, x⟩
    change (FreeCostAlg (aaraValues A)).le
      ((interpPositiveAARA A).alpha.fn (c + (d.eval x).1, (d.eval x).2))
      ((q + ((interpPositiveAARA Γ).alpha.fn (c, x)).1) + 0,
        (d.eval ((interpPositiveAARA Γ).alpha.fn (c, x)).2).2)
    rw [interpPositiveAARA_alpha, interpPositiveAARA_alpha]
    have h := eval_bound d x
    exact ⟨by dsimp; omega, rfl⟩

@[simp]
theorem interpret_top_fn {Γ A : AARAType} {q : Nat} (d : AARADerivation Γ A q)
    (c : Nat) (x : aaraValues Γ) :
    d.interpret.hom_top.fn (c, x) = (c + (d.eval x).1, (d.eval x).2) := rfl

@[simp]
theorem interpret_abs_fn {Γ A : AARAType} {q : Nat} (d : AARADerivation Γ A q)
    (c : Nat) (x : aaraValues Γ) : d.interpret.hom_abs.fn (c, x) = (c, (d.eval x).2) := rfl

end AARADerivation
end Grodin2026.Revised
Source
Grodin, Chu, Li, Hoffmann, and Harper (2026), Potential Functions as Types, §§5.1–5.2. https://arxiv.org/abs/2607.08547v2
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)

Typing derivations. Write Γ→qA\Gamma\xrightarrow{q}AΓq​A for a derivation with input context type Γ\GammaΓ, result type AAA, and grade q∈Nq\in\mathbb Nq∈N. Context and result types range over the grammar with free types F(X)F(X)F(X) for arbitrary types XXX, the unit 1\mathbf 11, tensors ⊗\otimes⊗, sums ⊕\oplus⊕, credited types Cp(A)C_p(A)Cp​(A), and list types Lp(A)L_p(A)Lp​(A) and Qp1,p2(A)Q_{p_1,p_2}(A)Qp1​,p2​​(A). All grades and credit parameters are natural numbers, including zero. The family is generated by the following rules. A variable gives A→qAA\xrightarrow{q}AAq​A at any grade. Let-binding takes Γ1→q1A\Gamma_1\xrightarrow{q_1}AΓ1​q1​​A and Γ2⊗A→q2B\Gamma_2\otimes A\xrightarrow{q_2}BΓ2​⊗Aq2​​B to Γ1⊗Γ2→qB\Gamma_1\otimes\Gamma_2\xrightarrow{q}BΓ1​⊗Γ2​q​B if q1+q2≤qq_1+q_2\le qq1​+q2​≤q. Spending ppp takes Γ→q′A\Gamma\xrightarrow{q'}AΓq′​A to Γ→qA\Gamma\xrightarrow{q}AΓq​A if p+q′≤qp+q'\le qp+q′≤q, and weakening does so if q′≤qq'\le qq′≤q. Returning any chosen x∈Xx\in Xx∈X gives 1→qF(X)\mathbf 1\xrightarrow{q}F(X)1q​F(X) at any grade. Reading takes a family of derivations Γ→qA\Gamma\xrightarrow{q}AΓq​A indexed by x∈Xx\in Xx∈X and gives F(X)⊗Γ→qAF(X)\otimes\Gamma\xrightarrow{q}AF(X)⊗Γq​A. Tensor introduction takes Γ1→q1A\Gamma_1\xrightarrow{q_1}AΓ1​q1​​A and Γ2→q2B\Gamma_2\xrightarrow{q_2}BΓ2​q2​​B to Γ1⊗Γ2→qA⊗B\Gamma_1\otimes\Gamma_2\xrightarrow{q}A\otimes BΓ1​⊗Γ2​q​A⊗B if q1+q2≤qq_1+q_2\le qq1​+q2​≤q. At fixed grade and result type, a derivation’s input can be changed from Γ2⊗Γ1\Gamma_2\otimes\Gamma_1Γ2​⊗Γ1​ to Γ1⊗Γ2\Gamma_1\otimes\Gamma_2Γ1​⊗Γ2​, between (Γ1⊗Γ2)⊗Γ3(\Gamma_1\otimes\Gamma_2)\otimes\Gamma_3(Γ1​⊗Γ2​)⊗Γ3​ and Γ1⊗(Γ2⊗Γ3)\Gamma_1\otimes(\Gamma_2\otimes\Gamma_3)Γ1​⊗(Γ2​⊗Γ3​) in either direction, or between Γ\GammaΓ and 1⊗Γ\mathbf 1\otimes\Gamma1⊗Γ in either direction. At fixed input and grade, either summand can be injected into A⊕BA\oplus BA⊕B. Sum elimination takes premises Γ⊗A→qC\Gamma\otimes A\xrightarrow{q}CΓ⊗Aq​C and Γ⊗B→qC\Gamma\otimes B\xrightarrow{q}CΓ⊗Bq​C to Γ⊗(A⊕B)→qC\Gamma\otimes(A\oplus B)\xrightarrow{q}CΓ⊗(A⊕B)q​C. Storing ppp takes Γ→q′A\Gamma\xrightarrow{q'}AΓq′​A to Γ→qCp(A)\Gamma\xrightarrow{q}C_p(A)Γq​Cp​(A) if p+q′≤qp+q'\le qp+q′≤q. Releasing takes Γ1→q1Cp(A)\Gamma_1\xrightarrow{q_1}C_p(A)Γ1​q1​​Cp​(A) and Γ2⊗A→p+q2B\Gamma_2\otimes A\xrightarrow{p+q_2}BΓ2​⊗Ap+q2​​B to Γ1⊗Γ2→qB\Gamma_1\otimes\Gamma_2\xrightarrow{q}BΓ1​⊗Γ2​q​B if q1+q2≤qq_1+q_2\le qq1​+q2​≤q. An empty list of either kind has input 1\mathbf 11 and arbitrary grade and credit parameters. A cons for Lp(A)L_p(A)Lp​(A) takes Γ1→q1A\Gamma_1\xrightarrow{q_1}AΓ1​q1​​A and Γ2→q2Lp(A)\Gamma_2\xrightarrow{q_2}L_p(A)Γ2​q2​​Lp​(A) to Γ1⊗Γ2→qLp(A)\Gamma_1\otimes\Gamma_2\xrightarrow{q}L_p(A)Γ1​⊗Γ2​q​Lp​(A) if p+q1+q2≤qp+q_1+q_2\le qp+q1​+q2​≤q. A cons for Qp1,p2(A)Q_{p_1,p_2}(A)Qp1​,p2​​(A) instead takes the tail from Γ2→q2Qp2+p1,p2(A)\Gamma_2\xrightarrow{q_2}Q_{p_2+p_1,p_2}(A)Γ2​q2​​Qp2​+p1​,p2​​(A), gives Γ1⊗Γ2→qQp1,p2(A)\Gamma_1\otimes\Gamma_2\xrightarrow{q}Q_{p_1,p_2}(A)Γ1​⊗Γ2​q​Qp1​,p2​​(A), and requires p1+q1+q2≤qp_1+q_1+q_2\le qp1​+q1​+q2​≤q. The Lp(A)L_p(A)Lp​(A) fold takes a list derivation Γ→qLp(A)\Gamma\xrightarrow{q}L_p(A)Γq​Lp​(A), a base 1→0B\mathbf 1\xrightarrow{0}B10​B, and a step A⊗B→pBA\otimes B\xrightarrow{p}BA⊗Bp​B, and gives Γ→qB\Gamma\xrightarrow{q}BΓq​B. The Qp1,p2(A)Q_{p_1,p_2}(A)Qp1​,p2​​(A) fold takes a list derivation Γ→qQp1,p2(A)\Gamma\xrightarrow{q}Q_{p_1,p_2}(A)Γq​Qp1​,p2​​(A) and, for any type family B(r)B(r)B(r) indexed by r∈Nr\in\mathbb Nr∈N, a base 1→0B(r)\mathbf 1\xrightarrow{0}B(r)10​B(r) and a step A⊗B(p2+r)→rB(r)A\otimes B(p_2+r)\xrightarrow{r}B(r)A⊗B(p2​+r)r​B(r) for every rrr. The result is Γ→qB(p1)\Gamma\xrightarrow{q}B(p_1)Γq​B(p1​).

Evaluation. For any context and result types Γ,A\Gamma,AΓ,A, grade q∈Nq\in\mathbb Nq∈N, and derivation ddd from Γ\GammaΓ to AAA at grade qqq, evaluation EdE_dEd​ maps each x∈V(Γ)x\in V(\Gamma)x∈V(Γ) to a pair (k,y)∈N×V(A)(k,y)\in\mathbb N\times V(A)(k,y)∈N×V(A) of cost and result. The value type VVV assigns XXX to F(X)F(X)F(X), a singleton to the unit, products to tensors, disjoint unions to sums, V(A)V(A)V(A) to Cp(A)C_p(A)Cp​(A), and ordinary finite lists of V(A)V(A)V(A) to both list types. A variable returns its input at cost zero, and a return rule gives its chosen value at cost zero. Let-binding and release both evaluate the value premise on the first input component, evaluate the body on the second component paired with the value just obtained, and return the body’s result with the sum of the two costs. Spending adds ppp to the body’s cost. Weakening and storing use the body’s evaluation directly. Reading uses the first input component to select the body and evaluates it on the second. Tensor introduction evaluates the two premises on their respective components, pairs the results, and adds their costs. Swapping and reassociating rearrange the input pair or nested pairs to match the body’s input type. The two unit rules supply or drop the left singleton component before evaluating the body. A sum injection tags the body’s result and uses its cost. Sum elimination selects the premise by the input sum tag and evaluates it on the context component paired with the payload. Both empty-list rules give the empty list at zero cost. Both cons rules evaluate the head and tail on their respective input components, construct the list from those values, and add the two costs. Both folds first evaluate the list premise and then fold its resulting list from the right. At index rrr, the empty list evaluates the base for rrr on the singleton value. For a head and tail, evaluate the tail at the next index, then apply the step at rrr to the head paired with the tail result. The cons case returns the step’s result and the sum of the tail and step costs. For the first fold the index starts at ppp, the next index is identical, and the base and step are fixed. For the second fold the index starts at p1p_1p1​ and the next index after rrr is p2+rp_2+rp2​+r. Each fold adds the initial list-evaluation cost to the fold cost.

Interpretation. For any context and result types Γ,A\Gamma,AΓ,A, grade q∈Nq\in\mathbb Nq∈N, and derivation ddd from Γ\GammaΓ to AAA at grade qqq, the interpretation is a lax map from the interpretation of Γ\GammaΓ credited by qqq to the interpretation of AAA. The source and target at both phases consist of a natural-number cost paired with a value of the respective type. For a value type VVV, the order on these pairs is (c,x)≤(c′,x′)(c,x)\le(c',x')(c,x)≤(c′,x′) exactly when c≤c′c\le c'c≤c′ and x=x′x=x'x=x′, and charging s∈Ns\in\mathbb Ns∈N sends (c,x)(c,x)(c,x) to (s+c,x)(s+c,x)(s+c,x). For any input (c,x)(c,x)(c,x) with c∈Nc\in\mathbb Nc∈N and Ed(x)=(k,y)E_d(x)=(k,y)Ed​(x)=(k,y), the concrete map gives (c+k,y)(c+k,y)(c+k,y) and the abstract map gives (c,y)(c,y)(c,y). Each phase map is monotone and commutes with charging. The transition from concrete to abstract is (c,x)↦(q+(c+ΦΓ(x)),x)(c,x)\mapsto(q+(c+\Phi_\Gamma(x)),x)(c,x)↦(q+(c+ΦΓ​(x)),x) at the source and (c,y)↦(c+ΦA(y),y)(c,y)\mapsto(c+\Phi_A(y),y)(c,y)↦(c+ΦA​(y),y) at the target. Potential Φ\PhiΦ is zero for free and unit values, sums the two component potentials for a tensor, and uses the potential of the chosen summand for a sum. It adds ppp to the underlying potential in Cp(A)C_p(A)Cp​(A). On a list of length nnn it sums the potentials of all elements and adds npnpnp for Lp(A)L_p(A)Lp​(A) or np1+(n2)p2np_1+\binom{n}{2}p_2np1​+(2n​)p2​ for Qp1,p2(A)Q_{p_1,p_2}(A)Qp1​,p2​​(A). The lax relation places the concrete map followed by the target transition below the source transition followed by the abstract map. In the pair order both results have value yyy, and the cost inequality is c+k+ΦA(y)≤q+(c+ΦΓ(x))c+k+\Phi_A(y)\le q+(c+\Phi_\Gamma(x))c+k+ΦA​(y)≤q+(c+ΦΓ​(x)) for every such c,xc,xc,x.

Phase equations. For any context and result types Γ,A\Gamma,AΓ,A, grade q∈Nq\in\mathbb Nq∈N, derivation ddd from Γ\GammaΓ to AAA at grade qqq, incoming cost c∈Nc\in\mathbb Nc∈N, and input value xxx of Γ\GammaΓ, if evaluating ddd on xxx yields cost kkk and value yyy of AAA, then the concrete phase map of the interpretation sends (c,x)(c,x)(c,x) to (c+k,y)(c+k,y)(c+k,y). The abstract phase map sends (c,x)(c,x)(c,x) to (c,y)(c,y)(c,y).

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