The Cost of Usage in the Lambda-Calculus

A new “inductive” approach to standardization for the lambda-calculus has been recently introduced by Xi, allowing him to establish a double-exponential upper bound |M|^(2^|s|) for the length of the standard reduction relative to an arbitrary reduction s originated in M. In this paper we refine Xi’s analysis, obtaining much better bounds, especially for computations producing small normal forms. For instance, for terms reducing to a boolean, we are able to prove that the length of the standard reduction is at most a mere factorial of the length of the shortest reduction sequence. The methodological innovation of our approach is that instead of counting the cost for producing something, as is customary, we count the cost of consuming things. The key observation is that the part of a lambda-term that is needed to produce the normal form (or an arbitrary rigid prefix) may rapidly augment along a computation, but can only decrease very slowly (actually, linearly)