9 April 1997

Everyone wants Prolog.
You're gonna love Prolog.
Come on and get Prolog,
get Prolog, get Prolog...
-- with apologies to Ren and Stimpy

Much of programming in traditional languages consists of drudgery. Whipping data structures to and fro, playing "hide and go memory leak", while-ing away the nanoseconds, and specifying all sorts of algorithmic details that serve only to annoy. When a program's goal is simply to harness the CPU and reach a conclusion, we shouldn't have to waste our time holding its hand. We would prefer simply to specify the laws of the software's universe and let the rest take place automagically.

And so it goes, in Prolog. "Programming in Logic" is probably best known for its applications in artificial intelligence and expert systems, but it's useful for all sorts of tasks. If your application lends itself to expression in facts and rules, the Prolog code will be extremely concise relative to other languages.

A Prolog interpreter is essentially an extremely capable theorem prover. Program data consists of a set of facts (statements asserted to be true) and rules (mechanisms for logical inference.) It can then be presented with a question (a proposed theorem conclusion) and the interpreter will deduce whether it can be proven given the known facts and rules. The actual mechanisms by which this is done are under the hood (but I'll eventually let you in on the secret, because I like you.)

The feel is most easily communicated by example. Let's learn about Prolog through this crude but effective¹ matchmaking program. "gender" and "likes" are the relations we use to express facts. Arguments beginning with a lowercase letter are treated as constants and those beginning with an uppercase letter are variables. A variable holds the same meaning within the scope of a particular rule.

/*
 * Modern dating can be so confusing!
 * Sort it out with PROLOG.
 */

/* rule about who is destined for whom */
good_match(X, Y) :-
gender(X, A),
gender(Y, B),
likes(X, B),
likes(Y, A).
not(X = Y).

Once this is loaded into the Prolog interpreter, we can solve the mysteries of modern romance by asking simple questions. At the ?- interactive prompt, I will query "who is a good match for alicia?" Recall that Date is identified as a variable because of its initial capital letter.

?- good_match(alicia, Date).
Date = barbara ;
Date = dimh ;
Date = egbert ;
No

The interpreter goes about its work like so. It finds no facts that match our question (else it would have returned that fact immediately), but it does find the rule good_match(X, Y). It replaces our goal with the list of goals enumerated in the good_match rule, with the variable X now bound to the constant alicia and the variables Y and Date bound to one another. Now it must satisfy all these rules. First among them is gender(alicia, A). Our database contains the fact gender(alicia, female), so A is bound to female. This matching process continues until all variables are successfully bound, or all possibilities fail, or our CPU limit² is exceeded and the system administrator comes grimly stalking us with a LART³.

Once it satisfies the goal, it can be told to find further possibilities with a single semicolon. The interpreter scratches its initials into the spot on the parse tree where a solution is found, so it just backtracks⁴ from there until it finds another solution. In this example, there were eventually no dates remaining for poor alicia, and the interpreter displayed its innate indifference toward the lovelorn with: No.

The inclusion of not(X = Y) in the good_match conditions is necessary to keep barbara from pursuing a date with herself. The introduction of negation to a Prolog program has some interesting implications, because of what is called the "closed world assumption." Prolog assumes that everything that cannot be proven true, must be false⁵. So if you asked Prolog

?- not jimmy_hoffa(buried_in_giants_stadium)

it would most likely⁶ answer "yes", which seems to imply it proved that Jimmy Hoffa is not buried in Giant's stadium. In fact, it failed to prove that Jimmy Hoffa IS buried in Giant's stadium -- a considerably less controversial outcome.

Because Prolog is so thorough about exploring the possibilities, it can be extremely slow⁷. This difficulty is alleviated somewhat at a cost in elegance by allowing the programmer to control backtracking. If a program reaches a cut (represented by an exclamation point), the interpreter will not attempt any further backtracking⁸ from that point in the program.

Unfortunately cuts introduce a schism between the "procedural" and "declarative" meanings of a Prolog program. In code without cuts, the order in which facts and rules are asserted will not affect the result of a question. Cuts which prevent the interpreter from reaching goals it would otherwise have considered valid are called red cuts, and if you need many of these, Prolog may not have been such a good choice after all. Cuts that only prevent useless backtracking are used to improve efficiency; they are called green cuts, and they're A-OK in my book.

So there you have the basics of Prolog. I didn't delve into more complex data structures such as lists or the nifty things⁹ that can be done with them, but you can read about that another day. Remember, Prolog interpreters can be (and certainly have been) embedded into other applications. So the next time all or just some of a project sounds like a hairball logic problem, consider whether that sound can be improved with some Prologic.

Writing a (working) Prolog interpreter in Java was a little daunting for the time I had allocated. A few other people have nicely pulled this off: here's one. I did have some fun with JavaCC (a wonderful tool) and wrote a little parser (which isn't at all faithful to "real" Prolog) that builds up all the relevant data structures in Java. The source is just for you.

-- Paul <paulp@go2net.com> recently proved that he has no life, but then claimed the results were inaccurate due to the closed world assumption.