A parallel Prolog execution model: theoretical approach and experimental results

This paper presents a parallel all-solution extension of Prolog integrating AND parallelism and a restricted form of OR parallelism, both explicitly declared by the user. Parallel sub-goals may share variables and incrementally communicate partially instantiated terms via their common variables, thus allowing stream AND parallelism. Furthermore, the communication direction does not need to be declared by the user or deduced by a static analysis. The resolution model is detailed and its completeness proven. The authors describe a transputer network implementation