print · source · login   

Maciej Bendkowski

Jagiellonian University

Statistical properties and evaluation of random λ-terms -- a survey

In the talk we discuss selected enumerative and statistical results regarding random λ-terms in the de Bruijn notation. In particular, we investigate the distribution of various combinatorial parameters of closed lambda terms, including the number of β-redexes, head abstractions, free variables or the de Bruijn index value profile. Moreover, we analyse the cost of finding the leftmost-outermost β-redex in a random λ-term, showing that it is, on average, constant. Finally, we overview a recent, new approach towards the average-case analysis of substitution resolution in λ-calculus, based on the quantitative analysis of so-called calculi of explicit substitutions.