tag:blogger.com,1999:blog-18587342316550143192014-10-02T06:36:27.129+02:00Szopa's Other BlogMy English blog. More technical stuff.Ryszard Szopanoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-1858734231655014319.post-58549079768122198432007-06-15T19:59:00.000+02:002007-06-15T20:35:00.836+02:00Bad requests, XML-RPC, Lisp and Perl: note for myselfFor the last couple of months I have been working on a <a href="http://ccl.kuleuve.be/%7Erichard/lemmatizer.html">rule-based lemmatizer</a> for the <a href="http://ccl.kuleuven.be/">KU Leuven's CCL</a>. It isn't language specific, but the language I had in mind developing is Dutch, and there exists only one ruleset at the moment---for Dutch, of course. Surprisingly, it actually works, which is quite odd if you think about my non-existing Dutch skills.<br /><br />Anyway, I wrote my program in Lisp, while the rest of CCL works in Perl. This was sort of a problem, because delivering executables in SBCL is <span style="font-style: italic;">funny</span>, and I don't know any smart way of compiling libraries so that they can be called from other languages. Also, loading all Common Lisp and a few libraries just to lemmatize a small token would be a bit impractical.<br /><br />So, I had to find a way of letting Python, Perl and friends to talk with my lispy lemmatizer. <a href="http://japhy.fnord.org/">Maciek</a> suggested me I could use <a href="http://xmlrpc.com">XML-RPC</a>, and that was a good idea. I asdf-installed <a href="http://common-lisp.net/project/s-xml-rpc/">S-XML-RPC</a>, wrote the server, wrote a client in Python (to see if it really works), and everything seemed fine.<br /><br />It seemed so until a couple of days ago, when I wrote the Perl client. My Perl skills are as impressing as my Dutch skills, but this didn't ruin my self-confidence. After all, I just had written a <span style="font-style: italic;">whole lemmatizer</span> for Dutch, so a tiny script in a language I don't know shouldn't be a challenge.<br /><br />And at first it wasn't. I downloaded the <a href="http://www.blackperl.com/RPC::XML/">right library</a>, had them installed. I wrote what I thought I should have written, and there weren't any syntax errors. But then I run it, and all I could get was “Bad request.”<br /><br />Well, I took <a href="http://search.cpan.org/%7Ekmacleod/Frontier-RPC-0.07b4/">another XML-RPC Perl</a> library, wrote what the tutorials said I should have written... And got the same frustrating “Bad request.”<br /><br />Well, I tried lots of tricks. I threatened the computer with a screw-driver. I read the Perl source. I made the XML requests be printed, and run them through Python and Lisp---successfully. As for Perl---nothing better than “Bad request.”<br /><br />Finally, when looking through the source of S-XML-RPC, I found it is checking whether the URL is ending with “/RPC2”. I change appropriately the URL... And it started working. With both libraries. Apparently, Lisp and Python libraries were doing that implicitly, but Perl was too straight forward for it.<br /><br />In principle the whole affair wasn't Perl's fault---the XML-RPC specification doesn't specify how should the first line of the request look like. On the other hand, life would be a lot easier if Perl libraries did what other expect them to do. Like the Python version ;-)Ryszard Szopanoreply@blogger.com0tag:blogger.com,1999:blog-1858734231655014319.post-65104363418174503822007-06-15T12:41:00.000+02:002007-06-15T13:00:02.387+02:00Abductive reasoningDuring my first semester in KU Leuven I took a course “Logic as Foundations for AI”. There were only 4 participants, so instead of taking we could prepare an assignment.<br /><br />One of the exercises consisted of performing some <a href="http://en.wikipedia.org/wiki/Abductive_reasoning">abductive reasoning</a>, about boolean circuits where some logical gates could be broken (there were ~5 gates in the circuit). And it was tedious... And I was always making an error somewhere... So I decided: “enough is enough,” and wrote a Prolog program to solve this task for me.<br /><br />And it was a great success: it took me only a day to write a program that solves a task it would take two hours to solve it (provided you were extremely pedantic).<br /><br />(However, I've included my program into the assignment and I suspect it may have boosted the mark I received.) ;-)<br /><br /><code></code><pre><br /><br />:- op(1200, xfx, ====>).<br /><br />% Give all the possible explanations for Goal in KB, as conjunctive clauses<br />explanations(Goal, KB, Explanations) :-<br /> prime_implicates(KB, Implications),<br /> no_goal(Goal, Implications, NoGs),<br /> findall(Explanation, (member(X, NoGs), negate_all(X, Explanation)), Explanations).<br /><br /><br />% find all the prime implicates from KB<br />prime_implicates(KB, Implicates) :-<br /> resolution(KB, Cons),<br /> findall(Imp, (member(Imp, Cons), prime_implicate_(Imp, Cons)), Implicates).<br /><br />prime_implicate_(_, []).<br />prime_implicate_(I, [H|Set]) :-<br /> ( \+subset(H,I)<br /> ; I ==H),<br /> prime_implicate_(I, Set).<br /><br /><br />% resolution(KB, AllResolvents).<br />resolution(List, Solution) :-<br /> % we have to sort the clauses in order to obtain the<br /> % “canonical” form (useful to remove duplicates).<br /> findall(Sorted, (member(L,List), sort(L,Sorted)), SortedList),<br /> resolution2(SortedList, Solution).<br /><br />resolution2(List,Solution) :-<br /> member(A, List),<br /> member(B, List),<br /> A \==B,<br /> print(A),<br /> resolve(A, B, R1),<br /> sort(R1, R),<br /> \+ smember(R, List),<br /> pretty(A,B,R),<br /> resolution2([R|List], Solution)<br /> ;<br /> List=Solution.<br /><br />resolve(XX,YY,Z) :-<br /> new_var(XX,X),<br /> new_var(YY,Y),<br /> member(Rx,X),<br /> member(Ry, Y),<br />% ( Rx=not(Ry)<br />% ; Ry=not(Rx)),<br /> % We must use sound unification (no cyclic terms)<br /> ( unify_with_occurs_check(Rx, not(Ry))<br /> ; unify_with_occurs_check(Ry, not(Rx))),<br /> select(Ry,Y, NewY),<br /> select(Rx, X, NewX),<br /> sunion(NewX, NewY, Z).<br /><br />% prover by resolution for Horn Clauses<br />% hresolution(+Goal, +KB, -ResolutionTrail)<br />% prove Goal in KB<br /><br />hresolution(Goal, KB, Sol) :-<br /> negate(Goal, NG),<br /> hresolution_(NG, KB, Sol).<br /><br /><br />hresolution_(_,[],[]).<br />hresolution_(X, KB, [X/Y====>Resolvent|Rest]) :-<br /> member(Y,KB),<br /> resolve(X,Y, Resolvent),<br /> ( Resolvent = [],<br /> Rest=[]<br /> ;<br /> select(Y,KB, NewKB),<br /> hresolution_(Resolvent, NewKB, Rest)).<br /><br />/* *************************<br />* *<br />* Tool predicates: *<br />* *<br />***************************/<br /><br />% put brand new new variables in the clause<br />new_var(X,Y) :-<br /> assert(p(X)),<br /> retract(p(Y)).<br /><br />pretty(A,B,C) :- print(A/B====>C), nl, nl.<br /><br /><br />% like select, but uses sound unification and succeeds if El is not in<br />% the List<br />minus(_, [], []).<br />minus(X, [X1|Tail], Tail) :-<br /> sunifiable(X, X1).<br />minus(Elem, [Head|Tail], [Head|Rest]) :-<br /> minus(Elem, Tail, Rest).<br /><br /><br />% sound-unifiable<br />sunifiable(X,Y) :-<br /> \+ \+ unify_with_occurs_check(X,Y).<br /><br />% like member, but tests identity instead of unification (we don't<br />% want to instantiate X in f(X) to 1 by checking if f(r) is already in<br />% the KB)<br /><br /><br />smember(X,[H|_]) :-<br /> %X==H.<br /> sunifiable(X, H).<br />smember(X, [_|Rest]) :-<br /> smember(X, Rest).<br /><br />sunion([], L, L1) :-<br /> unify_with_occurs_check(L, L1),<br /> !.<br />sunion([H|T], L, R) :-<br /> smember(H, L), !,<br /> sunion(T, L, R).<br />sunion([H|T], L, [H|R]) :-<br /> sunion(T, L, R).<br /><br />negate(not(X), X) :- !.<br />negate(X,not(X)).<br /><br />% negate all literals in an disjunctive clause, giving a conjunctive clause<br />negate_all([],[]).<br />negate_all([H|T],[NH|NT]) :-<br /> negate(H, NH),<br /> negate_all(T, NT).<br /><br />% eliminate the goal Goal form the clause<br />no_goal(_, [], []).<br />no_goal(Goal, [H|T], [NH|NT]) :-<br /> minus(Goal, H, NH),<br /> no_goal(Goal, T, NT).<br /><br /><br />test(Z):-<br /><br /> List = [<br /> [not(tennis_elbow), sore_elbow],<br /> [not(tennis_elbow), tennis_player],<br /> [not(arthritis), treated, sore_joints],<br /> [sore_elbow, not(sore_joints)],<br /> [not(sore_joints), sore_hips]<br /> ],<br /> List2 = [<br /> [not(p), not(q), not(r), g],<br /> [p, not(q), g],<br /> [q, not(r), g]<br /> ],<br /> explanations(g, List2,Z).<br /><br />test_nonprovable(A) :-<br /> List = [[p(X)], [p(X)]],<br /> resolution(List, A).<br /><br />test_plus(Solution, Result) :-<br /> A=[<br /> [rplus(W,0,W)],<br /> [rplus(X, s(Y), s(Z)), not(rplus(X,Y,Z))]<br /> ],<br /><br /> Goal = [rplus(s(s(s(0))), s(s(0)), Result)],%s(s(s(s(s(0))))))],<br /><br /> hresolution(Goal, A, Solution).<br /><br /><br /><br /><br /></pre>Ryszard Szopanoreply@blogger.com0tag:blogger.com,1999:blog-1858734231655014319.post-32827014581878335682007-04-03T18:35:00.000+02:002007-04-18T13:11:04.326+02:00A simple regular language recognizerThere are some programs that you just have to write in order to have the feeling that you know <span style="font-style: italic;">a bit</span> of the programming language you are learning. For me such a program is a regular expression recognizer.<br /><br />Both strings and regular expressions are represented by lists of Lisp symbols (a regexp description may be also a nested list)<br />Let me introduce my notation of regexp-s by example:<br /><ul><li>(* a b c d) is the same as (a b c d)* in the usual notation</li><li>(+ a b c d) is (a b c d)+</li><li>(or a b c d) is (a|b|c|d)<br /></li></ul><code></code><pre><br /><br />(defun recognize (regexp string)<br />"T if string matches to regexp, nil otherwise."<br />(let ((end (list (gensym))))<br /> (if (null regexp)<br /> ;; the language {\sigma} must be a special case because nil is<br /> ;; the value returned by reg-eval on failure<br /> (null string)<br /> (equal end (reg-eval regexp (append string end))))))<br /><br />(defun reg-eval (regexp string)<br />"If string has a prefix matching regexp, returns the part that doesn't match (nil otherwise)."<br />(when string<br /> (cond ((null regexp)<br /> string)<br /> ((not (listp (car regexp)))<br /> (when (equal (car string) (car regexp))<br /> (reg-eval (cdr regexp) (cdr string))))<br /> (t (let ((prefix (caar regexp))<br /> (body (cdar regexp)))<br /> (case prefix<br /> ((*)<br /> (reg-eval (cdr regexp) (let ((match (reg-eval body string)))<br /> (if (not match)<br /> string<br /> (reg-eval (list (car regexp)) match)))))<br /> ((+)<br /> (reg-eval (nconc (list (cons 'subexp body) (cons '* body)) (cdr regexp)) string))<br /> ((or)<br /> (some #'(lambda (x) (reg-eval x string)) body))<br /> ((subexp)<br /> (reg-eval (cdr regexp) (reg-eval body string)))))))))<br /><br /><br />(defun test ()<br />(let ((cases '((recognize '(a b c d) '(a b c d))<br /> (recognize '((* a b c)) '(a b c a b c))<br /> (recognize '((or ((+ 1) 2) (2 1))) '(1 1 1 2))<br /> (recognize '((or (1 2) (2 1))) '(1 2)))))<br /> (dolist (cas cases)<br /> (format t "~&~s => ~s." cas (eval cas)))))<br /></pre>Ryszard Szopanoreply@blogger.com1tag:blogger.com,1999:blog-1858734231655014319.post-41765475475483516462007-03-06T00:31:00.000+01:002007-03-06T03:43:47.600+01:00LisprologAs someone has observed <a href="http://groups.google.com/group/comp.lang.prolog/browse_thread/thread/2d9bed17ddcfac0c/488f66ab072e5614">on comp.lang.prolog</a>, there's a strange tendency among Lisp enthusiasts (some of whom I profoundly respect) to enthusiastically depreciate Prolog. Symptomatic for this imperialistic approach are the lots of toy Prolog interpreters written in Lisp you can find in the Internet (just <a href="http://www.google.com/search?ie=UTF-8&oe=UTF-8&sourceid=navclient&gfns=1&q=prolog+in+lisp">try google</a>).<br /><br />For a long time, poor Prolog guys didn't have a good answer. However, this annoying situation has changed, thanks to <a href="http://stud4.tuwien.ac.at/%7Ee0225855/">Marcus Triska</a>. Let me present, ladies and gentlemen, <a href="http://stud4.tuwien.ac.at/%7Ee0225855/lisprolog/lisprolog.html">Lisprolog,</a> the toy Lisp interpreter written in Prolog! It's very small (~200 lines of code), very clean and very neat. Maybe the language in it is a bit underimplemented, but that seems to be a part of the joke (a really complete implementation wouldn't be a good revenge for all that toy interpreters).<br /><br />Personally, I find Lisprolog absolutely cute. I like very much both Lisp and Prolog, and implementing some of the missing features seems like a good exercise, allowing to learn something about Lisp and not forget Prolog, at the same time (I am reading <span style="font-style: italic;">Essentials of Programming Languages</span> by Friedman, Wand & Haynes at the moment).Ryszard Szopanoreply@blogger.com0tag:blogger.com,1999:blog-1858734231655014319.post-51930013262887593212007-03-04T21:45:00.000+01:002007-03-04T21:59:29.396+01:00Moving from wordpress to bloggerI have been maintaining my Polish blog on Wordpress.com server for more than half a year and become quite fed up of it. Paid upgrades, no access to the source of the style-sheet, and, last but not least, problems with logging in under firefox helped me a lot making my decision.<br /><br />There's quite a lot written about <a href="http://www.google.com/search?hl=en&q=how+to+move+from+blogger+to+wordpress&btnG=Search">moving your blog archive from blogger to wordpress</a>. I, however, wanted to do just the opposite, which this turned to be a bit less trivial: Blogger is still beta and doesn't have any of the import/export facilities wordpress can be proud of.<br /><br />Fortunately, I found a very nice python script which allowed me to make the move without any excessive pain: <a href="http://zeaster.blogspot.com/2007/01/tool-that-import-all-posts-from_4359.html">wordpress2blogger</a>. Many thanks to the author!Ryszard Szopanoreply@blogger.com4tag:blogger.com,1999:blog-1858734231655014319.post-64228122695393763192006-12-07T16:54:00.000+01:002006-12-08T00:55:12.207+01:00Prolog and regular expressionsSome 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.<br /><br />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 <i>normal</i>, 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.<br /><br />A good place for starting my quest for perl-style regexp was <a href="http://www.let.rug.nl/~vannoord/prolog-rx/PrologAndRegex.html">this</a>. 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.<br /><br />The two Prologs I tested were <a href="http://www.clip.dia.fi.upm.es/Software/Ciao/">Ciao</a> and <a href="http://www.ncc.up.pt/~vsc/Yap/">Yap</a>.<br /><br />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 <a href="http://www.clip.dia.fi.upm.es/Software/Ciao/ciao_html/ciao_168.html#SEC695">didn't find it</a>), which rendered it quite useless.<br /><br />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).<br /><br />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:<br /><code><br /> ?- use_module(library(regexp)).<br /> ?- regexp("^(.+)=\\1$", "a=a", []).<br />yes<br /></code><br /><br />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.<br /><br />(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 <a href="http://kitenet.net/~joey/code/alien.html">alien</a>.)Ryszard Szopanoreply@blogger.com2tag:blogger.com,1999:blog-1858734231655014319.post-36697638062990981042006-11-16T17:01:00.000+01:002006-11-18T22:46:55.668+01:00SudokuIn 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.<br /><br />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.<br /><br />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).<br /><pre><br />%<br />% all the elements in a column, row, 3x3 box.<br />%<br /><br />column(X/_, Sudoku, Column) :-<br /> findall(X/Y/Z , (member(X/Y/Z, Sudoku), nonvar(Z)), Column).<br /><br />row(_/Y, Sudoku, Row) :-<br /> findall(X/Y/Z, (member(X/Y/Z, Sudoku), nonvar(Z)), Row).<br /><br /><br />% believe me or not, this was the most difficult predicate to write.<br />box(Base, X/Y, Sudoku, Box) :- % Base: size of the puzzle<br /> DiffX is (X-1) mod (Base/3),<br /> DiffY is (Y-1) mod (Base/3),<br /> StartX is X - DiffX,<br /> StartY is Y - DiffY,<br /> EndX is StartX + (Base/3) - 1,<br /> EndY is StartY + (Base/3)-1,<br /> findall(X1/Y1/Z,<br /> (<br /> between(StartX,EndX,X1),<br /> between(StartY, EndY, Y1),<br /> member(X1/Y1/Z, Sudoku),<br /> nonvar(Z)<br /> ),<br /> Box).<br /><br />%<br />% We can assign the value Possible to X/Y without<br />% violating the rules of the sudoku.<br />%<br />possible(_,X/Y/Possible, Sudoku) :-<br /> member(X/Y/Possible, Sudoku),<br /> nonvar(Possible), !.<br />possible(Base, X/Y/Possible, Sudoku) :-<br /> column(X/Y, Sudoku, Column),<br /> row(X/Y, Sudoku, Row),<br /> box(Base, X/Y, Sudoku, Box),<br /> between(1,Base, Possible),<br /> \+member(_/_/Possible, Column),<br /> \+member(_/_/Possible, Row),<br /> \+member(_/_/Possible, Box).<br /><br />% solve the puzzle, iterating through each grid<br />solve(_,N,N,_).<br />solve(Base,N,K,Solution) :-<br /> nth1(N, Solution, X/Y/Z),<br /> possible(Base, X/Y/Z, Solution),<br /> NewN is N+1,<br /> solve(Base, NewN, K, Solution).<br />solve(Base,Solution) :-<br /> N is Base*Base+1,<br /> solve(Base,1, N, Solution).<br /><br />% the main predicate<br />%<br />sudoku(Base,Constraints, Solution) :-<br /> findall(X/Y/_, (between(1,Base,X), between(1,Base,Y)), Solution),<br /> subset(Constraints, Solution),<br /> solve(Base,Solution).<br /><br />/*<br /><br />And some example puzzles to solve:<br /><br />*/<br /><br />s3([3/1/3, 2/2/8,<br /> 5/1/4, 4/2/6, 6/2/3, 4/3/5,<br /> 8/1/9, 8/3/4,<br /> 1/4/5, 1/6/2, 3/6/7,<br /> 4/4/9, 5/4/1, 4/5/2, 6/5/7, 5/6/8, 6/6/6,<br /> 7/4/3, 9/4/7, 9/6/5,<br /> 2/7/3, 2/9/5,<br /> 4/8/7, 5/9/6, 6/7/5, 6/8/1,<br /> 7/9/4, 8/8/5]).<br /><br />% the sudoku from class<br />s1([1/4/2, 1/5/3, 1/9/5,<br /> 2/2/4, 2/3/2, 2/5/9, 2/9/3,<br /> 3/1/3, 3/6/8, 3/7/7,<br /> 4/3/7, 4/8/5, 4/9/6,<br /> 5/2/9, 5/4/7, 5/5/2, 5/8/1, 5/9/4,<br /> 6/1/5, 6/4/9,<br /> 7/1/6, 7/6/2, 7/7/8, 7/8/4, 7/9/9,<br /> 8/3/8, 8/6/1, 8/9/7,<br /> 9/1/2, 9/2/5, 9/6/9, 9/7/6]).<br /><br />s2([4/1/2, 5/1/3, 9/1/5,<br /> 2/2/4, 3/2/2, 5/2/9, 9/2/3,<br /> 1/3/3, 6/3/8, 7/3/7,<br /> 3/4/7, 8/4/5, 9/4/6,<br /> 2/5/9, 4/5/7, 5/5/2, 8/5/1, 9/5/4,<br /> 1/6/5, 4/6/9,<br /> 1/7/6, 6/7/2, 7/7/8, 8/7/4, 9/7/9,<br /> 3/8/8, 6/8/1, 9/8/7,<br /> 1/9/2, 2/9/5, 6/9/9, 7/9/6]).</pre><br />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 :).<br /><br />Now, we can use Prolog to run the following query:<br /><pre>?- s1(Constraints),sudoku(9,Constraints,Sudoku), print_su(Sudoku).<br /><br />1 7 3 || 4 8 5 || 6 9 2<br />8 4 6 || 2 9 1 || 7 3 5<br />9 2 5 || 7 6 3 || 1 8 4<br />==============================<br />2 5 4 || 1 7 9 || 3 6 8<br />3 9 1 || 8 2 6 || 5 4 7<br />7 6 8 || 3 5 4 || 2 1 9<br />==============================<br />4 1 7 || 9 3 2 || 8 5 6<br />6 8 9 || 5 1 7 || 4 2 3<br />5 3 2 || 6 4 8 || 9 7 1<br /><br />Constraints = [1/4/2, 1/5/3, 1/9/5, 2/2/4, 2/3/2, 2/5/9, 2/9/3, ... /... /3, ... /...|...]<br />Sudoku = [1/1/1, 1/2/8, 1/3/9, 1/4/2, 1/5/3, 1/6/7, 1/7/4, ... /... /6, ... /...|...] </pre><br />and voilà, your sudoku is ready!<br /><br />(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. ;-))Ryszard Szopanoreply@blogger.com1tag:blogger.com,1999:blog-1858734231655014319.post-23574912358869858562006-10-26T18:38:00.000+02:002006-10-27T17:51:55.825+02:00Two programs for one chess problem<a href="http://www.ktn.freeuk.com/">Knight's tour</a> 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.<br /><br />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.<br /><br />Lets represent a square on the board by a pair of numbers divided by a slash.<br /><br />First of all, the way the knight moves:<br /><pre>boardX(8).<br /><br />boardY(8).<br /><br />knight(X/Y,X1/Y1) :-<br />boardX(BoardX),<br />boardY(BoardY),<br /><br /> (<br /> (X1 is X+2 ;<br /> X1 is X-2),<br /> (Y1 is Y+1 ;<br /> Y1 is Y-1)<br /> <br /> ;<br /> <br /> (Y1 is Y+2 ;<br /> Y1 is Y-2),<br /> (X1 is X+1 ;<br /> X1 is X-1)<br /> ),<br /> X1 >= 1, X1 =< BoardX,<br /> Y1 >= 1, Y1 =< BoardY.<br /></pre><br />The dimensions of the board aren't hardcoded in case we want to solve the puzzle on a nonstandard board, eg. 4x8.<br /><pre>knights_way([_/_],_).<br />knights_way([First,Second|Rest],Visited) :-<br /> knight(First,Second),<br /> \+member(Second,Visited), % No repetitions, please!<br /> knights_way([Second|Rest],[Second|Visited]).<br /><br /><br /><br />knights_tour_1(X,N) :-<br /> length(X,N),<br /> X=[1/1|_],<br /> knights_way(X,[]).<br /><br />knights_tour(X) :-<br /> N is BoardX*BoardY,<br /> knights_tour_1(X,N).<br /></pre> 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:<br /><pre>?- time(knights_tour_1(X,59)).<br />% 46,797 inferences, 0.02 CPU in 0.01 seconds (141% CPU, 2339850 Lips)<br /><br />X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]<br /><br />?- time(knights_tour(X,60)).<br />% 1,677,669 inferences, 0.50 CPU in 0.50 seconds (100% CPU, 3355338 Lips)<br /><br />X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]<br /><br />?- time(knights_tour_1(X,61)).<br />% 92,595,863 inferences, 27.43 CPU in 28.15 seconds (97% CPU, 3375715 Lips)<br /><br />X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]<br /><br />?- time(knights_tour_1(X,63)).<br />C-c C-c<br />Action (h for help) ? a<br />abort<br />% 4,550,510,155 inferences, 1345.57 CPU in 1418.71 seconds (95% CPU, 3381846 Lips)<br />% Execution Aborted<br /></pre><br />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.<br /><br />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 <a href="http://http://www.ktn.freeuk.com/cb.htm">here</a> and <a href="http://mathworld.wolfram.com/KnightsTour.html">here</a>). It is said not to work very well for boards bigger than 76x76, but I don't think it's a very big deal.<br /><pre><br />heuristic(X/Y, Visited, N) :-<br /> findall(A,knight(X/Y,A),Possible),<br /> subtract(Possible,Visited,List),<br /> 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.<br /><br />better_heuristic(Visited,A,B) :-<br /> heuristic(A,Visited,HA),<br /> heuristic(B,Visited,HB),<br /> HA =< HB. <br /></pre><br />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).<br /><br />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.<br /><br />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.<br /><pre><br />split(Fun,Pivot,[H|Tail],[H|Positives], Negatives) :- % Fun for function. We all know that fuctions are funny.<br /> call(Fun,Pivot,H),!,%H > Pivot,!,<br /> split(Fun,Pivot,Tail, Positives, Negatives).<br />split(Fun,Pivot,[H|Tail], Positives, [H|Negatives]) :-<br /> call(Fun,H, Pivot),<br /> split(Fun,Pivot,Tail, Positives, Negatives).<br /><br />qsort(_,[],[]).<br />qsort(Fun,[Pivot|List],Sorted):-<br /> split(Fun,Pivot, List, Bigger, Smaller),<br /> qsort(Fun,Bigger,NewBigger),<br /> qsort(Fun,Smaller,NewSmaller),<br /> append(NewSmaller, [Pivot|NewBigger], Sorted).<br /></pre><br /><br /><br />Now, lets put everything together:<br /><pre><br />hknight(A/B,X,Visited) :- % the `h' is for `heuristic.'<br /> findall(W, knight(A/B, W), Moves),<br /> qsort(better_heuristic(Visited), Moves, SortedMoves),<br /> member(X, SortedMoves). % member chooses the elements preserving the order.<br /><br />hknights_way([_/_],_).<br />hknights_way([First,Second|Rest],Visited) :-<br /> hknight(First,Second,Visited),<br /> \+member(Second,Visited),<br /> hknights_way([Second|Rest],[Second|Visited]).<br /><br />hknights_tour_1(X,N) :-<br /> length(X,N),<br /> X=[1/1|_],<br /> hknights_way(X,[1/1]).<br /><br />hknights_tour(X) :-<br /> N is BoardX*BoardY,<br /> hknights_tour_1(X,N).<br /></pre><br /><br />And voilà! We have our problem solved. An example solution:<br /><pre><br />[ 1, 16, 51, 34, 3, 18, 21, 36]<br />[50, 33, 2, 17, 52, 35, 4, 19]<br />[15, 64, 49, 56, 45, 20, 37, 22]<br />[32, 55, 44, 63, 48, 53, 42, 5]<br />[61, 14, 57, 54, 43, 46, 23, 38]<br />[28, 31, 62, 47, 58, 41, 6, 9]<br />[13, 60, 29, 26, 11, 8, 39, 24]<br />[30, 27, 12, 59, 40, 25, 10, 7]<br /></pre><br /><span style="font-style:italic;">I updated this post on Fri Oct 27, 5:14 PM in order to incorporate some useful suggestions made by Daan Fierens. Thank you!</span>Ryszard Szopanoreply@blogger.com1tag:blogger.com,1999:blog-1858734231655014319.post-82797869830915151962006-10-18T21:55:00.000+02:002006-10-19T00:12:06.757+02:00Is 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.<br /><br />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 <span style="font-style: italic;">voilà!</span>, it outputs the right answer.<br /><br />For example, the Prolog code for solving the famous <a href="http://www.naute.com/puzzles/puzzle13.phtml">Einstein's riddle</a> is quite straight forward (see also <a href="http://sandbox.rulemaker.net/ngps/119">this</a> solution):<br /><pre>%% the answer is a list of five houses, in the right order.<br />%% each house is a list of items in the following order:<br />%% [Color, Nationality, Beverage, Cigaretts, Pet]<br /><br />left(L, R, [L | [R | _]]).<br />left(L, R, [_ | Rest]) :- left(L, R, Rest).<br /><br />next(X,Y,List) :-<br /> left(Y,X,List).<br />next(X,Y,List) :-<br /> left(X,Y,List).<br /><br />einstein(List,FishOwner) :-<br /><br /> List=[_,_,[_,_,milk,_,_],_,_],<br /> List=[[_,norwegian,_,_,_],_,_,_,_],<br /><br /> member([red, brit,_,_,_],List),<br /> member([_,swede,_,_,dog],List),<br /> member([_,dane,tea,_,_],List),<br /> left([green,_,_,_,_],[white,_,_,_,_],List),<br /><br /> member([green,_,coffee,_,_],List),<br /> member([_,_,_,pall_mall,bird],List),<br /> member([yellow,_,_,dunhill,_],List),<br /><br /> next([_,_,_,blends,_],[_,_,_,_,cat],List),<br /> next([_,_,_,_,horse],[_,_,_,dunhill,_],List),<br /> member([_,_,beer,bluemaster,_],List),<br /> member([_,german,_,prince,_],List),<br /> next([blue,_,_,_,_],[_,norwegian,_,_,_],List),<br /> next([_,_,_,blends,_],[_,_,water,_,_],List),<br /> member([_,FishOwner,_,_,fish],List),<br /><br /> write('The '),write(FishOwner),write(' owns the fish.').<br /></pre>Unfortunately, not all simple riddles are so simple for Prolog as the latter one. A good example may be the <a href="http://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_puzzle">fox, goose and bag of beans puzzle</a>. 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.<br /><br />These rules govern the movement of the farmer and his stuff:<br /><pre>next(state([rolnik|Tail],X), state(Tail, [rolnik|X])).<br />next(state(X,[rolnik|Tail]), state([rolnik|X], Tail)).</pre><br />(The constants are in Polish: rolnik = farmer, koza = goat (goose), kapusta = cabbage (bag of beans), wilk = wolf (fox).)<br /><pre>next(state([rolnik|Animals], Right), state(NewLeft,[rolnik|Rest])) :-<br /> member(X,Animals),<br /> delete(Animals, X, NewLeft),<br /> append([X],Right,Rest).<br /><br />next(state(Left,[rolnik|Animals]), state([rolnik|Rest],NewRight)) :-<br /> member(X,Animals),<br /> delete(Animals, X, NewRight),<br /> append([X],Left,Rest).</pre>Next, we write which states of the world are acceptable, and which not:<br /><pre>meal(koza,kapusta). % goats eat cabbage<br />meal(wilk,koza). % wolfs eat goats<br /><br />not_good(Bank) :-<br /> \+member(rolnik,Bank),<br /> meal(X,Y),<br /> subset([X,Y],Bank).<br /><br /><br />good(state(X,Y)) :-<br /> \+not_good(X),<br /> \+not_good(Y).</pre>and the constraints we want the solution to obey:<br /><pre>legal_chain([X]).<br /><br />legal_chain([Car, Cadr|Tail]) :- % ah, Lisp reminiscences! :-)<br /> next(Car,Cadr),<br /> good(Cadr),<br /> legal_chain([Cadr|Tail]).</pre><br /><br />Now, the most intuitive thing we could do now would be to state something like this:<br /><pre>naive-solution(Solution) :-<br /> Solution = [state([rolnik, koza, kapusta, wilk], []) | _],<br /> legal_chain(Solution),<br /> last(Solution, state([], [rolnik, koza, kapusta, wilk]).</pre>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.<br /><br />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).<br /><br />(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.)<br /><pre>solve(Solution,N) :-<br /> (<br /> between(1,N,X),<br /> length(Solution,X),<br /> legal_chain([state([rolnik,koza,kapusta,wilk],[])|Solution]),<br /> last(Solution,state([],[rolnik,koza,kapusta,wilk]))<br /> ),<span style="color: rgb(255, 0, 0);">!</span><br />;<br /> (<br /> NewN is N+1,<br /> solve(Solution,NewN)<br /> ).<br /><br />solution(Solution) :-<br />solve(Solution,1).</pre>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.<br /><br />The last noteworthy thing is the cut operator (the red “!” in <span style="font-family:courier new;">solve</span>). 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 <a href="http://www.cse.unsw.edu.au/%7Ebillw/cs9414/notes/prolog/intro.html#cut">someone has said</a>, “[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. ;-)Ryszard Szopanoreply@blogger.com0tag:blogger.com,1999:blog-1858734231655014319.post-44536721521502168842006-10-14T01:41:00.000+02:002006-10-14T23:47:28.663+02:00Lists are not sets, Prolog is not logicIn Ivan Bratko's <span style="font-style: italic;">Prolog. Programming for Artificial Intelligence</span>, 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.<br /><br />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.<br /><br />But first things first--the two programs and what is wrong with them. The “canonical” solution is the following:<br /><pre>subset([],[]).<br /><br />subset([First|Rest],[First|Sub]) :-<br /> subset(Rest,Sub).<br /><br />subset([First|Rest],Sub) :-<br /> subset(Rest,Sub).</pre>My solution is a bit simpler:<br /><pre>m_subset(Set,[]).<br /><br />m_subset(X,[Y|Tail]) :-<br /> m_subset(X,Tail),<br /> member(Y,X).<br /></pre>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:<br /><pre>subset([1,2,3],X).</pre>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<br /><pre>subset([1,2,3],[3,2]).</pre> (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).<br /><br />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 <span style="font-family: courier new;">[1,2,3]</span> it starts saying<br /><pre>[1,2,3,1] ;<br />[1,2,3,2] ;<br />[1,2,3,3] ;<br />...<br /></pre>etc.<br /><br />In fact, that <span style="font-style: italic;">is</span> 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.<br /><br />I claim that my definition of <span style="font-family:courier new;">subset</span> 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 (<span style="font-style:italic;">very</span> 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.<br /><br />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.Ryszard Szopanoreply@blogger.com4