Tootfinder

Positive Sharing and Abstract Machines
Beniamino Accattoli, Claudio Sacerdoti Coen, Jui-Hsuan Wu
https://arxiv.org/abs/2506.14131 https://

Positive Sharing and Abstract Machines
Wu's positive $λ$-calculus is a recent call-by-value $λ$-calculus with sharing coming from Miller and Wu's study of the proof-theoretical concept of focalization. Accattoli and Wu showed that it simplifies a technical aspect of the study of sharing; namely it rules out the recurrent issue of renaming chains, that often causes a quadratic time slowdown. In this paper, we define the natural abstract machine for the positive $λ$-calculus and show that it suffers from an inefficiency: the quad…

Term Assignment and Categorical Models for Intuitionistic Linear Logic with Subexponentials
Daniel Rogozin
https://arxiv.org/abs/2507.12360 https://…

Term Assignment and Categorical Models for Intuitionistic Linear Logic with Subexponentials
In this paper, we present a typed lambda calculus ${\bf SILL}(λ)_Σ$, a type-theoretic version of intuitionistic linear logic with subexponentials, that is, we have many resource comonadic modalities with some interconnections between them given by a subexponential signature. We also give proof normalisation rules and prove the strong normalisation and Church-Rosser properties for $β$-reduction by adapting the Tait-Girard method to subexponential modalities. Further, we analyse subexponential…

Homogeneous Linear Calculus of Order 1 and a $\lambda$-Taylor Formula
Ronald Orozco L\'opez
https://arxiv.org/abs/2506.22976 https://

Homogeneous Linear Calculus of Order 1 and a $λ$-Taylor Formula
In this paper, a new calculus on sequences is defined. Also, the $λ$-derivative and the $λ$-integration are investigated. The fundamental theorem of $λ$-calculus is included. A suitable function basis for the $λ$-derivative and the $λ$-integral is provided, and various properties of this basis are given. A $λ$-Taylor formula for functions is given.

A simple formalization of alpha-equivalence
Kalmer Apinis, Danel Ahman
https://arxiv.org/abs/2507.10181 https://arxiv.org/pdf/2507.10…

A simple formalization of alpha-equivalence
While teaching untyped $λ$-calculus to undergraduate students, we were wondering why $α$-equivalence is not directly inductively defined. In this paper, we demonstrate that this is indeed feasible. Specifically, we provide a grounded, inductive definition for $α$-equivalence and show that it conforms to the specification provided in the literature. The work presented in this paper is fully formalized in the Rocq Prover.

Winner of the 2025 Alonzo Church Award

The 2025 Alonzo Church Award for Outstanding Contributions to Logic and Computation is presented to Paul Blain Levy for his fundamental study of effectful λ-calculi through the Call-by-Push-Value calculus.
Initiated by Alonzo Church, the research programme into the λ-calculus as an abstract model of computation has spurred volumes of fundamental research in logic and computation. By the end of the 20th century, the studies of the λ-cal…

From Partial to Monadic: Combinatory Algebra with Effects
Liron Cohen (BGU), Ariel Grunfeld (BGU), Dominik Kirst (PICUBE), \'Etienne Miquey (I2M)
https://arxiv.org/abs/2506.09453

From Partial to Monadic: Combinatory Algebra with Effects
Partial Combinatory Algebras (PCAs) provide a foundational model of the untyped $λ$-calculus and serve as the basis for many notions of computability, such as realizability theory. However, PCAs support a very limited notion of computation by only incorporating non-termination as a computational effect. To provide a framework that better internalizes a wide range of computational effects, this paper puts forward the notion of Monadic Combinatory Algebras (MCAs). MCAs generalize the notion of P…

This https://arxiv.org/abs/2505.20314 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csLO_…

$Δ$-Nets: Interaction-Based System for Optimal Parallel $λ$-Reduction
I present a model of universal parallel computation called $Δ$-Nets, and a method to translate $λ$-terms into $Δ$-nets and back. Together, the model and the method constitute an algorithm for optimal parallel $λ$-reduction, solving the longstanding enigma with groundbreaking clarity. I show that the $λ$-calculus can be understood as a projection of $Δ$-Nets -- one that severely restricts the structure of sharing, among other drawbacks. Unhindered by these restrictions, the $Δ$-Nets model…

This https://arxiv.org/abs/2405.03536 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csLO_…

Extensional and Non-extensional Functions as Processes
Following Milner's seminal paper, the representation of functions as processes has received considerable attention. For pure $λ$-calculus, the process representations yield (at best) non-extensional $λ$-theories (i.e., $β$ rule holds, whereas $η$ does not). In the paper, we study how to obtain extensional representations, and how to move between extensional and non-extensional representations. Using Internal $π$, $\mathrm{I}π$ (a subset of the $π$-calculus in which all outputs are boun…