/*-------------------------------------------------------------*/ /* Stream AND-parallelism in DD-rules */ /* (C) 1993 Zdravko Markov, II-BAS */ /*-------------------------------------------------------------*/ /* DESCRIPTION: ----------- This is an illustration of how DD-rules can be used to implement the classical example of the stream AND-parallelism - the "sumtree" program. It is defined in Horn clauses as follows: sumtree(T,N) <- flatten(T,P),sum(P,N). flatten(t(t(X,Y,Z),U,V),P) <- flatten(t(X,Y,t(Z,U,V)),P). flatten(t(e,N,Y),[N|P]) <- flatten(Y,P). flatten(e,[]). sum(Z,N) <- sigma(Z,0,N). sigma([N|P],M,S) <- plus(N,M,M1),sigma(P,M1,S). sigma([],N,N). In the stream AND-parallel model this program works as follows. The goals "flatten(T,P)" and "sum(P,N)" incrementally communicate through the shared variable P. The "flatten" goal is a producer, which gradually creates a list of the labels of the tree T. When a new label is generated, the "sum" goal (the consumer) processes it immediately, not waiting for the whole list to be completed. In PARLOG for example, the process of producer-consumer synchronization is determined by mode declarations for the variable types (input or output) of the corresponding predicates. In the DD-rule implementation the "flatten" predicate is modified in such a way that given a tree as a dynamic data item, it generates a list of its labels. While this list is being generated the local database "flatten(_,_)" is available for the other DD-rules. Thus the "sum" rule (3), working in parallel, uses each newly generated label and adds it to the previously calculated sum. The initial value for the sum is specified by a static data item - "sum([],0)". Rule 4 is used to keep track of the process, printing all currently available solutions. The whole process can be seen as an incremental communication between rules 1,2 and 3 through local database "flatten(_,_)". It is important to note that no explicit (defined by the programmer) distinction between the producer and the consumer is needed. */ /*-------------------------------------------------------------*/ flatten(t(t(X,Y,Z),U,V),P) => flatten(t(X,Y,t(Z,U,V)),P). /* 1 */ flatten(t(e,N,Y),P) => flatten(Y,[N|P]). /* 2 */ flatten(_,[N|T]):sum(T,S) => S1 is S+N,sum([N|T],S1). /* 3 */ sum(P,S) => write(P-S),nl. /* 4 */ sum([],0). /*-------------------------------------------------------------*/ /* EXAMPLE: */ /*-------------------------------------------------------------*/ ?- flatten(t(t(e,2,t(e,3,e)),4,t(e,7,e)),[]). /* [2] - 2 [3,2] - 5 [4,3,2] - 9 [7,4,3,2] - 16 */