Graded typing derivations in the positive AARA fragment of Giralf
DefinitionGrodin2026_AARADerivationsThe 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.
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
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
Typing derivations. Write for a derivation with input context type , result type , and grade . Context and result types range over the grammar with free types for arbitrary types , the unit , tensors , sums , credited types , and list types and . All grades and credit parameters are natural numbers, including zero. The family is generated by the following rules. A variable gives at any grade. Let-binding takes and to if . Spending takes to if , and weakening does so if . Returning any chosen gives at any grade. Reading takes a family of derivations indexed by and gives . Tensor introduction takes and to if . At fixed grade and result type, a derivation’s input can be changed from to , between and in either direction, or between and in either direction. At fixed input and grade, either summand can be injected into . Sum elimination takes premises and to . Storing takes to if . Releasing takes and to if . An empty list of either kind has input and arbitrary grade and credit parameters. A cons for takes and to if . A cons for instead takes the tail from , gives , and requires . The fold takes a list derivation , a base , and a step , and gives . The fold takes a list derivation and, for any type family indexed by , a base and a step for every . The result is .
Evaluation. For any context and result types , grade , and derivation from to at grade , evaluation maps each to a pair of cost and result. The value type assigns to , a singleton to the unit, products to tensors, disjoint unions to sums, to , and ordinary finite lists of 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 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 , the empty list evaluates the base for on the singleton value. For a head and tail, evaluate the tail at the next index, then apply the step at 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 , the next index is identical, and the base and step are fixed. For the second fold the index starts at and the next index after is . Each fold adds the initial list-evaluation cost to the fold cost.
Interpretation. For any context and result types , grade , and derivation from to at grade , the interpretation is a lax map from the interpretation of credited by to the interpretation of . 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 , the order on these pairs is exactly when and , and charging sends to . For any input with and , the concrete map gives and the abstract map gives . Each phase map is monotone and commutes with charging. The transition from concrete to abstract is at the source and at the target. Potential 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 to the underlying potential in . On a list of length it sums the potentials of all elements and adds for or for . 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 , and the cost inequality is for every such .
Phase equations. For any context and result types , grade , derivation from to at grade , incoming cost , and input value of , if evaluating on yields cost and value of , then the concrete phase map of the interpretation sends to . The abstract phase map sends to .