Versions disponibles : v1 (09-10-2012) v2 (15-12-2012) v3 (07-01-2013) v4 (04-02-2013) v5 (11-04-2013) v6 (24-04-2013) v7 (04-07-2013)
ensl-00740034, version 7
arXiv:1210.2610
 Informatique/Logique en informatique Informatique/Algorithme et structure de données
Counting and generating lambda terms
Katarzyna Grygiel1, Pierre Lescanne1, 2
 1 : TCS - Theoretical Computer Science Department 2 : LIP - Laboratoire de l'Informatique du Parallélisme
Plume
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.
Anglais
Lambda calculus – combinatorics – functional programming – test – random generator – ranking – unranking
F.3.2 Semantics of Programming Languages F.2.2 Nonnumerical Algorithms and Problems
Liste des fichiers attachés à ce document :
 PDF
 KG_PL_Counting_Lambdas.pdf(600.9 KB)
 ensl-00740034, version 7 http://hal-ens-lyon.archives-ouvertes.fr/ensl-00740034 oai:hal-ens-lyon.archives-ouvertes.fr:ensl-00740034 Contributeur : Pierre Lescanne <> Soumis le : Mercredi 3 Juillet 2013, 10:11:54 Dernière modification le : Jeudi 4 Juillet 2013, 08:16:19