PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (03/26/87)
PROLOG Digest Friday, 27 Mar 1987 Volume 5 : Issue 22
Today's Topics:
Administration - Abhorrent Behavior,
Programming - 91 Function & Splay Trees & Axiomatisation
----------------------------------------------------------------------
Date: Thu 26 Mar 87 10:11:09-PST
From: Chuck Restivo <Restivo@Sushi.Stanford.EDU>
Subject: Restatement of policy.
Dear Friends,
This forum is not an appropriate venue for commercial advertisement.
Recent abuse of this dictum has unfortunately made it necessary to
remind everyone and in particular those with commercial interests that
have not been able to restrain themselves of this. I apologize to the
network sponsors and those who have conscientiously governed
themselves.
-- Chuck
------------------------------
Date: Tue, 24 Mar 87 20:04 EDT
From: BAGLEY%temple.csnet@RELAY.CS.NET
Subject: 91 function mistake
In Prolog Digest Volume 5, Issue 21, it is pointed out that there is
an unnecessary cut in this code:
> foo(X,Z) :-
> X > 100,
> Z is X - 10.
> foo(X,Z) :-
> X < 101,
> T is X + 11,
> foo(T,Z),
> !. % <<<<<<< Unnecessary cut
>
>I've seen this kind of unecessary use of cut more times than I care to
>remember.
Actually, the code is just plain wrong, and since I submitted it, I
feel compelled to try to fix it, even though it is sort of after the
fact and other submissions on the same topic were superior.
The problem was concerning a recursive function that always returns
91.
What I should have submitted was:
% for domain (of X) = {0..101}
foo(X, Z):-
X > 100,
Z is X - 10, !. % Cut necessary!
foo(X, Z) :-
Y is X + 11,
foo(Y, N),
foo(N, Z).
Here, the cut is necessary, because the answer on backtracking is
wrong. However, this is not such a pleasing answer, because of the
limitation on the domain.
I think the best answer is:
% domain is Natural Numbers
foo(91,91).
foo(X, Z) :-
X > 100,
Y is X - 10,
foo(Y, Z).
foo(X, Z) :-
Y is X + 11,
foo(Y, N),
foo(N, Z).
Here, no cut is necessary, because the answer on backtracking is
still 91.
-- Doug Bagley
------------------------------
Date: Tue 24 Mar 87 08:36:27-EST
From: vijay <Vijay.Saraswat@C.CS.CMU.EDU>
Subject: Axiomatisation of splay trees.
For the logic programming purists out there: Note that both the top-down
and bottom-up splay tree programs can be converted to *pure definite
clause axiomatisations*, without any control information at all.
-- Vijay.
------------------------------
Date: Tue 24 Mar 87 07:55:59-EST
From: vijay <Vijay.Saraswat@C.CS.CMU.EDU>
Subject: More on splay trees.
23 March 1987.
Merge trees using splaying --- or how to splay in parallel
and bottom-up.
-- Vijay Saraswat
Here is a simple and efficient merge of a dynamically varying number
of streams, with logarithmic delay. It uses the concept of
self-adjusting splay trees [Sleator and Tarjan, 1985] rather than 2:3
trees as in [Shapiro and Mierwosky, 1984], the code for which is quite
complex, and its correctness not obvious. (In this note I am concerned
simply with obtaining a balance requirement on dynamically changing
binary merge trees --- in particular I am not concerned with
establishing fairness of the merge, or bounds on the responsiveness
etc. of the merge. See [Saraswat 87] for some ideas on how to do
that.)
Binary search trees have an obvious `forgetful' mapping into merge
trees: the addition and deletion of a stream at a leaf corresponds to
the addition and deletion of a node and the propagation of a message
from a leaf to the root corresponds to an access from the root to the
node. In merge trees, no information (e.g. ordering) needs to be
associated with the nodes in the tree.
In order to obtain the efficiency of splay trees, all that is really
needed is the path-halving heuristic. Since the splitting of an input
stream is purely a local operation (i.e. we do not have to traverse a
path from the root to a leaf in order to determine that the input
stream at the leaf needs to split), we may simply do it locally and
omit any splaying (constant time). Similarly for the termination of an
input stream. We only do splaying if an input arrives at an input
stream and has to be propagated to the root.
For an efficient and clean implementation of bottom-up splaying, a
good mapping from splay trees to merge trees is essential. A major
problem is that splaying at a node requires information two links up
in the tree, and we have to implement each splay step as an atomic
operation. Matters are considerably simplified by adopting the
following representation. To every node in the tree corresponds a
*merge(Left, Out, RIght)* process: its first argument is its left
input stream , its second its output stream and its third its right
input stream. Whenever a node needs to be splayed, we pass up (along
the output arc of the node) information about the inputs to the node:
the inputs to the node stand, in a sense, as representatives of the
whole subtree rooted at that node. After two steps, when the message
reaches the grandparent of the node to be splayed, the grandparent
knows the path that the message took from the node (zig-zig, zig-zag,
zag-zag, zag-zig) and, having access to all the relevant subtrees, can
create the new local rearrangements of the tree.
These streams will carry six types of messages, i.e they will be
instantiated to six types of terms. A stream is instantiated to:
-- *[]* if it terminates;
-- *item(I).In* if it has a message (*I*) to be merged;
-- *stream(I).In)* it needs to split into two streams I
and In;
-- *item(I, A, B)* if it is the output of a merge
node which has received an input *item(I)* and whose
input streams are *A* (left) and *B* (right);
-- *left(I, A, B, C)* if it is the output of a merge whose
left son is to be splayed and whose left son has output
the message *item(I, A, B)* (*C* is the right son of the
current merge node);
-- *right(I, A, B, C)* if it is the output of a merge whose
right son is to be splayed, and has output the message
*item(I, A, B)* (*C* is the left son of the current merge
node).
We start with a call to *root/1*, which contains one input stream. A
root process terminates if its input stream terminates; it passes on
any messages of the form *item(I)*; it spawns a merge process if its
input stream splits.
root([], []!).
root(item(I).Out, item(I)!.In):- root(Out, In).
root(Out, stream(I)!. In):- root(Out, New), merge(I, New, In).
If one of the input streams to a merge terminates, it terminates after
shorting its other input with its output. If it receives an *item(I)*
message, it terminates after sending the remaining active streams as
part of an *item/3* message on its output. An *item/3* message is
converted into a *left/4* or a *right/4* message depending upon which
channel it came in: the new argument is the other channel.
merge([]!, Right, Right).
merge(Left, Left, []!).
merge(item(I)!.Left, item(I, Left, Right), Right).
merge(Left, item(I, Left, Right), item(I)!.Right).
merge(item(I, A, B)!, left(I, A, B, C), C).
merge(C, right(I, A, B, C), item(I, A, B)!).
The zig-zig, zig-zag, zag-zag and zag-zig operations now become
straightforward.
merge(left(I, A, B, C)!, item(I, A, Y), D):-
merge(C, Z, D), merge(B, Y, Z).
merge(right(I, A, B, C)!, item(I, Y, Z), D):-
merge(C, Y, A), merge(B, Z, D).
merge(D, item(I, Y, B), right(I, A, B, C)!):-
merge(D, X, C), merge(X, Y, A).
merge(A, item(I, Y, Z), left(I, B, C, D)!):-
merge(C, Y, D), merge(A, Z, B).
If an input stream of a leaf process forks, a new merge process is
created, in the obvious manner.
merge(stream(I)!.Left, Out, Right):-
merge(I, New, Left), merge(New, Out, Right).
merge(Left, Out, stream(I)!.Right):-
merge(Left, Out, New), merge(I, New, Right).
We now return to the remaining transitions for the root process. If it
receives a left message on its input, then it must execute a zig step
(the terminating single rotation). Similarly for a right message. In
the case of an item message, the two streams are passed into a newly
created merge.
root(item(I).Out, left(I, A, B, C)!):-
root(Out, In), merge(A, In, Y), merge(B, Y, C).
root(item(I).Out, right(I, A, B, C)!):-
root(Out, In), merge(Y, In, C), merge(A, Y, B).
root(item(I).Out, item(I, Left, Right)!):-
root(Out, In), merge(Left, In, Right).
This is the entire program. Note that there is no need at all to
consider the complex synchronisation conditions that are discussed in
the Shapiro and Mierwosky paper concerning shrinking of 2:3 trees.
The analysis of this simple program is rather complex. First,
consider only a sequence of n merge operations starting from the
leaves and making their way out of the root in a stream i1, i2, ...
in. EVEN though all the operations are being done concurrently,
according to the program above, we make the claim that if M_0 is the
initial tree, then after all these messages have left the tree, and if
there are no other messages in the tree, the tree M_1 that results is
exactly the same tree that would have been obtained by executing the
sequence l1, l2, ..., ln of accesses (with splaying), where lj is the
leaf from which the message ij emanated.
The claim is based on the following observation. Let l1 and l2 be any
two leaves. The splays of these leaves do not interfere with each
other until their messages reach the least common ancestor of the two
leaves. According to the algorithm above, some one of the two
messages, say the one corresponding to l1, will be forwarded
non-determinstically, and a splay operation performed based on the
direction from which l1 entered the merge node. Now the claim is that
in the output stream of the merge system, l1 will appear before the
other message l2 --- messages from the same subtree cannot `overtake'
each other --- and the entire sequence of concurrent operations will
result in the tree that would have been obtained if l1 was accessed
(and splayed) first, and then l2. Note that *we have not defined the
behaviour of a merge if it receives a message of the form left(I, A,
item(I, A1, B1), C)* --- in other words, once a message (left or
right) is forwarded by a node, any other messages on its input stream
are not considered until the splay operation due to the forwarded
message is completed. (When the splay operation is completed, the
stream which may have the other message --item(I, A1, B1) above ---
again becomes a top-level argument to a merge process, and can be
accepted by the merge process.) Thus the combination of the facts
that each splay operation is done atomically and no two splay
operations from the same subtree can overtake each other establishes
the claim.
I believe this proposition can be utilised to show that even with the
(local) additions and deletions, the cost of m operations (merges or
additions or deletions) is at most O((m + n)*log(n)+ n), where n is
the number of nodes at some suitable point during the sequence of
operations.
References:
[Shapiro and Mierowsky, 1984] `Fair, biased and
self-balancing merge operators: Their specification and
implementation in Concurrent Prolog.'
E.Y. Shapiro, and C. Mierowsky
New Generation Computing 2 (1984) 221-240
[Sleator and Tarjan 1985] `Self-adjusting binary search
trees'
D.D. Sleator and R.E. Tarjan
JACM 32(3) (July 1985) 652-686
[Saraswat 1987] `Merging many streams efficiently'
V.A. Saraswat
To Appear in `Concurrent Prolog', ed. Ehud Shapiro, MIT
Press, 1987.
------------------------------
End of PROLOG Digest
********************