Logical Programming

Currently I’m taking a class called “Knowledge representation and reasoning” which is about logical programming and the theory behind it (*cough* I mean, mainly the theory behind it). Logical programming is a form of declarative programming, you don’t write an algorithm that solves your problem, but rather declare your problem and let the interpreter find a solution for it.

Sounds new to you? SQL is a declarative programming language aswell. In SQL you don’t write code that iterates over a table, checks fields, sorts them. You just say, “listen, I want to have the value of these fields from those tables, combined with those that match these criteria, find a way to do it.” Many people don’t realize that this is a way of programming that’s radically different from the normal imperative/object oriented programming they usually do. For example, have a look at this little piece of Prolog code:

parent(anna, peter).
parent(peter, john).
parent(peter, christina).
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).First some elementary syntactical rules:

  1. Each “statement” in Prolog ends with a period
  2. Constant values are all lowercase
  3. Variables start with a capital letter

Now, what does this mean? The first statement says “Anna is a parent of Peter.” The second says, “Peter is a parent of John.” The third says “Peter is a parent of Christina.” Realize this means that John and Christina must be brother and sister. Every statement in Prolog declares a truth. You define the way things are. The notation used on the fourth line means, the part on the left of the ”:-” is true, under the condition that the part on the right is true. Here you see the right part consists of two statements (parent(X,Y) and parent(Y,Z)) separated by a comma, this means that both have to be true, in order to let grandparent(X, Z) to be true.

X, Y and Z are variables. Variables can have any value. In the fourth line it says grandparent(X, Z) :- parent(X, Y), parent(Y, Z). What this means is X is a grandparent of Z only if there’s a X and Y to be found for which parent(X, Y) is true, but also that there should be a Y and Z for which parent(Y, Z) is true. Note that each X refers to the same value as other X’s, Y’s refer to the same value as the other Y’s and Z’s refer to the same value as other Z’s.

We explain this further by asking Prolog a question, in logical programming this is called a “goal.” The goal we set is grandparent(anna, peter). In other words, is Anna a grandparent of Peter? Let’s see, X = anna and Z = peter (by simply replacing the variables with their respective values in the fourth line of Prolog code). Is there a predicate that “matches” parent(anna, Y)? In other words is there somebody that has anna as his/her parent? Yes there is, it’s Peter. Peter also appears to be her only son. So we find Y = peter. Now, we have to see if Y (peter) really is a parent of Z (peter) (the second part of the condition in order to qualify as a grandparent). Obviously, this is not true. So the statement grandparent(anna, peter). is false.

What if we want to find all grandchildren of Anna. How would we formulate that goal? Well, there must be a person (G) that has anna as his/her grandparent, isn’t that so? So the goal we set (question we ask) is grandparent(G, anna). When we try to run this in Prolog the answer we’ll get is:
G = john
G = christina
As you can see, that’s indeed true, Anna has got two grandchildren, there are two possible values of G for which there’s a parent Anna who has a son/daughter Y (Peter) who has on his/her turn has a child Z (John and Christina).

As I said in the beginning, the power of declarative programming is that all you do is define the problem in terms so the interpreter can understand it. You don’t have to think of a solution, the interpreter will find one for you. That means less for you to think about, which is always good of course (“Laziness is a programmer’s main virtue” as Larry Wall says).

If you want to play with Prolog, SWI-Prolog is a nice free interpreter. For the .NET addepts there’s now P#, a compiler that compiles Prolog code into C# (which you can then compile to CIL and use in your software).