Lazy Specialization

Abstract

This thesis describes a scheme to combine the benefits of lazy evaluation with partial evaluation. By performing specializations only when needed (lazily), the specialize-residualize decision is changed from being semantic to operational. It is demonstrated that a completely lazy evaluator is capable of eliminating towers of interpreters. The scheme is generalised, devising a new implementation of optimal evaluation, and it is demonstrated that optimal evaluators do not eliminate towers of interpreters. It is argued that the concept of scope has too often been overlooked in the lambda-calculus. A new system of depths is introduced in order to handle the issue of scope. The new approach leads to a much richer understanding of the issue of sharing in the lambda-calculus. Although optimal evaluators are well known, it is argued that less well understood degrees of sharing, in between the sharing of conventional functional languages and optimal evaluators, are of more practical use. A new classification of possible function body reduction strategies is shown to be analogous and orthogonal to argument reduction strategies.

Keywords: lambda calculus, partial evaluation, lazy evaluation, graph reduction, full laziness, complete laziness, optimal evaluation, de Bruijn notation, delayed substitution, tower of interpreters test.

Michael Jonathan Thyer, Lazy Specialization, PhD thesis, York, 1999.

PDF: Lazy Specialization