| ||||
| ||||
![]() Title:Combinatorics of explicit substitutions (extended abstract) Conference:HOR 18 Tags:Catalan numbers, combinatorics, explicit substitution and random generation 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. Combinatorics of explicit substitutions (extended abstract) ![]() Combinatorics of explicit substitutions (extended abstract) | ||||
Copyright © 2002 – 2025 EasyChair |