{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:06:04Z","timestamp":1779836764633,"version":"3.53.1"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2013,10,30]],"date-time":"2013-10-30T00:00:00Z","timestamp":1383091200000},"content-version":"unspecified","delay-in-days":59,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    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 \u2018typical\u2019 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 aforementioned 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 (de Bruijn, N. (1972) Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem.\n                    <jats:italic>Indagat. Math.<\/jats:italic>\n                    <jats:bold>34<\/jats:bold>\n                    (5), 381\u2013392), 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 \u03bb-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? (\n                    <jats:italic>Very small!<\/jats:italic>\n                    ) How are simply typable lambda terms distributed among all lambda terms? (\n                    <jats:italic>A typable term almost always starts with an abstraction<\/jats:italic>\n                    .) In this paper, abstractions and applications have size 1 and variables have size 0.\n                  <\/jats:p>","DOI":"10.1017\/s0956796813000178","type":"journal-article","created":{"date-parts":[[2013,10,30]],"date-time":"2013-10-30T06:22:06Z","timestamp":1383114126000},"page":"594-628","source":"Crossref","is-referenced-by-count":27,"title":["Counting and generating lambda terms"],"prefix":"10.1017","volume":"23","author":[{"given":"KATARZYNA","family":"GRYGIEL","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"PIERRE","family":"LESCANNE","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2013,10,30]]},"reference":[{"key":"S0956796813000178_ref28","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/1993498.1993532","volume-title":"Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2011)","author":"Yang","year":"2011"},{"key":"S0956796813000178_ref27","unstructured":"Wang J. (2005) Generating Random Lambda Calculus Terms. Citeseer. Available at: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.95.2624. Accessed October 17, 2013."},{"key":"S0956796813000178_ref26","unstructured":"Wang J. (2004, May) The Efficient Generation of Random Programs and Their Applications, MPhil thesis, Honors Thesis, Wellesley College, Wellesley, MA."},{"key":"S0956796813000178_ref23","unstructured":"Stein W. et al. (2012) Sage Mathematics Software (Version 4.8) (The Sage Development Team). Available at: http:\/\/www.sagemath.org. Accessed October 17, 2013."},{"key":"S0956796813000178_ref22","first-page":"93","volume-title":"Third International Workshop, AAIP","author":"Rodriguez","year":"2009"},{"key":"S0956796813000178_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1982595.1982615"},{"key":"S0956796813000178_ref20","volume-title":"Testing an Optimising Compiler by Generating Random Lambda Terms","author":"Pa\u0142ka","year":"2012"},{"key":"S0956796813000178_ref15","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1080\/00150517.2002.12428630","article-title":"On polynomials related to derivatives of the generative functions of the Catalan numbers","volume":"40","author":"Lang","year":"2002","journal-title":"Fibonacci Q."},{"key":"S0956796813000178_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(72)90034-0"},{"key":"S0956796813000178_ref4","first-page":"207","volume-title":"Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages","author":"Damas","year":"1982"},{"key":"S0956796813000178_ref24","unstructured":"The On-Line Encyclopedia of Integer Sequences (OEIS)\u00ae Wiki. (2013) Ranking and Unranking Functions. Available at: https:\/\/oeis.org\/wiki\/Ranking_and_unranking_functions. Accessed June 18, 2013."},{"key":"S0956796813000178_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"S0956796813000178_ref25","volume-title":"Kolmogorov Complexity and Applications","author":"Tromp","year":"2006"},{"key":"S0956796813000178_ref7","first-page":"61","volume-title":"Proceedings of the 5th ACM SIGPLAN Symposium on Haskell (Haskell 2012)","author":"Dureg\u00e5rd","year":"2012"},{"key":"S0956796813000178_ref8","volume-title":"Analytic Combinatorics","author":"Flajolet","year":"2008"},{"key":"S0956796813000178_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100017722"},{"key":"S0956796813000178_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.11.019"},{"key":"S0956796813000178_ref14","volume-title":"The Art of Computer Programming, Generating All Trees-History of Combinatorial Generation","author":"Knuth","year":"2006"},{"key":"S0956796813000178_ref16","first-page":"60","volume-title":"Proceedings of the 21st Annual ACM Symposium on Principles of Programming Languages","author":"Lescanne","year":"1994"},{"key":"S0956796813000178_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973013.3"},{"key":"S0956796813000178_ref10","volume-title":"Concrete Mathematics","author":"Graham","year":"1989"},{"key":"S0956796813000178_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000186"},{"key":"S0956796813000178_ref3","unstructured":"Curien P.-L. (2005) Introduction to linear logic and ludics, part I. Corr abs\/cs\/0501035. Accessed October 17, 2013. Available at: http:\/\/arxiv.org\/abs\/cs\/0501035."},{"key":"S0956796813000178_ref5","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(1:2)2013"},{"key":"S0956796813000178_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90004-2"},{"key":"S0956796813000178_ref11","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exm001"},{"key":"S0956796813000178_ref12","first-page":"257","volume-title":"Computational Logic. Essays in Honor of Alan Robinson","author":"Jouannaud","year":"1991"},{"key":"S0956796813000178_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796812000263"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796813000178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:37:03Z","timestamp":1779835023000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796813000178\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["S0956796813000178"],"URL":"https:\/\/doi.org\/10.1017\/s0956796813000178","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}