Hello everyone,
lately I have started reworking with the de facto Prolog Bible “The Craft of Prolog” by Richard O’Keefe. In particular I’m trying to make my way through chapter 2, which deals with searching and implementing different search strategies in Prolog.
O’Keefe deals with two different search strategies (at least in the first part of chapter 2 which I’m studying): depth-first and breadth-first. These two different strategies are closely related to the two different data structures that we use to store the nodes yet to be visited: a stack in the case of depth-first, a queue in the case of breadth-first search.
Depth-first search is so to say the “natural”, the “default” search strategy used by Prolog to look for an answer to queries, this doesn’t mean that one cannot implement other search strategies.
In keeping with the common vocabulary that parallels the relation between nodes in a graph to that of a family tree we may say that a depth-first search explores the children of a node (or its grand-children, or its grand grand-children and so on) before visiting its siblings. In a breadth-first search the siblings are visited first and only if a solution isn’t found the search explores the children nodes. Here I’ve shared a link a of a gif animation showing the order in which nodes are visited in a depth-first search:
https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif#/media/File:Depth-First-Search.gif
In a breadth-first search the order in which nodes are visited would be: 1 2 5 9 3 6 8 10 4 7
Now the interesting thing is that these two different strategies are closely tied to how we store the nodes to visit. If we use a stack we get depth-first, if we use a queue we get breadth-first.
A stack is a collection of items in which we add and remove items from the same side, so to say (these two actions are usually named “pushing” to and “popping” items from the stack): we may imagine a stack as a bag in which we place several things one above the other. Of course when we remove something from the bag the first item we pop is the last item we have added and certainly not the first one, which probably lies deep in the bag under lots of other stuff…). For this reason a stack is called a LIFO (Last In First Out) data structure. Stacks are well known to Prolog programmers because lists are stacks: we add and remove items of lists always from the left side and though the usual representation [a, s, d] hides the truth, we know that the real representation of a list is rather .(a, .(s, .(d, ))) (I use here the traditional dot notation for the list constructor instead of the more verbose [|]).
In a queue on the contrary we add items at one side and remove them from the other (these two operations are usually named “enqueuing” and “dequeuing” items): queues are therefore FIFO (First In First Out) data structures.
O’Keefe explains very well how the only different thing we have to do to build a stack or a queue is to append the children of a node to the front (in which case children nodes will be visited first) or to the back of the list of the nodes to visit (in which case sibling nodes will be visited first and children after).
But there is a problem: in Prolog doing things at the right side of a list is more complicated than doing the same things at the left side of it. Adding and removing items at the left is a constant time operation, adding and removing items at the right side of a list requires more time and space as the length of the list grows and the number of items to add grows…
So of course O’ Keefe asks himself: is it possible to implement a queue in Prolog (so that we can have breadth-first search, and not only depth-first) in a more efficient way than what appending to the right allows us to do? The answer is yes, there is a way. But it’s a little bit crazy, or at least it looks a little bit crazy at first, before one understand how it works.
To implement a queue O’Keefe uses a list pair, that is two lists united by a functor which can be + or / or whatever one likes more (he uses + by the way). An empty queue looks like this: empty_queue(+). The Front list will be the list from which we dequeue items, the Back list will be the one in which we enqueue them. The interesting fact is that, being both lists, we always work at the left side of the two, we avoid working (appending) to the right side (which is the costy operation that would slow down the whole thing if we work with big data).
A queue with some items looks like this: queue([a, b, c]+[f, e, d]).
If we dequeue an item (in this case ‘a’), the new queue would be: queue([b, c]+[f, e, d]).
Now the question is: what happens when the front list is empty and we want to dequeue one more item?
Like this: queue(+[f, e, d])?
In this case we reverse the back list and move it to the front, dequeue the first item from it (in this case ‘d’, remember that the list has been reversed!) and add an empty list as the new back list. So after dequeuing ‘d’ the new queue will look like queue([e, f]+). So we can start again adding new items to the back list or dequeuing them from the new front list…
It works. Even though it looks a little bit crazy at first (or at least it looked crazy to me)… and more importantly it’s efficient because we emulate a queue behavior by using two lists and working always at the left side of lists both in enqueing and dequeuing instead of working at the right side (which would be highly inefficient). Thanks for now
Here I paste the code to implement a queue in Prolog, in case you wanted to try it yourself:
% Implementing the same data type (a queue) using two lists
empty_queue([]/[]).
% Enqueuing here means prepending to the back list
enqueue(Item, Front/Back, Front/[Item|Back]).
% Dequeuing here means popping the first item from the front list.
% If the front list is empty: we reverse the back list, return the first element from it
% and move the rest to the front adding a new empty back list
dequeue(Item, [Item|Front]/Back, Front/Back).
dequeue(Item, []/Back, Front/[]) :-
reverse(Back, [Item|Front]).
There is the “length as a term” weird bit that’s true.