Logic Programming Research

Complete and Efficient Methods for Supporting Side-Effects and Cuts in And-Or Parallel Prolog

In Proc. of IEEE International Symposium on Parallel and Distribuited Processing, IEEE Computer Society Press, Dec. 1992, pp. 288-295

Gopal Gupta, Vitor Santos Costa

Practical Prolog programs usually contain extra-logical features like cuts, side-effects, and database manipulating predicates. In order to exploit implicit parallelism from real applications a parallel logic programming system should necessarily support these features. In this paper we show how Prolog's extra-logical features can be supported in an and-or parallel logic programming system. We show that to support extra-logical features an and-or parallel logic programming system should recompute the solutions to independent goals instead of sharing them. We describe an abstraction called the Composition Tree for representing and-or parallel execution with recomputation. We introduce the notion of ``local-leftmostness'' in the Composition Tree and use it for deriving complete and efficient methods for supporting extra-logical predicates in and-or parallel logic programming systems based on the Composition Tree abstraction.

The whole paper can be downloaded from our server.

Logic Prog. Page Research Page Lab Home Page