Introduction and Contents of "Partial Evaluation of Prolog"

This work has been written in Dutch. The introduction and the contents are the only parts that have been translated to English. The complete title of this manuscript is: "Partial Evaluation of Prolog and its Application to the Generation Abstract Prolog Machines".

Introduction

Currently some instruction sets for abstract Prolog machines are available. However until recently there was no method for automatically deriving instruction sets for abstract machines for Prolog or other high level computer languages. Peter Kursawe published such a method in 1986 [Kursawe 86]. The method uses the program transformation process partial evaluation. It relies on the fact that an abstract Prolog machine can be derived by partially evaluating a Prolog meta-interpreter. Erik Schipper has done further research in this topic [Schipper 1988]. He managed to derive abstract Prolog machines by manually performing partial evaluation of Prolog meta-interpreters. We would like to know if similar results can be achieved by performing this evaluation process automatically.

The partial evaluation software that has been discussed in the available literature is small. It has problems with processing recursively defined predicates and it is not capable of handling all system predicates. There is insufficient knowledge available about automatic partial information. This knowledge has to be acquired before partial evaluation can be used for generating abstract machines.

The main goal of this report is to investigate to what extent partial evaluation can be applied to Prolog automatically. The partial evaluation process has to be able to deal with recursively defined predicates and be able to deal with as many Prolog system predicates as possible. A second goal of this report is to try to find out if partial evaluation software can be used for generating abstract Prolog machines in practice.

This report contains four chapters. The first chapter gives an introduction to the program transformation technique partial evaluation. The second chapter deals with partial evaluation of Prolog. Using partial evaluation for generating abstract Prolog machines is the topic of the third chapter. In the fourth chapter discusses our implementation of a partial evaluator for Prolog. After this chapter we make some concluding remarks. The appendices contain information about the usage of the partial evaluator for Prolog, its code and the code of a meta-interpretor which can be used for deriving instructions for a Prolog machine.

Contents

0. Introduction                                                 5
1. The program transformation technique partial evaluation      7
2. Partial evaluation of Prolog                                13
3. Application of partial evaluation to generating abstract
   Prolog machines                                             38
4. The implementation of the partial evaluator for Prolog      48
5. Concluding remarks                                          64
6. References                                                  65
A. Using the partial evaluator for Prolog                      66
B. The code of the partial evaluator for Prolog                74
C. Erik Schipper's meta-interpreter                           149