9

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?

Community
  • 1
  • 1
ivt
  • 301
  • 3
  • 9
  • @p.s.w.g: Why did you vote to close this? – false Mar 17 '13 at 12:40
  • 1
    `'-'` 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). – Will Ness Mar 17 '13 at 13:49
  • You are totally right - unfortunately, it won't let me remove the flag. I deleted my comment, however. – Troy Alford Mar 17 '13 at 18:51
  • 1
    @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. – false Mar 17 '13 at 21:58
  • I hope so - the question shouldn't be penalized for me mis-clicking while reviewing with a head-cold. – Troy Alford Mar 18 '13 at 18:25

2 Answers2

6

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

false
  • 10,264
  • 13
  • 101
  • 209
  • `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. – Will Ness Mar 17 '13 at 13:46
  • @WillNess: You know a concrete library in a Prolog system that uses this convention? – false Mar 17 '13 at 13:49
  • no, I didn't say anything like that. "Cause and Effect" is an 80-s book, I think. – Will Ness Mar 17 '13 at 13:51
  • @WillNess: That's why I said uncommon convention. Likewise AoP uses \ . – false Mar 17 '13 at 13:52
  • it is indeed an accepted wisdom that two separate arguments should be used when possible. – Will Ness Mar 17 '13 at 13:55
  • @WillNess: BTW, why don't you review for prolog? There are again two closing robots .... – false Mar 17 '13 at 15:14
  • 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. :) – Will Ness Mar 17 '13 at 16:54
  • @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#). – false Mar 17 '13 at 22:00
2

I thought you meant the :-.

It is a difference list.

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

BrettD
  • 381
  • 1
  • 4
  • 12