MultiLog(ID:8325/)Data-Or parallel as opposed to control-or parallel prolog running initially on CM1 and then on BBN butterfly References: MultiLog and Multi,SLD Resolution The implementation of disjunction in top-down logic programming languages like Prolog typically relies on backtracking and depth-first search, or on the provision of multiple threads of control (control or-parallelism). However, both backtracking and control or- parallelism have disadvantages backtracking returns answers one at a time, often causing similar work to be repeated when a choice turns out to be the wrong one: and control or-parallelism is expensive in implementation complexity In this paper we investigate an alternative form of disjunction, expressed by a new operator disj, in which the SLD resolution model of Prolog execution is extended to permit multiple substitution "constraint" environments. We call the new logic programming language MultiLog The syntax of MultiLog differs from that of Prolog by the addition of the unary operator disj, whose argument is an arbitrary goal On encountering the goal disj G, MultiLog computes all or some subset of the solutions to G and turns these solutions into a set of environments disjunctive constraint. Subsequent goals then execute in this extended set of environments, with unification being performed (in parallel) on multiple bindings: backtracking occurs only if unification fails in all environments The goal disj G. results in a partial breadth-first search inwhich multiple solutions to G are processed by subsequent goals (in parallel) via the mechanism of multiple environments The slogan one control, multiple environments summarizes the (data or-parallelism) of MultiLog The operator disj is a logical analogue to the bagof operator of Prolog The goal bagof(X,G,L) computes all solutions to G and collects the respective bindings of X into the list L Analogously, the disjunctive goal disj G computes potentially. all solutions to G: but unlike bagof, disj makes the set of solutions into a disjunctive set of environments internal to the Prolog interpreter Clearly, the goal disj G will never terminate if G enters an infinite loop or if G succeeds infinitely often and we require disj to collect all solutions Even if G)s search tree is finite, it may be the case that G has too many solutions to handle with multiple environments Accordingly, we allow MultiLog to revert to backtracking after any number of solutions has been collected the then current set of solutions is fed to the success continuation, and if control backtracks into the disjunctive goal, additional solutions are collected , , , , and so on This is why we said above, "On encountering the goal disj G, MultiLog computes all or some subset of the solutions to G". In this way, backtracking and multiple environments can be combined in a single program and for a single goal In [Smi93], the operational semantics is formalized by defining the notions of multi-SLD resolution, multi-SLD derivation, and multi-SLD tree For multi-SLD resolution, the input to a resolution step is a goal, a set of substitutions, and a program: the output is a set of substitutions and a resolvent In [Smi93], where the disj operator is given a semantics based on the notion of disjunctive constraints, multi-SLD resolution is shown to be a sound and complete inference rule, given a breadth-first interpreter But in fact, the use of multiple environments amounts to a partial breadth-first exploration of the search tree, and as a result it leads to increased completeness of depth-first interpreters At each step of multi-SLD resolution, unification must be performed on multiple en- vironments Furthermore, each time a solution is returned to a disj goal, environments must be effectively. copied Abstractly, an ideal architecture for MultiLog would involve a data parallel machine in which one unification processor can be devoted to each environ- ment We have in fact implemented a prototype of MultiLog on the Connection Machine CM- However, unification in multiple environments is not a data parallel operation in the narrow sense, since variables can in general be bound to different size terms in differ- ent environments While we are pursing SIMD implementation of MultiLog for restricted classes of programs, we have concentrated our efforts on implementation on shared memory MIMD machines In effect, we simulate SIMD in MIMD In this paper, we describe an implementation of MultiLog on a shared memory MIMD machine, the Butterfly |