{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T21:54:44Z","timestamp":1693864484420},"reference-count":24,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2015,12,29]],"date-time":"2015-12-29T00:00:00Z","timestamp":1451347200000},"content-version":"unspecified","delay-in-days":362,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2015]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In a paper, entitled<jats:italic>Binary lambda calculus and combinatory logic<\/jats:italic>, John 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<jats:italic>n<\/jats:italic>grows roughly like 1.963447954.\u00a0.\u00a0.<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>. In a second part we use this approach to generate random lambda terms using Boltzmann samplers.<\/jats:p>","DOI":"10.1017\/s0956796815000271","type":"journal-article","created":{"date-parts":[[2015,12,29]],"date-time":"2015-12-29T04:08:23Z","timestamp":1451362103000},"source":"Crossref","is-referenced-by-count":12,"title":["Counting and generating terms in the binary lambda calculus"],"prefix":"10.1017","volume":"25","author":[{"given":"KATARZYNA","family":"GRYGIEL","sequence":"first","affiliation":[]},{"given":"PIERRE","family":"LESCANNE","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2015,12,29]]},"reference":[{"key":"S0956796815000271_ref24","unstructured":"Wang J. 2004 (May). The Efficient Generation of Random Programs and their Applications. Honors Thesis, Wellesley College, Wellesley, MA."},{"key":"S0956796815000271_ref23","volume-title":"Kolmogorov Complexity and Applications","author":"Tromp","year":"2006"},{"key":"S0956796815000271_ref21","first-page":"179","article-title":"Un proc\u00e9d\u00e9 it\u00e9ratif de d\u00e9nombrement d'arbres binaires et son application \u00e0 leur g\u00e9n\u00e9ration al\u00e9atoire","volume":"19","author":"R\u00e9my","year":"1985","journal-title":"ITA"},{"key":"S0956796815000271_ref19","volume-title":"Combinatorial Algorithms","author":"Nijenhuis","year":"1978"},{"key":"S0956796815000271_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49820-1"},{"key":"S0956796815000271_ref16","unstructured":"Lescanne P. (1994) From \u03bb\u03c3 to \u03bb\u03c5, a journey through calculi of explicit substitutions. In Boehm H. (ed), Proceedings of the 21st Annual ACM Symposium on Principles of Programming Languages, Portland (Or., USA), ACM, pp. 60\u201369."},{"key":"S0956796815000271_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511608865"},{"key":"S0956796815000271_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"S0956796815000271_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(72)90034-0"},{"key":"S0956796815000271_ref20","volume-title":"Haskell 98 Language and Libraries: The Revised Report","author":"Peyton Jones","year":"2003"},{"key":"S0956796815000271_ref4","doi-asserted-by":"crossref","first-page":"P30","DOI":"10.37236\/3051","article-title":"Enumeration of generalized BCI lambda-terms","volume":"20","author":"Bodini","year":"2013","journal-title":"Electr. J. Comb."},{"key":"S0956796815000271_ref15","volume-title":"The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees, History of Combinatorial Generation (Art of Computer Programming)","author":"Knuth","year":"2006"},{"key":"S0956796815000271_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796813000178"},{"key":"S0956796815000271_ref10","volume-title":"Analytic Combinatorics","author":"Flajolet","year":"2008"},{"key":"S0956796815000271_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973013.3"},{"key":"S0956796815000271_ref1","unstructured":"Bacher A. , Bodini O. & Jacquot A. (2014) Efficient random sampling of binary and unary-binary trees via holonomic equations. Corr, abs\/1401.1140."},{"key":"S0956796815000271_ref12","unstructured":"Grygiel K. & Lescanne P. (2014) Counting terms in the binary lambda calculus. Corr, abs\/1401.0379. Published in the Proceedings of 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Available at: https:\/\/hal.inria.fr\/hal-01077251."},{"key":"S0956796815000271_ref14","unstructured":"Karttunen A. (2015) Ranking and Unranking Functions. OEIS Wiki. Available at: http:\/\/oeis.org\/wiki\/Ranking_and_unranking_functions."},{"key":"S0956796815000271_ref6","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(1:2)2013"},{"key":"S0956796815000271_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972979.5"},{"key":"S0956796815000271_ref22","unstructured":"Tarau P. (2015) On type-directed generation of lambda terms. In Proceedings of the 31st International Conference on Logic Programming (ICLP 2015), Available at: http:\/\/dblp.uni-trier.de\/rec\/bibtex\/conf\/iclp\/Tarau15."},{"key":"S0956796815000271_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.11.019"},{"key":"S0956796815000271_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.008"},{"key":"S0956796815000271_ref5","unstructured":"Claessen K. & Hughes J. (2000) QuickCheck: A lightweight tool for random testing of Haskell programs. In ICFP, Odersky M. & Wadler P. (eds), ACM, pp. 268\u2013279."}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796815000271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,13]],"date-time":"2020-09-13T08:41:12Z","timestamp":1599986472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796815000271\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":24,"alternative-id":["S0956796815000271"],"URL":"https:\/\/doi.org\/10.1017\/s0956796815000271","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"article-number":"e24"}}