Combinatorics of Explicit Substitutions - Archive ouverte HAL Access content directly
Conference Papers Year :

Combinatorics of Explicit Substitutions

(1) , (2)


λυ 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.

Dates and versions

ensl-01892388 , version 1 (10-10-2018)



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⟩
46 View
0 Download



Gmail Facebook Twitter LinkedIn More