Sorting program for SWI Prolog

Question

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.

Variables in Prolog must be upper case. I also think there is some confusion going on here about arity and lists. — Daniel Lyons
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
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! instead if you are an absolute beginner. — user1812457
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. — user1812457
@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

Unknown Unknown · Accepted Answer · 2015-10-05T08:03:37

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.

Sorting program for SWI Prolog

1 Answers