Learn Prolog

Prolog is short for PROgramming in LOGic, and has its roots in predicate calculus. One needn't have a solid understanding of that to make use of it, though.

A good Prolog implementation written in Java is tuProlog, the latest version of which can be found here.

The premier book for learning Prolog is Programming in Prolog, but other resources are available, like this online introduction that's also available as a PDF.

Prolog question can be asked in the Logic Programming forum right here on the Ranch.

An example

To start with, here's a short Prolog program that solves the first problem of Project Euler : If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Save the following code in a file called euler1.pl.
dividableBy3or5(X) :- 0 is mod(X, 3). dividableBy3or5(X) :- 0 is mod(X, 5). euler1(LIMIT, 0) :- LIMIT < 3. euler1(X, SUM) :- dividableBy3or5(X), X1 is X - 1, euler1(X1, SUM1), SUM is SUM1 + X. euler1(X, SUM) :- X1 is X - 1, euler1(X1, SUM).
First we define the a function for determining whether a number is dividable by 3 or 5. The ":-" can be read as "if the right side is true, then the left side is true, too". "is" can be both an assignment or a test for equality; in this case it's the latter.

Then we define euler1, the actual program. The first line says "For any LIMIT smaller than 3, the result will be zero". So if LIMIT is smaller than 3, this line determines a result, and the execution stops. Otherwise, the next line is executed. It tests whether dividableBy3or5 returns true; if so, it adds the current X to the sum and repeats the call with X decremented by 1. If 'dividableBy3or5 is not true, the third line is executed which simply calls euler1'' with X decremented by 1. The comma acts as a delimiter, kind of like the semicolon in Java.

To run Prolog code, double-click the 2p.jar file (in the bin directory).. From the GUI that pops up, open the file euler1.pl. Now, in the text field next to "?-", type "euler1(10, X)." and click on the button with the right arrow to its right. That's Prolog's way of saying "find me some X so that euler1(10, X) is true. It will come back saying that X is 33.

That's close, but not quite there. The result for 10 should be 23 - not 33. That's because the recursion starts at 10 inclusively, not exclusively as the problem description states. We can avoid that by introducing a little helper function that starts the calculation at the number below LIMIT. We also combine the two rules for dividableBy3or5 into a single one joined by ";" - that's Prolog-speak for "or".
dividableBy3or5(X) :- 0 is mod(X, 3) ; 0 is mod(X, 5). euler1(LIMIT, 0) :- LIMIT < 2. euler1(LIMIT, SUM) :- LIMIT1 is LIMIT - 1, euler1Minus1(LIMIT1, SUM). euler1Minus1(0, 0). euler1Minus1(X, SUM) :- dividableBy3or5(X), X1 is X - 1, euler1Minus1(X1, SUM1), SUM is SUM1 + X. euler1Minus1(X, SUM) :- X1 is X - 1, euler1Minus1(X1, SUM).
Enter this code into the source window, and run the ''euler1(10,X)." query again- it will report that X is indeed 23.

More examples

Like Scheme, Prolog is well suited for problems that are defined recursively, or that can solved by recursive algorithms. Here are functions that calculate the Factorial of a number and the Fibonacci number sequence.

Note that the fibonacci function is very inefficient, and will become slow very quickly for growing n. But the code mirrors the recursive definition closely, and is thus the "natural" implementation.
factorial(0, 1). factorial(N, F) :- N > 0, N1 is N-1, fact(N1,F1), F is N*F1. fibonacci(0, 0). fibonacci(1, 1). fibonacci(N, F) :- N > 1, N1 is N-1, fibonacci(N1,F1), N2 is N-2, fibonacci(N2,F2), F is F1+F2.

A common Prolog example

It needs to be pointed out that although the examples above are of a mathematical nature, that's not really Prolog's strength. It's more often used with words, language and concepts than with numbers.

Suppose we wish to model family relationships. We want to keep track of who is related to whom, and to draw conclusions from that. Let's start simple:
father(bob, alice). father(bob, peter). father(carl, bob). grandfather(X, Y) :- father(X, Z), father(Z, Y).
This states that the grandfather of someone is his (or hers) father's father. We also have a few rules of who is father of whom. Given these rules, if we query for "grandfather(X,Y)." Prolog will tell us that "X=carl, Y=alice", which is one of the solutions. But we can make it look for more solutions if we click Retry. That'll lead to "X=carl, Y=peter". Clicking Retry again will come up empty, because no further relationships are defined. In this way, a query can have more than a single result.

But the rules may not be complete with respect to who is whose father. Instead, we may know that Alice is Laura's sister:
sibling(alice, laura).
Now we just need to add a rule that the grandfather of someone's sibling is also that person's grandfather (for simplicity's sake we're ignoring the issue of half-brothers and half-sisters that may not have the same grandfather):
grandfather(X, Y) :- father(X, Z1), father(Z1, Z2), sibling(Z2, Y).
If we now run the query again, we'll also get "X=carl, Y=laura".

---

CategoryLearnSomethingNew