License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2018.11
URN: urn:nbn:de:0030-drops-91817
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9181/
Go to the corresponding LIPIcs Volume Portal

Bendkowski, Maciej ; Lescanne, Pierre

Counting Environments and Closures

pdf-format:
LIPIcs-FSCD-2018-11.pdf (0.5 MB)

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 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 environments and closures.

BibTeX - Entry

@InProceedings{bendkowski_et_al:LIPIcs:2018:9181,
  author =	{Maciej Bendkowski and Pierre Lescanne},
  title =	{{Counting Environments and Closures}},
  booktitle =	{3rd International Conference on Formal Structures for  Computation and Deduction (FSCD 2018)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-077-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{108},
  editor =	{H{\'e}l{\`e}ne Kirchner},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9181},
  URN =		{urn:nbn:de:0030-drops-91817},
  doi =		{10.4230/LIPIcs.FSCD.2018.11},
  annote =	{Keywords: lambda-calculus, combinatorics, functional programming, mathematical analysis, complexity}
}

Keywords: lambda-calculus, combinatorics, functional programming, mathematical analysis, complexity
Collection: 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI