udi%humus.csnet@csnet-relay.arpa (06/12/84)
Some updates from the Weizmann Institute (WISDOM, by the way,
stands for the Weizmann Institute of Science, Department
Of Mathematics).
1. Workshop
Some of you might have heard of (or even participated in!!)
the Workshop on Implementation of Concurrent Prolog, held
here last April. There were around 35 participants, 25 from
abroad. I think the common conclusion of most participants
was that there is a long way still to an efficient
multiprocessor implementation of Concurrent Prolog, and that
Israel is a splendid place. The strength of the conclusions
depended on the amount of time each participant spent debating
and touring, respectively.
2. Implementation work at the Weizmann Institute
Since it seems that the ultimate goal of a Concurrent Prolog
compiler for multiprocessor systems is still quite far ahead,
we have set a more modest target: an efficient interpreter
for a conventional uniprocessor. As you may know, there is
already an interpreter for Concurrent Prolog, written in Prolog,
but it is incredibly slow (150 LIPS when compiler on a DEC 2060).
It has two conceptual problems: it does buzy waiting, and it
does not implement Or-parallelism, but instead simulate it via
backtracking. Our first effort to implement a correct, non-busy
waiting, true Or-parallel interpreter for Concurrent Prolog
(carried by Jacob Levy, a student of mine), was bogged down by
difficulties in maintaining independent Or-parallel environment.
At the workshop we have presented a solution to this problem,
which will also be presented at Uppsala. However, it turned out
to have some more bugs in it. Together with Steve Taylor from
Columbia, who joined us for the summer, we have fixed the bugs
(we think), but the resulting scheme is quite complex.
So we have changed direction, and decided to start even lower,
and implement an interpreter for the And-parallel subset of
Concurrent Prolog, called Flat Concurrent Prolog. FCP is
Concurrent Prolog with guards restricted to be empty or to
contain only simple tests.
The simplicity of this language is very appealing, and for a
long time I have been playing with this language, hoping to
find a simple and efficient way to write an interpereter for
Concurrent Prolog in it, thus having a layered implementation.
I did not succeed, but two things made me decide it may be
worth while to start with FCP. One is that almost all the
parallel algorithmic code written so far in Concurrent Prolog
really is in FCP (or can be hand-compiled into it easily).
The other is that I have succeeded in writing a meta-interpreter
for FCP in FCP. This means that FCP is a respectable language,
since it can implement its own meta-interpreter, debugger,
operating system, etc.
Here it is:
/* A Flat Concurrent Prolog meta-Interpreter, 23/5/84 */
% Succeeds if the interpreted program succeeds, fails if it
% fails, suspends if it suspends.
reduce(true).
reduce((A,B)) :- reduce(A), reduce(B).
reduce(A) :- system(A) | A.
reduce(A) :- otherwise | clauses(A,Cs), resolve(A,Cs,0,ME,
success).
resolve(A,[C|Cs],N,ME,R) :-
unify(A,C,N,ME,R1),
N1:=N+1,
resolve(A,Cs,N1,ME,R2),
combine_or(R1?,R2?,R).
resolve(_,[],_,_,failure).
unify(A,(A:-G|B),N,N,success) :- G | reduce(B).
unify(A,_,N,ME,failure) :- otherwise | true.
combine_or(success,_,success).
combine_or(failure,R,R).
combine_or(_,success,success).
combine_or(R,failure,R).
The main ideas in the interpreter are:
- Or-parallelism clause selection is converted into
And-parallelism
- A shared variable (ME) is used to enforce mutual
exclusion.
- The result of each reduction is forced to be 'success'
by the 'combine_or' processes.
Question: by complicating this interpreter a bit, it can be
made to implement Clark and Gregory's two- and three-argument
meta-call primitive (c.f. A Note on Systems Programming in
PARLOG, 1984).
call(P,Result) :- executes P and returns in Result success
or failure. call(P,Result,Abort) is the same, except that
it aborts the computation of P if Abort gets bound to abort.
Another question: enhance this interpreter to handle 'otherwise'
correctly. I'll distribute our answers (written together
with Steve Taylor and Jacob Levy) in a couple of weeks.
As expected, executing a program via this meta-interpreter
causes a 10-15 fold slowdown. The more complex interpreters
are even slower.
We plan to have two implementation efforts in parallel, in C
and in OCCAM.
>From the FCP interptreter there are several research directions
to go. One is a Concurrent Prolog interpreter. The other is
an FCP compiler (I beleive David HD Warren's New Engine can be
adapted for FCP). A third direction is a distributed FCP
interpreter,written in OCCAM. This should be much simpler then
a distributed interpreter for Concurrent Prolog, and hence a
good milestone on the way to parallel processing of Concurrent
Prolog. Another direction is a compiler from (subsets of)
Concurrent Prolog to FCP. We have found that the hand-compliation
of many Concurrent Prolog programs to FCP is not so difficult.
3. Other implementations of Concurrent Prolog
Besides the implementations reported in Prolog Digest V2 #23,
there is a working interpreter for a language which is a mixture
of Prolog and FCP, in which you can call general Prolog goals
from within guards, written in C by Kazumi Nitta from ETL-Japan.
The interpreter and it executes on a VAX-780 around 1K FCP LIPS,
and 1.5 Prolog LIPS.
Another interesting implementation is a recent work by Takashi
Chikayama from ICOT. It is a compiler from Concurrent Prolog
to Prolog. The basic execution algorithm is the same as in the
interpreter I have written, but unification is compiled as far
as it can be (rather than being interpreted by a general
unification algorithm).
The speedups are amazing: it is reported to run 4K LIPS when
compiled on a DEC-2060, and runs 150 LIPS interpreted under
C-Prolog on a VAX 780. I do not know the state of availability
of this compiler. If it can be made public I'll ship it to the
Prolog library.
3. Prolog Kernel (RE Pereira's Proposal, Prolog Digest #23)
Muli Safra, Leon Sterling, and I have worked out a proposal
for a Prolog Kernel, which was submitted to FGCS-84. It was
used to define an Edinburgh-compatible (with some clean-ups)
set of system predicates in an (almost working...) Prolog
implementation written in C by Muli. I'll check if we
can ship it over the net, to start some discussion.
-- Udi Shapiro
P.S. Please don't send me huge files over the net. The Hebrew
University (humus) pays for our mail, both incomming and outgoing,
and they keep threatenning to close our connection if we don't
behave...