Optimal implementation of and-or parallel Prolog

• Tipo: Artigo em Revista Científica Internacional
• Data: 1994

Autores

Gupta, G (Autor) Outra; Costa, VS (Autor) FCUP

Revista

Título: Future Generation Computer Systems

Vol. 10

Páginas: 71-92

ISSN: 0167-739X

Editora: Elsevier

Indexação

Scopus - 12 Citações

Outras Informações

ID Authenticus: P-007-6AA

DOI: 10.1016/0167-739X(94)90052-3

Abstract (EN): Most models that have been proposed, or implemented, so far for exploiting both or-parallelism and independent and-parallelism have only considered pure logic programs (pure Prolog). We present an abstract model, called the Composition-Tree, for representing and-or parallelism in full Prolog. The Composition-Tree recomputes independent goals to ensure that Prolog semantics is preserved. We combine the idea of Composition-Tree with ideas developed earlier, to develop an abstract execution model that supports full Prolog semantics while at the same time avoiding redundant inferences when computing solutions to (purely) independent and-parallel goals. This is accomplished by sharing solutions of independent goals when they are pure (i.e. have no side-effects or cuts in them). The Binding Array scheme is extended for and-or parallel execution based on this abstract execution model. This extension enables the Binding Array scheme to support or-parallelism in the presence of independent and-parallelism, both when solutions to independent goals are recomputed as well as when they are shared. We show how extra-logical predicates, such as cuts and side-effects, are supported in this model. © 1994.

Idioma: Inglês

Tipo (Avaliação Docente): Científica