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.