Is it possible to write an empty list as a difference list in Prolog?

3
votes

Empty lists are ... strange, to a Prolog beginner like myself. I would say that it isn't possible to write an empty list [] as a difference list T1-T2 just as it isn't possible to write an atom as a difference list. However, I would guess that to use recursion, there must be a way to use [] in a difference list setting. I have Google'd for this but I cannot find an answer, and Bratko (Prolog Programming for AI) only briefly touches the subject.

So, is it possible to write an empty list as a difference list in Prolog, if so how and when would it be useful?

2
listprologempty-listdifference-lists
After seeing your other question, How to use difference lists in a Prolog interpreter, I see that you are reading Bratko. In there it reads The empty list is represented by any pair of the form L-L. In your question you have it as T1-T2, so are you asking about two different list that are not the same and using them to represent the empty list? Note the emphasis on represent. - Guy Coder
@GuyCoder DCGs indeed come in handy (we discussed them in class as well), though it still doesn't make the empty list clear to me. The idea and benefit of 'representing' a structure (say [a,b]) as a difference list [a,b|T]-T) escapes me. As I commented here it's in particular not clear how concatenating/appending is solved with difference lists since the result is not what you'd want - if I'm not mistaken. - Bram Vanroy
@GuyCoder As an example, we want to append [a,b] and [ c,d]. Proposed solution: conc_d([a,b|T]-T, [d,e|T1]-T1, L). However, the result would be L = [a,b,c,d|T1]-T1, but as a programmer I would need [a,b,c,d], plain and simple. I have a feeling I am missing the point, but I don't see the practical benefit or fail to see how to use difference lists in practice. - Bram Vanroy
Here is one reference about pointer to end. It is from "The art of Prolog : advanced programming techniques". Using Google Scholar search the book for difference list pointer end and you should be on page 286. - Guy Coder
I would generally use a difference list inside a computation when I need efficient appending. When that computation is finished, I'd probably hand a normal list back to the calling process. This is something phrase/2 does for you automatically when using DCGs. But this goes for any data structure with holes, not just difference lists—I may need holes (like the end of the list) while computing something but I don't usually want to reason over them in general. - Daniel Lyons

2 Answers

5
votes

Problems with understanding this topic are typically due to using misleading terminology.

As recommended in tutorial.pdf and especially pap95.pdf, use for example list difference or simply difference.

Section 5 of Teaching beginners Prolog contains relevant reasons for this.

The empty list is uniquely denoted by the atom [].

Note that a list difference always means reasoning about two lists, and due to this categorical difference between a single and multiple lists, you can at best find some correspondence or analogy, but not identity between the empty list and a list difference.

I completely support the view expressed in the paper above that you should focus on using DCGs, at least at first. Reasoning about differences explicitly will come naturally later to you.

0
votes

Appending two list differences means just a unification of first diff's end pointer with the second one's head. With regular lists it requires retracing of the whole list structure of the first list. Thus repeated concatenation on the right is linear with the list difference technique, and quadratic with plain lists.

When all the intended concatenations are done, to return the whole structure as a plain list to a caller we just unify the "end pointer" logvar with [].

In C terms, list difference is a portion of singly-linked list where we maintain two variables: its head pointer but also its tail pointer:

// typedef struct { int payload; node* next } node;
typedef struct { node** head; node** tail } list_diff;

Now each concatenation is just an assignment of the end pointer:

void diff_concat( list_diff* a, list_diff* b)
{
    *(a -> tail) -> next = *(b -> head);
    a -> tail = b -> tail;
}

And finalization is

void diff_finalize( list_diff* a)
{
    *(a -> tail) = NULL;  // or some sentinel value, whatever
}

In Prolog we could represent it as a binary term like -/2, e.g. -(A,B) or A-B.

But (as in C also) there's no actual need to build an actual structure in memory just for holding the two pointers; we can just maintain two logvars individually. Or let DCGs do it for us.

The above was the motivational introduction to list difference technique, "what are they good for?". It also makes clear that the representation of empty difference is 

list_diff* d;
*(d -> head) = *(d -> tail);

Or in Prolog, a pair of logvars unified with each other: L-L, var(L). To see why, see what happens when empty diff is appended with some other diff on its right (it is always on the right that we append things, thus growing the lists in the top-down manner). My C may be off here, the idea being that by setting the tail the appending to an empty diff will also update its head.