yowjian@thumper.bellcore.com (Jian Lin) (09/12/89)
The representation of a queue q(Count,Front,Back), originally suggested by Stuart Shieber, was mentioned in Richard O'keefe's LP'88 tutorial note. There is an implicit assumption, if I understand it correctly, that while coding queue operations based upon such structure, 'Back' is always an unbound variable. For example, the clause queue_last(X, q(N,F,[X|B]), q(s(N),F,B)). will fail if I try to enqueue an item 'a' to a queue 'q(0,[b|B],[b|B])'. However, if I use the queue package as I am supposed to, (i.e., use queue(QUEUE) or queue(X,QUEUE) to construct a new queue; don't use IN queue as an argument of conjuctive subgoals after the execution of queue_last(X,IN,OUT); etc.), 'Back" should remain as an unbound variable in any queue structure. It also implies that I should use only the mode queue_last(input,input,output). Now, suppose that I want to use queue_last in various modes (e.g. queue_last(input,output,input) to undo the enqueue operation). "queue_last(X, q(N,F,[X|B]), q(s(N),F,B))." certainly won't work in general. Is there any way that I can issue and undo an enqueue operation using the same clause with different modes (in constant time)? Thanks, Yow-Jian Lin
ok@cs.mu.oz.au (Richard O'Keefe) (09/14/89)
In article <1713@thumper.bellcore.com>, yowjian@thumper.bellcore.com (Jian Lin) writes: > queue_last(X, q(N,F,[X|B]), q(s(N),F,B)). > It also implies that I should use only the mode queue_last(+, +, -). Well, queue_last(?, +, -), but yes, you can't use this clause to pop things off the end of a queue. queue_head(X, q(N,F,B), q(s(N),[X|F],B)). _can_ be used both ways around, but not queue_last/3. (The problem is related to the fact that lists can share _suffixes_ but not _prefixes_.) > Now, suppose that I want to use queue_last in various modes (e.g. > queue_last(+, -, +) to undo the enqueue operation). > Is there any way that I can issue and undo an enqueue operation using the > same clause with different modes (in constant time)? Those same course notes describe the well known "back to back lists" implementation of queues which works in constant *average* time provided you don't backtrack over a "flip" too often. With that representation, queues of ground terms are themselves ground, so you can "undo" a queueing operation simply by keeping a copy of the original state.