Logic Programming Research

Implementing Prolog Programs Free from Unification


Paolo Frigo, Massimo Marchiori

In recent years many efforts have been spent in developing methods for efficiently execute Prolog programs. The usual approach to study improvements in the implementation of unification is based on abstract interpretation techniques. In this paper, we follow an alternative approach based on syntactical analysis, that is we restrict our attention to a subclass of Prolog programs, with the advantage of obtaining a very precise analysis of properties useful for compilation (like groundness, freeness and dereferencing). The subclass we will implement is that of Simply Well Moded (SWM) programs. This class has the important property of being unification free, that is to say unification can be performed by iterated matching; moreover this class is quite large. In order to implement efficiently SWM programs we start from the standard way of compiling Prolog, i.e. the Warren Abstract Machine (WAM). We show how, with some modifications both on the clause compilation scheme and on the instructions semantics, one can obtain an efficient and nice compiled code for these programs. In particular the following unpleasant WAM features disappear: the presence of free variables and reference chains, unsafe variables, the general unify operation, the bind operation, the trail structure and operations, and the read/write switch in all head instructions. Since it is quite simple to test whether a program is SWM, we think an high performance compiler should be able to compile SWM programs according to our new scheme, otherwise it should apply other techniques in order to optimize the WAM code.

The whole paper can be downloaded from our server.

Logic Prog. Page Research Page Lab Home Page