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