I’m using: SWI-Prolog version 8.0.2 on Ubuntu Linux 18.04.
I need to know if there is a data structure in SWI-Prolog that allows me to emulate a queue or linked list that I can access from “either end”. By either end I mean access the elements linearly from the oldest element to the newest, or conversely, from the newest element to the oldest.
My app maintains a history of each transaction with the user. It needs to examine that history but most of the time it just needs to access a few of the most recent transactions, reading in reverse chronological order, starting with the newest transaction and iterating towards the oldest. Every now and then it will need to access that history in the opposite direction, from the oldest to the newest.
So I need to know what is the SWI-Prolog equivalent of a queue or linked list that one can traverse in either direction? If no such thing exists, I need to know how to get the same effect from the Prolog database.
The worst situation is if I have to read from the beginning of the history all the way to the most recent transactions in order to get just those recent transactions. It is most convenient if I can read the elements in reverse chronological order without having to sort them. I don’t know enough about the Prolog database to know in what order elements are stored in the database when you make assertions to the same predicate and subsequently make a query with backtracking upon that predicate.
So, if there is no such data structure in SWI-Prolog that does what my app needs here, how can I use asserta/assertz to add elements in the correct order so that when I do a query to the predicate, I get the newest element first and upon backtracking, iterate from the newest transaction in a direction iterates progressively towards the oldest element ever asserted to the database?
You can use a pair consisting of a list to which you add the transaction at the beginning and a difference list to which you add the transaction at the end. Use the list for reverse chronological traversal and the difference list for chronological. That’s assuming you don’t need to remove any transactions.
You probably know this, but it’s generally a bad idea to use the dynamic database unless you absolutely have to.
Queues are something of a nightmare in Prolog, traditionally involving difference lists and incomplete data structures, which are confusingly explained using different notations in different textbooks (worse yet, the notation used in The Art of Prolog doesn’t work at all in SWI Prolog since it uses the escape slash).
To sidestep all that, I’d suggest looking at builtin nth1/4 predicate to create enqueue and dequeue predicates
Not long time ago, I was surprised with how fast the dynamic database was performing. I think that using it depends on the application, and one may reach competitive times when using this database. I’ll try to ellaborate on this when time permits.
Firstly, OP is asking about traversing the elements from both sides, so a simple queue is not the right data structure. Possibly a deque (double-ended queue) is needed, but I think the requirements are a bit less general.
Secondly, there is nothing wrong with using difference lists in a queue data structure. O’Keefe explains in The Craft of Prolog how to use successor arithmetic to keep track of the length of the queue in a pure way, so that you can even prevent the queue from “hallucinating” (his terminology) new elements when you dequeue an element from an empty queue.
Thirdly, the code you give is doing enqueue and dequeue at the end of the list, so that what you actually have is a stack. You probably meant to enqueue at the head of the list.
Fourthly, the operations you are using are O(N), so you might as well just append/3 to get to the last element and avoid using length/2. Much better would be to use difference lists and have O(1) enqueue and dequeue operations.
I believe I’ll use a combination of asserta/assertz and a heap (thanks @swi). I will keep a “global” counter in the database to act as the hash key. Then with each transaction I add to history I will:
increment the “global” counter to create a new key.
insert the new history compound term into the heap using the key
assertz the key to a predicate named history_z for oldest to newest ordering
asserta the key to a predicate named history_a for newest to oldest ordering
Then I can just backtrack through either history predicate to get the order I desire. With each solution I will get the hash key and then just do a lookup in the heap to get the actual value. I believe the above solution is a good combination of performance and storage efficiency that is linear in the number of operations necessary to implement it?
@michaelby I am familiar with difference lists since the The Art of Prolog was the first Prolog book I ever read. But I need this data to be in the database since it has to persist across asynchronous transactions with the user. I assume you weren’t indicating that I should save/restore the difference list to the database since that would be a very heavy transaction given how large the history will become over time.
True, dequeue is the wrong term since I’m refering to removing from the end of the list as opposed to LIFO. The point is that adding and removing things from the ends of lists in Prolog is not very elegant, and using DCGs are generally the best way of handling difference lists.
Ah, sorry. I misunderstood. Indeed, I wasn’t suggesting saving and restoring a large data structure to and from the database. It’s possible to thread the Prolog data structure through your code as an argument but it can become very annoying in code that is very I/O heavy or impossible without copying when threads are involved.
There are two alternatives: backtrackable global variables allow for keeping a global data structure without argument passing and engines allow sharing such a thing also between threads. Engines are a pretty neat solution to create a global and possible shared resource built around a large complex Prolog term.