Clojure: generating sentences given a grammar (part 1)

Introduction

The idea of this post is writing a simple sentence generator based on a given (context free) grammar. The idea and the program come from PAIP.

However, this is essentially only a starting point to present some philosophical differences of programming languages and to show how Clojure is every bit as versatile as Common Lisp (on this kind of problems) and perhaps some new built-in features make it an even more interesting choice for this problem.

Description of the problem

The problem here is simple: generate sentences in a small subset of english. Small is an overstatement; perhaps diminutive is more appropriate. At the cost of looking snob, I believe that many mainstream programmers may already be cowling in fear or, if skilled enough, they are looking for a library doing the task.

There is nothing wrong with the library approach. Moreover, it is probably the right choice for a "real" project, because it is certainly more versatile than the few lines we are going to write, more tested [well, actually not, as our piece of code is just a very close translation of some 25 years old program or so ]. Perhaps, more efficient.

Now suppose we are not meant to use external libraries. Unrealistic as it may be, consider that we want to learn something beside a new bunch of API's. Or maybe we just want a lightweight solution. Different approaches are favored for different programming languages.

I jump the stage in which the programmer writes a program specifically translating the example grammar. I believe it is clear from the specs that we want to generate sentences for every grammar with some prerequisites. As a consequence, we have just to represent the grammar in some format, read it, understand it and generate the sentences.

This is essentially a language interpretation problem: we have a "program" written in a given language (the grammar) and we want to interpret it (and generate the sentence). The language is not turing-complete, of course [ as we have decided that it should be a CFG, and consequently out interpreter machine needs not to be a turing machine ]. I read somewhere (which I mistakenly believed to be the Unix Programming Environment) that the authors strongly advised to transform generic problems into language interpretation problems. The idea is that this way it is easier to think at a higher level of abstraction (the one given by the interpreted language, not C); efficiency is probably not an issue either, as a specific domain language is likely to be more efficient than a general purpose interpreted language.

An example grammar is:

Sentence : Noun-Phrase + Verb-Phrase
Noun-Phrase : Article + Noun
Verb-Phrase : Verb + Noun-Phrase
Article : the, a, ...
Noun : man, ball, woman, table, ...
Verb : hit, took, saw, liked, ...

Implementation details

The question is how to represent the grammar. I believe that most Java programmers here are already mentally checking the API's of their favourite XML parser. Although in Clojure there are more appropriate data structures, I chose to represent it as a list of lists, as with the Lisp tradition. This has the advantage that examples prepared for PAIP program can be directly used without modification. Moreover, the size of the grammar is modest enough not to make it an issue. Besides, switching from lists to vectors does not lead to changes in the code.

I belive that here we can spot a very evident cultural difference. In the Java/OOP world the problem is two-fold. First we have to translate the grammar in data structures manipulable by Java, then we have to actually interpret them. The first part is essentially the task of a parser: for XML there are many parsers (but the syntax becomes very clumsy, IMHO); on the other hand it is possible to use parser generators such as Yacc or Antlr. The second part is also considered a serious issue: in fact in GOF's Design Patterns the Interpreter pattern exactly deals with these kind of problem. Their suggestion is to create a class for every terminal and non terminal. Please notice that we are not talking about the terminals and non terminals of the grammar (such as Sentence or Noun Phrase) but about the terminals and non terminals of the language in which we express the grammar (such as Rule, Alternative, Head and things like that).

It is interesting to notice how both problems in Lisp are non-problems. Lists and atoms provide a nice representation for the grammar itself:

(def *simple-grammar*
'((sentence -> (noun-phrase verb-phrase))
(noun-phrase -> (Article Noun))
(verb-phrase -> (Verb noun-phrase))
(Article -> the a)
(Noun -> ball man woman table)
(Verb -> hit took saw liked)))

The parser problem is completely solved. And the interpreter pattern just becomes some list processing. Less fancy for sure, far easier nonetheless. It is just list processing. Nothing more, nothing less.

This is essentially a straightforward translation of the original common-lisp variant. However, does the job. You can also experiment with different grammars.

Morale

Notice that here the key was not lisp homoiconicity. It is a feature which has not been used. A similar approach could have been used also in C (though grammars would have been impossible to share, unless a specific file based representation was developed). Here the key was just thinking in terms of a DSL.

This is not obvious. Some times ago I developed a toy Prolog program which generates imprecations and similar stuff. Unfortunately enough, this example did not immediately come to my mind. Instead I assumed that Prolog ease of development would be (alone) a time safer. It was not. Using the full language power to generate sentences proved to be far more complex than switching to a simple grammar representation + a bunch of procedures.

Future work

Right now, I'm trying to adapt the generate-all to Clojure. Indeed, although the straightforward translation actually works, it is not lazy, and consequently cannot be used with grammars generating an infinite language.

Books & Amazon associates

"Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp" (Peter Norvig)

"Unix Programming Environment (Prentice-Hall Software Series)" (Brian W. Kernighan, Rob Pike)

Technorati Tags: Clojure, Lisp, Programming

The machine age - NYPOST.com

An extremely interesting survey on modern pratical AI from an AI master.

The machine age - NYPOST.com






Here some undergraduate level books on AI from Norvig:

Artificial Intelligence: A Modern Approach (3rd Edition)

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp

AI, Programming, Artificial Intelligence

Evolutionary Game in Python

A couple of nights ago, after reading like the 10th consecutive network analysis paper, I absolutely needed to do something different. Consequently I grabbed my copy of land of lisp and decided to port chapter 10 game to Python.

The game is easy to understand. It starts with a single animal moving in the world. The animal is able to reproduce (alone, no sex, it's family friendly! -- well don't know) introducing mutations. At each stage each animal chooses a direction, moves there, if there are plants then it eats them (gaining energy) and if has enough energy spawns a child. New plants are grown at each stage: one in a random spot of the central "jungle" area and one in a random spot in the whole board (possibly in the jungle). When the animal finishes energy, dies.

The original lisp code is very loop oriented, with massive use of global mutated variables. As a consequence I thought that a Python translation would be very easy, and in fact, it was. The "sensible" spots are where I expected them to be. For example here:

(defun turn (animal)
(let ((x (random (apply #'+ (animal-genes animal)))))
(labels ((angle (genes x)
(let ((xnu (- x (car genes))))
(if (< xnu 0)
0
(1+ (angle (cdr genes) xnu))))))
(setf (animal-dir animal)
(mod (+ (animal-dir animal) (angle (animal-genes animal) x)) 8)))))

For those who are not fluent in Lisp, in the "labels" form the recursive function angle is defined and that is used afterwards. In the first version of the code, I did a rather faithful translation (and the resulting code was very unpythonic).

def turn(self):
    # inefficient and unpythonic, rewrite!
    x = random.randint(0, sum(self.genes)-1)
    def angle(index, x):
        xnu = x - self.genes[index]
        if xnu < 0:
            return 0
        else:
            return 1 + angle(index+1, xnu)
    self.dir += angle(0, x)
    self.dir %= 8

Now, the code is horrible, in my opinion. And it was late night... I convinced myself that the gratuitous use of recursion should not impact too much on the execution times: after all it can't blow the stack as it is on exactly 8 elements. I was quite wrong. I run the profiler on the file (-mprofile) and let it run just 5000 iterative evolutions. The total time is 75.698 seconds. Please, consider that the profiler slows things a lot. I am going to give performance impressions later. Here I report some snippets of the full profile output.

781884	2.911	0.000	2.911	0.000	:0(random)
755960	2.791	0.000	2.791	0.000	:0(sum)
65076/2958	1.482	0.000	4.095	0.001	copy.py:145(deepcopy)
755960	3.482	0.000	3.482	0.000	isle.py:31(move)
755960	10.859	0.000	51.522	0.000	isle.py:44(turn)
3528217/755960	21.310	0.000	21.310	0.000	isle.py:47(angle)
755960	2.488	0.000	2.517	0.000	isle.py:56(eat)
755960	2.555	0.000	6.802	0.000	isle.py:61(reproduce)
5000	10.540	0.002	75.516	0.015	isle.py:73(update_world)
1	0.000	0.000	75.698	75.698	profile:0(execfile('isle.py'))
781884	7.859	0.000	10.770	0.000	random.py:160(randrange)
781884	6.353	0.000	17.123	0.000	random.py:224(randint)

Here we notice that calls to random & co. take a huge amount of time. But that was to be expected. Here the point is that turn and in turn (pun intended) angle take a huge amount of time. The code could be rewritten in a much simpler way, without the inner recursive function. Here turn is responsible for 2/3 of the time: if we could just reduce the time of an order of magnitude (that is, place the function in the same order of the other methods of Animal) we could achieve acceptable performance. However, even without the profiler Python proves quite slow. For example lets time 10000 evolutionary iterations:

% time python isle.py << EOF
10000
quit
EOF
13.04s user 0.02s system 99% cpu 13.070 total

Notice the trick with << EOF to let us automate user input (I love Unix). Let us compare it with the original lisp implementation. With clisp the performance are less than spectacular to say the least:

% time clisp << EOF<br />(load "evolution.lisp")<br />(evolution)<br />10000<br />quit<br />EOF<br />clisp <<< '(load "evolution.lisp") (evolution) 10000 quit'  <br />57.54s user 4.96s system 98% cpu 1:03.31 total<br /><br />

Probably I could pre-compile the stuff and improve performance. No time right now, moreover I was more interested in SBCL anyway. However, with SBCL it is impressive:

% time sbcl --noinform --load evolution.lisp --eval '(evolution)' << EOF
10000
quit
EOF
0.90s user 0.10s system 99% cpu 1.011 total

That is like 13 times faster than the Python version. I'm sure I can optimize the Python program. For sure, I expect to cut down the execution time of a factor of at least 2 fixing the bloody recursive function. And about what to optimize afterwards, bets are open. On the other hand, the careful reader has surely noticed that turn is a method: in fact I decided to transform Animal in a class. I believe that it is a mistake (that is to say, either transform the full program in an object oriented way or let the whole thing without objects). For example the "reproduce" method *sucks* to a very large extent:

def turn(self):
    # inefficient and unpythonic, rewrite!
    x = random.randint(0, sum(self.genes)-1)
    def angle(index, x):
        xnu = x - self.genes[index]
        if xnu < 0:
            return 0
        else:
            return 1 + angle(index+1, xnu)
    self.dir += angle(0, x)
    self.dir %= 8

It is clear that the method should return the copy instead of adding to the global ANIMALS list.  Anyway... I will deal with object orientation of that code in a later post. My opinion is that the lisp code which I translated is not very lispish, but I like a lot the idea of writing the program quickly. This is the classical example where one risks to over-engineer the simple program, which does its job and is really funny. I loved looking at the black and white terminal with all my animals running around trying to survive! Still, I believe that writing the thing in Python in the first place would have yielded very different code, as it would have done doing it in Haskell or even Scheme. I believe that the example was more on the procedural/imperative aspects of lisp than on writing functional (or OO) code... Full code here.

Evolution, Programming, Python, Lisp, Land of Lisp

Lexical Scope vs. Dynamic Scope

Most languages have lexical scope, nowadays. This is good news, as it is easier to use. In fact, many programmers do not even know the difference between lexical and dynamic scopes, leaving the distinction to programming language junkies.

In languages with lexical scope a variable name is resolved to the object with the same name in the nearest lexical environment. In other words, the compiler chooses the innermost object considering local variables, function parameters, enclosing function variables, global variables and so on. If it is not clear, by the description I gave (which is not clear, I admit) just think to C or Java or Python. That is lexical scope. It is also called static scope, as it can be statically determined with just the source and no runtime information.

It is good because the one who writes the function knows the environment where it is defined (and that is what matters), while the one who calls it does not need to know anything about it:  just to pass the parameters. On the other hand, with dynamic scope functions access the object with a given name that is *nearer* on the call stack. That is to say... the caller environment influences the function behaviour.

Early Lisp dialects have this strategy, as well as Emacs Lisp. Luckily, Common Lisp default mode is lexical scope (but dynamic scope can be used as well). Perl has dynamic scope (with optional "my") static scope.

A good example of the two different strategies is this snippet:

(let 
    ((f (let ((x 1))
          (lambda () x)))
     (x 0))
  (funcall f))

If that snippet is evaluated in emacs *scratch* buffer (C-j) the result is 0. This is because when f is executed, the x nearest in the call stack is the one labeling 0. On the other hand a common lisp compiler would evaluate the thing to 1, as the x referenced in the lambda function is the one in the lexical closure.

* (let 
    ((f (let ((x 1))
          (lambda () x)))
     (x 0))
  (funcall f))
; in: LAMBDA NIL
;     (LET ((F
;            (LET (#)
;              (LAMBDA # X)))
;           (X 0))
;       (FUNCALL F))
; 
; caught STYLE-WARNING:
;   The variable X is defined but never used.
; 
; compilation unit finished
;   caught 1 STYLE-WARNING condition

1

Emacs, Lisp, Functional Programming

Land of Lisp (part 1)

I did not want to buy this book. I have a pretty busy schedule and I /knew/ that if I had it on my desk it would have made things worse. Moreover, Lisper have the tendency to make every other language inadequate; considering that I am (unfortunately) not going to use Lisp in the near future, that would be on the demotivational side of things. Just hope to be able to use clojure, but that's another story.

The introduction is one of the funniest pieces of half-technical writing I ever read. In the rest of the book the humor is present and that is great value. I don't consider myself a Lisp expert; however, it's about a decade since my first exposure to Lisp, I have recently dig into scheme and used quite an amount of functional, logic, dynamic, high-level and whatever languages. That means that I was afraid the first chapters of the book would just be very boring to read (because I already know the contents), but perhaps a necessary evil to familiarize with the concepts and the philosophy of the book, which could prove useful when reading more advanced stuff.

Well, I was right and I was wrong. I was right since it's pretty hard resisting to read the book, even though I have some compelling things to do (or maybe more so). O was wrong because the first chapters are a pleasant reading /even if you know/ the concepts presented. Perhaps it is even more interesting as my brain is not involved into understanding difficult new concepts but can just enjoy the beautiful presentation of familiar stuff.

Besides, the book is a wonderful introduction to the functional way of thinking and covers relatively advanced topics. You can really learn Lisp from the book, even if you don't know a thing about Lisp and functional programming. However, it is nice to read for someone familiar with FP and not with Lisp. I believe that it is funny even for experienced Lisp hackers, as the comics and jokes inside the book are really funny.

Clojure is mentioned, as are Scheme and Arc. However, the focus is just Common Lisp. It is not hard to port the examples to other Lisps, however. As macros are introduced relatively late, the example could also be used with other languages, such as Python.

Lisp, Land of Lisp, Programming Languages, Scheme, Clojure, Game Programming, AI

"Land of Lisp: Learn to Program in Lisp, One Game at a Time!" (Conrad Barski M.D.)

FOAF, crawlers, etc

 

As part of my research, I have to gather a large number of FOAF profiles. So I looked for some crawlers able to get the profiles (without having to write one myself, which is boring, considering the flexibility of RDF -- and consequently the number of outbound links which could be meaningful).

 

So... looking for FOAF crawlers (which are semantic crawlers, also called scutters). The first one I found is Futil (funny name choice, BTW). The project page gives some information on the project (quite generic) and has a link to the web svn browsing page. I did not find references to the actual svn repo (but I could easily infer it). Ok. So far so good.

So I examined the list of dependencies the project has:

• Python >= 2.4.0
• RDFLib >= 2.3.1
• PyLucene >= 2.0.0
• PySQLite >= 2.3.2
• Python-MySQLdb >= 1.2.1
• PyXML >= 0.8.4
• Python-URL >= 1.0.1

The first dependency is obvious. It's a python project so we need a python environment. And 2.4 is a very low requirement. Good. RDFLib can be easily installed with easy_install, even on windows. Really, easy_install RDFLib

 

just works! Ok. Then it comes to PyLucene: I found it quite impossible to install on windows. I'm sure I can work it out, but instructions are terrible. There is a binary build project, however, it does not work. At least, not the simple instructions they give. I installed the egg and then:

C:\Users\enrico>python
Python 2.6.5 (r265:79096, Mar 19 2010, 21:48:26) [MSC v.1500 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
[1]: import lucene
Traceback (most recent call last):
File "stdin", line 1, in module
File "C:\Python26\lib\site-packages\lucene-2.9.3-py2.6-win32.egg\lucene\__init__.py", line 2, in module
import os, _lucene
ImportError: DLL load failed: The specified module could not be found.

Ok. Things are getting nasty and for no reason. Compiling Python modules on Windows is usually a PITA. Especially because I have Visual Studio 2010 and not Visual Studio 2009 or 2008 or whatever is the default compiler for Python on Windows. Thanks to the little "limited compile yourself dll hell" I'm not going that route (moreover, I'm a gcc guy).

So I tried the futil package without pylucene. Maybe, I thought, something works even without PyLucene. Afterall, Python is a very dynamic language. It is trivial to create a program/library which does not load things it does not use. So I tries just:

 

python futil-run.py --help<br />

What I got was an error related to not having MySQLdb. What the fuck! I asked for an help message. Nothing more! I need no stinking mysql! Just a bloody help message. Consequently, I suppose that the whole project needs everything installed, even if I don't use it. Which is bad.

 

I suppose I'll try with slug , written in Java, and see what happens.

FOAF, futil, python, semantic web, crawler, scutter, MySQL, Java

Powered by ScribeFire.

Anagrams: fast python algorithm

So in this post I showed how the trivial algorithm to compute anagrams is stupid (and consequently slow) beyond hope. On the other hand I promised a nice algorithm to do that. In fact, it is just a matter of pre-processing the data. The idea is to compute a key which is unique to all the words which have the very same letters and then group all the words with the same key. One of the simplest keys could be a bag of the letters (if your language supports bags -- or multi-sets --). Python sets have unique keys, so they are not a good candidate. However a "sorted" variant of the word has the right properties. Every word with the same letters (which is the definition of palindrome) yields the same string if we sort its letters. A good structure is a dictionary with this key as key and a list of strings as value. When we find a string with a previously found key, we add it to the list of strings, otherwise we generate a new list. This is the very popular setdefault idiom:

d.setdefault(key, []).append(w)

The key for a word of length n is computed in O(n log n), insertion in the dictionary is O(1) (get the key is O(1) in average and append to the list is O(1)). So the algorithm uses rather efficient elementary operations. At this point "general" questions on the processed wordlist can be answered in O(M) if M is the number of the words (e.g., longest anagram, word with most anagrams). Simply getting the anagrams of a given word is an O(n log n) operation. We are not using an excessive amount of memory. We basically have an hash-table and some "pointers" to the original words. And now the code:

class Anagrams(object):
    def __init__(self, dictionary):
        self.dictionary = dictionary
        self.indexed_words = {}
        self.preprocess()

    def make_key(self, word):
        sorted_word = list(word)
        sorted_word.sort()
        return tuple(sorted_word)

    def preprocess(self):
        for word in self.dictionary:
            key = self.make_key(word)
            self.indexed_words.setdefault(key, []).append(word)

    def anagram(self, word):
        key = self.make_key(word)
        return tuple(self.indexed_words[key])

    def anagrams(self):
        return [anagrams for key, anagrams in self.indexed_words.iteritems()
                if len(anagrams) > 1]

As a matter of fact, if we extend the corpus of words, the required time increases. In fact, using the dictionary from here it took 4 whole seconds. Which is nonetheless a lot less time than some million of years. I did not use that dictionary because it contains lots of misspells which can have sense when computing Levenshtein distances, but are quite a PITA if we compute anagrams (we don't want non existing words to popup as solutions).

Technorati Tags: Efficiency, Optimization, Python, Algorithms, Anagram

Anagrams and (brains vs. cpu)

In AI there is a vast category of algorithms which follow a (blind) generate and test strategy. They essentially "generate" the solutions (as a whole or step by step) and then test if the solution complies with an acceptance function. Unfortunately, this simple strategy is usually ineffective. The cost is often exponential in the size of the input and since there is no "intelligence" all solutions (even dumb ones) are explored). In AI it is customary to use smarter search techniques (A*) or to "change" the problem so that even smarter solutions are viable. An apparently unrelated example, is "finding the anagrams of a word". The trivial (and generate and test) solution is:

1. [generate]: try all the permutations of the word
2. [test]: check if the word is in the dictionary

and this strategy also shares the very same problems of the other generate and test strategies. All the permutation of a k characters word are k! = k(k-1)(k-1)...2. It is customary to see algorithms like:

def yield_anagrams(dictionary, word):
return [word for word in
(''.join(candidate) for candidate in it.permutations(word))
if word in dictionary]

which in other languages are even longer and less attractive. This approach is rather tempting for very small words. I got some interesting wordlists from here. As a good starting point I used the 12Dict list and in particular the 2of12.txt file. More info on the lists can be found in the ReadMes. In the rest of the post we are going to work with that dictionary. This graph shows the distribution of word lengths: This other graph shows how many groups of words with the same anagram we have by word length: For those preferring tabular data:

Size of the word	Number of groups
2	8
3	97
4	319
5	313
6	329
7	239
8	124
9	73
10	30
11	27
12	9
13	4
14	2

As we can see, the longest words with anagrams are 14 characters long. Even though most anagrams are very short word, our algorithm should work reasonably well with every input. The code I showed cannot. For example, let us consider the time required to compute the anagrams of words of increasing size:

scoreless	9	0,174
praetorian	10	1,828
rationalize	11	21,03
indiscreetly	12	269,0

In the first graph, we both axes are linear. If we do not believe me when I say that the growth is exponential, then look at this other graph: here the y axis is in logarithmic scale. Exponential means that if you simply change the implementation or the implementation language, things are going to blow up once again a couple of steps later. So, let us sum up: we have 41238 words. Of these words, 5644 have 12 or more characters. If we suppose that anagrams for words longer than 12 character cost exactly as anagrams for words 12 characters long, the whole process is going to take 1518236 seconds, that is to say more than 17 days. In fact, the whole process is going to be far more expensive. I have a full table (excel -- here you may want to download the file --, csv) with times estimated using the formula derived from our 4 values. Of course, this is not extremely precise, but the sheer magnitude of the computed values should make the point clear. To compute all the anagrams for all the words up to size 11 (included) it takes one day. If you want to reach size 13 it is going to take one year. However, it is still a long way to process all the words... for example, in order to discover that our dictionary words with anagrams of length 15, our program is going to run for more than 38 years. The conclusion that no words longer than 14 has an anagram (according to our dictionary) takes more than 4000000 years. Of course, I did not wait all that time to gather these results... tomorrow I am showing a smarter strategy which drops the required time from 4000000 years to 0.16 seconds.

Technorati Tags: Efficiency, Optimization, Python, Algorithms, Anagram

Mastermind/Bulls and Cows Breaker

Introduction

Mastermind is a classical code breaking game. And I bet almost everyone has played it at least one time (at least, any geek[0]). I won't explain the rules here. If you really don't know the rules, here there is an explanation. Besides, we are playing Bulls and Cows, which is very similar, but has no copyright.

I sincerely find the game rather boring, though I find writing programs solving boring games quite entertaining. This is a very old prolog program I wrote to break the code. The algorithm is extremely trivial, and is more an example in how easy to solve are this class of problems in Prolog with native backtracking than anything else.

Wikipedia page also list some scientific papers on Mastermind/Bulls and Cows code breaking algorithms. I find them really interesting, indeed. But this is about Prolog and backtracking, indeed.

The code

:- use_module(library(lists)).
:- dynamic query/3.

mastermind(Code) :-
 cleanup, guess(Code), check(Code), announce.

guess(Code) :-
 Code = [_X1, _X2, _X3, _X4],
 selects(Code, [1,2,3,4,5,6,7,8,9]).

check(Guess) :-
 \+ inconsistent(Guess),
 ask(Guess).

inconsistent(Guess) :-
 query(OldGuess, Bulls, Cows),
 \+ bulls_and_cows_match(OldGuess, Guess, Bulls, Cows).

bulls_and_cows_match(OldGuess, Guess, Bulls, Cows):-
 exact_matches(OldGuess, Guess, N1),
 N1 =:= Bulls,
 common_members(OldGuess, Guess, N2),
 Cows =:= N2-Bulls.

ask(Guess) :-
 repeat,
 format('How many bulls and cows in ~p?~n', [Guess]),
 read((Bulls, Cows)),
 sensible(Bulls, Cows), !,
 assert(query(Guess, Bulls, Cows)),
 Bulls =:= 4.

sensible(Bulls, Cows) :-
 integer(Bulls),
 integer(Cows),
 Bulls + Cows =< 4.


%%  Helpers
exact_matches(Xs, Ys, N) :-
 exact_matches(Xs, Ys, 0, N).
exact_matches([X|Xs], [Y|Ys], K, N) :-
 (   X = Y ->
 K1 is K + 1
 ;   
 K1 is K),
 exact_matches(Xs, Ys, K1, N).
exact_matches([], [], N, N).

common_members(Xs, Ys, N) :-
 common_members(Xs, Ys, 0, N).
common_members([X|Xs], Ys, K, N) :-
 (   member(X, Ys) ->
 K1 is K+1
 ;   
 K1 is K),
 common_members(Xs, Ys, K1, N).
common_members([], _Ys, N, N).

cleanup :-
 retractall(query(_,_,_)), !.
cleanup.

announce :-
 size_of(X, query(X, _A, _B), N),
 format('Found the answer after ~d queries.~n', [N]).
%%  Utilities
selects([X|Xs], Ys) :-
 select(X, Ys, Ys1),
 selects(Xs, Ys1).
selects([], _Ys).

size_of(X, G, N) :-
 findall(X, G, Xs),
 length(Xs, N).

Notes

[0] Most of the type when you say "any" or "everyone" you are wrong. This applies to me as well.