一句话：研究 lambda 演算中普通与封闭环境和闭包的渐近计数，并用生成函数构造有效随机采样器。
该论文研究 lambda 演算求值中环境与闭包的组合计数性质。闭包由 lambda 项与环境组成，环境则是绑定自由变量的 lambda 项列表。作者针对普通（plain）与封闭（closed）两类环境/闭包，分析其规模为 n 时的渐近计数问题，给出普通环境与闭包数量的渐近近似。借助与这些组合类相关的生成函数，他们构造了有效的随机采样器，可生成对应规模的环境与闭包。最后还讨论封闭环境与闭包的渐近计数和随机生成问题。
Environments and closures are two of the main ingredients of evaluation in lambda-calculus. A closure is a pair consisting of a lambda-term and an environment, whereas an environment is a list of lambda-terms assigned to free variables. In this paper we investigate some dynamic aspects of evaluation in lambda-calculus considering the quantitative, combinatorial properties of environments and closures. Focusing on two classes of environments and closures, namely the so-called plain and closed ones, we consider the problem of their asymptotic counting and effective random generation. We provide an asymptotic approximation of the number of both plain environments and closures of size $n$. Using the associated generating functions, we construct effective samplers for both classes of combinatorial structures. Finally, we discuss the related problem of asymptotic counting and random generation of closed environemnts and closures.
@article{paperbot749,
title = {On the enumeration of closures and environments with an application to random generation},
author = {Maciej Bendkowski and Pierre Lescanne},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 4},
year = {2019},
doi = {10.23638/lmcs-15(4:3)2019}
}