Theorem 2.25 — Polynomial step and resource bounds on data
OpenABHS2004V2.theorem_2_25An almost closed program between data types normalizes on canonical inputs. A polynomial in total input syntax length bounds the step count, with degree at most the larger of one and the iterator depth. Both the output resource size and its free-variable count are bounded by the corresponding input totals plus a program-dependent constant.
import Definitions.Def_ABHS2004V2_TermSystem
namespace ABHS2004V2
/-- Theorem 2.25. An almost-closed program between data types normalizes on
canonical inputs in polynomially many steps. The nested number of list cells
in the result grows by at most a constant depending on the program. -/
theorem theorem_2_25 {τs : List Ty} {τ : Ty} {r : Term}
(hdata_in : ∀ σ ∈ τs, IsDataType σ)
(hdata_out : IsDataType τ)
(ht : HasType r (Ty.lolliMany τs τ))
(hac : IsAlmostClosed r) :
∃ (B : Nat → Nat) (k : Nat),
BoundedByPolyOfDegree B (Nat.max (iterNesting r) 1) ∧
∀ ws : List Term,
ValidDataInputs r τs ws →
∃ (steps : Nat) (w : Term),
RedSteps steps (Term.appMany r ws) w ∧
IsDataObject τ w ∧
steps ≤ B (totalTermLength ws) ∧
dataSize w ≤ totalDataSize ws + k ∧
freeVarCount w ≤ totalFreeVarCount ws + k := by sorry
end ABHS2004V2Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
Let be a list of types, let be a type, and let be a term. Assume every and is a data type, has the right-associated function type , and every free variable occurrence of has type . The empty type list gives type for . There exist a function and a number such that, writing , there exist with
For every term list that is valid for and the input type list, there exist and a term such that the left-associated application reaches in exactly ordinary steps, and is a data object of type . For this chain and output,
Validity means , is a data object of type , and the free variables of are disjoint from those of the preceding application for each . When the type list is empty, the valid input is empty, the starting term is , and the three sums are zero.
Data types are generated from by lists, tensors, and sums of data types. A data object of type must have that type by the term typing rules, have only -typed free variable occurrences, and have no ordinary one-step reduct. The typing rules assign variables and constants their recorded types, type an abstraction by a function arrow, require disjoint free variables and compatible function and argument types at an application, and require a list of type and a closed step of type for an iterator of type . A reduction contracts beta, tensor elimination on introduction, product projection on introduction, sum elimination on an injection, or nil/cons iteration on a seed, at the root or through either child of applications or iterators. A cons iteration requires its tail to be syntactically built from fully applied cons constants ending in nil. A chain of zero steps keeps the starting term.
The length is on a variable or constant, adds through an abstraction, and adds the two child lengths at an application or iterator. The size counts occurrences of all cons constants, including bare cons constants, throughout the term. The count is the length of the free-occurrence list, so it counts repetitions. This list contains one entry for a variable, is empty for a constant, concatenates the child lists at an application or iterator, and removes all entries equal to the binder at an abstraction. A variable is the pair of its natural-number identifier and its recorded type. The nesting measure is on variables and constants, passes through an abstraction, is the maximum of the two child values at an application, and satisfies .