×

zbMATH — the first resource for mathematics

Counting and generating terms in the binary lambda calculus. (English) Zbl 1419.68039
Summary: In a paper [in: Randomness and complexity. From Leibniz to Chaitin. Dedicated to Gregory J. Chaitin on the occasion of his 60th birthday. Hackensack, NJ: World Scientific. 237–260 (2007; Zbl 1137.68020)], J. Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive results from their generating functions, especially that the number of terms of size \(n\) grows roughly like \(1.963447954\dots^n\). In a second part we use this approach to generate random lambda terms using Boltzmann samplers.

MSC:
68N18 Functional programming and lambda calculus
03B40 Combinatory logic and lambda calculus
05A15 Exact enumeration problems, generating functions
Software:
Haskell
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bacher, A.; Bodini, O.; Jacquot, A., (2014)
[2] Bodini, O.; Gardy, D.; Gittenberger, B., (2011)
[3] Bodini, O.; Gardy, D.; Jacquot, A., Asymptotics and random sampling for BCI and BCK lambda terms., Theor. Comput. Sci., 502, 227-238, (2013) · Zbl 1297.68184
[4] Bodini, O.; Gardy, D.; Gittenberger, B.; Jacquot, A., Enumeration of generalized BCI lambda-terms, Electr. J. Comb., 20, P30, (2013) · Zbl 1295.05040
[5] Claessen, K.; Hughes, J.; Odersky, M.; Wadler, P., (2000)
[6] David, R.; Grygiel, K.; Kozik, J.; Raffalli, C.; Theyssier, G.; Zaionc, M., Asymptotically almost all λ-terms are strongly normalizing, Log. Methods Comput. Sci., 9, 1-30, (2013) · Zbl 1278.03034
[7] De Bruijn, N. G., Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem, Indagationes Math., 34, 381-392, (1972) · Zbl 0253.68007
[8] Duchon, P.; Flajolet, P.; Louchard, G.; Schaeffer, G., Boltzmann samplers for the random generation of combinatorial structures, Comb. Probab. Comput., 13, 577-625, (2004) · Zbl 1081.65007
[9] Flajolet, P.; Pivoteau, C., (2007)
[10] Flajolet, P.; Sedgewick, R., Analytic Combinatorics, (2008), Cambridge University Press
[11] Grygiel, K.; Lescanne, P., Counting and generating lambda terms, J. Funct. Program., 23, 594-628, (2013) · Zbl 1311.68045
[12] Grygiel, K.; Lescanne, P., (2014)
[13] Hindley, J. R., Basic Simple Type Theory, (1997), Cambridge University Press · Zbl 0906.03012
[14] Karttunen, A., (2015)
[15] Knuth, D. E., The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees, History of Combinatorial Generation (Art of Computer Programming), (2006), Addison-Wesley
[16] Lescanne, P.; Boehm, H., (1994)
[17] Lescanne, P., On counting untyped lambda terms., Theor.Comput. Sci., 474, 80-97, (2013) · Zbl 1259.68028
[18] Li, M.; Vitányi, P., An Introduction to Kolmogorov Complexity and its Applications, (2008), New York, Inc: Springer-Verlag, New York, Inc · Zbl 1185.68369
[19] Nijenhuis, A.; Wilf, H. S., Combinatorial Algorithms, (1978), New York: Academic Press, New York · Zbl 0476.68047
[20] Peyton Jones, S., Haskell 98 Language and Libraries: The Revised Report, (2003), Cambridge University Press · Zbl 1067.68041
[21] Rémy, J.-L., Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, ITA, 19, 179-195, (1985) · Zbl 0565.05037
[22] Tarau, P., (2015)
[23] Tromp, J.; Hutter, M.; Merkle, W.; Vitányi, P. M. B., Kolmogorov Complexity and Applications, Binary lambda calculus and combinatory logic, (2006), Schloss Dagstuhl: Schloss Dagstuhl, Germany
[24] Wang, J., (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.