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.