## Authors: Maciej Bendkowski and Pierre Lescanne

## Paper Information

Title: | Combinatorics of explicit substitutions (extended abstract) |

Authors: | Maciej Bendkowski and Pierre Lescanne |

Proceedings: | HOR Pre-proceedings |

Editor: | Stefano Guerrini |

Keywords: | explicit substitution, combinatorics, Catalan numbers, random generation |

Abstract: | ABSTRACT. lambda-upsilon is an extension of the lambda-calculus which internalises the calculus of substitutions. In the current paper, we investigate the combinatorial properties of lambda-upsilon focusing on the quantitative aspects of substitution resolution. We exhibit an unexpected correspondence between the counting sequence for lambda-upsilon terms and famous Catalan numbers. As a by-product, we establish effective sampling schemes for random lambda-upsilon terms. We show that typical lambda-upsilon terms represent, in a strong sense, non-strict computations in the classic lambda-calculus. Moreover, typically almost all substitutions are in fact suspended, i.e., unevaluated, under closures. Consequently, we argue that lambda-upsilon is an intrinsically non-strict calculus of explicit substitutions. Finally, we investigate the distribution of various redexes governing the substitution resolution in lambda-upsilon and investigate the quantitative contribution of various substitution primitives. |

Pages: | 6 |

Talk: | Jul 07 10:00 (Session 25) |

Paper: |