There are various approaches to evaluating lambda terms. In the same article, I also discuss the possibility to have superoptimal ' About the efficient reduction of lambda terms'. I recently wrote a short article trying to explain these issues: That difference, in practice: both computations are just unfeasible. To reduce a term in time O(2^n) instead of O(2^(2^n)) does not make all With a really high rank, and when you do they are frequently linear.Īs soon as you raise the rank, the intrinsic complexity of lambda

In the practice of functional programming you very seldom use functionals The reason functional languages are not yet implemented in this way is that

Reduction is faster than other techniques, it is not true: it was proved both So, if you hear people saying that it has never been proved that optimal Proved that our implementation outperformed both caml-light (the precursor Some benchmarks are given in the above book (see pag.296-301), where we Reduction techniques (environment machine, supercombinators, or whatever). On pure lambda terms, optimal graph reduction is faster than all other known

Graphs (dags) are enough for managing sharing, but as soon as you enter in a higher order setting you need more complex graph structures comprising In a first order setting, directed acyclic In lambda calculus you have a lot of duplication and the efficiency of the reduction is cruciallyīased on avoding replicating work. The term 'optimal' refers to the management of sharing. You may find a survey in my book with S.Guerrini ' The optimal implementation of functional programming languages', Cambridge Tracts in Theoretical Computer Science n.45, 1998. The technique was introduced in 1989 by J.Lamping in his POPL article ' An algorithm for optimal lambda calculus reduction', and then revised and improved by several authors. At the current state of knowledge, the best way of evaluating lambda terms is the so called optimal graph reduction technique.

Lambda calculus normalise