Pro Prolog

Last time, I mentioned that different programming paradigms involve thinking about the problem you’re trying to solve in completely different ways. Most languages you normally see in use, be they procedural, object-oriented, functional, or something else, typically involve giving the computer a series of commands to execute. The way you do that can vary quite a bit, but that’s essentially what’s going on. The computer doesn’t particularly care what you’re trying to accomplish; it just does as it’s told. We might call this the Meatwad Programming Paradigm:

Do what I said, ’cause I said it.

- Meatwad

Prolog is different; it’s a logic programming language. In logic programming, instead of giving the computer a series of commands, you give it a database of facts and rules. Facts are, well, simple facts that you know are true. Rules tell the computer how to derive new facts from other facts. Once you load the database, you can ask the computer where things are true. If the computer can use the facts and rules it knows to prove what you asked, it will tell you so. Otherwise, it will report failure.

An example might make this clearer. Let’s say we want to study the relationships between people in a family. Our database needs to have a simple set of relationships we know, such as:


father(george,michael).
father(george,lindsay).
father(george,gob).
father(george,buster).
father(michael,george_michael).
father(tobias,maeby).
 
mother(lucille,michael).
mother(lucille,lindsay).
mother(lucille,gob).
mother(lucille,buster).
mother(lindsay,maeby).

Our facts take the form of predicates with one or more arguments. Here, we’re using father(X,Y) to mean that X is the father of Y. We use mother(X,Y) similarly.

Given just this database, we can execute queries to see if certain parent-child relationships are true. For example:


| ?- father(george,lindsay).
 
true ?
 
(4 ms) yes
| ?- father(tobias,buster).
 
no

It should be exceedingly obvious that, given the above database, George is Lindsay’s father, but Tobias is not Buster’s father. Technically, Prolog hasn’t proved that Tobias isn’t Buster’s father, but it did fail to prove that he was, which is good enough for Prolog.

Naturally, if this were all we could do with Prolog, it wouldn’t be very interesting. One neat thing is that we can put variables in the arguments to, for example, get a list of everyone whose father is George:


| ?- father(george,X).
 
X = michael ? a
 
X = lindsay
 
X = gob
 
X = buster
 
(4 ms) yes

Prolog tells us all the values of X that would satisfy the query. We could have used a variable in the first argument to father instead (to find out who someone’s father is) or use variables for both arguments (to find out all father-child relationships).

Things get a bit more interesting once we start adding some rules to our database. For example, let’s start with a predicate parent(X,Y) that is true whenever X is Y‘s parent:


parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).

The first rule tells Prolog that X is Y‘s parent if X is Y‘s father. The second says that X is Y‘s parent if X is Y‘s mother. Now we can use the parent predicate just like the others we defined via facts:


| ?- parent(lucille,buster).
 
yes
| ?- parent(X,maeby).
 
X = tobias ? a
 
X = lindsay
 
yes

But this is kid’s stuff so far. Prolog wouldn’t be much of a programming language if we couldn’t use rules recursively, so let’s do that to define arbitrary ancestral relationships between two people:


ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

The first rule simply says that X is Y‘s ancestor if X is Y‘s parent. The second one is where things get interesting: X is Y‘s ancestor if X is the parent of some Z, and Z is an ancestor of Y. Now we can use Prolog to probe ancestral relationships of arbitrary length:


| ?- ancestor(george,maeby).
 
true ?
 
yes
| ?- ancestor(X,maeby).
 
X = tobias ? a
 
X = lindsay
 
X = george
 
X = lucille
 
no

Observe that that last query finds not only Maeby’s parents (Tobias and Lindsay) but also her grandparents (George and Lucille).

Prolog also lets us use lists in additional to individual terms. To show that we can also implement algorithms in Prolog, here’s a (fairly unoptimized) implementation of mergesort:


mergesort([], []).
mergesort([X], [X]).
mergesort(In, Out) :-
    length(In, InLen),
    InLen >= 2,
    append(X, Y, In),
    length(X, XLen),
    length(Y, YLen),
    ( 0 is YLen - XLen; 1 is YLen - XLen ),
    mergesort(X, XSorted),
    mergesort(Y, YSorted),
    merge(XSorted, YSorted, Out).
 
merge([], Y, Y).
merge(X, [], X).
merge([XHead | XTail], [YHead | YTail], [XHead | RTail]) :-
    XHead =< YHead,
    merge(XTail, [YHead | YTail], RTail).
merge([XHead | XTail], [YHead | YTail], [YHead | RTail]) :-
    YHead < XHead,
    merge([XHead | XTail], YTail, RTail).

That may look quite a bit like a mergesort written in a functional language, but note that there is some logic programming uniqueness to it. In particularly, we split the “input” list in half by telling Prolog to find two lists X and Y who, appended together, equal the original list, and whose lengths are within 1 of each other. Prolog takes care of figuring out what X and Y should be in any particular instance. Having something called append do double duty as a way to split a list in twain is one of the crazy things logic programming lets you do.

Plain old Prolog does fall down a bit when it comes to math. While it can handle arithmetic just fine, it doesn’t know how to do algebra. For example:


| ?- X is 3 + 5.
 
X = 8
 
yes
| ?- 8 is X + 5.
uncaught exception: error(instantiation_error,(is)/2)

From what we’ve seen so far, Prolog doesn’t quite satisfy the needs for implementing a bridge bidding system for Old Lady. On the one hand, predicates and variable unification are a good fit for the bidding rules: something like bid(Bid, HandInfo) could be used to choose a bid if we pass it information about a hand, and can also be used to learn about a hand given a certain bid. This “it works in both directions”-ness is exactly what we’re looking for to both make our own bids and to interpret those of other players, without having to duplicate our rules.

However, an inability to do mathematics more complex than basic arithmetic is a problem, since most of the information communicated through bidding is precisely that: how many HCP a player has, or how many cards of a certain suit he has, and so on. There’s also known mathematical relationships between all the variables: for example, the deck only has 13 spades, so if I have 5 and my partner has at least 3, that tells me that the other two players have at most 5 spades between them. Plain old Prolog doesn’t have an elegant way to express these sorts of constraints.

But notice how I slipped “plain old” in front of Prolog? Some Prolog implementations, such as GNU Prolog (the one I’m experimenting with) also do constraint logic programming, which lets us express mathematical relationships between variables. For example, let’s try to find all numbers less than or equal to 100 that are equal to the square of a prime number:


| ?- fd_domain(X,0,100), fd_prime(Y), X #=# Y * Y.
 
X = _#3(4:9:25:49)
Y = _#23(2..3:5:7)
 
yes

The constraint solver in GNU Prolog has figured out that X must be 4, 9, 25, or 49, and Y must be 2, 3, 5, or 7. As we add constraints, we can narrow that down even further. For example, let’s also require that X is even:


| ?- fd_domain(X,0,100), fd_prime(Y), X #=# Y * Y, 0 #=# rem(X, 2).
 
X = 4
Y = 2
 
yes

Given this, a way to implement a bidding system in GNU Prolog reveals itself. Encode the bidding system rules in Prolog rules, using these numerical constraints. Then build a query that includes all the basic information we know, namely our hand and the bidding history so far. In evaluating the query, GNU Prolog will determine constraints on the variables of interest (i.e., who has how many of each suit, and their hands’ estimated strength), and pick the next bid we should make.

Even better, GNU Prolog has ways to issue queries from C code. While this might not seem very useful when Old Lady is written in Python, there are ways to interact between C and Python, so we just need to write a little duct tape in C that communicates between GNU Prolog and Python.

So, it turns out I was looking for a constraint logic solver all this time, and was writing an exceedingly two-ninths-assed one in Python.

If any of the above has piqued your interest in Prolog, there’s a pretty good Prolog tutorial here that does a much better job explaining Prolog than I’ve done here.

9 Responses

  1. Your database doesn’t properly encapsulate the revelations of the third season. For shame.

  2. 1,000 points for using Arrested Development example data. Also, 50 points for avoiding spoilers/complications of the third season (even though I’ve seen all of it and love it to death).

    So…you could use Prolog to do algebra, but you have to basically write math as we know and use it as part of the rule set first? Pain in the ass…

  3. Check out PySWIP, a Python/SWI-Prolog bridge!

  4. Yes, I cleverly avoided any third-season spoilers, which I did solely out of my own benevolence and has nothing to do with the fact that I’ve only seen the first season.

    You could easily create unary numbers of the form 0, s(0), s(s(0)), s(s(s(0))), etc, and write rules that perform operations on them, but it’s horribly inefficient. It also has a tendency to try every possible value for a variable in a query, and since there are infinite natural numbers, that doesn’t work so well when there’s no solution.

    PySWIP looks promising, assuming SWI-Prolog can do constraints like GNU Prolog can.

  5. SWI-Prolog has more constraint libraries than GNU Prolog: CLP(Q), CLP(R), library(bounds) and library(clpfd). SWI also provides the important dif/2 constraint over arbitrary terms.

  6. Here’s a shorter and generalised version of mergesort that can be used for lists of arbitrary terms (not just numbers):

    mergesort([], []) :- !.
    mergesort(List, Ascending) :-
    length(List, Length),
    ( Length = Ascending = List
    ; FrontLen is Length // 2,
    length(Front, FrontLen),
    append(Front, Back, List),
    mergesort(Front, SFront),
    mergesort(Back, SBack),
    merge(SFront, SBack, Ascending)
    ).

    merge([], Y, Y) :- !.
    merge(X, [], X) :- !.
    merge([X|Xs], [Y|Ys], [Z|Zs]) :-
    ( X @ Z = X, merge(Xs, [Y|Ys], Zs)
    ; Z = Y, merge([X|Xs], Ys, Zs)
    ).

    It also doesn’t leave unnecessary choice-points. Consider using =:=/2 instead of is/2 for comparisons. I also changed the argument names, since In/Out is not the only way you can use the predicate (you can also use it in mode In/In, to test whether a list is sorted). Also, parent/2 is not a very descriptive name for a relation – consider using a name like parent_child; similarly, father_child/2.

  7. Here’s the code again with the right tag:

    mergesort([], []) :- !.
    mergesort(List, Ascending) :-
    length(List, Length),
    ( Length = Ascending = List
    ; FrontLen is Length // 2,
    length(Front, FrontLen),
    append(Front, Back, List),
    mergesort(Front, SFront),
    mergesort(Back, SBack),
    merge(SFront, SBack, Ascending)
    ).

    merge([], Y, Y) :- !.
    merge(X, [], X) :- !.
    merge([X|Xs], [Y|Ys], [Z|Zs]) :-
    ( X @ Z = X, merge(Xs, [Y|Ys], Zs)
    ; Z = Y, merge([X|Xs], Ys, Zs)
    ).

  8. However, the Debian packages for SWI-Prolog look quasi-unmaintained, which makes me a bit apprehensive about using that over GNU Prolog. I’ll need to look if SWI-Prolog’s extra constraint libraries are helpful or not for what Old Lady will need to do.

    Alas, from a brief look at the SWI-Prolog manual, the syntax between the two implementations is different enough to preclude an elegant cross-Prolog-environment solution. I guess that’s what happens when you go beyond the main language.

    In your mergesort implementation, is Length = Ascending = List right, or is something getting eaten by WordPress? I don’t see how a list would unify with its length.

  9. You can download the RPM from http://www.swi-prolog.org and use alien -d to get a Debian package; also, try the git repository, which should compile without problems. Regarding the merge sort, many characters got eaten – in particular in the if-then-else construct (dash plus greater than); the code should read: if the list’s length is less than or equal 1, unify Ascending with List (actually, you can therefore omit the base case totally, because this covers the Length == 0 case). Also the single “at” sign you see in merge/3 should be term comparison: A “less than” sign before the “at” was eaten. The CLP(FD) solver of GNU Prolog has severe deficiencies for several uses (no negative values, upper bound on domains etc.), but its syntax isn’t very different from library(bounds) or library(clpfd) in SWI, and a compatibility library is pretty straight-forward.

Comments are closed.