0

Why this program answers False in SWI-PROLOG?

sor(x, y):- sorted(y), perm(x, y).
sorted([]).
sorted([x, []]).
sorted([x, y, z]):- mi(x, y), sorted([y, z]).
perm([], []).
perm([x,y],[u,v]):- delete(u,[x,u],z), perm(z,v).
delete(x,[x,y],y].
delete(x, [y, z], [y, w]):- delete(x,z,w).
mi(0, x).
mi(s(x), s(y)):- mi(x, y).

for the query ?-

sor([s(s(s(s(s(0))))), s(s(s(s(s(s(0)))))), s(s(s(0))), s(s(0)), []], y).

This is an adaptation to SWIProlog of an inefficient sorting-program used as example in the book Foundations of Logic Programming, by Loyd (you can find the original SLOWSORT program example in this pdf, on page 9)

SWI Prolog is a standard Prolog, isn't it?

Edit

Now I have tried to correct the program (looking a little to the lists syntax in Prolog)

sor(X, Y):- perm(X, Y), sorted(Y).
sorted([]).
sorted([X|[]]).
sorted([X|[Y|Z]]):- mi(X, Y), sorted([Y|Z]).
perm([], []).
perm([X|Y],[U|V]):- delete(U,[X|Y],Z), perm(Z, V).
delete(X,[X|Y],Y). 
delete(X, [Y|Z], [Y|W]):- delete(X, Z, W).
mi(0, X).
mi(s(X), s(Y)):- mi(X, Y).

and changing the query in

sor([s(s(s(s(s(0)))))|[ s(s(s(s(s(s(0))))))|[s(s(s(0)))|[ s(s(0))|[]]]]], Y).

Well, Prolog now gives success, but it gives this substitution

Y = [s(s(0)), s(s(s(0))), s(s(s(s(s(0))))), s(s(s(s(s(s(...))))))]

and I don't understand the meaning of (...): Why not (0)?

Edit2

I notice that after giving the command swipl -s slowsort.pl I obtain this error message

Warning: /home/navigazione/Scrivania/slowsort.pl:3:
Singleton variables: [X]
Warning: /home/navigazione/Scrivania/slowsort.pl:9:
Singleton variables: [X]

It seems to refer to 3th and 9th rows of the program, but I don't understand what it means.

false
  • 10,264
  • 13
  • 101
  • 209
Bento
  • 223
  • 1
  • 12
  • 2
    Variables in Prolog _must_ be upper case. I also think there is some confusion going on here about arity and lists. – Daniel Lyons Oct 05 '15 at 06:17
  • okay for the uppercase, I'm litterally new to Prolog syntax. About the arity what do you mean? I have meant the lists have arbitrary arity.. please take a look to page 9 of the book at the link I have given – Bento Oct 05 '15 at 06:31
  • 1
    SWI-Prolog is quite standard, yes, but in the book you have linked, the "code" examples are **not** correct, standard Prolog syntax. Try something like [Learn Prolog Now!](http://www.learnprolognow.org/lpnpage.php?pageid=online) instead if you are an absolute beginner. –  Oct 05 '15 at 06:59
  • Yeah, looking at the PDF you have linked, this is not going to teach you how to _program_ in Prolog. It is rather about the theory of logic programming. –  Oct 05 '15 at 07:02
  • @Boris,I had found that interesting site some hours ago, and I had given a glance fast to some points that I was interested in, but they seem to be insufficient now. – Bento Oct 05 '15 at 07:36
  • @Boris, note however that Loyd takes the example later in the book, and he says that (reversing the subgoal of sort) you *get an higly inefficient sorting program for the Prolog standard*. I then have a text that develops over the theory also the syntax but I only read the first chapter that introduces it briefly. – Bento Oct 05 '15 at 07:44
  • What is your goal? If you want to learn Prolog programming, the Lloyd book is definitely not going to help you in the short run. The "Learn Prolog Now!" book has some deficiencies but it is the best on-line tutorial available (to my knowledge). If you just want to learn the theory behind logic programming, the Lloyd book might be fine, but at least don't try to type in the examples as if they were correct code because they are not. –  Oct 05 '15 at 07:45
  • Yes I think the tutorial/book you mentioned is very special. I point to it and to my book (it's not an english book, translated the title sounds Logic Programming and Prolog; it treats all the aspects in the terminal part, ie. IA etc.). I think Learn Prolog Now! for my actual porpouse is the correct item. – Bento Oct 05 '15 at 07:55
  • See the answer! These are all problems you will avoid if you work your way through a tutorial first, or simply google the warning / error messages! –  Oct 05 '15 at 08:15
  • [EDIT of my comment 3] @Boris, note however that Loyd takes the example later in the book, and he says that (reversing the **ATOMS** of sort) you get an higly inefficient sorting program for the Prolog standard. I then have a text that develops over the theory also the syntax but I only read the first chapter that introduces it briefly. – Bento Oct 05 '15 at 22:37
  • I am not sure what you mean with that comment. You should try using the built-in `sort/2` on the same list as in your example query: it sort it perfectly fine. –  Oct 05 '15 at 23:05

1 Answers1

1

Great, you managed to translate it to correct Prolog :)

What you see is the top level trying to make things readable by omitting stuff (the ... means there is stuff there that is not shown). See this question and answers for different ways you can tell the top level to show the complete term instead of hiding parts of it.

As for the singleton variable warnings, it just tells you that you have logical variables (on lines 3 and 9) that you have only mentioned once in their syntactical scope. You can write _X instead of X to make it explicit that you are not using the value of the variable in that scope.

Community
  • 1
  • 1
  • thanks to you and Daniel who has illuminated me in some way about arity problem. So singleton is merely a warning (just like that sort in traditional imperative languages when you declare a variable without using it - perhaps a forgetting) telling you that something on a logical ground could be problematic (this is not the case for my example). A technical matter of Prolog language/compiler, with no correlation with the theoretical counterpart. – Bento Oct 05 '15 at 20:49