3

I found this Prolog code in this answer, which implements a queue using difference lists:

%% empty_queue(-Queue)
% make an empty queue
empty_queue(queue(0, Q, Q)).

%% queue_head(?Queue, ?Head, ?Queue0)
% Queue, with Head removed, is Queue0
queue_head(queue(s(X), [H|Q], Q0), H, queue(X, Q, Q0)).

%% queue_last(+Queue0, +Last, -Queue)
% Queue0, with Last at its back, is Queue
queue_last(queue(X, Q, [L|Q0]), L, queue(s(X), Q, Q0)).

doing something like this it works as expected:

..., empty_queue(Q), queue_last(Q, 999, Q_), writeln(Q_), ....

and I get

queue(s(0),[999|_3076],_3076)

also interestingly if I observe the value of Q with this snippet:

empty_queue(Q), writeln(Q), queue_last(Q, 999, Q_), writeln(Q)

I get:

queue(0,_3750,_3750)
queue(0,[999|_3758],[999|_3758])

which I suppose it should be like this, since the difference results to empty list, so they are somewhat equivalent.

The problem is, after the command

queue_last(Q, 999, Q_)

I cannot reuse Q to create a Q__, ex:

empty_queue(Q), queue_last(Q, 999, Q_), queue_last(Q, 888, Q__)

because the binding of queue_last(queue(X, Q, [L|Q0]), L, queue(s(X), Q, Q0)). fails.

L = 888, L = 999 (tries to be both)

How can I solve this problem ? Is there some workaround ? (always using diff lists)

Will Ness
  • 70,110
  • 9
  • 98
  • 181
but-why
  • 533
  • 3
  • 10
  • 1
    how is that a problem? can `X` be both `1` and `2`, in any language? can the same list be both `L=[1,2]` and `L=[1,999]`? it _can_ be both `L=[1,2|T]` and `L=[1,2,999|T2]` though. (and then `T` can even be `T=T2`). – Will Ness Jun 06 '21 at 17:08
  • 2
    Linking the answer from which the queue example was copied: https://stackoverflow.com/a/31925828/14411997 – TA_intern Jun 07 '21 at 07:22
  • you should read that answer closely. :) it discusses some of this stuff already, I believe. – Will Ness Jun 07 '21 at 15:18

2 Answers2

1

I cannot reuse Q to create a Q__

That's because you must use the "threaded out" new structure that you call Q_. The old Q is a burner and must be discarded. It doesn't correctly describe a "difference list" anymore.

?- empty_queue(Q1), 
   queue_last(Q1, 999, Q2), 
   queue_last(Q2, 888, Q3).

Q1 = queue(0,[999,888|_14714],[999,888|_14714]),   % Useless
Q2 = queue(s(0),[999,888|_14714],[888|_14714]),    % Burnt
Q3 = queue(s(s(0)),[999,888|_14714],_14714).       % Correct, valid

After the empty_queue(Q1) call, this is Q1:

queue
├── arg 0: 0
├── arg 1: ----+---> <empty cell #1>
|              |
└── arg 2: ----+

After the queue_last(Q1, 999, Q2) call, this is Q1 and Q2:

Q1 (invalid)

queue
├── arg 0: 0
├── arg 1: ----+---->[|]
|              |     / \
|              |  999  <empty cell #2>
|              |
└── arg 2: ----+

Q2 (valid)

queue
├── arg 0: s(0)
├── arg 1: --------->[|]
|                    / \
|                 999  <empty cell #2>
|                          ^
|                          |
└── arg 2: ----------------+

After the queue_last(Q2, 888, Q3) call, this is Q1, Q2 and Q3:

Q1 (invalid)

queue
├── arg 0: 0
├── arg 1: ----+---->[|]
|              |     / \
|              |  999   [|]
|              |       /   \
└── arg 2: ----+    888    <empty cell #3>

Q2 (invalid)

queue
├── arg 0: s(0)
├── arg 1: --------->[|]
|                    / \
|                 999  [|]<------------------+
|                      /  \                  |
|                   888   <empty cell #3>    |
|                                            |
└── arg 2: ----------------------------------+

Q3 (valid)

queue
├── arg 0: s(s(0))
├── arg 1: --------->[|]
|                    / \
|                 999  [|]
|                      /  \              
|                   888   <empty cell #3>
|                                ^
|                                | 
└── arg 2: ----------------------+
Will Ness
  • 70,110
  • 9
  • 98
  • 181
David Tonhofer
  • 14,559
  • 5
  • 55
  • 51
  • Ok, I see, so is there any workaround if I want to use the "burnt" one twice in order to produce two different queues from an initial one ? – but-why Jun 06 '21 at 14:43
  • 1
    @but-why You can use [copy_term/2](https://eu.swi-prolog.org/pldoc/doc_for?object=copy_term/2) to create a deep copy with renamed (fresh) variables, i.e newly allocated "empty cells". – David Tonhofer Jun 06 '21 at 15:09
  • but if I am going to copy a list, why shouldn't I use append in the first place ? – but-why Jun 06 '21 at 15:20
  • @but-why The idea of the "difference list" is that nothing of the structure existing at _t0_ is copied, you would just "append at the end", growing the structure at the place where it is still undefined. However, to keep the "difference listness" of the variables named the tip and the fin of the difference list, you then have to switch to a new context. This is generally done by a tail-recursive call. In the code using "queue" this is obscured because it _looks as it was_ object-oriented or functional, but really isn't, you cannot use the "old queues". – David Tonhofer Jun 06 '21 at 15:57
  • @but-why If you used `append/2`, the structure existing at `t0` would be fully defined (no empty cell at the fin), and you could keep it forever, but it also would have to be fully copied at every append. If you want to have append to the "difference list" while still keeping the _same_ difference list at `t0` for another use (but why?), you would indeed have to deep-copy it first and you might as well use `append/2` directly. – David Tonhofer Jun 06 '21 at 15:59
  • it really _is_ functional though, where you also can't have different tails in the same list. – Will Ness Jun 06 '21 at 17:05
  • @but-why to repeat what DavidTonhofer said, if you `append(X, Y, Z)`, it makes a fresh shallow copy of the whole structure of `X` and keeps that of `Y`, in `Z`. consider `X=[A,B|T], T=[], Y=[C|T2], append(X,Y,Z), T2=[100].`. – Will Ness Jun 06 '21 at 17:05
  • @DavidTonhofer `Q1, Q2` being "useless" is a bit of an overstatement, you can still query them for the elements in them, with `queue_head/3`. you just can't enqueue new elements into them (you can enqueue the same ones). interestingly `0` is not necessary, you can have a fresh var there and then even have negative-length queues (do more pops initially, only later completed with the necessary adds) -- I think I saw this in Clause and Effect, was it, or maybe the Art of Prolog. never tried it for real myself though. – Will Ness Jun 06 '21 at 17:26
  • @WillNess Page 3 of these [Lecture Notes by Frank Pfenning](https://www.cs.cmu.edu/~fp/courses/lp/lectures/11-diff.pdf): "Negative Queues". Agree that Q1 and Q2 are not useless but they are like burnt stages of a satellite launcher. Possibly reusable, but probably not. – David Tonhofer Jun 06 '21 at 20:27
  • The "burned" queues are not burned and are not invalid. I appreciate your attempts to develop a new vocabulary for Prolog but it might be that this only adds to the confusion instead of clearing it up. – TA_intern Jun 07 '21 at 07:58
  • I also notice now that in your diagrams the length of the queue is `s(0)` even if the queue itself has two elements in it. Is that right? Maybe I am reading it wrong. – TA_intern Jun 07 '21 at 10:09
1

Prolog variables cannot be reassigned. You cannot reuse them. I don't know if calling variables "burned" helps much, they aren't burnt, they are bound to a concrete value.

Don't use "write" and friends, unless you are doing some complicated print-style debugging. Try things out on the top level, you will get everything printed out anyway. Here is how you can use this queue implementation. Note that I am using Q0, Q1, Q2, etc because I have trouble counting the underscores once there is more than one underscore.

Enqueueing a, then b at the end of the queue:

?- empty_queue(Q0), queue_last(Q0, a, Q1), queue_last(Q1, b, Q2).
Q0 = queue(0, [a, b|_15096], [a, b|_15096]),
Q1 = queue(s(0), [a, b|_15096], [b|_15096]),
Q2 = queue(s(s(0)), [a, b|_15096], _15096).

Enqueueing a, then b, then popping the first value you enqueued (FIFO order):

?- empty_queue(Q0), queue_last(Q0, a, Q1), queue_last(Q1, b, Q2), 
    queue_head(Q2, Popped, Q3).
Q0 = queue(0, [a, b|_17772], [a, b|_17772]),
Q1 = queue(s(0), [a, b|_17772], [b|_17772]),
Q2 = queue(s(s(0)), [a, b|_17772], _17772),
Popped = a,
Q3 = queue(s(0), [b|_17772], _17772).

Pushing at the front twice, then popping (LIFO order):

?- empty_queue(Q0), queue_head(Q1, x, Q0), queue_head(Q2, y, Q1), 
    queue_head(Q2, Popped, Q3).
Q0 = queue(0, _21688, _21688),
Q1 = Q3, Q3 = queue(s(0), [x|_21688], _21688),
Q2 = queue(s(s(0)), [y, x|_21688], _21688),
Popped = y.

The answer that I linked in the comment below your question (here it is again: https://stackoverflow.com/a/31925828/14411997) explains in some detail how this works. It also has links to other related Q/As and so on.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
TA_intern
  • 2,222
  • 4
  • 12