An Implementation of the Extended Andorra Model
Ricardo Lopes
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150 Porto, Portugal
December 2001
Abstract
Logic programming provides a high-level view of programming, giving
implementers a vast latitude in what techniques to research towards
obtaining the best performance for logic programs. Progress in
coroutining, constraints, and tabulation allow for substantial
reductions in search space over the traditional Prolog selection
function, and provide a basis on which to build advanced features and
support novel applications. Parallelism further allows logic programs
to transparently exploit the advantages of the new parallel machines
that are more than ever gaining in popularity.
Towards obtaining maximum performance, one of the holy grails of logic
programming has been to design computational models that could be
executed efficiently and would allow both for a reduction of the
search space and for exploiting all the available parallelism in the
application. These goals have motivated the design of the Extended
Andorra Model, a novel model where goals that do not constrain
non-deterministic goals can execute first.
In this work we present the Basic design for Extended Andorra Model
(BEAM), a design that builds upon David H. D. Warren's original EAM
with Implicit Control. We provide a complete description of an EAM
kernel as a set of rewrite and control rules, and we evaluate these
rules through a prototype implementation. We present the major data
structures and execution algorithms that are required for efficient
execution. We discuss the basic data structures required to implement
the model and some issues on extending the EAM to avoid infinite
computations. A detailed study of our prototype performance and
memory usage is also included. Lastly, we propose a novel parallel
execution model for the BEAM.
