queue - Difference lists in Prolog and mutable variables

Question

Are difference lists a means to 'get-around' the fact that variables are immutable in prolog?

I.e. if I implement append using difference lists:

diff_append(OpenList, Hole, L2) :-
    Hole = L2.

And then run:

X=[a,b,c|Hole], diff_append(X, Hole, [d,e,f]).

The X, in a way, has been used as a mutable variable. For our intents and purposes it has been changed?

In other words, the fact that we have been able to modify X (mutable) rather than having to construct a new list, say Z (immutable) is what makes difference lists attractive. So why not just have mutable variables?

Update:

diff_append2(OpenList-Hole,L2):-
    Hole=L2.

X=[a,b,c|Ho]-Ho,diff_append2(X,[d,e,f]).

Answer 1

Difference lists are rather used to get around another limitation: that you need to traverse the whole list to "append" to its end (think of a singly linked list where you have a pointer to the first element, but not to the sentinel).

In code: since a list [a, b, c] is (traditionally) the nested term .(a, .(b, .(c, []))), adding a d to the end of it means "peeling off" each term before replacing the [] at the end (the center) with .(d, []). So, to implement append/3:

append([], L, L).
append([H|T], L, [H|R]) :-
    append(T, L, R).

which is how it is traditionally implemented.

This is another answer which covers the topic quite extensively.

Something that that answer doesn't go into is that library predicates that "return" lists might offer a difference-list version of the predicate, for efficiency reasons, in case you might want to append to the end of the list. Examples would be read_pending_codes/3 and read_pending_chars/3, or the four-argument version of findall/4.

DCGs are a convenient way of working with difference lists without explicitly passing around the two arguments for the list and the tail.

Implementing a queue

The three most basic operations for a queue: making an empty queue, pushing to the back, and popping from the front:

%% 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)).

As one should notice, queue_head/3 will let you pop from the front or push to the front of the queue. queue_last/3 only lets you push to the back: once you have pushed an element, you don't have (constant time) access to the element before it in the queue.

The first argument to the queue/3 term is there to prevent what Richard O'Keefe calls "hallucinating" variables, that is, popping from a queue more elements than have been pushed to it. It is interesting to leave out that first argument from the predicates above and see what happens:

?- empty_queue(Q0), queue_head(Q0, H, Q1).
Q0 = queue([H|_G341], [H|_G341]),
Q1 = queue(_G341, [H|_G341]).

instead of failing.