Saturday, October 14, 2006

Lists are not sets, Prolog is not logic

In Ivan Bratko's Prolog. Programming for Artificial Intelligence, in the part introducing lists, there's an obvious exercise consisting in writing a program that gives all the subsets of a given list. In terms of Prolog: a predicate subset(Set,Subset), where all the elements of Subset are elements of Set.

The task seems elementary, but in fact it's quite tricky. The program I wrote did only half of the job, and when (after a half an hour of frantic debugging) I eventually checked the author's program in the Solutions, it turned out that it neither did all the job properly. The interesting point is that this example shows how logic background may in some cases influence your programming intuitions.

But first things first--the two programs and what is wrong with them. The “canonical” solution is the following:
subset([],[]).

subset([First|Rest],[First|Sub]) :-
subset(Rest,Sub).

subset([First|Rest],Sub) :-
subset(Rest,Sub).
My solution is a bit simpler:
m_subset(Set,[]).

m_subset(X,[Y|Tail]) :-
m_subset(X,Tail),
member(Y,X).
What's wrong with the two programs? Well, the canonical version deals fine with generating all the subsets of a given set/list--that is, when you give Prolog the following command:
subset([1,2,3],X).
However, when it turns to checking whether there is inclusion between two given sets, it appears to be quite lame: it won't give you the correct answer unless the two lists are given in the same order. That is, it says “no” to the query
subset([1,2,3],[3,2]).
(I have to make a remark that the stipulation that the lists should be sorted in the same way wasn't given in the text of the exercise).

My program, on the other hand, is great in determining if there is an inclusion, but as for the second task... Well, it just doesn't stop in the right moment. That is, after generating all the subsets of [1,2,3] it starts saying
[1,2,3,1] ;
[1,2,3,2] ;
[1,2,3,3] ;
...
etc.

In fact, that is true (if we want to use lists to represent sets, we should ignore any double occurrences), but if I wanted to have a list of all subsets and manipulate it, an infinite list would not really be the best thing.

I claim that my definition of subset is good, and in some aspects even superior over Bratko's: it is shorter, it's more intuitive, it takes account of some trivial set-theoretic facts the latter ones ignore (like for example that the empty set is a subset of every set). The only problem is that lists just aren't sets (very surprising, isn't it?), and they have different conditions of identity. So when Prolog finds the four element list, which represents a set that already was given, it thinks it is something new. Well, and (sadly), Prolog it's completely right: it is something new.

Now, this problem allows us to observe the fact that Prolog, even if it is not an imperative but a declarative programming language, it is still a programming language, not logic. And things like infinite classes just aren't good. So, my approach towards it should be more as my approach towards e.g. scheme than to logic. And that's why, even if my program was directly translatable to predicate calculus and set theory (of course, limited to Horn clauses), it just wouldn't do.

4 comments:

zero said...

Hello,
I'm Ertan Dogrultan from Turkey, Bogazici University. I am studying Computer Engineering and Mathematics. Your small article about Prolog has been helpful to me. You can contact me if you want I am also interested in logic and mathematics.
e.dogrultan [at] gmail [dot] com

szopa said...

Thank you. Sorry for not noticing your comment before, but I've been doing quite a lot of other things recently ;-)

Anonymous said...

Well, you could always just sort your subset list first. If it deals with it correctly when they are sorted, then just adding something like

sort(Your_subset,Sorted_subset)

and then just use that for your comparison. Since all sorted subsets are as subsetty as unsorted subsets, there's no breach of any logic.

Of course, this is unelegant, but if it works correctly, and elegant solutions don't, well... :p

黃耀賢 said...

Hi. I don't agree the title of this post. Does "lists are not sets" imply "Prolog is not logic?"

By the way, though what you've described is agreeable, I wonder how students answer the question: "find all subsets of the set {1, 2, 3}." Will someone give an infinite answer "{}, {1}, {2}, {3}, {1,1}, {1,2}, ..., {1,1,1,1}, {1,1,1,2}, ..." Interesting. :)