Technical Report: DCC-2000-1
IAP for Dummies: The YAP Design
Manuel Eduardo Correia(1) and Vítor Santos Costa(2)
(1)
mcc@ncc.up.pt / DCC & LIACC, FCUP, University of Porto, Portugal
(2) vitor@cos.ufrj.br / COPPE/Sistemas, UFRJ, Brasil
February 2000
Abstract
One of the advantages of logic programming is the fact that it
offers several sources of implicit parallelism. One particularly
interesting form of And-Parallelism is Independent And-Parallelism
(IAP). Most work on the implementation of IAP is based on
Hermenegildo's RAP-WAM. Unfortunately there are some drawbacks
associated with the classical approaches based on the use of
parcalls and markers. One first observation is that the
introduction of parcall frames significantly slows down sequential
execution. Moreover, it may result in fine-grained parallel work. We
found these problems to be particularly significant in the context
of the implementation of combined AND/OR systems.
In this paper we take a fresh look at this issue. Our goal is to
start from a standard sequential Prolog implementation and try to
discover the minimal number of changes that would be required for an
efficient implementation of IAP. The key ideas in our design are to
(i) to always take advantage of analogy between or-parallelism and IAP; (ii) to
avoid creating new structures by adapting already existing WAM data-structures
wherever possible; and (iii) to avoid major changes to the
compiler.
