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

Before learning about difference lists, first learn about the [tag:dcg] formalism. First use it to appreciate its power, only then start to think how it is implemented (that is, some weeks later). — false, Aug 10 '15 at 11:35
In any case, your predicate is not an implementation of difference lists. — false, Aug 10 '15 at 11:36
ok - i thought that DCGs in Prolog were syntactic sugar hiding an underlying difference list type implementation - but happy to be advised otherwise, I think the predicate in the OP utilises difference lists to implement append? I've added a second - is that any better? i.e. is it true to say it is a difference list append predicate? — bph, Aug 10 '15 at 11:42
It all depends on your taste for sweetness: The translation to Prolog is relatively straight-forward, no deep semantics involved. I still have some hesitation calling it sugar, when taking into account the very fine and complex nitty-gritty details ... — false, Aug 10 '15 at 11:45
your link got me here: http://www.metalevel.at/dcg.html - worth digesting? — bph, Aug 10 '15 at 11:46
Prolog's logvars are not immutable - they are *set once*. Check out my answers on diff-lists for more discussion in line with your approach. — Will Ness, Aug 10 '15 at 11:48
OK, but do not forget to read "Prolog and Natural-Language Analysis", you find it in [tag:prolog]. I will add it to [tag:dcg], too — false, Aug 10 '15 at 11:48
Is a logvar another term for Prolog variable, or something more specific? — bph, Aug 10 '15 at 11:51
you can also use "open list" as the extention being appended, to end up with an extended open list, so the process can continue... exactly how the diff lists work. — Will Ness, Aug 10 '15 at 11:51
ah of course - what a dope! immutable and set once at first glance seem to imply the same thing - where do they differ? — bph, Aug 10 '15 at 11:53
about the mutability - is is what unification is doing, in a principled way. imperative languages have raw immutability, in an unprincipled way. — Will Ness, Aug 10 '15 at 11:54
Haskell's variables are immutable, they can only be defined once. but they can't be in an explicitly "uninitialized" state, as Prolog's logvars do. — Will Ness, Aug 10 '15 at 11:54
@false sorry i'm a bit unclear, are you saying read a question with the title "Prolog and Natural-Language Analysis" tagged with 'prolog' and 'dcg' on stack overflow? If so i searched for it but returned a blank (ah i think it maybe a book?) — bph, Aug 10 '15 at 11:58
On http://stackoverflow.com/tags/prolog/info you find it at the end! It's pdf, book-on-demand, and example code. — false, Aug 10 '15 at 12:07
i.e. you call `X=[a,b,c|Z],diff_append(X,Z,[d,e,f])` but you can also call `X=[a,b,c|Z],diff_append(X,Z,[d,e,f|Z2])`. there's no need to use a compound term under `-/2`, passing the arguments straight up is more efficient. — Will Ness, Aug 10 '15 at 12:18
so you'd want to make it more symmetrical; a usual difference list append predicate "definition" is `app(A-B,B-C,A-C).` but with sub-parts just held as logvars, no definition is needed. for two lists `A-B` and `X-Y` you'd just write `B=X` (using `-` only conceptually there). — Will Ness, Aug 10 '15 at 12:28
Making variables mutable in Prolog wouldn't make sense at all like it does in imperative languages. Prolog works through an "argument" to determine if something is true. To make a variable mutable in the middle of that would be like me making an argument about something to you but then changing the premises along the way. The argument becomes nonsense. Prolog *does* allow variables to change through backtracking, which means the argument backs up to a point where a premise can change then moves forward through argument again. — lurker, Aug 10 '15 at 15:51

score 5 · Accepted Answer · edited May 23 '17 at 12:16

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.

so perhaps a summarisation could be that a prolog list is like a stack, you have to pop everything of the top before you can get to whats at the bottom, but adding the 'hole' at the end to make a list into a difference-list turns it into a queue, with both ends accessible directly? — bph, Aug 12 '15 at 10:22
@bph Exactly. I will actually add the code for a basic Prolog "queue" to the answer if I find a few minutes because it is relevant to your question. — , Aug 12 '15 at 11:01
@bph I added it. For more on difference lists and Prolog in general I strongly recommend "The Craft of Prolog" by Richard O'Keefe. It is somewhat old but I don't know of any book on Prolog that goes into that much technical detail and has that much useful code in it. — , Aug 12 '15 at 15:32
Ok. Ploughing through clocksin,mellish and sterling,Shapiro at the moment. Will see if I can get a copy of o keefe — bph, Aug 12 '15 at 19:35
@bph It is necessary to be somewhat comfortable with Prolog before reading that book, it is quite technical. What you have at the moment is very good. — , Aug 13 '15 at 06:02
@false I linked to `read_pending_codes/3` because its documentation is complete. Will link both. — , Dec 01 '16 at 11:32

Difference lists in Prolog and mutable variables

1 Answers1

Implementing a queue

Linked