Exploiting type analysis for unification in a distributed environment

Abstract

Unification, in distributed implementations of logic programming, involves sending and receiving messages to access data structures spread among different nodes.  In traditional implementations, processes access remote data structures by exchanging messages which carry either the overall data structures or only remote references to them. Intermediate but fixed solutions are also possible.  These fixed policies can be far from optimal on various classes of programs and may induce substantial overhead. This paper presents an implementation scheme for distributed logic programming which consists of tailoring the copying level for each procedure argument. The scheme is based on a consumption specification which describes the way each procedure "consumes" its arguments locally. Consumption specification avoids unnecessary copying and allows to request data structures globally. The consumption specification (or an approximation of it) can be obtained through a static analysis inspired by traditional type analyses. The paper presents two implementations which exploit the consumption specification. The low-level implementation extends the Warren Abstract Machine with instructions and data structures for exploiting the consumption specification during code compilation. The high-level implementation is based on attributed variables in order to capture and implement, at a higher-level, distributed unification. Experimental results of the high-level implementation on a network of workstations show the potential of the approach.