Having seen some of the principles of partial evaluation we now consider practicalities. In this chapter we will study the standard algorithm used in partial evaluation and introduce an extended example which we develop throughout the thesis. The material of this chapter draws very heavily on the experience of the DIKU group and much of the material presented here may be found in [JSS85], [Ses86] and [JSS89].

Partial evaluation has been attempted in a number of different programming paradigms. The earliest work used LISP-like languages because programs in such languages can easily be treated as data. In particular, the first self-applicable partial evaluator was written in a purely functional subset of first-order, statically scoped LISP. Since then work has been done to incorporate other language features of LISP like languages including, for example, global variables [BD89]. A self-applicable partial evaluator for a term rewriting language has been achieved [Bon89], and more recently a higher-order A-calculus version has been developed [Gom89].

Because of these successes, partial evaluation is sometimes linked with functional languages. Indeed the word “evaluation” itself is expression orientated. However, partial evaluation has also become popular in logic languages, and in Prolog in particular. Kursawe, investigating “pure partial evaluation”, shows that the principles are the same in both the logic and functional paradigms [Kur88]. Using the referentially opaque clause primitive, very compact interpreters (and hence partial evaluators) can be written. However, it is not clear how the clause predicate itself should be handled by a partial evaluator and, hence, whether this approach can ever lead to self-application. Other “features” of Prolog that can cause problems for partial evaluation are the cut and negation-by-failure.

We have studied some of the theoretical aspects of using projections in binding-time analysis and how, again in theory, the dependent sum construction can be used to define the run-time arguments. In this chapter we will draw these threads together in the implementation of a projection-based partial evaluator. The current version is written in LML [Aug84] and not in PEL itself, so it is not yet self-applicable. Indeed there are still some problems about self-application of LML-like languages, which we discuss in the concluding chapter.

One slightly surprising feature is that the moderately complicated dependent sum construction turns out to be almost trivial to implement. In contrast, however, the binding-time analysis is fairly intricate because of the complexity involved in representing projections. Of necessity, parts of the following will interest only those intending to produce an implementation themselves. Anyone uninterested in the gory details should skim much of this chapter and turn to the final section where we develop the extended example.

General

A PEL program, as defined in Chapter 4, consists of type definitions followed by a series of function definitions. At the end of these is an expression to be evaluated. The value of this expression gives the value of the whole program. When we intend to partially evaluate a program we present it in exactly the same form except that the final expression is permitted to have free variables. These free variables indicate non-static data.