Counting and generating terms in the binary lambda calculus*. (29th December 2015)

• Record Type: Journal Article
• Authors: GRYGIEL, KATARZYNA; LESCANNE, PIERRE
• Is Part Of: Journal of functional programming. Volume 25(2015)
• Publication Date: 2015-12-29
• Subjects: Functional programming (Computer science) -- Periodicals
• DOI: 10.1017/S0956796815000271
• Languages: English
• ISSNs: 0956-7968

Abstract

Abstract: In a paper, entitled Binary lambda calculus and combinatory logic, 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 n grows roughly like 1.963447954. . . n . In a second part we use this approach to generate random lambda terms using Boltzmann samplers.