Compiling cp (↓,|,&) on top of Prolog
Vijay Saraswat · 1987
In this paper we present an implementation for the concurrent logic programming language cp(i ,!,&). The implementation compiles such programs into Prolog programs, which may further be compiled and run on Prolog systems. The design differs significantly from [Ueda and Chikayama, 1985], We present the implementation in a series of steps. We start with a design that compiles cp(i, I ,&) programs into a cp(f, | t &; o), which corresponds closely to Prolog, enhanced with a 'geler' (or f r e e z e ) capability, ([Boizumault, 1986]). The design uses a concept of modes to partition the clauses for a predicate into equivalence classes such that all the clauses in one class have identical suspension conditions. Multiple modes are examined 'simultaneously' by invoking a 'mode-goal' for each mode for that goal, and arranging for distributed commitment of these mode-goals using mutual and single exclusion. Because of the static nature of cp's T-annotation (as opposed to Concurrent Prolog's *?'), a number of important optimisations are possible. Most implementations of Prolog, however, do not have a f r e e z e capability. We present a meta-interpreter for cp(f, I o). By adding a 'suspension queue', we can obtain an interpreter for cp(f, | ,&; o) in cp( I 0). The code generated by the cp(j, I ,&) compiler may be thought of as being obtained by partially evaluating the output of the cp(|, I ,&) to cp(f, I 0) translator with respect to this interpreter to obtain a cp( I ,&; o) program. cp( I 0) programs may be trivially implemented in Prolog. Finally, we present a number of important optimisations for multi-mode predicates, and compare the performance of this compiler with [Ueda and Chikayama, 1985]. This research was sponsored in part by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 4976, monitored by the Air Force Avionics Laboratory Under Contract F33615-84-K-1520.