Remote predicate calls
Miguel Calejo
Technical Note DI/UNL, October 1989
preliminary draft
This note adresses the following problem:
Given a Prolog program distributed in disjunct
parts among N Prolog processes, to provide a simple mechanism
for evaluation of any goal in a process which relies on (remote)
subgoals evaluated by any of the other processes .
Two applications motivated this:
Having two Prologs with different sets of builtins
use each other's abilities to solve goals, by distributing a program
among both. Typically, one Prolog has all the interface builtins
(MacLogic/C-Prolog), and the other has more computational power,
the user program but nearly no interface builtins (IM).
Computing goals in a Prolog processor while using
local information from other processors. For example, such may
be the case in the future for a network of Macintoshes, each having
an IM instance running on it.
This framework is inspired on Alegria's remote goal
posting proposal [Alegria et al.], and may be seen as a particular
concretization of his sketched protocol.
Here we're specifically concerned with the problem
of having "Prolog agents" ask each other to solve goals,
allowing recursive requests to solve subgoals. We're interested
in a minimal and reasonably efficient solution, involving no significative
overhead or implementation complexity. We start by incrementally
building a schema for a pair of processes, and conclude generalizing
to N processes.
1. Binary distributed coroutining
We'll define a "top-down constructive coroutining"
scheme for Prolog computations, where a subgoal can be evaluated
in a computation environment (coroutine) different from the one
of its father. Consider that we have two coroutines and 2 Prolog
primitives for communication:
send(T)
Sends a copy of term T to the other coroutine
and succeeds, continuing execution.
receive(T)
Suspends the coroutine until a term matching T is
available from the other coroutine. Bindings later performed in
T do not propagate to the sender coroutine. Terms arrive
assynchronously and transparently, and are kept in a FIFO queue.
We'll also assume that both coroutines are up and
running (check below).
1.1. Deterministic remote goals
Let's remember an existing schema for deterministic
goals. Goals to be evaluated locally are computed as usually.
Goals to be evaluated at the "remote coroutine" environment
must be computed with a metapredicate remote:
remote(G) :- send( call(G)
), receive(T), remote2(T,G).
remote2( answer(G), G) :- !.
remote2( call(G), A ) :- !, G, send(
answer(G) ), receive(T), remote2(T,A).
The second coroutine can start with the goal:-
repeat, receive(T), remote2(T,_).
The first coroutine (say, C-Prolog) starts with the
usual top level. Whenever it wishes to solve a goal G in the other
one (say,the IM), it calls remote(G).
The IM may solve goals in C-Prolog by calling remote(G)
as well.
Unfortunately, execution of cuts on backtracking
can cause dessynchronization - i.e one computation being ready
to give an additional answer to a call which no longer exists,
because it was skipped over by some cut. We'll return to this
problem after the next section.
1.2. Nondeterministic goals
To allow non-deterministic goals we must make
sure both computations go forward and backward in sync. Here's
a tentative solution:(******)
remote(G)
:- send( call(G) ), receive(T), remote2(T,G).
remote2( answer(G), G).
remote2( answer(_), A) :- !, send( redo
), receive(T), remote2(T,A).
remote2( call(G), A ) :- fail_port,
G, send( answer(G) ), receive(T), remote2(T,A).
fail_port.
fail_port :-
send( fail ), !, fail. % send anything _ answer(_) or call(_)…
1.3. Computations with cuts, part I
In order to synchronize both computations, on backtracking
to a remote
call we may have to backtrack further in the remote derivation.
To each solution computed remotely we associate a mark (ID in
the code below), and use it to later jump back.
remote(G)
:- !, send( call(G) ), receive(T), remote2(T,G).
remote2( answer(_,G), G).
remote2( answer(ID,_), A) :- !, send(
redo_to(ID) ), receive(T), remote2(T,A).
remote2( redo_to(ID),
_ ) :- !, fail_back_to(ID).
remote2( call(G), A ) :- !, fail_port,
G, this_place(ID), send( answer(ID,G) ), receive(T), remote2(T,A).
fail_port.
fail_port :- send( fail ), !, fail.
If a cut in one of the computations (C1) causes several
"remote(G)" calls to be skipped on backtracking, the
other computation C2 is nevertheless forced to backtrack to the
appropriate point, as soon as C1 backtracks until an (older) remote(G)
call. If the subcomputations in C2 (corresponding to the skipped
remote(G) calls) included remote calls themselves (to C1), the
corresponding subcomputations in C1 are skipped automatically:
they are under the aforementioned remote(G) calls in C1.
The two complementary "jumping" primitives,
fail_back_to(ID)
and this_place(ID),
can be implemented using a pair goal_number/retry, or a generalized
"cut" primitive. For example, ALPES C-Prolog provides
an "ancestor cut" - a cut which cuts up to a specified
ancestor of the clause with the cut. A more general version of
cut is available with YAP - removing choicepoints up to any previous
goal in the derivation, not necessarily an ancestor.
Using YAP:
this_place(ID)
:- ID is local_sp. % Current choice pointthis_place(_) :- fail
. % to force creation of a choice point
fail_back_to(ID) :- '$cut_by'(ID), fail. % commit and fail
A clumsier and less efficient implementation could
possibly make without these jumping primitives, by simulating
them on backtracking to remote.
However, there's another related problem.
1.4. Cuts, part II: "Disjunctive garbage"
There's one problem left: the computations may remain
with "dangling OR" branches - when one of the computations
is not forced back beyond a call which the other one no longer
cares about, and instead goes strictly forward to satisfy later
call requests.
It does not affect the results of computations, it's just a space
inefficiency issue.
This "dangling OR" situation is identical
to when an user enters "break" mode in a conventional
Prolog tracer and decides to never go back; or when an user asks
more solutions to an incremental Prolog top level but never lets
his original goal fail completely, while adding more constraints
to his (incremental) query.
Ensuring absence of "dangling ORs" seems
to involve either of:
Having the low-level implementation of cuts sending
messages to the other process whenever a remote
call is skipped during backtracking
Implementing an explicit trail-like mechanism
to later check, at the call port of any remote
call, whether the other process needs extra synchronization (i.e.,
prunning of dangling ORs)
The first involves changes in the implementation
of cuts. The second needs some means to distinguish active remote
calls (in the current derivation) from those which have been skipped
- again a solution involving either global overhead or a low-level
implementation (to check whether there's an active choice point
for a certain remote call).
Time to be pragmatic, and adopt two directives:
If possible, make sure that the first remote
call to the other process is failed explicitly (i.e., it is not
skipped over by a cut)
Use an additional primitive, flush_remote,
to initialize the remote coroutine, making it forget its current
computation whenever desired.
Following are the changes to the definitions above.
First, the new definition:flush_remote
:- send(flush).
An extra clause is added to remote2:remote2(flush)
:- !, $start(ID), fail_back_to(ID).
And the coroutining creation goal becomes::-
repeat,
this_place(ID), assert($start(ID)),
receive(T), remote2(T,_).
We'll now generalize to N coroutines instead of just
two.
2. Distributed coroutining
We conjecture that the same scheme applies for more
than 2 coroutines, since only one of them is active in turn, and
global execution is essentially mimicking what would be an ordinary
local Prolog execution. It's just necessary to make explicit names
for processes.
The communication primitives should be:
send(D,T)
Sends a copy of term T to the destinatary coroutine
D and succeeds.
receive(T,S)
Suspends the coroutine until a term is available
from another coroutine. S is bound to the name of the sender coroutine.
Bindings later performed in T do not propagate to the sender coroutine.
Terms arrive assynchronously and transparently, and are kept in
a FIFO queue.
And now the definitions for remote,
etc.:
remote(D,G) :- !,
send( D, call(G) ), receive(T,S), remote2(T,S,G).
remote2( answer(_,G), S, G).
remote2( answer(ID,_),
S, A) :- !, send( S,redo_to(ID) ), receive(T,S2), remote2(T,S2,A).
remote2(
redo_to(ID),S,_ ) :- !, fail_back_to(ID).
remote2( call(G), S,
A ) :- !, fail_port(S), G, this_place(ID), send( S,answer(ID,G)
), receive(T,S2), remote2(T,S2,A).
remote2(flush) :- $start(ID),
fail_back_to(ID).
fail_port(_).
fail_port(S) :- send( S, fail ), !, fail.
flush_remote(P) :- send(P,flush).
The coroutine creation goal :
:-
repeat,
this_place(ID), assert($start(ID)),
receive(T,S), remote2(T,S,_).
References
J. Alegria, A. Dias and L. Caires, "Towards
Distributed Tools for Heterogeneous Logic Programming Environments"
in Proceedings of the 6th International Conference on Logic Programming
(eds. Levi and Martelli), MIT Press, , 1989.
L.M. Pereira and R. Nasr, "Delta-Prolog: a distributed
logic programming language" in Proc. International Conference
on Fifth Generation Computer Systems , ICOT, ICOT, Tokyo, 283-291,
1984.
|
Declarativa