Skip to Main content Skip to Navigation
Conference papers

Combinatorics of Explicit Substitutions

Abstract : λυ is an extension of the λ-calculus which internalises the calculus of substitutions. In the current paper, we investigate the combinatorial properties of λυ focusing on the quantitative aspects of substitution resolution. We exhibit an unexpected correspondence between the counting sequence for λυ terms~and famous Catalan numbers. As a by-product, we establish effective sampling schemes for random λυ terms. We show that typical λυ terms~represent, in a strong sense, non-strict computations in the classic λ-calculu. Moreover, typically almost all substitutions are in fact suspended, i.e.~unevaluated, under closures. Consequently, we argue that λυ is an intrinsically non-strict calculus of explicit substitutions. Finally, we investigate the distribution of various redexes governing the substitution resolution in λυ and investigate the quantitative contribution of various substitution primitives.
Complete list of metadata
Contributor : Pierre Lescanne <>
Submitted on : Wednesday, October 10, 2018 - 3:41:59 PM
Last modification on : Thursday, November 21, 2019 - 2:36:20 AM

Links full text




Maciej Bendkowski, Pierre Lescanne. Combinatorics of Explicit Substitutions. PPDP 2016, ACM et Université de Francfort de, Sep 2018, Frankfurt am Main, France. ⟨10.1145/3236950.3236951⟩. ⟨ensl-01892388⟩



Record views