Thursday, December 07, 2006

Prolog and regular expressions

Some time ago I started writing a lemmatizer (i.e. a program that receives as input a word and some tags that describe it ad outputs the dictionary form of the word) for Dutch. I have been programming nearly exclusively in Prolog for the last three months, so the choice of language was quite obvious (also, I have the feeling that trying to write something serious in a new programming language helps you learn it a lot better than writing even a gazillion of text-book exercises). However, not everything was so simple. When you are doing any text-processing, you surely want to use regular expressions.

Both Prologs I usually use --SWI and Sicstus-- allow you of course to use DCG, but that was not quite what I was looking for. I wanted normal, Posix style regular expressions. First of all, it is what I know and I'm used to. Secondly, it is what the majority of people who will have anything to do with my program will be used to and will understand. And, last but not least, I don't really feel like writing and naming a new predicate every time I have to match something.

A good place for starting my quest for perl-style regexp was this. It is a quite extensive list of resources related to regular expressions. My first idea was finding a library that I could use with SWI or Sicstus. However (you may call me dumb) I didn't manage to compile or put to work any of the things I found on Van Nord's page. So, I decided to try to find a Prolog implementation that comes with regexp out of the box.

The two Prologs I tested were Ciao and Yap.

Ciao at first makes a good impression (even though it's web-page is *really* ugly), however, the regexp implemented are quite lame: the don't support extracting found groups (or at least I didn't find it), which rendered it quite useless.

In Yap (which stands for Yet Another Prolog and it's developed in Portugal), however, regexp finally worked. It's regexp library is a direct port of the FreeBSD regex library, so it's pleasantly plain and normal. The only drawback is that it is very poorly documented. For example, I spent quite a long time wondering who and why would implement regular expressions without back-references. And I would still wonder if not a lucky typo, which revealed that in Yap regexp you access groups found earlier not by a backslash followed by number, but by a *double* backslash followed by a number (maybe for some reason this should be obvious, but it wasn't for me).

So, if you want to have a regular expression that matches all strings of the form "X=X", where X may be any string, you have to write:

?- use_module(library(regexp)).
?- regexp("^(.+)=\\1$", "a=a", []).
yes


Apart from that strange incident, Yap turned to be a nice and fast Prolog implementation. I appreciate especially the SWI-Prolog compatibility module, which allows me to write exactly the way I'm used to (btw, there also exists a SICstus compatibility module). It's only a pity that Yap depends on some non-free elements (exactly, “free for non-commercial use”) which causes that Yap binaries aren't shipped in any major Linux distribution.

(Oh, and one last problem---the binaries from binaries.tar.gz crash after you try to import the library regexp... Luckily, the RPM version for Fedora works fine on Ubuntu, after you convert it to DEB with alien.)

Thursday, November 16, 2006

Sudoku

In the last week Prolog classes writing a sudoku solver was one of the exercises. Of course, this is not such a small task, so we concentrated on writing just a part of the solver. However, when I came home I felt the very strange feeling that I want to write my own sudoku solver. So here it is.

The representation I chose is a bit different from the ones I have seen in class and in the Internet. It is neither an array (Prolog emulation of an array using arg/3) of numbers, nor a plain list of numbers. It is a list of triples of the form X/Y/Value, where X and Y are the horizontal/vertical coordinates, and Value the number in the square. At first such a representation may seem a bit strange. However, it allows us (for example) to extract whole columns and rows through unification, which simplifies things a bit.

I have written the whole program with readability and conceptual simplicity in mind. This means it is not very efficient. I planned it to be as general as possible, so in principle it should be able to sort 27x27 sudoku. However, due to the lack of efficiency this may take quite a long time (provided you had a 27x27 grid partially filled with integers from 1 to 81, of course).

%
% all the elements in a column, row, 3x3 box.
%

column(X/_, Sudoku, Column) :-
findall(X/Y/Z , (member(X/Y/Z, Sudoku), nonvar(Z)), Column).

row(_/Y, Sudoku, Row) :-
findall(X/Y/Z, (member(X/Y/Z, Sudoku), nonvar(Z)), Row).


% believe me or not, this was the most difficult predicate to write.
box(Base, X/Y, Sudoku, Box) :- % Base: size of the puzzle
DiffX is (X-1) mod (Base/3),
DiffY is (Y-1) mod (Base/3),
StartX is X - DiffX,
StartY is Y - DiffY,
EndX is StartX + (Base/3) - 1,
EndY is StartY + (Base/3)-1,
findall(X1/Y1/Z,
(
between(StartX,EndX,X1),
between(StartY, EndY, Y1),
member(X1/Y1/Z, Sudoku),
nonvar(Z)
),
Box).

%
% We can assign the value Possible to X/Y without
% violating the rules of the sudoku.
%
possible(_,X/Y/Possible, Sudoku) :-
member(X/Y/Possible, Sudoku),
nonvar(Possible), !.
possible(Base, X/Y/Possible, Sudoku) :-
column(X/Y, Sudoku, Column),
row(X/Y, Sudoku, Row),
box(Base, X/Y, Sudoku, Box),
between(1,Base, Possible),
\+member(_/_/Possible, Column),
\+member(_/_/Possible, Row),
\+member(_/_/Possible, Box).

% solve the puzzle, iterating through each grid
solve(_,N,N,_).
solve(Base,N,K,Solution) :-
nth1(N, Solution, X/Y/Z),
possible(Base, X/Y/Z, Solution),
NewN is N+1,
solve(Base, NewN, K, Solution).
solve(Base,Solution) :-
N is Base*Base+1,
solve(Base,1, N, Solution).

% the main predicate
%
sudoku(Base,Constraints, Solution) :-
findall(X/Y/_, (between(1,Base,X), between(1,Base,Y)), Solution),
subset(Constraints, Solution),
solve(Base,Solution).

/*

And some example puzzles to solve:

*/

s3([3/1/3, 2/2/8,
5/1/4, 4/2/6, 6/2/3, 4/3/5,
8/1/9, 8/3/4,
1/4/5, 1/6/2, 3/6/7,
4/4/9, 5/4/1, 4/5/2, 6/5/7, 5/6/8, 6/6/6,
7/4/3, 9/4/7, 9/6/5,
2/7/3, 2/9/5,
4/8/7, 5/9/6, 6/7/5, 6/8/1,
7/9/4, 8/8/5]).

% the sudoku from class
s1([1/4/2, 1/5/3, 1/9/5,
2/2/4, 2/3/2, 2/5/9, 2/9/3,
3/1/3, 3/6/8, 3/7/7,
4/3/7, 4/8/5, 4/9/6,
5/2/9, 5/4/7, 5/5/2, 5/8/1, 5/9/4,
6/1/5, 6/4/9,
7/1/6, 7/6/2, 7/7/8, 7/8/4, 7/9/9,
8/3/8, 8/6/1, 8/9/7,
9/1/2, 9/2/5, 9/6/9, 9/7/6]).

s2([4/1/2, 5/1/3, 9/1/5,
2/2/4, 3/2/2, 5/2/9, 9/2/3,
1/3/3, 6/3/8, 7/3/7,
3/4/7, 8/4/5, 9/4/6,
2/5/9, 4/5/7, 5/5/2, 8/5/1, 9/5/4,
1/6/5, 4/6/9,
1/7/6, 6/7/2, 7/7/8, 8/7/4, 9/7/9,
3/8/8, 6/8/1, 9/8/7,
1/9/2, 2/9/5, 6/9/9, 7/9/6]).

I also wrote print_su/1, a sudoku pretty-printer. It is not very interesting, and I used findall/3 to iterate through a list and print its elements (which may be considered abusive), so I decided not to publish it here :).

Now, we can use Prolog to run the following query:
?- s1(Constraints),sudoku(9,Constraints,Sudoku), print_su(Sudoku).

1 7 3 || 4 8 5 || 6 9 2
8 4 6 || 2 9 1 || 7 3 5
9 2 5 || 7 6 3 || 1 8 4
==============================
2 5 4 || 1 7 9 || 3 6 8
3 9 1 || 8 2 6 || 5 4 7
7 6 8 || 3 5 4 || 2 1 9
==============================
4 1 7 || 9 3 2 || 8 5 6
6 8 9 || 5 1 7 || 4 2 3
5 3 2 || 6 4 8 || 9 7 1

Constraints = [1/4/2, 1/5/3, 1/9/5, 2/2/4, 2/3/2, 2/5/9, 2/9/3, ... /... /3, ... /...|...]
Sudoku = [1/1/1, 1/2/8, 1/3/9, 1/4/2, 1/5/3, 1/6/7, 1/7/4, ... /... /6, ... /...|...]

and voilà, your sudoku is ready!

(I think that it may be sensible using constraint logic programming for solving sudoku... However, I haven't reached the chapter about CLP in my book yet, so I didn't use it. ;-))

Thursday, October 26, 2006

Two programs for one chess problem

Knight's tour is one of those chess problems I always wanted to solve, but I never had enough patience. Now, thanks to Prolog, it is easy--I just have to write a simple program. And, yes, I am completely aware of the fact that solving it by myself probably would take me less time; however, at the moment I don't own a chess board (without the board it is no fun) and I feel this is a good way of improving my Prolog skills. So, here we go.

To solve the problem to visit all the squares on the board, without any repetitions, moving by horse-jumps (that seems the best way of calling the movement of the knight). The starting square and size of the board are given as parameters.

Lets represent a square on the board by a pair of numbers divided by a slash.

First of all, the way the knight moves:
boardX(8).

boardY(8).

knight(X/Y,X1/Y1) :-
boardX(BoardX),
boardY(BoardY),

(
(X1 is X+2 ;
X1 is X-2),
(Y1 is Y+1 ;
Y1 is Y-1)

;

(Y1 is Y+2 ;
Y1 is Y-2),
(X1 is X+1 ;
X1 is X-1)
),
X1 >= 1, X1 =< BoardX,
Y1 >= 1, Y1 =< BoardY.

The dimensions of the board aren't hardcoded in case we want to solve the puzzle on a nonstandard board, eg. 4x8.
knights_way([_/_],_).
knights_way([First,Second|Rest],Visited) :-
knight(First,Second),
\+member(Second,Visited), % No repetitions, please!
knights_way([Second|Rest],[Second|Visited]).



knights_tour_1(X,N) :-
length(X,N),
X=[1/1|_],
knights_way(X,[]).

knights_tour(X) :-
N is BoardX*BoardY,
knights_tour_1(X,N).
Now, this seems pretty easy (although writing it properly took me some time--I don't know Prolog very well, yet). However, not everything in life is as easy as it seems. When you try to run knights_tour on your computer, you won't get an answer, unless your computer is very fast, or you are very patient and long-lived. Why? Let's compare the times:
?- time(knights_tour_1(X,59)).
% 46,797 inferences, 0.02 CPU in 0.01 seconds (141% CPU, 2339850 Lips)

X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]

?- time(knights_tour(X,60)).
% 1,677,669 inferences, 0.50 CPU in 0.50 seconds (100% CPU, 3355338 Lips)

X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]

?- time(knights_tour_1(X,61)).
% 92,595,863 inferences, 27.43 CPU in 28.15 seconds (97% CPU, 3375715 Lips)

X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]

?- time(knights_tour_1(X,63)).
C-c C-c
Action (h for help) ? a
abort
% 4,550,510,155 inferences, 1345.57 CPU in 1418.71 seconds (95% CPU, 3381846 Lips)
% Execution Aborted

It seems clear, that the number of inferences is growing very fast, or at least faster than we can afford. That shouldn't be a big surprise: the knight has on average from 2 to 8 possible moves--the size of the solution space we have to search grows exponentially. Blind search just won't do.

So, what we now need is a good heuristic. Fortunately, there's such a heuristic, and it has been developed in 1832 by H.C. von Warnsdorf, which says that the best available square is the one which is available from the least unvisited squares (see here and here). It is said not to work very well for boards bigger than 76x76, but I don't think it's a very big deal.

heuristic(X/Y, Visited, N) :-
findall(A,knight(X/Y,A),Possible),
subtract(Possible,Visited,List),
length(List,N). % I know this may be incorporated to the next predicate, but somehow I feel that splitting it apart is a good thing.

better_heuristic(Visited,A,B) :-
heuristic(A,Visited,HA),
heuristic(B,Visited,HB),
HA =< HB.

A crucial part of our program will be sorting the list of available moves using the heuristic. At first I thought this wouldn't be very important--there were going to be at most 7 elements in the list I wanted to sort--so I wrote a quite lousy linear insert sort. However, this turned to be a bad idea: the whole thing just worked too slow. Changing it to quicksort gave my program a big speed boost (practically, made it work).

Basically, I'm against rewriting things like sorting functions, if there are functions for doing the same provided by the interpreter, written in C and usually much faster. However, SWI-Prolog's sort/2 is lame: it just sorts a list of numbers. And I am used to the Lisp approach, which is a lot more flexible: you are supposed to provide a function that you want to use to compare the elements as an argument to the sorting function.

To my very surprise, implementing such a Lisp-style sorting function in Prolog using call wasn't tricky nor difficult. Of course, there are no lambda-expressions in Prolog, so the final effect is a bit crude: you have to very careful when planning the order of arguments in your predicates. However, this is acceptable--nothing is perfect. As far as I know, this isn't Prolog mainstream, and that's a pity. I feel it's the most elegant solution.

split(Fun,Pivot,[H|Tail],[H|Positives], Negatives) :- % Fun for function. We all know that fuctions are funny.
call(Fun,Pivot,H),!,%H > Pivot,!,
split(Fun,Pivot,Tail, Positives, Negatives).
split(Fun,Pivot,[H|Tail], Positives, [H|Negatives]) :-
call(Fun,H, Pivot),
split(Fun,Pivot,Tail, Positives, Negatives).

qsort(_,[],[]).
qsort(Fun,[Pivot|List],Sorted):-
split(Fun,Pivot, List, Bigger, Smaller),
qsort(Fun,Bigger,NewBigger),
qsort(Fun,Smaller,NewSmaller),
append(NewSmaller, [Pivot|NewBigger], Sorted).



Now, lets put everything together:

hknight(A/B,X,Visited) :- % the `h' is for `heuristic.'
findall(W, knight(A/B, W), Moves),
qsort(better_heuristic(Visited), Moves, SortedMoves),
member(X, SortedMoves). % member chooses the elements preserving the order.

hknights_way([_/_],_).
hknights_way([First,Second|Rest],Visited) :-
hknight(First,Second,Visited),
\+member(Second,Visited),
hknights_way([Second|Rest],[Second|Visited]).

hknights_tour_1(X,N) :-
length(X,N),
X=[1/1|_],
hknights_way(X,[1/1]).

hknights_tour(X) :-
N is BoardX*BoardY,
hknights_tour_1(X,N).


And voilà! We have our problem solved. An example solution:

[ 1, 16, 51, 34, 3, 18, 21, 36]
[50, 33, 2, 17, 52, 35, 4, 19]
[15, 64, 49, 56, 45, 20, 37, 22]
[32, 55, 44, 63, 48, 53, 42, 5]
[61, 14, 57, 54, 43, 46, 23, 38]
[28, 31, 62, 47, 58, 41, 6, 9]
[13, 60, 29, 26, 11, 8, 39, 24]
[30, 27, 12, 59, 40, 25, 10, 7]

I updated this post on Fri Oct 27, 5:14 PM in order to incorporate some useful suggestions made by Daan Fierens. Thank you!

Wednesday, October 18, 2006

Is a goose worth sinning?

If there's a field, where Prolog is very good from first sight, it is no doubt solving logical puzzles. You know what I mean: those where you have to tell who owns the fish, how to measure two liters of water only with a bucket of 3 liters and one of 4 liters, solve a sudoku, and so on. Of course, Prolog will be able to deal only with purely combinatorial riddles--any involving self-reference or some dose of creativity are beyond its scope.

If one was to write it in an imperative programming language, it would take quite a lot of time to write a sound representation of the solution-space and then search through it; in Prolog, you just have to declare the rules which the world of the riddle must obey, and voilà!, it outputs the right answer.

For example, the Prolog code for solving the famous Einstein's riddle is quite straight forward (see also this solution):
%% the answer is a list of five houses, in the right order.
%% each house is a list of items in the following order:
%% [Color, Nationality, Beverage, Cigaretts, Pet]

left(L, R, [L | [R | _]]).
left(L, R, [_ | Rest]) :- left(L, R, Rest).

next(X,Y,List) :-
left(Y,X,List).
next(X,Y,List) :-
left(X,Y,List).

einstein(List,FishOwner) :-

List=[_,_,[_,_,milk,_,_],_,_],
List=[[_,norwegian,_,_,_],_,_,_,_],

member([red, brit,_,_,_],List),
member([_,swede,_,_,dog],List),
member([_,dane,tea,_,_],List),
left([green,_,_,_,_],[white,_,_,_,_],List),

member([green,_,coffee,_,_],List),
member([_,_,_,pall_mall,bird],List),
member([yellow,_,_,dunhill,_],List),

next([_,_,_,blends,_],[_,_,_,_,cat],List),
next([_,_,_,_,horse],[_,_,_,dunhill,_],List),
member([_,_,beer,bluemaster,_],List),
member([_,german,_,prince,_],List),
next([blue,_,_,_,_],[_,norwegian,_,_,_],List),
next([_,_,_,blends,_],[_,_,water,_,_],List),
member([_,FishOwner,_,_,fish],List),

write('The '),write(FishOwner),write(' owns the fish.').
Unfortunately, not all simple riddles are so simple for Prolog as the latter one. A good example may be the fox, goose and bag of beans puzzle. It is one of my favorite puzzles (my father told me it when I was five and it was the first real puzzle I've ever solved), so it was quite obvious that this was going to be the second program I would write.

These rules govern the movement of the farmer and his stuff:
next(state([rolnik|Tail],X), state(Tail, [rolnik|X])).
next(state(X,[rolnik|Tail]), state([rolnik|X], Tail)).

(The constants are in Polish: rolnik = farmer, koza = goat (goose), kapusta = cabbage (bag of beans), wilk = wolf (fox).)
next(state([rolnik|Animals], Right), state(NewLeft,[rolnik|Rest])) :-
member(X,Animals),
delete(Animals, X, NewLeft),
append([X],Right,Rest).

next(state(Left,[rolnik|Animals]), state([rolnik|Rest],NewRight)) :-
member(X,Animals),
delete(Animals, X, NewRight),
append([X],Left,Rest).
Next, we write which states of the world are acceptable, and which not:
meal(koza,kapusta). % goats eat cabbage
meal(wilk,koza). % wolfs eat goats

not_good(Bank) :-
\+member(rolnik,Bank),
meal(X,Y),
subset([X,Y],Bank).


good(state(X,Y)) :-
\+not_good(X),
\+not_good(Y).
and the constraints we want the solution to obey:
legal_chain([X]).

legal_chain([Car, Cadr|Tail]) :- % ah, Lisp reminiscences! :-)
next(Car,Cadr),
good(Cadr),
legal_chain([Cadr|Tail]).


Now, the most intuitive thing we could do now would be to state something like this:
naive-solution(Solution) :-
Solution = [state([rolnik, koza, kapusta, wilk], []) | _],
legal_chain(Solution),
last(Solution, state([], [rolnik, koza, kapusta, wilk]).
However, this definitely won't work. It may be perfectly correct from the declarative and logical point of view, but, as I have said in the previous post, Prolog is not logic. It doesn't automagically find the answer--it performs a depth-first search through the solution space. And in this case, the first path Prolog selects is one of the worst for us. The farmers goes to the other side of the river, returns, goes to the other side, and... Yes, ladies and gentlemen. An infinite loop.

Of course, it is possible to solve this problem in Prolog. The only think we have to do is think about our program more... well, as a program, not as a set of propositions, and change its search behavior. For example, we could implement an iterated, depth-first search (AFAIK, this was the least invasive way of altering my code so that it started to work).

(Well, it isn't precisely iterated depth-first (it looks for the answers only at the bottom o each layer), but the idea is quite the same.)
solve(Solution,N) :-
(
between(1,N,X),
length(Solution,X),
legal_chain([state([rolnik,koza,kapusta,wilk],[])|Solution]),
last(Solution,state([],[rolnik,koza,kapusta,wilk]))
),!
;
(
NewN is N+1,
solve(Solution,NewN)
).

solution(Solution) :-
solve(Solution,1).
You may have noticed that the program does nothing to avoid loops in the solutions. However, this is fine--for every “loopy” solution there exists a shorter one without loops, so we can be sure that the first solution we will find (the shortest one) is loop-free.

The last noteworthy thing is the cut operator (the red “!” in solve). Its task is to prevent backtracking after we have found a solution. It isn't really necessary--if you removed it, the program would just try to find other answers (and would find infinitely many of them--all except one loopy). Overusing it is considered very bad style in Prolog (as someone has said, “[cut] turns Prolog from a nice declarative language into a hybrid monster. Use cuts sparingly and with a sense of having sinned.”). However, I am still learning the language and couldn't resist the temptation of trying it, as soon as I found an adequate occasion. Yes, I am a sinner, and the goose was worth it. ;-)

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.