LFPL: Revisited and Mechanized

Nathaniel Glover, Jan Hoffmann · 2026

Read LFPL: Revisited and Mechanized by Nathaniel Glover, Jan Hoffmann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12893.txt.

Introduction

Glover and Hoffmann give a modern, self-contained account of LFPL, a functional language from 1999 that captures exactly the functions computable in polynomial time. Despite its influence on cost analysis and type theory, no full presentation or machine-checked version existed. They streamline the strongest known soundness and completeness proofs and mechanise both in the Istari proof assistant, adapting a 2002 technique to bound expression costs with explicit polynomials.

Catalog record

CREATORNathaniel Glover, Jan Hoffmann
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE117732
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.12893

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

LFPL: Revisited and Mechanized Nathaniel Glover, Jan Hoffmann Abstract Hofmann (1999) introduced the functional programming language LFPL to characterize the functions computable in polynomial time using an affine type system. LFPL enables a natural programming style, including nested recursion, and has inspired the development of type systems for automatic cost analysis, linear dependent type theories, and efficient memory management in functional programming languages. Despite its prominence, there does not exist a self-contained presentation, let alone a full mechanization, of LFPL and its core metatheory. This article presents a modern account and mechanization of LFPL and its metatheory with the goal of being self-contained and accessible while streamlining the strongest-known soundness and completeness results. The soundness proof works with the language LFPL + \text{LFPL}^{+} , which extends LFPL with additional language features. The proof is novel, adapting a technique by Aehlig and Schwichtenberg (2002) to construct explicit polynomials that bound the cost of an LFPL + \text{LFPL}^{+} expression with respect to a big-step cost semantics. The completeness proof shows that LFPL programs can simulate polynomial-time Turing machines while only relying on restricted forms of linear functions and lists. It has the same structure as the original proof by Hofmann (2002) but greatly simplifies the core argument with a novel stack-like data structure that is implemented with first-class functions and lists. The mechanization includes the full soundness and completeness proofs, and serves as one of the first case studies of mechanized metatheory in the recently developed proof assistant Istari. Carnegie Mellon University, United States and https://www.cs.cmu.edu/~nsglover [email protected]://orcid.org/0009-0006-1123-4277 Carnegie Mellon University, United States and https://www.cs.cmu.edu/~janh [email protected]://orcid.org/0000-0001-8326-0788 {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003790.10011740¡/concept_id¿ ¡concept_desc¿Theory of computation Type theory¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003777.10003787¡/concept_id¿ ¡concept_desc¿Theory of computation Complexity theory and logic¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10003801¡/concept_id¿ ¡concept_desc¿Theory of computation Linear logic¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ keywords Type Theory, Implicit Computational Complexity, Affine Logic ccs Theory of computation Type theory ccs Theory of computation Complexity theory and logic ccs Theory of computation Linear logic † † runningauthor: N. Glover and J. Hoffmann † † copyright: Nathaniel Glover and Jan Hoffmann † † supplement: Software: https://doi.org/10.5281/zenodo.18348212 1 Introduction The goal of implicit computational complexity (ICC) is to provide a programming language which characterizes a given complexity class. Concretely, this means that a procedure is representable in the language if and only if it inhabits the desired complexity class. ICC has been extensively studied for many complexity classes including P [ 17 , 18 , 20 , 12 ] , PSPACE [ 20 , 12 , 13 ] , EXPTIME [ 19 ] , and LOGSPACE [ 31 , 30 ] . Such languages often achieve their desired complexity class via modifications of standard linear or affine type systems [ 10 ] . One prominent such programming language for the complexity classes P and FP is Martin Hofmann’s Linear Function Programming Language (LFPL). It was first defined in 1999, when Hofmann [ 17 ] showed that LFPL is polynomial-time sound, that is, all functions definable in LFPL belong to FP. In 2002, Hofmann [ 19 ] proved the logical inverse of this statement, polynomial-time completeness. LFPL is notable for characterizing FP while also supporting a natural programming style and giving rise to the development of automatic amortized resource analysis [ 16 ] . Recently, there has been renewed interest in LFPL. Atkey [ 3 ] extends LFPL with dependent types and unrestricted computation at the type level, creating a language equipped with the powerful guarantees of dependent type theory while still enforcing that computation is polynomial-time at the term level. Lorenzen et al. [ 24 ] utilize the type system of LFPL in their language Koka to ensure that certain functional programs can be executed fully in-place. Despite its prominence, we are not aware of a fully self-contained presentation of LFPL and its core metatheory. The original presentation by Hofmann [ 17 ] contains a semantic soundness proof but only a weak completeness result for linear-space polynomial-time Turing machines. A somewhat informal completeness result for the original LFPL is given as a corollary in Hofmann [ 19 ] , where polynomial time is not the main focus. Aehlig and Schwichtenberg [ 2 ] provide a syntactic soundness proof for a small-step semantics and a weaker completeness proof for a strong extension of LFPL. Atkey [ 3 ] presents a similar completeness proof, as well as a soundness proof for LFPL extended with dependent type theory. Lorenzen et al. [ 24 ] present LFPL’s type system without the metatheory. None of these works contains both a soundness proof and a completeness proof of the original LFPL without extensions. In this article, we give a modern account and mechanization [ 14 ] of LFPL and its metatheory. Our primary goal is for this article to be a self-contained and accessible resource for those who are interested in learning about LFPL, with all of our results guaranteed correct by the mechanization. We have witnessed firsthand the necessity of such a resource. It was challenging to collect all this information on LFPL from across the various different papers we have mentioned, and during the process we discovered some errors in Hofmann’s completeness proof [ 19 ] , the only full completeness proof that we are aware of. Our presentation of LFPL involves a denotational semantics similar to the original given by Hofmann [ 17 ] as well as a big-step operational cost semantics, which, to our knowledge, was not developed for LFPL. An advantage of both semantics—which greatly reduce the complexity of our mechanization—is that they both avoid making use of syntactic substitution, which is a notoriously tedious operation to support and reason about in proof assistants. The mechanized completeness proof is a simplified and streamlined version of the one given by Hofmann [ 19 ] . The main novelty is the implementation of a stack-like data structure in LFPL that allows us to avoid much of the complexity of Hofmann’s proof as well as sidestep the errors we discovered in that proof. To our knowledge, ours is the strongest completeness result for LFPL. Hofmann also gave a weaker completeness theorem for linear-time Turing machines only [ 17 ] . Both Aehlig and Schwichtenberg [ 2 ] and Atkey [ 3 ] provide full completeness proofs but for powerful extensions of LFPL, thereby weakening the completeness result. Like Hofmann’s version [ 19 ] , our completeness proof works with a minimal version of LFPL, using the fewest tools to simulate a polynomial-time Turing machine. The mechanized soundness proof is inspired by Aehlig and Schwichtenberg [ 2 ] . We give a modern presentation of their result for a big-step operational cost semantics and an extended language \text{LFPL}^{+} . Using this cost semantics allows us to reason about concrete program executions and avoids the substitution-related tedium that arises when mechanizing a small-step semantics. While a big-step operational cost semantics is further away from a concrete machine model, it is well-known how to link it to small-step semantics, which have been shown to be reasonable with respect to lower-level semantic models [ 6 , 1 ] . Notably, for each \text{LFPL}^{+} term, the proof constructs a concrete polynomial that bounds the execution cost of the term as defined by

Read the complete text