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?

Thunell

@p.s.w.g: Why did you vote to close this? – Atone

'-' here is not a predicate, it is a "functor" - name of a compound structure. E.g. in f(1,2), f is a functor of a compound term with two arguments. (if you search, do search for "Prolog functor"; just "functor" will show you a ton of unrelated stuff). – Bretbretagne

You are totally right - unfortunately, it won't let me remove the flag. I deleted my comment, however. – Cardigan

@TroyAlford: Fine. I flagged the question to get moderator attention. With your comment here, there should be no doubt. Otherwise it would remain like that for weeks. – Atone

I hope so - the question shouldn't be penalized for me mis-clicking while reviewing with a head-cold. – Cardigan

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.

Atone

q(end_of_file,Z) :- !, Z=X-X. q(end,Z) :- !, Z=X-X.. Just saying. I think "Clause and Effect" uses the '-' functor, IIRC. – Bretbretagne

@WillNess: You know a concrete library in a Prolog system that uses this convention? – Atone

no, I didn't say anything like that. "Cause and Effect" is an 80-s book, I think. – Bretbretagne

@WillNess: That's why I said uncommon convention. Likewise AoP uses \ . – Atone

it is indeed an accepted wisdom that two separate arguments should be used when possible. – Bretbretagne

@WillNess: BTW, why don't you review for prolog? There are again two closing robots .... – Atone

I'm weak on meta stuff. :) And if I say "don't close" it just continues counting to 5, isn't it? It's just as if I didn't vote at all? Also, I don't know, technically, how to do that (specifically for Prolog I mean). If I go to "review", I see the queues, mostly about stuff I don't know anything about anyway. ... OK, I see it now, in the filter there's "tag" field. Thanks for the suggestion. :) – Bretbretagne

@WillNess: The policy changes here every now and then. You can either go to "review" and filter for Prolog. Or you flag the post stating that it is not a duplicate. There is a period after which the duplicate-flags would fade (provided noone else would flag it), but it is much too generous for a tiny group as Prolog (which is roughly 1/100th of C#). – Atone

Answer 2

I thought you meant the :-.

It is a difference list.

http://en.wikibooks.org/wiki/Prolog/Difference_Lists

Vallonia