Counting and generating lambda terms
From MaRDI portal
Abstract: Lambda calculus is the basis of functional programming and higher order proof assistants. However, little is known about combinatorial properties of lambda terms, in particular, about their asymptotic distribution and random generation. This paper tries to answer questions like: How many terms of a given size are there? What is a "typical" structure of a simply typable term? Despite their ostensible simplicity, these questions still remain unanswered, whereas solutions to such problems are essential for testing compilers and optimizing programs whose expected efficiency depends on the size of terms. Our approach toward the afore-mentioned problems may be later extended to any language with bound variables, i.e., with scopes and declarations. This paper presents two complementary approaches: one, theoretical, uses complex analysis and generating functions, the other, experimental, is based on a generator of lambda-terms. Thanks to de Bruijn indices, we provide three families of formulas for the number of closed lambda terms of a given size and we give four relations between these numbers which have interesting combinatorial interpretations. As a by-product of the counting formulas, we design an algorithm for generating lambda terms. Performed tests provide us with experimental data, like the average depth of bound variables and the average number of head lambdas. We also create random generators for various sorts of terms. Thereafter, we conduct experiments that answer questions like: What is the ratio of simply typable terms among all terms? (Very small!) How are simply typable lambda terms distributed among all lambda terms? (A typable term almost always starts with an abstraction.) In this paper, abstractions and applications have size 1 and variables have size 0.
Recommendations
- A hiking trip through the orders of magnitude: deriving efficient generators for closed simply-typed lambda terms and normal forms
- Counting and generating terms in the binary lambda calculus
- Enumerating lambda terms by weighted length of their de Bruijn representation
- On counting untyped lambda terms
- Lambda terms of bounded unary height
Cited in
(26)- On uniquely closable and uniquely typable skeletons of lambda terms
- Enumerating lambda terms by weighted length of their de Bruijn representation
- On the number of unary-binary tree-like structures with restrictions on the unary height
- On counting untyped lambda terms
- On some enumerative problems in lambda calculus
- Statistical properties of lambda terms
- A hiking trip through the orders of magnitude: deriving efficient generators for closed simply-typed lambda terms and normal forms
- Almost every simply typed -term has a long -reduction sequence
- scientific article; zbMATH DE number 1808200 (Why is no real title available?)
- Ranking/unranking of lambda terms with compressed de Bruijn indices
- Enumeration of generalized BCI lambda-terms
- scientific article; zbMATH DE number 1222102 (Why is no real title available?)
- Combinatorics of \(\lambda\)-terms: a natural approach
- Random generation of closed simply typed λ-terms: A synergy between logic programming and Boltzmann samplers
- scientific article; zbMATH DE number 7029315 (Why is no real title available?)
- scientific article; zbMATH DE number 845591 (Why is no real title available?)
- On the enumeration of closures and environments with an application to random generation
- Deriving efficient sequential and parallel generators for closed simply-typed lambda terms and normal forms
- Counting environments and closures
- On the number of variables in special classes of random lambda-terms
- scientific article; zbMATH DE number 7455712 (Why is no real title available?)
- Sampling -normal linear -terms
- Lambda terms of bounded unary height
- Generating constrained random data with uniform distribution
- Counting and generating terms in the binary lambda calculus
- Normal-order reduction grammars
This page was built for publication: Counting and generating lambda terms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5398332)
