Parallel Logic Models
=====================
The world consists of propositions to be proved.
Program = set of (logic) relations ("clauses", "rules")
qsort([], []).
qsort([H|T], L):-
lesser(H, T, A),
greater(H, T, B),
qsort(A, AS),
qsort(B, BS),
append(AS, [H|BS], L).
plus a proposition to be proved ("goal", "query")
:- qsort([3,2,1], R)
true.
variable bindings are generated as a side effect
R = [1, 2, 3]
Logic Basis
-----------
pred(S1) :- p1(S2), p2(S3).
pred(T1) :- q1(T2), q2(T3).
is syntactic sugar for the relation
forall X_i
p1(S2) /\ p2(S3) -> pred(S1)
/\ q1(T2) /\ q2(T3) -> pred(T1)
(where the X_i are all free variables in S_j, T_k)
which is equivalent to
forall X_i
~ p1(S2) \/ ~p2(S3) \/ pred(S1)
/\ ~ q1(T2) \/ ~q2(T3) \/ pred(T1)
Executing the program
:- p1(T1), p2(T2)
means proving the relation
exists X_i.
p1(T1) /\ p2(T2)
(where the X_i are all free variables in the T_i)
and generating bindings for the X_i (where the
generated bindings may also contain unbound i.e.
existentially quantified variables).
This kind of logic is called "Horn Clauses" (HC).
PROLOG is an implementation of HC logic where
- goals are selected from left to right
- clauses are searched from top to bottom
for matching heads
- unification is applied to generate variable bindings
- backtracking is applied to select alternative clauses
when the current goal cannot be resolved
This strategy yields a depth-first search of the proof tree
for the whole set of solutions (which may run into
infinite branches and not terminate).
And/Or Trees
------------
are graphical representations of the proof trees corresponding
to logic programs.
EXAMPLE
Parallelism
-----------
a) Parallelism within unification
The unification algorithm itself may be parallelized
=> too fine-grained for practical use
b) Parallelism among unifications
Multiple unifications of a goal against
a set of matching procedures may proceed in parallel
=> useful for "database oriented" Prolog programs
with many potentially matching facts
c) Parallelism in control strategy
OR-parallelism:
- sons of OR-node are processed in parallel
- alternative solutions of a goal are computed in parallel
(generalization of Prolog top-down/backtracing strategy)
- solution sets retrieved from sons are joined
p(T1) :- ...
p(T2) :- ...
AND parallelism:
- sons of AND-node are processed in parallel
- different subgoals of a goal are computed in parallel
(generalization of Prolog left-right strategy)
- variable bindings must be communicated among processes
p(T) :- q1(T1), q2(T2).
Parallelization of Prolog
-------------------------
Full Prolog semantics.
- Implicit/Automatic Parallelization
(difficulties => functional languagues)
[ Furthermore: Prolog has a *sequential* semantics
(practically *less* declarative than functional languages) ]
- Explicit imperative parallel layer
explicit task creation/synchronization constructs
CS-Prolog:
new(Goal, PID, Processor)
send(Message, ProcessList)
wait_for(Message)
Message passing model!
Backtracking works accross processes
- when backtracking passes communication point,
*anti-messages* are sent causing other processes
to backtrack as well
Prolog-Linda
tuple space communication
- Restricted AND Parallelism
Parsytec Prolog
goal(A,B,C) :- ground(C) | subgoal_1(A, C) & subgoal_2(B, C).
- & triggers parallel evaluation of subgoals
if guard condition separated by | is true.
- variables shared among parallel subgoals must be
bound and independent (bindings must not share variables).
Parallel Logic Languages
------------------------
Parallel semantics embedded in logical framework
(restriction of Prolog semantics to suit parallel context)
Most important: Guarded Horn Clause Languages
- GHC
- Concurrent Prolog
- Parlog
- Strand
Application/development in the Japanese Project
on 5th Generation Computers (1980s, ICOT institute)
- AND and (restricted) OR parallelism
- *Commited choice* mechanism replaces backtracking
pred(S0) :- guard0(T0) | p1(U0), p2(V0).
pred(S1) :- guard1(T1) | q1(U1), q2(V1).
....
:- pred(T)
- n parallel processes are started to match the goal predicate
against the n clauses of this predicate (OR-parallelism)
- each process i matches T against S_i generating local bindings
for the variables in S_i and then evaluates the option guard
predicate with this binding.
matching does *not* bind variables in T (*no unification*)
- if the guard of some process evaluates to true, all other
processes are aborted and further computation comits
to the use of that particular clause
=> only one solution is found!
=> non-deterministim!
- m parallel processes are started to evaluate the
m subgoals of that particular clause (AND-parallelism)
variable sharing is handled by distinguishing the
"input" and "output" positions of a predicate
- a shared variable may only appear in one output position
- process with output position generates variable binding
- processes with input position are blocked on unbound variables
=> single assignment semantics!
=> directionality of predicates! (predicates => functions)
Example:
mode producer(N?, L^)
mode consumer(L?, R^)
mode main(N?, R^).
producer(N, []):- N <= 0.
producer(N, [H|T]):- N > 0 | p(N, H), N1 is N-1, producer(N1, T).
consumer([], []).
consumer([H0|T0], [H1|T1]):- | q(H0, H1), consumer(H1, T1).
main(N, R):- producer(N, L), consumer(L, R).
:- main(1000, R).
PICTURE
- Horizontal parallelism
- Vertical/pipeline/stream parallelism
Non-deterministic merging
mode merge(?,?,^)
merge([],[],[]).
merge([H|T], L, [H|R]) :- | merge(T, L, R).
merge(L, [H|T], [H|R]) :- | merge(T, L, R).
:- produce(1000, A), produce(1000, B), merge(A, B, C).
Backwards communication
mode server(Requests?).
mode client(State?, Requests^)
server([]).
server([{Request, Answer}|Rest]) :- |
process(Request, Answer), server(Rest).
client(State, []) :- finished(State).
client(State, [{Request, Answer} | Rest]):- notfinished(State) |
newrequest(State, Request), newstate(State, Answer, NewState),
client(NewState, Rest),
:- client1(InitState1, Requests1),
client2(InitState2, Requests2),
merge(Requests1, Requests2, Requests),
server(Requests).
- Rather efficient parallel implementations of logic-like languages
- Logic semantics essentially reduced to
- functional semantics
- plus non-determinism
- plus single-assignment variables as first-order objects
Concurrent Constraint Languages
-------------------------------
Constraint Languages = logic languages where variables do not only range over
term domains but also over more general domains (integers, reals, ...) and
associated constraints (equalities/inequalities over arithmetic expressions)
p(X, Y, Z):- X = Y*Z.
:- p(-2.5, 2, Z).
true.
Z = -1.25.
no directionality!
The underlying formal framework of concurrency is a generalization/cleanup of
the GHC languages framework:
- set of concurrently executing agents
- central store of constraints over shared variables
- communication and control by operations on constraint store
- "tell": add new constraint to store
(consistent with those already in the store)
- "ask": determine whether a proposition can be inferred from the
current constraint store
- different agent behaviors are enabled depending on constraints
max(X,Y,Y):- X <= Y.
max(X,Y,X):- Y <= X.
=>
max(X,Y,Z):- ask(X <= Y) | tell(Y = Z).
max(X,Y,Z):- ask(Y <= X) | tell(Y = X).
Operational behavior similar to parallel logic languages where variable
binding/matching/unification operations are replaced by operations on
constraint store.
=> agents not deferred by accessing unbound variables but
by "ask" operations that cannot yet be answered
(blocking until more information available i.e.
more constraints have been added from other agents)
=> implementation of distributed constraint space required.