Compartmentalized Connection Graphs for Concurrent Logic Programming I : Compartmentalization, Transformation and Examples

Abstract

The research reported in this paper and its sequels represents a revolt against the explicit and restricitve control of PROLOG and the present generation of Concurrent and Parallel Logic Programming Languages. It returns to the original Connection Graph paradigm of Kowalski and provides a methodology for logic programming in this framework. An elementary analysis of where the expenses in executing a logic program occur shows how processing of each of the linear components in a proof (or execution trace) can be executed in (non-deterministic) logarithmic time within the CONG system. Our implementation demonstrates that lemmatization can result in even more dramatic improvement. This paper deals primarily with recursion both in relation to connection graphs and in relation to Horn logic programs. In the first case a modified “compartmentalized” connection graph framework emerges, which allows proofs which are in general logarithmic in the size of a conventional connection graph proof. Furthermore, in the latter case we exhibit a technique allowing arbitrary recursive predicates in a logic program to be reduced to a canonical form involve only one single recursive predicate. The method is demonstrated on standard PROLOG examples.