Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The Calf interpretation of positive AARA types

Definition
Grodin2026_AARATypes

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

amortized-analysisprogram-semanticstype-theory

The positive AARA grammar, its value types, and the potential function of Figure 2. The two-world Calf interpretation takes the tensor of free cost algebras and builds the linear-credit list by applying the list connective to credited elements. In the quadratic list family the linear coefficient increases by the quadratic coefficient at each tail.

Definition code
import Definitions.Def_Grodin2026_Banker

/-!
# Positive AARA computation types

The positive Calf connectives are interpreted in the paper's two-world model with natural
number costs. Both phase algebras of a positive AARA type are free. In particular, its
tensor uses the free algebra on pairs and combines costs additively. The list constructions
apply the abstraction map element by element, using the credit operator on each cons cell.

The interpretation is defined from these connectives. Theorem 5.7 identifies its result
with the separate potential interpretation of Figure 2.
-/

namespace Grodin2026.Revised

/-- Extend a function on generators to a homomorphism from a free cost algebra. -/
def extendFree {X : Type} {B : CostAlg} (f : X → B.carrier) : CostHom (FreeCostAlg X) B where
  fn := fun (c, x) ↦ B.charge c (f x)
  map_charge := fun p (c, x) ↦ B.charge_add p c (f x)
  mono := by
    intro a b h
    rcases a with ⟨c, x⟩
    rcases b with ⟨d, y⟩
    change c ≤ d ∧ x = y at h
    obtain ⟨hcd, rfl⟩ := h
    exact B.charge_mono_cost (f x) hcd

/-- The universal property of the tensor on two free cost algebras. Its pairing sends
`((c,x),(d,y))` to `(c+d,(x,y))`. A separately cost-preserving map on the two factors
extends uniquely to an ordinary cost homomorphism out of the tensor. -/
theorem freeTensor_universal {X Y : Type} {B : CostAlg}
    (f : (FreeCostAlg X).carrier → (FreeCostAlg Y).carrier → B.carrier)
    (hleft : ∀ (p : Nat) (x : (FreeCostAlg X).carrier) (y : (FreeCostAlg Y).carrier),
      f ((FreeCostAlg X).charge p x) y = B.charge p (f x y))
    (hright : ∀ (p : Nat) (x : (FreeCostAlg X).carrier) (y : (FreeCostAlg Y).carrier),
      f x ((FreeCostAlg Y).charge p y) = B.charge p (f x y)) :
    ∃! g : CostHom (FreeCostAlg (X × Y)) B,
      ∀ (c d : Nat) (x : X) (y : Y), g.fn (c + d, (x, y)) = f (c, x) (d, y) := by
  refine ⟨extendFree (fun xy ↦ f (0, xy.1) (0, xy.2)), ?_, ?_⟩
  · intro c d x y
    change B.charge (c + d) (f (0, x) (0, y)) = f (c, x) (d, y)
    rw [B.charge_add]
    have hl := hleft c (0, x) (d, y)
    have hr := hright d (0, x) (0, y)
    simp only [FreeCostAlg, Nat.add_zero] at hl hr
    rw [hl, hr]
  · intro g hg
    apply CostHom.ext
    funext xy
    obtain ⟨c, x, y⟩ := xy
    simpa only [Nat.add_zero, extendFree] using hg c 0 x y |>.trans
      (by
        have h := hleft c (0, x) (0, y)
        simpa only [FreeCostAlg, Nat.add_zero] using h)

/-- A two-world computation type whose algebras at both worlds are free. -/
structure FreePhase (X Y : Type) where
  alpha : CostHom (FreeCostAlg X) (FreeCostAlg Y)

/-- View a two-world map of free algebras as a Calf computation type. -/
def FreePhase.toComp {X Y : Type} (A : FreePhase X Y) : CompType :=
  AbstractionComp (FreeCostAlg X) (FreeCostAlg Y) A.alpha

/-- The constant free computation type. -/
def FreePhase.free (X : Type) : FreePhase X X :=
  ⟨CostHom.id (FreeCostAlg X)⟩

/-- The Calf tensor restricted to free algebras at both phases. On generators its
transition is obtained by applying the two input transitions and combining their
results by the tensor pairing from `freeTensor_universal`. -/
def FreePhase.tensor {X₁ X₂ Y₁ Y₂ : Type} (A : FreePhase X₁ Y₁) (B : FreePhase X₂ Y₂) :
    FreePhase (X₁ × X₂) (Y₁ × Y₂) :=
  ⟨extendFree fun (x, y) ↦
    let a : Nat × Y₁ := A.alpha.fn (0, x)
    let b : Nat × Y₂ := B.alpha.fn (0, y)
    (a.1 + b.1, (a.2, b.2))⟩

/-- The Calf coproduct of types whose phase algebras are free. -/
def FreePhase.sum {X₁ X₂ Y₁ Y₂ : Type} (A : FreePhase X₁ Y₁) (B : FreePhase X₂ Y₂) :
    FreePhase (Sum X₁ X₂) (Sum Y₁ Y₂) :=
  ⟨extendFree fun s ↦ match s with
    | .inl x =>
        let a : Nat × Y₁ := A.alpha.fn (0, x)
        (a.1, .inl a.2)
    | .inr x =>
        let b : Nat × Y₂ := B.alpha.fn (0, x)
        (b.1, .inr b.2)⟩

/-- Restrict the original Calf credit operator to free phase algebras. -/
def FreePhase.credit {X Y : Type} (p : Nat) (A : FreePhase X Y) : FreePhase X Y :=
  ⟨(CreditComp p A.toComp).alpha⟩

/-- The generator action of the inductive list connective. The empty list has no
incoming cost, and the cons constructor uses the tensor pairing on the translated
head and tail. -/
def FreePhase.listGenerator {X Y : Type} (A : FreePhase X Y) : List X → Nat × List Y
  | [] => (0, [])
  | x :: xs =>
      let a : Nat × Y := A.alpha.fn (0, x)
      let b := A.listGenerator xs
      (a.1 + b.1, a.2 :: b.2)

/-- The free phase interpretation of Calf's inductive list connective. -/
def FreePhase.list {X Y : Type} (A : FreePhase X Y) : FreePhase (List X) (List Y) :=
  ⟨extendFree A.listGenerator⟩

/-- Interpret `CList1` by applying the inductive list connective to the credited
element type. -/
def FreePhase.clist1 {X Y : Type} (p : Nat) (A : FreePhase X Y) :
    FreePhase (List X) (List Y) :=
  (A.credit p).list

/-- The generator action of the indexed quadratic-credit list connective, on the
ordinary list normal forms of its nil and cons constructors. The tail belongs to
the family at shifted index `p₂ + p₁`. -/
def FreePhase.clist2Generator {X Y : Type} (A : FreePhase X Y) (p₂ : Nat) :
    Nat → List X → Nat × List Y
  | _, [] => (0, [])
  | p₁, x :: xs =>
      let a : Nat × Y := (A.credit p₁).alpha.fn (0, x)
      let b := A.clist2Generator p₂ (p₂ + p₁) xs
      (a.1 + b.1, a.2 :: b.2)

/-- The free phase interpretation of the indexed quadratic-credit list family. -/
def FreePhase.clist2 {X Y : Type} (p₁ p₂ : Nat) (A : FreePhase X Y) :
    FreePhase (List X) (List Y) :=
  ⟨extendFree (A.clist2Generator p₂ p₁)⟩

/-- The positive AARA type grammar given in §5.2. -/
inductive AARAType : Type 1 where
  | free (X : Type) : AARAType
  | top : AARAType
  | tensor (A B : AARAType) : AARAType
  | sum (A B : AARAType) : AARAType
  | credit (p : Nat) (A : AARAType) : AARAType
  | clist1 (p : Nat) (A : AARAType) : AARAType
  | clist2 (p₁ p₂ : Nat) (A : AARAType) : AARAType

/-- The value interpretation of positive types in Figure 2. -/
def aaraValues : AARAType → Type
  | .free X => X
  | .top => PUnit
  | .tensor A B => aaraValues A × aaraValues B
  | .sum A B => Sum (aaraValues A) (aaraValues B)
  | .credit _ A => aaraValues A
  | .clist1 _ A => List (aaraValues A)
  | .clist2 _ _ A => List (aaraValues A)

/-- Sum the potentials of the elements of a list, counting every occurrence. -/
def listPotentialSum {X : Type} (φ : X → Nat) : List X → Nat
  | [] => 0
  | x :: xs => φ x + listPotentialSum φ xs

/-- The independently defined potential function of Figure 2. -/
def aaraPotential : (A : AARAType) → aaraValues A → Nat
  | .free _, _ => 0
  | .top, _ => 0
  | .tensor A B, (a, b) => aaraPotential A a + aaraPotential B b
  | .sum A _, .inl a => aaraPotential A a
  | .sum _ B, .inr b => aaraPotential B b
  | .credit p A, a => p + aaraPotential A a
  | .clist1 p A, l => l.length * p + listPotentialSum (aaraPotential A) l
  | .clist2 p₁ p₂ A, l =>
      l.length * p₁ + binom2 l.length * p₂ + listPotentialSum (aaraPotential A) l

/-- Interpret each grammar constructor by its Calf connective, in the subcollection
of computation types with free algebras at both worlds. -/
def interpPositiveFree : (A : AARAType) → FreePhase (aaraValues A) (aaraValues A)
  | .free X => .free X
  | .top => .free PUnit
  | .tensor A B => (interpPositiveFree A).tensor (interpPositiveFree B)
  | .sum A B => (interpPositiveFree A).sum (interpPositiveFree B)
  | .credit p A => (interpPositiveFree A).credit p
  | .clist1 p A => (interpPositiveFree A).clist1 p
  | .clist2 p₁ p₂ A => (interpPositiveFree A).clist2 p₁ p₂

/-- The compositional Calf interpretation of positive AARA types for Theorem 5.7. -/
def interpPositiveAARA (A : AARAType) : CompType :=
  (interpPositiveFree A).toComp

/-- The potential on a linear-credit cons is its head and tail potentials plus
one cell's credit. -/
theorem aaraPotential_clist1_cons (p : Nat) (A : AARAType) (x : aaraValues A)
    (xs : List (aaraValues A)) :
    aaraPotential (.clist1 p A) (x :: xs) =
      p + aaraPotential A x + aaraPotential (.clist1 p A) xs := by
  simp only [aaraPotential, List.length_cons, listPotentialSum, Nat.succ_mul]
  ac_rfl

/-- The potential on a quadratic-credit cons is its head and indexed tail
potentials plus the current index's credit. -/
theorem aaraPotential_clist2_cons (p₁ p₂ : Nat) (A : AARAType) (x : aaraValues A)
    (xs : List (aaraValues A)) :
    aaraPotential (.clist2 p₁ p₂ A) (x :: xs) =
      p₁ + aaraPotential A x + aaraPotential (.clist2 (p₂ + p₁) p₂ A) xs := by
  simp only [aaraPotential, List.length_cons, listPotentialSum, binom2, Nat.succ_mul,
    Nat.add_mul, Nat.mul_add]
  ac_rfl

theorem FreePhase.credit_alpha {X Y : Type} (p : Nat) (A : FreePhase X Y)
    (x : Nat × X) :
    (A.credit p).alpha.fn x = (p + (A.alpha.fn x).1, (A.alpha.fn x).2) :=
  rfl

private theorem linear_generator_eq (A : AARAType)
    (h : ∀ x : aaraValues A,
      (interpPositiveFree A).alpha.fn (0, x) = (aaraPotential A x, x))
    (p : Nat) (xs : List (aaraValues A)) :
    ((interpPositiveFree A).credit p).listGenerator xs =
      (aaraPotential (.clist1 p A) xs, xs) := by
  induction xs with
  | nil => simp [FreePhase.listGenerator, aaraPotential, listPotentialSum]
  | cons x xs ih =>
      simp only [FreePhase.listGenerator, FreePhase.credit_alpha, h, ih,
        aaraPotential_clist1_cons]

private theorem quadratic_generator_eq (A : AARAType)
    (h : ∀ x : aaraValues A,
      (interpPositiveFree A).alpha.fn (0, x) = (aaraPotential A x, x))
    (p₁ p₂ : Nat) (xs : List (aaraValues A)) :
    (interpPositiveFree A).clist2Generator p₂ p₁ xs =
      (aaraPotential (.clist2 p₁ p₂ A) xs, xs) := by
  induction xs generalizing p₁ with
  | nil => simp [FreePhase.clist2Generator, aaraPotential, listPotentialSum, binom2]
  | cons x xs ih =>
      simp only [FreePhase.clist2Generator, FreePhase.credit_alpha, h, ih,
        aaraPotential_clist2_cons]

private theorem interpPositiveFree_generator (A : AARAType) (x : aaraValues A) :
    (interpPositiveFree A).alpha.fn (0, x) = (aaraPotential A x, x) := by
  induction A with
  | free => rfl
  | top => rfl
  | tensor A B ihA ihB =>
      obtain ⟨a, b⟩ : aaraValues A × aaraValues B := x
      simp only [interpPositiveFree, FreePhase.tensor, extendFree, FreeCostAlg,
        ihA, ihB, Nat.zero_add, aaraPotential] <;> rfl
  | sum A B ihA ihB =>
      change Sum (aaraValues A) (aaraValues B) at x
      cases x <;> simp only [interpPositiveFree, FreePhase.sum, extendFree, FreeCostAlg,
        ihA, ihB, Nat.zero_add, aaraPotential] <;> rfl
  | credit p A ih =>
      change aaraValues A at x
      change ((interpPositiveFree A).credit p).alpha.fn (0, x) =
        (p + aaraPotential A x, x)
      rw [FreePhase.credit_alpha, ih]
  | clist1 p A ih =>
      simp only [interpPositiveFree, FreePhase.clist1, FreePhase.list, extendFree, FreeCostAlg,
        Nat.zero_add, linear_generator_eq A ih p x] <;> rfl
  | clist2 p₁ p₂ A ih =>
      simp only [interpPositiveFree, FreePhase.clist2, extendFree, FreeCostAlg,
        Nat.zero_add, quadratic_generator_eq A ih p₁ p₂ x] <;> rfl

/-- The transition computed from the Calf connectives agrees with Figure 2. -/
theorem interpPositiveAARA_alpha (A : AARAType) (x : Nat × aaraValues A) :
    (interpPositiveAARA A).alpha.fn x = (x.1 + aaraPotential A x.2, x.2) := by
  obtain ⟨c, x⟩ := x
  change (interpPositiveFree A).alpha.fn (c, x) = (c + aaraPotential A x, x)
  have h := (interpPositiveFree A).alpha.map_charge c (0, x)
  rw [interpPositiveFree_generator] at h
  simpa only [FreeCostAlg, Nat.add_zero] using h

/-- Theorem 5.7 in the two-world natural-cost model. The equivalence is the
identity on both free algebras, with commutation proved from the grammar. -/
def aaraCalfEquiv (A : AARAType) :
    CompEquiv (interpPositiveAARA A) (PotentialType (aaraValues A) (aaraPotential A)) where
  toHom :=
    { hom_top := CostHom.id _
      hom_abs := CostHom.id _
      comm := fun x ↦ (interpPositiveAARA_alpha A x).symm }
  invHom :=
    { hom_top := CostHom.id _
      hom_abs := CostHom.id _
      comm := interpPositiveAARA_alpha A }
  left_inv := rfl
  right_inv := rfl

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

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

Free extension. Let XXX be a type and BBB a cost algebra. Such an algebra has a preordered carrier and an action charge⁡B(p,b)\operatorname{charge}_B(p,b)chargeB​(p,b) of natural numbers that is monotone in ppp and bbb, acts as the identity at zero, and turns addition into composition. The free cost algebra F(X)F(X)F(X) has carrier N×X\mathbb N\times XN×X, with (c,x)≤(d,y)(c,x)\le(d,y)(c,x)≤(d,y) exactly when c≤dc\le dc≤d and x=yx=yx=y, and charge ppp sends (c,x)(c,x)(c,x) to (p+c,x)(p+c,x)(p+c,x). For every function fff from XXX to the carrier of BBB, the definition gives the monotone, charge-preserving map F(X)→BF(X)\to BF(X)→B sending (c,x)(c,x)(c,x) to charge⁡B(c,f(x))\operatorname{charge}_B(c,f(x))chargeB​(c,f(x)).

Tensor universal property. Let X,YX,YX,Y be types and BBB a cost algebra. Take any function fff from a pair of inputs in F(X)F(X)F(X) and F(Y)F(Y)F(Y) to the carrier of BBB. Assume that for every p∈Np\in\mathbb Np∈N and every pair of inputs, charging either input by ppp has the same effect as charging the output by ppp. Then there is exactly one monotone, charge-preserving map ggg from F(X×Y)F(X\times Y)F(X×Y) to BBB such that g(c+d,(x,y))=f((c,x),(d,y))g(c+d,(x,y))=f((c,x),(d,y))g(c+d,(x,y))=f((c,x),(d,y)) for all c,d∈Nc,d\in\mathbb Nc,d∈N, x∈Xx\in Xx∈X, and y∈Yy\in Yy∈Y. Here each free algebra consists of a natural-number cost and a value, and charge adds to the cost. The quantifiers allow XXX and YYY to be empty.

Free phase. For types X,YX,YX,Y, a free-phase structure is a monotone, charge-preserving transition α\alphaα from F(X)F(X)F(X) to F(Y)F(Y)F(Y). These algebras have carriers N×X\mathbb N\times XN×X and N×Y\mathbb N\times YN×Y, order by cost within each fixed value, and charge by adding a natural number to the cost. The corresponding computation type has top algebra F(X)F(X)F(X), abstract algebra F(Y)F(Y)F(Y), and top-to-abstract transition α\alphaα. The constant free computation type has F(X)F(X)F(X) at both phases with the identity transition (c,x)↦(c,x)(c,x)\mapsto(c,x)(c,x)↦(c,x).

Tensor. For types X1,X2,Y1,Y2X_1,X_2,Y_1,Y_2X1​,X2​,Y1​,Y2​ and free-phase structures AAA from X1X_1X1​ to Y1Y_1Y1​ and BBB from X2X_2X2​ to Y2Y_2Y2​, the result has free algebras on X1×X2X_1\times X_2X1​×X2​ and Y1×Y2Y_1\times Y_2Y1​×Y2​. For c∈Nc\in\mathbb Nc∈N, x∈X1x\in X_1x∈X1​, and y∈X2y\in X_2y∈X2​, write αA(0,x)=(a,u)\alpha_A(0,x)=(a,u)αA​(0,x)=(a,u) and αB(0,y)=(b,v)\alpha_B(0,y)=(b,v)αB​(0,y)=(b,v). Its transition sends (c,(x,y))(c,(x,y))(c,(x,y)) to (c+(a+b),(u,v))(c+(a+b),(u,v))(c+(a+b),(u,v)).

Sum. For types X1,X2,Y1,Y2X_1,X_2,Y_1,Y_2X1​,X2​,Y1​,Y2​ and free-phase structures AAA from X1X_1X1​ to Y1Y_1Y1​ and BBB from X2X_2X2​ to Y2Y_2Y2​, the result has free algebras on the tagged disjoint unions X1⊔X2X_1\sqcup X_2X1​⊔X2​ and Y1⊔Y2Y_1\sqcup Y_2Y1​⊔Y2​. For any c∈Nc\in\mathbb Nc∈N, if αA(0,x)=(a,u)\alpha_A(0,x)=(a,u)αA​(0,x)=(a,u), the transition sends (c,inl⁡x)(c,\operatorname{inl}x)(c,inlx) to (c+a,inl⁡u)(c+a,\operatorname{inl}u)(c+a,inlu). If αB(0,y)=(b,v)\alpha_B(0,y)=(b,v)αB​(0,y)=(b,v), it sends (c,inr⁡y)(c,\operatorname{inr}y)(c,inry) to (c+b,inr⁡v)(c+b,\operatorname{inr}v)(c+b,inrv).

Credit. For types X,YX,YX,Y, a free-phase structure AAA with transition αA\alpha_AαA​ from F(X)F(X)F(X) to F(Y)F(Y)F(Y), and p∈Np\in\mathbb Np∈N, the result has the same two free algebras. Its transition sends each (c,x)(c,x)(c,x) to (p+d,y)(p+d,y)(p+d,y), where (d,y)=αA(c,x)(d,y)=\alpha_A(c,x)(d,y)=αA​(c,x).

Lists. For types X,YX,YX,Y and a free-phase structure AAA from XXX to YYY, the list generator sends a finite list in XXX to a pair of a cost and a finite list in YYY. It sends the empty list to (0,[])(0,[])(0,[]). For a head xxx and tail sss, if αA(0,x)=(a,y)\alpha_A(0,x)=(a,y)αA​(0,x)=(a,y) and the result on sss is (b,t)(b,t)(b,t), it returns (a+b,y::t)(a+b,y::t)(a+b,y::t). The list connective extends this function to free algebras on lists, so that an incoming cost ccc is added to the total cost. The linear-credit list with parameter ppp applies this list connective to the element transition credited by ppp. In particular, if αA(0,xi)=(ai,yi)\alpha_A(0,x_i)=(a_i,y_i)αA​(0,xi​)=(ai​,yi​), the transition sends (c,[x1,…,xn])(c,[x_1,\ldots,x_n])(c,[x1​,…,xn​]) to (c+∑i(p+ai),[y1,…,yn])(c+\sum_i(p+a_i),[y_1,\ldots,y_n])(c+∑i​(p+ai​),[y1​,…,yn​]).

Quadratic lists. For types X,YX,YX,Y, a free-phase structure AAA, and natural numbers p,qp,qp,q, the generator acts on finite lists and an index initially equal to ppp. The empty list gives (0,[])(0,[])(0,[]) at any index. At index rrr, a head with αA(0,x)=(a,y)\alpha_A(0,x)=(a,y)αA​(0,x)=(a,y) is combined with the tail result (b,t)(b,t)(b,t) at index q+rq+rq+r, returning ((r+a)+b,y::t)((r+a)+b,y::t)((r+a)+b,y::t). The connective extends this recursion to free algebras on lists and adds the original input cost to its result. Both list connectives send (c,[])(c,[])(c,[]) to (c,[])(c,[])(c,[]).

Grammar. A type expression lies in the next universe above the types admitted by the free constructor. Its constructors are free(X)\mathrm{free}(X)free(X) for each small type XXX, unit, binary tensor and sum, fixed credit, linear-credit lists, and quadratic-credit lists. The latter three take, respectively, one, one, and two natural-number parameters and an element type expression.

Value type. The type V(A)V(A)V(A) of values is XXX for free(X)\mathrm{free}(X)free(X) and a singleton for unit. Tensor uses the Cartesian product of the component value types, sum uses their tagged disjoint union, credit uses the underlying value type, and both list constructors use finite lists in that underlying value type.

Potential. Each type expression AAA and x∈V(A)x\in V(A)x∈V(A) gives a natural number ΦA(x)\Phi_A(x)ΦA​(x). Free and unit values give zero. Tensor adds the component potentials, sum uses the potential in the selected summand, and credit adds its parameter to the underlying potential. For a list [x1,…,xn][x_1,\ldots,x_n][x1​,…,xn​], the linear case is np+∑iΦA(xi)np+\sum_i\Phi_A(x_i)np+∑i​ΦA​(xi​), and the quadratic case is np+b(n)q+∑iΦA(xi)np+b(n)q+\sum_i\Phi_A(x_i)np+b(n)q+∑i​ΦA​(xi​) where b(0)=0b(0)=0b(0)=0 and b(n+1)=n+b(n)b(n+1)=n+b(n)b(n+1)=n+b(n). Each position contributes once, and both list formulas give zero for the empty list.

Type interpretation. Each grammar expression AAA is assigned free algebras F(V(A))F(V(A))F(V(A)) in both phases. Free and unit use the identity transition. Tensor and sum use the binary connectives above. Credit adds its parameter to the recursively interpreted transition. Both lists use the corresponding list construction above, with the recursively interpreted element type. Viewing this as a computation type leaves its phase algebras and transition as specified.

Potential equations. For every head x∈V(A)x\in V(A)x∈V(A) and finite tail sss, the linear-credit cons potential is p+ΦA(x)+Φclist1(p,A)(s)p+\Phi_A(x)+\Phi_{\mathrm{clist1}(p,A)}(s)p+ΦA​(x)+Φclist1(p,A)​(s). The quadratic-credit cons potential is p+ΦA(x)+Φclist2(q+p,q,A)(s)p+\Phi_A(x)+\Phi_{\mathrm{clist2}(q+p,q,A)}(s)p+ΦA​(x)+Φclist2(q+p,q,A)​(s). Both statements allow zero parameters and empty tails. For every expression AAA, cost ccc, and value x∈V(A)x\in V(A)x∈V(A), the interpreted transition sends (c,x)(c,x)(c,x) to exactly (c+ΦA(x),x)(c+\Phi_A(x),x)(c+ΦA​(x),x).

Equivalence. For every type expression AAA, there is an explicit isomorphism from its recursively interpreted computation type to the one whose transition is (c,x)↦(c+ΦA(x),x)(c,x)\mapsto(c+\Phi_A(x),x)(c,x)↦(c+ΦA​(x),x). A computation homomorphism comprises compatible, monotone, charge-preserving maps at the two phases. The forward and inverse homomorphisms in this expression use the identity on N×V(A)\mathbb N\times V(A)N×V(A) at both phases, and their composites are identities.

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