Tootfinder

Intersection Types via Finite-Set Declarations
Fairouz Kamareddine, Joe Wells
https://arxiv.org/abs/2405.00440 https://arxiv.org/pdf/…

Intersection Types via Finite-Set Declarations
The lambda-cube is a famous pure type system (PTS) cube of eight powerful explicit type systems that include the simple, polymorphic and dependent type theories. The lambda-cube only types Strongly Normalising (SN) terms but not all of them. It is well known that even the most powerful system of the lambda-cube can only type the same pure untyped lambda-terms that are typable by the higher-order polymorphic implicitly typed lambda-calculus Fomega, and that there is an untyped λ-term U' that is…

The Essense of Useful Evaluation Through Quantitative Types (Extended Version)
Pablo Barenbaum, Delia Kesner, Mariana Milicich
https://arxiv.org/abs/2404.18874

The Essense of Useful Evaluation Through Quantitative Types (Extended Version)
Several evaluation notions for lambda calculus qualify as reasonable cost models according to Slot and van Emde Boas' Invariance Thesis. A notable result achieved by Accattoli and Dal Lago is that leftmost-outermost reduction is reasonable, where the term representation uses sharing and the steps are useful. These results, initially studied in call-by-name, have also been extended to call-by-value. However, the existing formulations of usefulness lack inductive structure, making it challenging …

(Towards a) Statistical Probabilistic Lazy Lambda Calculus
Radha Jagadeesan
https://arxiv.org/abs/2403.15570 https://arxiv.org/pdf/24…

(Towards a) Statistical Probabilistic Lazy Lambda Calculus
We study the desiderata on a model for statistical probabilistic programming languages. We argue that they can be met by a combination of traditional tools, namely open bisimulation and probabilistic simulation.

(Towards a) Statistical Probabilistic Lazy Lambda Calculus
Radha Jagadeesan
https://arxiv.org/abs/2403.15570 https://arxiv.org/pdf/24…

(Towards a) Statistical Probabilistic Lazy Lambda Calculus
We study the desiderata on a model for statistical probabilistic programming languages. We argue that they can be met by a combination of traditional tools, namely open bisimulation and probabilistic simulation.

Profinite trees, through monads and the lambda-calculus
Vincent Moreau
https://arxiv.org/abs/2402.13086 https://arxiv.org/pdf/2402.13…

Profinite trees, through monads and the lambda-calculus
In its simplest form, the theory of regular languages is the study of sets of finite words recognized by finite monoids. The finiteness condition on monoids gives rise to a topological space whose points, called profinite words, encode the limiting behavior of words with respect to finite monoids. Yet, some aspects of the theory of regular languages are not particular to monoids and can be described in a general setting. On the one hand, Bojańczyk has shown how to use monads to generalize the …

From Rewrite Rules to Axioms in the $\lambda$$\Pi$-Calculus Modulo Theory
Valentin BlotDEDUCTEAM, LMF, ENS Paris Saclay, Gilles DowekDEDUCTEAM, LMF, ENS Paris Saclay, Thomas Traversi\'eDEDUCTEAM, LMF, ENS Paris Saclay, MICS, Th\'eo WinterhalterDEDUCTEAM, LMF, ENS Paris Saclay
https://arxiv.org/abs/2402.09024

From Rewrite Rules to Axioms in the $λ$$Π$-Calculus Modulo Theory
The $λ$$Π$-calculus modulo theory is an extension of simply typed $λ$-calculus with dependent types and user-defined rewrite rules. We show that it is possible to replace the rewrite rules of a theory of the $λ$$Π$-calculus modulo theory by equational axioms, when this theory features the notions of proposition and proof, while maintaining the same expressiveness. To do so, we introduce in the target theory a heterogeneous equality, and we build a translation that replaces each use of the …

Mirroring Call-by-Need, or Values Acting Silly
Beniamino Accattoli, Adrienne Lancelot
https://arxiv.org/abs/2402.12078 https://arxiv.…

Mirroring Call-by-Need, or Values Acting Silly
Call-by-need evaluation for the lambda-calculus can be seen as merging the best of call-by-name and call-by-value, namely the wise erasing behaviour of the former and the wise duplicating behaviour of the latter. To better understand how duplication and erasure can be combined, we design a degenerated calculus, dubbed call-by-silly, that is symmetric to call-by-need in that it merges the worst of call-by-name and call-by-value, namely silly duplications by-name and silly erasures by-value. We…

On the complexity of normalization for the planar $\lambda$-calculus
Anupam Das, Damiano Mazza, L\^e Th\`anh D\~ung Nguy\^en, Noam Zeilberger
https://arxiv.org/abs/2404.05276

On the complexity of normalization for the planar $λ$-calculus
We sketch a tentative proof of P-completeness for the $β$-convertibility problem on untyped planar (a.k.a. ordered or non-commutative) $λ$-terms.

This https://arxiv.org/abs/2305.12601 has been replaced.
link: https://scholar.google.com/scholar?q=a

Simply typed convertibility is TOWER-complete even for safe lambda-terms
We consider the following decision problem: given two simply typed $λ$-terms, are they $β$-convertible? Equivalently, do they have the same normal form? It is famously non-elementary, but the precise complexity - namely TOWER-complete - is lesser known. One goal of this short paper is to popularize this fact. Our original contribution is to show that the problem stays TOWER-complete when the two input terms belong to Blum and Ong's safe $λ$-calculus, a fragment of the simply typed $λ$-cal…

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

A General Probabilistic Framework in IMALL: A Concrete Categorical Perspective
We consider the linear lambda-calculus extended with the sup type constructor, which provides an additive conjunction along with a non-deterministic destructor. The sup type constructor has been introduced in the context of quantum computing. In this paper, we study this type constructor within a simple linear logic categorical model, employing the category of semimodules over a commutative semiring. We demonstrate that the non-deterministic destructor, either weighted or not, finds a suitable …

Linear Contextual Metaprogramming and Session Types
Pedro \^Angelo (LIACC,Faculdade de Ci\^encias da Universidade do Porto, Portugal), Atsushi Igarashi (Kyoto University, Kyoto, Japan), Vasco T. Vasconcelos (LASIGE, Faculdade de Ci\^encias da Universidade de Lisboa, Portugal)
https://arxiv.org/abs/2404.05475

Linear Contextual Metaprogramming and Session Types
We explore the integration of metaprogramming in a call-by-value linear lambda-calculus and sketch its extension to a session type system. We build on a model of contextual modal type theory with multi-level contexts, where contextual values, closing arbitrary terms over a series of variables, may then be boxed and transmitted in messages. Once received, one such value may then be unboxed (with a let-box construct) and locally applied before being run. We present a series of examples where serv…