Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!sharkey!mcf!mibte!gamma!thumper!yowjian
From: yowjian@thumper.bellcore.com (Jian Lin)
Newsgroups: comp.lang.prolog
Subject: The coding of Queue
Message-ID: <1713@thumper.bellcore.com>
Date: 11 Sep 89 21:01:20 GMT
Reply-To: yowjian@thumper.bellcore.com (Yow-Jian Lin)
Organization: Bellcore MRE
Lines: 24

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