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 metadatas

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01892388
Contributor : Pierre Lescanne <>
Submitted on : Wednesday, October 10, 2018 - 3:41:59 PM
Last modification on : Friday, May 17, 2019 - 12:16:41 PM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

51