Ohana trees, linear approximation and multi-types for the λI-calculus: No variable gets left behind or forgotten
Rémy Cerda ORCID:0000-0003-0731-6211, Giulio Manzonetto ORCID:0000-0003-1448-9014, Alexis Saurin ORCID:0009-0002-1304-5518 · 2025
Read Ohana trees, linear approximation and multi-types for the λI-calculus: No variable gets left behind or forgotten by Rémy Cerda ORCID:0000-0003-0731-6211, Giulio Manzonetto ORCID:0000-0003-1448-9014, Alexis Saurin ORCID:0009-0002-1304-5518 (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-2505-06193.txt.
Introduction
Rémy Cerda, Giulio Manzonetto, and Alexis Saurin introduce a new semantics for a frugal flavor of the lambda calculus, in this 2025 paper. The catalog title and author field carry funding and identifier clutter, so both follow the head of the text. In this calculus, no argument may be erased, yet all classic models collapse its hard terms into one dull class.
Their Ohana trees fix that blindness: each tree is the term's usual shape tree, annotated with the free variables hidden in its dead subtrees and down its endless branches. Two approximation routes, finite trees and a series expansion, are shown to agree. A matching type-based model is then built. The authors open a finer theory of program equality for this calculus.
Catalog record
| CREATOR | Rémy Cerda ORCID:0000-0003-0731-6211, Giulio Manzonetto ORCID:0000-0003-1448-9014, Alexis Saurin ORCID:0009-0002-1304-5518 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06193
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ohana trees, linear approximation and multi-types for the λI-calculus: No variable gets left behind or forgotten! Thanks: This article is an extended version of the conference paper [ Cerda.Man.Sau.25 ] . Thanks: The first and third authors were partly funded by the ANR project RECIPROG (ANR-21-CE48-019). The second author is partly funded by the EMERGENCE project Bang! of the Université Paris Cité. Rémy Cerda ORCID:0000-0003-0731-6211, Giulio Manzonetto ORCID:0000-0003-1448-9014, Alexis Saurin ORCID:0009-0002-1304-5518 Abstract . Although the λ 𝖨 \lambda\mathsf{I} -calculus is a natural fragment of the λ \lambda -calculus, obtained by forbidding the erasure of arguments, its equational theories did not receive much attention. The reason is that all proper denotational models studied in the literature equate all non-normalizable λ 𝖨 \lambda\mathsf{I} -terms, whence the associated theory is not very informative. The goal of this paper is to introduce a previously unknown theory of the λ 𝖨 \lambda\mathsf{I} -calculus, induced by a notion of evaluation trees that we call “Ohana trees” . The Ohana tree of a λ 𝖨 \lambda\mathsf{I} -term is an annotated version of its Böhm tree, remembering all free variables that are hidden within its meaningless subtrees, or pushed into infinity along its infinite branches. We develop the associated theories of program approximation: the first approach — more classic — is based on finite trees and continuity, the second adapts Ehrhard and Regnier’s Taylor expansion. We then prove a Commutation Theorem stating that the normal form of the Taylor expansion of a λ 𝖨 \lambda\mathsf{I} -term coincides with the Taylor expansion of its Ohana tree. As a corollary, we obtain that the equality induced by Ohana trees is compatible with abstraction and application. Subsequently, we introduce a denotational model designed to capture the equality induced by Ohana trees. Although presented as a non-idempotent type system, our model is based on a suitably modified version of the relational semantics of the λ \lambda -calculus, which is known to yield proper models of the λ 𝖨 \lambda\mathsf{I} -calculus when restricted to non-empty finite multisets. To track variables occurring in subterms that are hidden or pushed to infinity in the evaluation trees, we generalize the system in two ways: first, we reintroduce annotated versions of the empty multiset indexed by sets of variables; second, we introduce a separate environment to account for the free variables present in these subterms. We show that this model retains the standard quantitative properties of relational semantics and that the induced theory precisely captures Ohana trees. We conclude by discussing the cases of Lévy-Longo and Berarducci trees, and possible generalizations to the full λ \lambda -calculus. [a,b] [a] [a,c] 1. Introduction In the pioneering article “The calculi of lambda-conversion” [ Church41 ] Alonzo Church introduced the \lambda -calculus together with its fragment without weakening, called the \lambda\mathsf{I} -calculus, where each abstraction must bind at least one occurrence of a variable. Historically, the \lambda\mathsf{I} -calculus has proven to be a useful framework for establishing results such as the finiteness of developments and standardization, which were successfully proven for the full \lambda -calculus only decades later. Despite that, in the last forty years there have been no groundbreaking advances in its study. The study of models and theories of \lambda -calculus flourished in the 1970s [ Bare ] and remained central in theoretical computer science for decades [ BarendregtM22 ] . Although the equational theories of \lambda -calculus, called \lambda -theories , form a complete lattice of cardinality 2^{\aleph_{0}} [ LusinS04 ] , only a handful are of interest to computer scientists. Most articles focus on \lambda -theories generated through some notion of “evaluation tree” of a \lambda -term, which means that two \lambda -terms are equated in the theory exactly when their evaluation trees coincide. The definitions of evaluation trees present in the literature follow the same pattern: they collect in a possibly infinite tree all stable portions of the output coming out from the computation, and replace the subterms that are considered meaningless by a constant \bot , representing the lack of information. By modifying the notions of “stable” and “meaningless” , one obtains Böhm trees [ Barendregt77 ] , possibly endowed with some form of extensionality [ Nakajima.75 , SeveriV17 , IntrigilaMP19 ] , Lévy-Longo trees [ Levy76 , Longo83 ] and Berarducci trees [ Berarducci96 ] . In the modern language of infinitary term rewriting systems, these trees can be seen as the transfinite normal forms of infinitary \lambda -calculi [ EndrullisHK12 , Czajka20 ] . Another popular method for defining \lambda -theories is via observational equivalences [ MorrisTh ] : two \lambda -terms are equivalent if they display the same behaviour whenever plugged in any context. For instance, the theory of Scott’s \mathcal{D}_{\infty} model [ Scott72 ] captures the maximal consistent observational equivalence [ Hyland75 , Wadsworth76 ] . Since the \lambda -calculus is an equationally conservative extension of the \lambda\mathsf{I} -calculus, every theory of the former is also a theory of the latter, namely a \lambda\mathsf{I} -theory , while the converse does not hold. A typical example is the \lambda\mathsf{I} -theory \mathcal{H}_{\mathsf{I}} generated by equating all \lambda\mathsf{I} -terms that are not \beta -normalizing. The maximal consistent observational equivalence \mathcal{H}_{\mathsf{I}}^{\eta} is similar, except for the fact that it is extensional. Note that equating all \lambda -terms without a \beta -normal form gives rise to an inconsistent \lambda -theory, but in the context of \lambda\mathsf{I} -calculus it is consistent and arises naturally: all “proper” denotational models of the \lambda\mathsf{I} -calculus studied so far induce either \mathcal{H}_{\mathsf{I}} or \mathcal{H}_{\mathsf{I}}^{\eta} [ HonsellL93 ] . This is somewhat disappointing, since models and theories are most valuable when they capture non-trivial operational properties of programs, and normalization is relatively elementary in this setting. In this paper we introduce a new \lambda\mathsf{I} -theory, induced by a notion of evaluation trees inspired by Böhm trees, but explicitly designed for \lambda\mathsf{I} -terms. Böhm trees and Taylor expansion for the \lambda\mathsf{I} -calculus An important feature of Böhm trees is that, because of their coinductive nature, they are capable of pushing some subterms into infinity. Consider for instance a \lambda\mathsf{I} -term M_{xf} containing free variables x,f and satisfying M_{xf}\mathrel{\rightarrow\mathrel{\mkern-14.0mu}\rightarrow}_{\beta}f(M_{xf})\mathrel{\rightarrow\mathrel{\mkern-14.0mu}\rightarrow}_{\beta}f(f(M_{xf}))\mathrel{\rightarrow\mathrel{\mkern-14.0mu}\rightarrow}_{\beta}f(f(f(M_{xf})))\mathrel{\rightarrow\mathrel{\mkern-14.0mu}\rightarrow}_{\beta}f^{n}(M_{xf})\mathrel{\rightarrow\mathrel{\mkern-14.0mu}\rightarrow}_{\beta}\cdots then the Böhm tree of M_{xf} is the limit of this infinite sequence, namely f^{\omega}=f(f(f(\cdots))) . Observe that x is “persistent” in the sense that it is never erased along any finite reduction, but disappears in the limit. We say that x is pushed into infinity or forgotten in the Böhm tree of M_{xf} . To some extent, also the variable f is pushed into infinity, but it occurs infinitely often in f^{\omega} . A variable x can also disappear because it is hidden behind a meaningless term like \mathsf{\Omega}=(\lambda y.yy)(\lambda y.yy) . For instance, the Böhm tree of the \lambda\mathsf{I} -term N=\mathsf{\Omega}x is just \bot and we say that x is left behind . As a consequence there are \lambda\mathsf{I} -terms, like \lambda xf.M_{xf} and \lambda xy.y(\mathsf{\Omega}x) , whose Böhm tree is not a \lambda\mathsf{I} -tree [ Bare , Def. 10.1.26] since the variable x is abstracted, but does not appear in the tree. This shows that Böhm trees are not well-suited for the \lambda\mathsf{I} -calculus, and the question of whether other notions of trees can model