Logic Programming Research
Implementing Prolog Programs Free from Unification
.
Author(s)
Paolo Frigo,
Massimo Marchiori
Abstract
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