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.