CODEWITHSUNDEEP
prolog
Bento
Bento

Reputation: 231

Sorting program for SWI Prolog

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.

Upvotes: 0

Views: 268

Answers (1)

user1812457
user1812457

Reputation:

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.

Upvotes: 1

Related Questions