A design and implementation of the Extended Andorra Model

• Type: Article in International Scientific Journal
• Date: 2012

Authors

Ricardo Lopes (Author) Other; Vitor Santos Costa (Author) FCUP; Fernando Silva (Author) FCUP

Journal

Title: Theory and Practice of Logic Programming

Vol. 12

Pages: 319-360

ISSN: 1471-0684

Publisher: Cambridge University Press

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 1 Citation

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-002-AG2

DOI: 10.1017/s1471068411000068

Abstract (EN): Logic programming provides a high-level view of programming, giving implementers a vast latitude into what techniques to explore to achieve the best performance for logic programs. Towards obtaining maximum performance, one of the holy grails of logic programming has been to design computational models that could be executed efficiently and that 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 (EAM), a model where goals that do not constrain nondeterministic goals can execute first. In this work, we present and evaluate the Basic design for EAM, a system that builds upon David H. D. Warren's original EAM with Implicit Control. We provide a complete description and implementation of the Basic design for EAM System as a set of rewrite and control rules. We present the major data structures and execution algorithms that are required for efficient execution, and evaluate system performance. A detailed performance study of our system is included. Our results show that the system achieves acceptable base performance and that a number of applications benefit from the advanced search inherent to the EAM.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 42