BRICS · Contents · Programme · References

An Overview of Lambda-Calculus Optimal Reductions and of their Implementation

A BRICS Mini-Course
February 24-26, 1999

Lectures by
Stefano Guerrini,
Department of Computer Science, Queen Mary and Westfield College, London, United Kingdom

Course Contents

Lambda-calculus optimal reductions were defined in Levy's dissertation in 78. Levy's optimal reductions rest on a beautiful abstraction of the intuitive concept of `sharable redex'. This abstraction led Levy to find a lower-bound for the cost of the reduction of a lambda-term T by any conceivable reduction machine capable to reduce, in a single step, all the sharable redexes in T. Unfortunately, Levy did not give any actual machine satisfying that optimality requirement. A brilliant solution for the problem was proposed by Lamping more than 10 years later by means of the so-called sharing graph reductions. Lamping's sharing graph technique was successively improved by several researchers (the list includes Gonthier, Asperti, Laneve, Danos, Regnier, etc.) that discovered surprising connections with Linear Logic and Geometry of Interaction. Finally, Asperti and Mairson proved that there is no chance to get an optimal reduction machine, at least in the tight sense defined by Levy, for this would contradict the time hierarchy theorem. Nevertheless, this does not decrease the relevance of optimal reductions and of sharing graphs. It only shows that the computational complexity of lambda-calculus cannot be captured by counting beta-rules only, neither by extending beta-rule to a rule reducing in parallel all the sharable redexes in a term.

In this mini-course, we want to focus on the main ideas behind optimal reductions and sharing reductions. For the amount and the complexity of the results that we want to analyze, there will be no time for a lot of details. The main aim is at justifying why optimal reductions and sharing graphs are milestones in the quest for understanding the computational complexity of beta-reduction, and in which sense Asperti-Mairson result opens new and interesting problems in the field.


Wednesday February 24, 1999, 15:15-17:00 in Auditorium D4

Levy's optimal reductions. Definition of family and family reduction. Labeled lambda-calculus.

Thursday February 25, 1999, 15:15-17:00 in Auditorium D4

Labels and paths. Sharing graphs and sharing reductions.

Friday February 26, 1999, 15:15-17:00 in Auditorium D4

eta-expansion. Asperti-Mairson result: family recursion in not Kalmar elementar. Examples and conclusions.


  1. Andrea Asperti and Stefano Guerrini. The Optimal Implementation of Functional Programming Languages. Vol. 45 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1998.