 | EasyChair Smart Slide | Docs/Log in |
Title:Counting Environments and Closures Tags:analytic generating function, asymptotic approximation, asymptotic growth rate, average case analysis, closed closure, closed term, combinatorial structure, combinatorics, complexity, counting environment, de bruijn index, de bruijn indices, de bruijn notation, de bruijn representation, functional programming, generating function, h shallow term, lambda-calculus, m open term, mathematical analysis, open h shallow term, philippe flajolet, plain environment, plain term, random generation, singularity analysis, super critical composition schema, term rewriting system, theoretical computer science and ugo dal lago Abstract: 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 environemnts 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.  |
|     |
