What does the "-" symbol mean in Prolog when dealing with lists?

Question

I was reading the answer to this question,

p(X) :- read(A), q(A,X-[]).

q(end,X-X) :- !.    
q(A,[A|X]-Y) :- read(B), q(B,X-Y).

The code above uses the syntax List-List. I somewhat understand what is going on, but I want to know what exactly what the "-" symbol/predicate does here. Also, is this SWI specific?

Answer 1

The (-)/2 to represent difference lists is a rather uncommon convention. In older books, another operator (\)/2 was used too.

Many prefer to use two separate arguments instead. There are several advantages compared to using an operator:

1. The predicate cannot accidentally be used with an uninstantiated variable for the argument. Think of calling q(A, X) in place of q(A, X-[]).

2. Execution is even a bit more efficient when using two arguments. Many systems, like SWI, have to create each (-)/2 structure dynamically.

Nevertheless, there is also another way to use difference lists, which is often less error-prone: You might use a dcg for this purpose.

In fact, there are two errors in the program, one of which is caused by the way how difference list are handled. The other error is that the program does not handle end-of-file. It would be better to use end_of_file in place of end. But that's a superficial thing you would have found yourself sooner or later.

The other, more subtle error is due to the interaction between difference lists and the cut. I am not a big fan of cuts, but let's look into that rule. A cut cuts after everything to its left-hand-side has been executed.

q(end_of_file,X-X) :- !.

The first argument is the atom end_of_file. Since we are using q/2 only with the result of read/1 as first argument, this can only be a comparison. So we are at the end of the file (or stream). Then, however, there are further things that must hold. And only if those succeed as well, will the cut be executed: The second argument must be a (-)/2 (ok, in all places there is a minus at its place). And then: The two arguments of (-)/2 must be the same (must unify). Why? We are at the end of the file, but if those arguments do not unify, the other rule will be tried.

When does this happen? Here is such a nasty case:

p([X,Y,Z]).

And simply enter a single constant, say my_constant. and then press Cntrl-d or Cntrl+z. What should p/1 do in such a case? Ideally, it would fail after you finished the input. However, it will wait for further input.

The reason is the inappropriate placing of the cut. We say that p/1 is not steadfast. This is a common error in Prolog programs. I can only recommend to reduce the usage of cuts and the adoption of DCGs. With DCGs, this cannot happen:

p2(X) :- read(A), phrase(q2(A),X).

q2(end_of_file) --> !.
q2(A) --> [A], {read(B)}, q2(B).

With DCGs, the cut is executed regardless of the argument of p/1.