Compile time transformation of Prolog programs

OData support
Supervisor:
Dr. Szeredi Péter
Department of Computer Science and Information Theory

Abstract

The topic of the diploma thesis is the compile time transformation of Prolog programs.

One of the main goals of compile time transformations is to obtain a more complex but more efficient (i.e. faster) program variant from a simpler, more transparent piece of code, with the same run time behaviour. In my thesis I discuss the method of Partial Evaluation, a widespread program transformation technique.

Partial Evaluation is an approach which can be used for arbitrary programming languages.

A partial evaluator has two inputs: a program and some of its input data; and it has one output, which is called the residual program. When the residual program created by the partial evaluator is run on the remaining input data, it produces the same results as the original program with all the input data.

In my thesis I describe a partial evaluator for Prolog programs, which is implemented on top of a module inline, developed earlier, which supports the inline expansion of certain procedure calls.

In my thesis I first give an introduction to the Prolog language, next, I discuss the main properties of the Partial Evaluation approach and its applicability to Prolog. Subsequently I give an overview of the module inline, and discuss whether it is applicable for supporting the Partial Evaluation technique. I show what preprocessing steps should be done on the input program so that the inline module becomes capable of producing the partially evaluated variant of the input program.

Next, I give a specification for the module ParEval, supporting partial evaluation, where the module name comes form the English expression ’partial evaluation’. After giving a formal specification for the algorithm of partial evaluation and describing the user options for describing to which parts of the program should partial evaluation be applied, I present techniques for reducing the task of partial evaluation to the functions of the inline module reviewed formerly.

The next part of my thesis deals with the process of implementation, introducing the main steps of the program development, the problems arising in this, and the solutions used. Finally, I give an evaluation of the ParEval module and I show examples on how to use it.

Downloads

Please sign in to download the files of this thesis.