Friday, June 15, 2007

Bad requests, XML-RPC, Lisp and Perl: note for myself

For the last couple of months I have been working on a rule-based lemmatizer for the KU Leuven's CCL. 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.

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 funny, 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.

So, I had to find a way of letting Python, Perl and friends to talk with my lispy lemmatizer. Maciek suggested me I could use XML-RPC, and that was a good idea. I asdf-installed S-XML-RPC, wrote the server, wrote a client in Python (to see if it really works), and everything seemed fine.

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 whole lemmatizer for Dutch, so a tiny script in a language I don't know shouldn't be a challenge.

And at first it wasn't. I downloaded the right library, 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.”

Well, I took another XML-RPC Perl library, wrote what the tutorials said I should have written... And got the same frustrating “Bad request.”

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.”

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.

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 ;-)

Abductive reasoning

During 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.

One of the exercises consisted of performing some abductive reasoning, 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.

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).

(However, I've included my program into the assignment and I suspect it may have boosted the mark I received.) ;-)



:- op(1200, xfx, ====>).

% Give all the possible explanations for Goal in KB, as conjunctive clauses
explanations(Goal, KB, Explanations) :-
prime_implicates(KB, Implications),
no_goal(Goal, Implications, NoGs),
findall(Explanation, (member(X, NoGs), negate_all(X, Explanation)), Explanations).


% find all the prime implicates from KB
prime_implicates(KB, Implicates) :-
resolution(KB, Cons),
findall(Imp, (member(Imp, Cons), prime_implicate_(Imp, Cons)), Implicates).

prime_implicate_(_, []).
prime_implicate_(I, [H|Set]) :-
( \+subset(H,I)
; I ==H),
prime_implicate_(I, Set).


% resolution(KB, AllResolvents).
resolution(List, Solution) :-
% we have to sort the clauses in order to obtain the
% “canonical” form (useful to remove duplicates).
findall(Sorted, (member(L,List), sort(L,Sorted)), SortedList),
resolution2(SortedList, Solution).

resolution2(List,Solution) :-
member(A, List),
member(B, List),
A \==B,
print(A),
resolve(A, B, R1),
sort(R1, R),
\+ smember(R, List),
pretty(A,B,R),
resolution2([R|List], Solution)
;
List=Solution.

resolve(XX,YY,Z) :-
new_var(XX,X),
new_var(YY,Y),
member(Rx,X),
member(Ry, Y),
% ( Rx=not(Ry)
% ; Ry=not(Rx)),
% We must use sound unification (no cyclic terms)
( unify_with_occurs_check(Rx, not(Ry))
; unify_with_occurs_check(Ry, not(Rx))),
select(Ry,Y, NewY),
select(Rx, X, NewX),
sunion(NewX, NewY, Z).

% prover by resolution for Horn Clauses
% hresolution(+Goal, +KB, -ResolutionTrail)
% prove Goal in KB

hresolution(Goal, KB, Sol) :-
negate(Goal, NG),
hresolution_(NG, KB, Sol).


hresolution_(_,[],[]).
hresolution_(X, KB, [X/Y====>Resolvent|Rest]) :-
member(Y,KB),
resolve(X,Y, Resolvent),
( Resolvent = [],
Rest=[]
;
select(Y,KB, NewKB),
hresolution_(Resolvent, NewKB, Rest)).

/* *************************
* *
* Tool predicates: *
* *
***************************/

% put brand new new variables in the clause
new_var(X,Y) :-
assert(p(X)),
retract(p(Y)).

pretty(A,B,C) :- print(A/B====>C), nl, nl.


% like select, but uses sound unification and succeeds if El is not in
% the List
minus(_, [], []).
minus(X, [X1|Tail], Tail) :-
sunifiable(X, X1).
minus(Elem, [Head|Tail], [Head|Rest]) :-
minus(Elem, Tail, Rest).


% sound-unifiable
sunifiable(X,Y) :-
\+ \+ unify_with_occurs_check(X,Y).

% like member, but tests identity instead of unification (we don't
% want to instantiate X in f(X) to 1 by checking if f(r) is already in
% the KB)


smember(X,[H|_]) :-
%X==H.
sunifiable(X, H).
smember(X, [_|Rest]) :-
smember(X, Rest).

sunion([], L, L1) :-
unify_with_occurs_check(L, L1),
!.
sunion([H|T], L, R) :-
smember(H, L), !,
sunion(T, L, R).
sunion([H|T], L, [H|R]) :-
sunion(T, L, R).

negate(not(X), X) :- !.
negate(X,not(X)).

% negate all literals in an disjunctive clause, giving a conjunctive clause
negate_all([],[]).
negate_all([H|T],[NH|NT]) :-
negate(H, NH),
negate_all(T, NT).

% eliminate the goal Goal form the clause
no_goal(_, [], []).
no_goal(Goal, [H|T], [NH|NT]) :-
minus(Goal, H, NH),
no_goal(Goal, T, NT).


test(Z):-

List = [
[not(tennis_elbow), sore_elbow],
[not(tennis_elbow), tennis_player],
[not(arthritis), treated, sore_joints],
[sore_elbow, not(sore_joints)],
[not(sore_joints), sore_hips]
],
List2 = [
[not(p), not(q), not(r), g],
[p, not(q), g],
[q, not(r), g]
],
explanations(g, List2,Z).

test_nonprovable(A) :-
List = [[p(X)], [p(X)]],
resolution(List, A).

test_plus(Solution, Result) :-
A=[
[rplus(W,0,W)],
[rplus(X, s(Y), s(Z)), not(rplus(X,Y,Z))]
],

Goal = [rplus(s(s(s(0))), s(s(0)), Result)],%s(s(s(s(s(0))))))],

hresolution(Goal, A, Solution).




Tuesday, April 03, 2007

A simple regular language recognizer

There are some programs that you just have to write in order to have the feeling that you know a bit of the programming language you are learning. For me such a program is a regular expression recognizer.

Both strings and regular expressions are represented by lists of Lisp symbols (a regexp description may be also a nested list)
Let me introduce my notation of regexp-s by example:
  • (* a b c d) is the same as (a b c d)* in the usual notation
  • (+ a b c d) is (a b c d)+
  • (or a b c d) is (a|b|c|d)


(defun recognize (regexp string)
"T if string matches to regexp, nil otherwise."
(let ((end (list (gensym))))
(if (null regexp)
;; the language {\sigma} must be a special case because nil is
;; the value returned by reg-eval on failure
(null string)
(equal end (reg-eval regexp (append string end))))))

(defun reg-eval (regexp string)
"If string has a prefix matching regexp, returns the part that doesn't match (nil otherwise)."
(when string
(cond ((null regexp)
string)
((not (listp (car regexp)))
(when (equal (car string) (car regexp))
(reg-eval (cdr regexp) (cdr string))))
(t (let ((prefix (caar regexp))
(body (cdar regexp)))
(case prefix
((*)
(reg-eval (cdr regexp) (let ((match (reg-eval body string)))
(if (not match)
string
(reg-eval (list (car regexp)) match)))))
((+)
(reg-eval (nconc (list (cons 'subexp body) (cons '* body)) (cdr regexp)) string))
((or)
(some #'(lambda (x) (reg-eval x string)) body))
((subexp)
(reg-eval (cdr regexp) (reg-eval body string)))))))))


(defun test ()
(let ((cases '((recognize '(a b c d) '(a b c d))
(recognize '((* a b c)) '(a b c a b c))
(recognize '((or ((+ 1) 2) (2 1))) '(1 1 1 2))
(recognize '((or (1 2) (2 1))) '(1 2)))))
(dolist (cas cases)
(format t "~&~s => ~s." cas (eval cas)))))

Tuesday, March 06, 2007

Lisprolog

As someone has observed on comp.lang.prolog, 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 try google).

For a long time, poor Prolog guys didn't have a good answer. However, this annoying situation has changed, thanks to Marcus Triska. Let me present, ladies and gentlemen, Lisprolog, 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).

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 Essentials of Programming Languages by Friedman, Wand & Haynes at the moment).

Sunday, March 04, 2007

Moving from wordpress to blogger

I 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.

There's quite a lot written about moving your blog archive from blogger to wordpress. 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.

Fortunately, I found a very nice python script which allowed me to make the move without any excessive pain: wordpress2blogger. Many thanks to the author!