On Uniquely Closable and Uniquely Typable Skeletons of Lambda Terms
Preprint
Abstract
Uniquely closable skeletons of lambda terms are Motzkin-trees that predetermine the unique closed lambda term that can be obtained by labeling their leaves with de Bruijn indices. Likewise, uniquely typable skeletons of closed lambda terms predetermine the unique simply-typed lambda term that can be obtained by labeling their leaves with de Bruijn indices. We derive, through a sequence of logic program transformations, efficient code for their combinatorial generation and study their statistical properties. As a result, we obtain context-free grammars describing closable and uniquely closable skeletons of lambda terms, opening the door for their in-depth study with tools from analytic combinatorics. Our empirical study of the more difficult case of (uniquely) typable terms reveals some interesting open problems about their density and asymptotic behavior. As a connection between the two classes of terms, we also show that uniquely typable closed lambda term skeletons of size $3n+1$ are in a bijection with binary trees of size $n$.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- The on-line encyclopedia of integer sequencesNotices of the American Mathematical Society, 2018
- Counting and generating terms in the binary lambda calculusJournal of Functional Programming, 2015
- Efficient generation of test data structures using constraint logic programming and program transformationJournal of Logic and Computation, 2013
- Counting and generating lambda termsJournal of Functional Programming, 2013
- Asymptotics and random sampling for BCI and BCK lambda termsTheoretical Computer Science, 2013
- On counting untyped lambda termsTheoretical Computer Science, 2013
- SWI-PrologTheory and Practice of Logic Programming, 2011
- Transformation of logic programs: Foundations and techniquesThe Journal of Logic Programming, 1994
- Lambda Calculus Notation with Nameless Dummies, a Tool for Automatic Formula Manipulation, with Application to the Church-Rosser Theorem1994
- Singularity Analysis of Generating FunctionsSIAM Journal on Discrete Mathematics, 1990