Logic Programming Research

A Systematic Approach to Exploiting Implicit Parallelism in Prolog

In 26th Hawaii International Conference on System Sciences, Maui Island, Jan. 1993.

Gopal Gupta, Vitor Santos Costa

Prolog is a practical declarative programming language based on Horn Logic. In this paper we argue that implicit parallelism can be extracted from full Prolog. By full Prolog we mean pure Prolog with extra-logical features such as side-effects, database predicates and cuts. Prolog programs have three main forms of implicit parallelism present in them: or-parallelism, independent and-parallelism and dependent and-parallelism. Starting from an or-parallel version of full Prolog, we show how independent and-parallel and dependent and-parallel versions can be systematically derived. We present details of how the environment is represented using Paged Binding Arrays to handle multiple bindings of variables in presence of or-, independent and-, and dependent and-parallelism. We also show how extra-logical predicates can be supported in this combined parallel implementation of Prolog.

The whole paper can be downloaded from our server.

Logic Prog. Page Research Page Lab Home Page