Understanding difference lists (Prolog)

Question

I'm having trouble understanding difference list, particularly in this predicate:

palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
   palindrome(A, B),
   B=[C|D].

Could anyone help me follow what's happening?

Cranmer

Before understanding difference lists, try to understand DCGs. See also #6443250 – Mastat

first clause seems wrong, it means identity – Lepton

@CapelliC: Not identity, but the empty list. – Mastat

@Mastat I don't follow... wouldn't A unify with anything, not just empty lists? How is this not a general identity relationship? – Landsman

I'm not clear on how the second predicate works to define a palindrome either, since ?- [a,b,c,b,a] = [_|A]. A = [b, c, b, a]. and but A is not a palindrome. – Landsman

@aBathologist: The best is to start with DCGs and phrase/2. See link above. From that you will see that the empty list (actually empty sequence) is described. If people plunge too early into difference lists they ignore the very fact that logicians needed about 7 years to understand them. That is from Robinson (1965) until Colmerauer (1972). – Mastat

@Mastat I think there might be some miscommunication? I believe CapelliC's remark was pointing out that as written here the first clause defines identity. Were you saying that, ideally, in a different context where palindrome is implemented correctly, this clause should be the empty list? – Landsman

@aBathologist: OP's program is the very expansion of a DCG. See my first comment. Thus, it must be used as palindrom(A,[]). – Mastat

@Mastat from operational viewpoint diff lists are just open-ended lists with explicitly maintained end pointer. pretty simple. without this, DCG is a complete mystery. – Chivers

@WillNess: Then can you explain me what is "open ended" to them, if the list is given. I cannot see anything there that is "open ended". – Mastat

@Mastat difference list is a pair of A=[.....|Z] and Z, correct? If Z=[] or other "closed" list, A is of course not open anymore, but then there's no more magic. – Chivers

@WillNess: The "magic" of the DCG-encoding using difference lists is that in works "in both directions", terminates nicely, and is comparable in efficiency to parsers in traditional languages (for comparable situations, indeed). But your statement: A difference list is ... is misleading because difference lists are not an explicit data structure ; rather an encoding. – Mastat

@Mastat about your last remark, whether we're holding a pair of ints, or two separate ints that we use throughout as if they were a pair, is the same situation to me. Same with logvars. – Chivers

@Mastat about efficiency, -- are you familiar with this 1974 :) work: cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR19 ? It basically describes the tail-recursion modulo cons optimization which is the basis of Prolog's efficiency in handling diff-lists, AFAI understand it. – Chivers

@WillNess: More or less familiar. More familiar with idioms like nreverseing the list for a tail-recursive mapcar. And for efficiency: palindrome/2 is not tail recursive. Still many DCG translations do it this way and incur a call stack to be used for various reasons. See also: #13100864 – Mastat

@Mastat I always thought TRMC was due to David H.D. Warren, 1980. It was a big surprise to see they already did it in 1974! :) In Lisp... :) but, they didn't name this thing. Like Lorentz and Einstein, you know. -- for palindrome, couldn't it be palindrome([C|A],D):- palindrome(A,[C|D]).? - and then it would be tail-recursive. – Chivers

Answer 1

palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
   palindrome(A, B),
   B=[C|D].

Seeing the arguments to this predicate as a difference list, the first clause says, a list from A to A (i.e., an empty list) is a palindrome.

The second clause says, a one-element list is a palindrome, whatever that one element is.

---

Don't panic!  Difference lists are just lists with explicit end "pointer"

A normal list, say [1,2,3], is a difference between its start and its end; the end of a normal list is always an empty list, []. That is to say, for a list [1,2,3] we are supposed to call this predicate as palindrome( [1,2,3], []) — namely, check whether the difference list [1,2,3] - [] is a palindrome.

From the operational point of view, a difference list is nothing but a (possibly open-ended) list with explicitly maintained "end pointer", for example: A - Z where A = [1,2,3|Z] and Z = []. Indeed, [1,2,3|[]] is the same as [1,2,3]. But when Z is not instantiated yet, the list A is still open ended - its "end pointer" Z can be instantiated to anything (but only once, of course, sans the backtracking).

If we were to instantiate Z later to an open-ended list, say, Z = [4|W], we'd get a new, extended difference list A - W where A = [1,2,3,4|W]. The old one would become A - Z = [1,2,3,4|W] - [4|W], i.e. still representing a prefix [1,2,3] of an open-ended list [1,2,3,4 ...]. Once closed, e.g. with W = [5], all the pairs of logvars still represent their corresponding difference lists (i.e. A - Z, A - W ...), but A is not open-ended anymore, so can't be extended anymore.

Instead of using the - functor, it is customary to just use both parts of the diff list definition as separate arguments to a predicate. When we always use / treat them as if they were two parts of a pair, then they form a pair, conceptually. It's the same thing.

---

Continuing. The third clause says, for [C|A]-D to be a palindrome, A-B must be a palindrome, and B must be [C|D]. A, D, B are lists, C is an element of a list. This might be confusing; let's use V instead. Also, use Z and Y instead of D and B, to remind us of "the end" of a list:

palindrome([V|A], Z):- palindrome(A, Y), Y=[V|Z].

V ................. V ----
  ^                 ^ ^
  |                 | |
  |                 | Z
  A                 Y = [V|Z]

Indeed, when the ...... core is a palindrome, putting two Vs around it gives us another palindrome.

Chivers

Where is your "endpointer" pointing to in: ?- phrase(n,[a],[b]). with n, [b] --> [a]? – Mastat

@Mastat this is not how we're supposed to call it. [a]-[b] is not a difference list. The OP's palindrome is regular Prolog predicate, not DCG rule, correct? – Chivers

If you do not accept the example, extend it accordingly to something that can be called with phrase/2. Your explanation reposes on a very specific property that does not hold for each and every DCG or difference list ; thus does not explain the essence of them. And: I do disagree with your statement that [a]-[b] is not a difference list. After all such difference occur in DCGs, and DCGs use difference lists. – Mastat

@Mastat I'm not prepared to defend my analogy with any degree of rigor. It was helpful to me. If DCG rules accept [a]-[b], then I can see them as being bigger than just diff-lists. palindrome([a],[b]) will fail, I see no problem with that. Of course I might be wrong and will appreciate being shown where and why. – Chivers

It was very confusing to me in AoP. Since I have used the encoding before but then was not sure whether or not this was something specific to Wisdom-Prolog (at least in the 1st edition it was advertised). – Mastat

@Mastat you're right, AoP was what I base my understanding on. Treating [b]-[a] as a difference list is new to me. :) [b,a]-[a] I can understand, but not this. – Chivers

Answer 2

The following is a summary that hopefully distills the best of the previous discussion, and adds one small but significant simplification.

First, the original question should be understood in the context of the problem at hand, which can be formulated as defining a Prolog predicate which will check whether a list is a palindrome, or more generally to generate palindromes. We wish to explore an implementation using difference lists, so we can begin as follows:

% List is a palindrome if List - [] is a palindrome:
palindrome( List ) :- palindrome(List, []).  

(As explained elsewhere, if a list, List, is the concatenation of two lists Front and Back, then Front can be viewed as being the difference between List and Back, that is, Front can be regarded as equivalent to (List - Back).)

To define palindrome/2, we begin with the two "base cases", an empty list and a singleton:

% The empty list (L-L) is a palindrome:
palindrome(L, L).

% A singleton list, ([X|L] - L), is a palindrome:
palindrome([X|L], L). 

Let us now turn to the general case.

If a list with more than one element is to be a palindrome, then it will look like this: E ... E

where ... is a (possibly empty) palindrome.

Tacking on a tail, Tail, our list must look like: E ... E Tail

Writing this regular list as [E|Rest], we can now see that the original list ( [E|Rest] - Tail ) is a palindrome if (Rest - [E|Tail]) is a palindrome, or in terms of our predicate palindrome/2:

palindrome( [E|Xs], Tail ) :- palindrome(Xs, [E|Tail]).

It's easy to see that this is equivalent to the original formulation.

That's it! Now we can, for example, generate templates for palindromes:

?- palindrome( X ).
X = [] ;
X = [_G1247] ;
X = [_G1247, _G1247] ;
X = [_G1247, _G1253, _G1247] ;
X = [_G1247, _G1253, _G1253, _G1247] 
....

Dropsonde