First, the stack. A lot of the time you can get away with using the call stack as a stack. Of course, this might not be the best idea if the stack is large, and depending on the problem it might be awkward. Stacks are particularly easy to implement in Prolog, requiring just two predicates:
% item to add; original stack; new stack
add_stack( Item, Stack, [Item|Stack] ).
% original stack; item to take; new stack
% original stack; item to take; new stack
remove_stack( [Item|RestStack], Item, RestStack ).
Pretty simple. By merely utilizing a list and manipulating the first element, one can make a simple stack. "remove_stack" is particularly simple; it will return false on an empty stack, which can lead to more natural solutions than those that explicitly must check for an empty stack.
Now for queues. This is also pretty straightforward:
add_queue( Item, Queue, NewQueue ) :-
append( Queue, [Item], NewQueue ).remove_queue( [Item|RestQueue], Item, RestQueue ).
Again, a simple list is used. The only difference is that added elements go to the end of the list, instead of the front. However, there is a problem with this. Generally, queue implementations are assumed to offer queue and dequeue operations in O(1). This one achieves an O(1) dequeue, but an O(n) queue because of the append operation. We want to put an item at the end of the list, but in order to do that, we need to traverse the entire list.
For trivial things, or where it can be guaranteed that n is small, this is probably not a problem. However, for real applications, this is definitely an issue.
We want to be able to add things to the back of the list, while taking things from the front of the list, both in constant time. The problem is that we can't do that with just a plain old list.
Think outside of Prolog a bit. Imagine this were C++ code. Each element of the list would likely be implemented as a node in a linked list. The way to get O(1) access for both the first and last nodes would be to store pointers to both the front and back. Prolog gives you the front for free, but not the back. You would like to store a pointer to the back, but Prolog doesn't let you do that.
At least not as a pointer. Prolog lets you do something much cooler: variables. Logical variables have seemingly magical properties to someone that is used to more traditional languages. The most magical bit is that they can be uninstantiated, to be instantiated at some later time (or not). With that in mind, consider the following:
?- Test = [1, 2, X, 3, 4], X = 10.
Test = [1, 2, 10, 3, 4],
X = 10.
The variable "X" is instantiated after it was put in the list. Now, normally X = 10 would be a constant time operation, but in this case...it's a constant time operation! With this simple example, one has a pointer to the middle of the list. So why not put the variable X at the end?
This is exactly how one can accomplish the trick of adding to the end in O(1). It does, however, require a more complicated queue definition. Queue operations must return both the queue and the variable at the back of the queue. Additionally, since the two terms are very closely related to each other, splitting them into two separate terms isn't advisable. Fortunately, Prolog's pattern matching makes this trivial. The power of pattern matching can be seen with the following example:
math( X-Y, Z ) :-
Z is X - Y.
math( X+Y, Z ) :-
Z is X + Y.
math( X*Y, Z ) :-
Z is X * Y.
math( X/Y, Z ) :-
Z is X/Y.
?- math( 2 + 5, X ).
X = 7.
?- math( 2 - 5, X ).
X = -3.
?- math( 2 * 5, X ).
X = 10.
?- math( 2 / 5, X ).
X = 0.4.
For this example, one essentially provides 3 parameters in one term: two numbers and an infix operator. Pattern matching allows this to be specified in a far more natural way.
Using this same technique, we can define a queue of the form [x1, x2, x3, ..., xn, X]-X, where X is the logical variable at the end of the queue. Using this form, we can then define operations that manipulate this form of queue, like so:
add_queue2( Item, Queue-X, Queue-Y ) :-
X = [Item|Y].
remove_queue2( [Item|Queue]-X, Item, Queue-X ).
It is assumed that X is at the end of Queue in these predicates. The whole "-X" part is just a way to keep the end of the queue in the same term, as described above. When we add to the queue, we replace the old logical variable X with a new one, Y, in addition to appending the given item. This achieves constant time for both operations.
Note that an empty queue is represented as X-X, not [X]-X. In the definition of add_queue2, with a base case of X-X to add to, a list is created. If there is already a list as in [X]-X, then this list ends up getting nested inside the initial list. To illustrate this, here is an example with the different base cases:
% empty queue: X-X
?- add_queue2( 1, X-X, NewQ ), add_queue2( 2, NewQ, NewQ2), add_queue2( 3, NewQ2, NewQ3 ), remove_queue2( NewQ3, Item, NewQ4 ).
X = [1, 2, 3|_G1416],
NewQ = [1, 2, 3|_G1416]-[2, 3|_G1416],
NewQ2 = [1, 2, 3|_G1416]-[3|_G1416],
NewQ3 = [1, 2, 3|_G1416]-_G1416,
Item = 1,
NewQ4 = [2, 3|_G1416]-_G1416.
X = [1, 2, 3|_G1416],
NewQ = [1, 2, 3|_G1416]-[2, 3|_G1416],
NewQ2 = [1, 2, 3|_G1416]-[3|_G1416],
NewQ3 = [1, 2, 3|_G1416]-_G1416,
Item = 1,
NewQ4 = [2, 3|_G1416]-_G1416.
% empty queue: [X]-X
?- add_queue2( 1, [X]-X, NewQ ), add_queue2( 2, NewQ, NewQ2), add_queue2( 3, NewQ2, NewQ3 ), remove_queue2( NewQ3, Item, NewQ4 ).X = [1, 2, 3|_G1422],
NewQ = [[1, 2, 3|_G1422]]-[2, 3|_G1422],
NewQ2 = [[1, 2, 3|_G1422]]-[3|_G1422],
NewQ3 = [[1, 2, 3|_G1422]]-_G1422,
Item = [1, 2, 3|_G1422],
NewQ4 = []-_G1422.
It *almost* works with [X]-X, and the other definitions could be tweaked so that it will work, but doing that skirts around the problem. X-X is just cleaner.
There is, however, one problem. In the original remove_queue definition with O(n) enqueue, the call simply failed on an empty queue. In this definition, this doesn't happen:
?- remove_queue2( X-X, Item, Q ).
X = [Item|_G1221],
Q = _G1221-[Item|_G1221].
Not only did this call succeed, it ended up placing the variable Item within the new queue. The easiest way to fix this is with an additional predicate. One might be tempted to add the following before the current definition of remove_queue2:
remove_queue2( X-X, _, _ ) :- !, fail.
Simple idea. When we explicitly see the form of an empty queue, fail with no chance of backtracking. At first, this appears to work:
?- remove_queue2( X-X, Item, Q ).
false.However, a little extra testing reveals that something horribly wrong is occurring:
?- add_queue2( 1, X-X, Q ), remove_queue2( Q, Item, NewQ ).
false.
The new predicate is matching everything that takes the form of this queue, empty or not! The reason for this is unfortunately quite low-level for my taste. It has to with how Prolog unifies terms. The short answer is that, likely for performance reasons, a certain check that would fix this is bypassed. A more detailed explanation can be found in John Wickerson's explanation of difference lists at www.cl.cam.ac.uk/~jpw48/difflists.pdf(note that a great deal of this post is based on that document!)
The solution is to explicitly perform this check, like so:
remove_queue2( X-Y, _, _ ) :-
unify_with_occurs_check( X, Y ), !, fail.
This acts to cut execution once the end of the queue is encountered. As long as this predicate is asserted before the predicate to actually remove items, this will work. A quick demonstration:
?- add_queue2( 1, X-X, NewQ ), add_queue2( 2, NewQ, NewQ2), add_queue2( 3, NewQ2, NewQ3 ), remove_queue2( NewQ3, Item, NewQ4 ).
X = [1, 2, 3|_G1419],
NewQ = [1, 2, 3|_G1419]-[2, 3|_G1419],
NewQ2 = [1, 2, 3|_G1419]-[3|_G1419],
NewQ3 = [1, 2, 3|_G1419]-_G1419,
Item = 1,
NewQ4 = [2, 3|_G1419]-_G1419.
We have a queue with O(1) enqueue and dequeue.
No comments:
Post a Comment