Linearization via Rewriting
Ugo dal Lago, Federico Olimpieri · 2025
Read Linearization via Rewriting by Ugo dal Lago, Federico Olimpieri (2025) 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-2503-04408.txt.
Introduction
Ugo dal Lago and Federico Olimpieri introduce a new formal calculus for computer science logic in this 2025 arXiv paper. The lambda calculus is a core model of computation, and some of its terms always finish computing. The authors want a system where such terms can be written naturally, and where the steps that make a proof use each resource exactly once happen inside the system itself.
Their structural resource lambda-calculus meets both goals. They show the system always finishes and that different orders of steps reach the same end. Every term that always finishes can be represented by a type derivation inside it. The authors note this is the first system where the linearization step is internal, finite, and driven purely by rewriting.
Catalog record
| CREATOR | Ugo dal Lago, Federico Olimpieri |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-04408
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Linearization via Rewriting Ugo dal Lago, Federico Olimpieri Abstract We introduce the structural resource λ \lambda -calculus , a new formalism in which strongly normalizing terms of the λ \lambda -calculus can naturally be represented, and at the same time any type derivation can be internally rewritten to its linearization. The calculus is shown to be normalizing and confluent. Noticeably, every strongly normalizable λ \lambda -term can be represented by a type derivation. This is the first example of a system where the linearization process takes place internally , while remaining purely finitary and rewrite-based . 1 Introduction Slightly less than a century since the pioneering contributions by Church and Gentzen, the study of proof theory, type systems and the \lambda -calculus has produced a multitude of logical and computational formalisms in which proofs and programs can be represented and the process of either eliminating cuts or evaluating a program by forms of rewriting can be studied directly within the system at hand, often giving rise to confluence and normalization results (see, e.g., [ Girard73 , Reynolds74 , ML80 , Parigot92 ] ). The considered systems are often very expressive, which is why the aforementioned normalization properties become logically non-trivial, and can hardly be carried out combinatorially. Since the mid-eighties, the situation sketched above has somehow changed: the advent of linear logic [ Girard87 ] has allowed a finer structure to be attributed to the underlying computation process. By identifying structural logical rules, and in particular contraction , as the bottleneck in the normalization results, linear logic gave rise to the introduction of proof and type systems in which structural rules are very severely restricted or not allowed at all . As a consequence, normalization properties can be proved by purely combinatorial means: rewriting and cut-elimination have the effect of strictly reducing the size of the objects at hand. Systems of this kind, which we will call quantitative — simply to distinguish them from the somehow qualitative systems we referred to in the previous paragraph — include not only multiplicative linear logic [ Girard87 , DanosRegnier89 ] , but also non-idempotent intersection types [ Gardner94 , DeCarvalho18 ] , the resource \lambda -calculus [ Boudol93 , EhrhardRegnier08 ] , and certain type systems based on restrictions of exponentials such as the so-called light logics [ GSS92 , Girard98 , Lafont04 ] . In quantitative systems, there is an aspect of finiteness absent in qualitative systems, which makes them particularly suitable to the characterization of complexity classes and in general whenever a fine control over the use of resources is considered necessary. A proof or program, in quantitative systems, is an object that reveals everything about its dynamics, i.e. , about the evolution it will undergo as a result of the evaluation. Since the early days of linear logic, there have been many attempts to relate quantitative and qualitative systems by studying how to transform proofs and programs in qualitative systems into equivalent objects in quantitative systems. Already in Girard’s original work [ Girard87 ] there is a trace of all this in the so-called approximation theorem , which states that every cut-free proof of multiplicative and exponential linear logic can be approximated, in a very natural sense, by a proof of multiplicative linear logic. We should also mention the line of work about linearizing the \lambda -calculus [ Kfoury00 , AlvesFlorido03 , AlvesFlorido05 , AlvesVentura22 ] , in which one studies to what extent pure \lambda -terms can be linearized into linear terms, establishing on one hand that this process can be applied to all normalizing terms following their reduction sequence, and that on the other hand a relationship exists between the emerging process and typeability in non-idempotent intersection types. We should also mention the crucial contribution of Ehrhard and Regnier [ EhrhardRegnier08 ] , who through an inductive and very elegant definition, provide a notion of Taylor expansion for any pure \lambda -term as the (infinite) set of its linear approximants. Continuing along the same vein, we must certainly mention the results on the extensional collapse of quantitative denotational models into qualitative models [ er:collapse ] . The collapse induces a categorical understanding of the relationship between idempotent ( i.e. , qualitative) and non-idempotent ( i.e. , quantitative) intersection types. However, this result does not directly yield an explicit program transformation. In all these attempts, the infinitary aspects of qualitative systems are either neglected by considering only cut-free proofs, or reflected in the target of the transformation, like in the Taylor expansion. In the case of Kfoury’s linearization [ Kfoury00 ] , in particular, the process of computing the linear approximant of a pure \lambda -term is delegated to a notion of expansion that, even if formally defined in terms of rewriting, is trivially not normalizing, because it consists in increasing the size of the right argument bag of an application, thus matching the number of arguments required by the related abstraction. In a certain sense, therefore, the linearization process remains fundamentally infinitary, similar to what happens in the Taylor expansion [ EhrhardRegnier08 ] . The same holds for the remarkable recent contribution by Pautasso and Ronchi [ PautassoRonchi23 ] , which introduces a quantitative version of the simple types in which derivations carry the same kind of quantitative information as in non-idempotent intersection types. The system turns out to be equivalent to the usual simply-typed \lambda -calculus in terms of typeability, but the proof of this fact is carried out externally to the system, and is nontrivial. Could linearization be made an integral part of the underlying system? Is there a way to compute a linear version of a program (or proof) so that this transformation happens within the system? The authors are strongly convinced of the interest of these questions and think that understanding to what extent all this is possible can help shedding some light on the relationship between qualitative and quantitative systems. The main contribution of the present paper is precisely to introduce a language and type system in which qualitative systems can be naturally embedded and an essentially quantitative fragment can be isolated. More specifically, terms typable in qualitative systems such as the simply-typed \lambda -calculus can be compositionally embedded into the calculus. Linearization, this is the real novelty, becomes a form of rewriting turning any term into a linear approximation of it. The role of this rewriting process, called exponential reduction, is to eliminate the use of structural rules without performing any \beta -reduction, the latter being part of the system itself. Crucially, exponential reduction is strongly normalizing. The calculus thus obtained can be seen as an extension of Boudol’s resource \lambda -calculus [ Boudol93 ] , and we call it the structural resource \lambda -calculus . Technically, the key ingredients in its definition are as follows. At the level of terms, there is both the possibility of having a nonlinear use of variables, but also of passing a bag of terms to an abstraction, in the style of the resource \lambda -calculus. Crucially, abstractions are labeled so as to identify the structural rules needed to fire the corresponding redex. An intersection type assignment system is an integral part of the calculus and