Offline Specialisation in Prolog Using a Hand-Written Compiler Generator

[folk]

Прошу прощения - кину как есть введение, если интересно выложу статью и переведу частично.
Futamura projections применяются уже в песочнице! Лет через 20 выйдут в карьеры.. )))


1 Introduction

Partial evaluation has over the past decade received considerable attention both M. Leuschel, J. Jørgensen, W. Vanhoof, and M. Bruynooghe
in functional (e.g. (Jones, Gomard and Sestoft 1993)), imperative (e.g. (Andersen
1994)) and logic programming (e.g. (Gallagher 1993, Komorowski 1992, Pettorossi
and Proietti 1994)). Partial evaluators are also sometimes called mix , as they usually
perform a mixture of evaluation and code generation steps. In the context of
pure logic programs, partial evaluation is sometimes referred to as partial deduction,
the term partial evaluation being reserved for the treatment of impure logic
programs.
Guided by the Futamura projections (Futamura 1971) a lot of effort, specially
in the functional partial evaluation community, has been put into making systems
self-applicable. A partial evaluation or deduction system is called self-applicable
if it is able to effectively1specialise itself. In that case one may, according to the
second Futamura projection, obtain compilers from interpreters and, according to
the third Futamura projection, a compiler generator (cogen for short). In essence,
given a particular program P, a cogen generates a specialised specialiser for P. If
P is an interpreter a cogen thus generates a compiler.
However writing an effectively self-applicable specialiser is a non-trivial task —
the more features one uses in writing the specialiser the more complex the specialisation
process becomes, because the specialiser then has to handle these features
as well. This is why so far no partial evaluator for full Prolog (like mixtus (Sahlin
1993), or paddy (Prestwich 1992)) is effectively self-applicable. On the other hand a
partial deducer which specialises only purely declarative logic programs (like sage
(Gurr 1994) or the system in (Bondorf, Frauendorf and Richter 1990)) has itself to
be written purely declaratively leading to slow systems and impractical compilers
and compiler generators.
So far the only practical compilers and compiler generators for logic programs
have been obtained by (Fujita and Furukawa 1988) and (Mogensen and Bondorf
1992). However, the specialisation in (Fujita and Furukawa 1988) is incorrect with
respect to some extra-logical built-ins, leading to incorrect results when attempting
self-application (Bondorf et al. 1990). The partial evaluator logimix (Mogensen
and Bondorf 1992) does not share this problem, but gives only modest speedups
when self-applied (compared to results for functional programming languages; see
(Mogensen and Bondorf 1992)) and cannot handle partially static data.
However, the actual creation of the cogen according to the third Futamura projection
is not of much interest to users since cogen can be generated once and for all
when a specialiser is given. Therefore, from a user’s point of view, whether a cogen
is produced by self-application or not is of little importance; what is important is
that it exists and that it is efficient and produces efficient, non-trivial specialised
specialisers. This is the background behind the approach to program specialisation
called the cogen approach (as opposed to the more traditional mix approach):
instead of trying to write a partial evaluation system mix which is neither too inefficient
nor too difficult to self-apply one simply writes a compiler generator directly.
This is not as difficult as one might imagine at first sight: basically the cogen turns
1 This implies some efficiency considerations, e.g. the system has to terminate within reasonable
time constraints, using an appropriate amount of memory.
Offline Specialisation in Prolog Using a Hand-Written Compiler Generator 3
out to be just a simple extension of a “binding-time analysis” for logic programs
(something first discovered for functional languages in (Holst 1989) and then exploited
in, e.g., (Holst and Launchbury 1991, Birkedal andWelinder 1994, Andersen
1994, Gl¨uck and Jørgensen 1995, Thiemann 1996)).
In this paper we will describe the first cogen written in this way for a logic
programming language. We start out with a cogen for a small subset of Prolog
and progressively improve it to handle a large part of Prolog and to extend its
capabilities.
Although the Futamura projections focus on how to generate a compiler from
an interpreter, the projections of course also apply when we replace the interpreter
by some other program. In this case the program produced by the second Futamura
projection is not called a compiler, but a generating extension. The program
produced by the third Futamura projection could rightly be called a generating
extension generator or gengen, but we will stick to the more conventional cogen.
The main contributions of this work are:
1. A formal specification of the concept of binding-time analysis and more generally
binding-type analysis, allowing the treatment of partially static structures,
in a (pure) logic programming setting and a description of how to obtain a
generic algorithm for offline partial deduction from such an analysis.
2. Based upon point 1, the first description of an efficient, handwritten compiler
generator (cogen) for a logic programming language, which has — exactly as
for other handwritten cogens for other programming paradigms — a quite
elegant and natural structure.
3. A way to handle both extra-logical features (such as var/1) and side-effects
(such as print/1) within the cogen. A refined treatment of the call/1 predicate
is also presented.
4. How to handle negation, disjunction and the if-then-else conditional in the
cogen.
5. Experimental results showing the efficiency of the cogen, the generating extensions,
and also of the specialised programs.
6. A method to obtain a binding-type analysis through the exploitation of existing
termination analysers.
This paper is a much extended and revised version of (Jørgensen and Leuschel
1996): points 3, 4, 5, 6 and the partially static structures of point 1 are new, leading
to a more powerful and practically useful cogen.
The paper is organised as follows: In Section 2 we formalise the concept of off-line
partial deduction and the associated binding-type analysis. In Section 3 we present
and explain our cogen approach in a pure logic programming setting, starting from
the structure of the generating extensions. In Section 4 we discuss the treatment
of declarative and non-declarative built-ins as well as constructs such as negations,
conditionals, and disjunctions. In Section 5 we present experimental results underlining
the efficiency of the cogen and of the generating extensions it produces. We
also compare the results against a traditional offline specialiser. In Section 6 we
present a method for doing an automatic binding-type analysis. We evaluate the
4 M. Leuschel, J. Jørgensen, W. Vanhoof, and M. Bruynooghe
efficiency and quality of this approach using some experiments. We conclude with
some discussions of related and future work in Section 7.