Programming with Logic

I enjoy working with symbolic logic because it's governed by a really simple set of rules, yet it can be just as expressive as natural language (albeit a lot more terse). In some sense, it's a simple language for expressing reason.

For example, if I want to say that Jane and Kimiko are married, I can state the fact:

Now one problem with this is that \(married(kimiko, jane)\) doesn't automatically hold as well. Obviously though, common sense dictates that a marriage has to hold both ways, because otherwise it's something else entirely... In order to express the symmetry, we can use an implication:

This states the rule that if Jane is married to Kimiko, then Kimiko is married to Jane. \(married(jane, kimiko)\) is the antecedent: the requirements to be satisfied before we can apply the rule. \(married(kimiko, jane)\) is our consequent: the result of applying the rule. So, applying the rule gives a second fact:

Now the rule doesn't actually say anything about other couples. To make it more general, we can use variables \(X\) and \(Y\) instead to stand in for arbitrary objects:

Using this new rule, the symmetry of marriage can be applied to every couple. This application of rules to deduce new facts is central to the idea of logic programming, which is most famously represented by the programming language Prolog, which stands for "Programming with Logic". However, we will see that Prolog deviates from classical logic. In fact, I've specifically chosen the example of married to trip Prolog up.

Prolog

Here's our first fact expressed in Prolog code:

married(jane, kimiko).

There is basically no difference, except that the fact ends with a period . much like how you would end a sentence. Now here's our marriage rule:

married(X, Y) :- married(Y, X).

Here, we use the symbol :- to mean \(\leftarrow\). Yes, the direction of implication is reversed, so actually the antecedent is on the right of the arrow, and the consequent on the left. In Prolog, we call the antecedent the body, and the consequent is the head.

These are the two core components of Prolog. In fact (pun intended), a fact is just a rule with no body. Having no body means there's no requirements to satisfy first: the rule always holds, which is exactly what a fact is.

Now how do we run the program? Actually, all prolog programs are interactive so we can ask questions to it. Running a prolog program will start a query prompt:

?-

We can type facts into the prompt and the program will tell you if the fact is true or false, according to the rules and facts stored in the program. For example, we can verify if Kimiko is married to Jane, as our marriage rule implied:

?- married(kimiko, jane).
true.

In order to check the truth value, Prolog actually applies rules backwards. It tries to find a rule whose head matches the query. In this case, that's our symmetry rule. By applying the substitution X/kimiko and Y/jane to the symmetry rule, it knows that in order for married(kimiko, jane) to be true, it needs to check married(jane, kimiko). Now in our program, we have given Prolog this explicit fact, so it matches without any substitutions (remember that a fact is also a rule, so we consider facts during the matching process). So the check succeeds and Prolog reports the success back to us.

Prolog also has another function. We can actually ask it to fill in the blanks in our query:

?- married(X, jane).
X = kimiko.

This is great! Prolog tells you what values you need so that the facts become true. The same principle applies: Prolog applies rules backwards. In this case, married(X, jane) matches our rule head via the substitution Y/jane. Prolog is also able to tell that we're just using X as a placeholder in our query, so conceptually, the X in the rule is different from the X in our query. Calling these X_rule and X_query respectively, Prolog substitutes X_rule/X_query.

Afterwards, Prolog checks the body of the rule, which after substitution is married(jane, X_query). This matches the fact married(jane, kimiko). via the substitution X_query/kimiko. At this point Prolog reports a success because it's found appropriate substitutions for all the query variables. This matching and substitution process between two expressions is called unification.

Oh and one more thing: sometimes multiple rule heads can match the expression. This is called a choice point, and Prolog initially picks the first rule it matches going from top to bottom. However, we can ask Prolog for an alternate answer, in which case it will rewind to the latest choice point and explore the second rule, and so on. For the most part, shuffling our program just leads to changes in output order. Sometimes though, it can break your Prolog program...

Infinite Loops

Here's an interesting query:

?- married(kimiko, kimiko).

Matching our symmetry rule, we apply the substitutions X/kimiko and Y/kimiko to arrive at the following:

married(kimiko, kimiko) :- married(kimiko, kimiko).

We're right back where we started because our next expression to check is again married(kimiko, kimiko). The program becomes stuck in an infinite loop. However, consider this rule in logic: it is just an obvious, harmless rule; a tautology. So Prolog is already deviating from classical logic because of the way it sequentially evaluates rules. Anyways, to deal with this, we can add married(kimiko, kimiko) as a fact (remembering to put this above our symmetry rule):

married(jane, kimiko).
married(kimiko, kimiko).
married(X, Y) :- married(Y, X).

This'll work just fine. This is because it will run into the fact before attempting to use the rule. Of course, if we reshuffled the program:

married(jane, kimiko).
married(X, Y) :- married(Y, X).
married(kimiko, kimiko).

It's once again stuck in an infinite loop, for the same reason as before. We see that Prolog completely changes behavior just by a shuffle of our program. Logically, this should not be: we do not impose an ordering over our rules and facts, so why should Prolog?

I suppose it's because any programming language must be executed by a computer with some unambiguous order, so we are forced to impose some ordering. There are newer logic programming languages like Answer Set Programming (ASP) that use a different algorithm to ensure the end result is more robust, but these are logic systems first and programming language second. I guess Prolog is a programming language first and foremost, and this reflects in the design choices of the language, especially with it's top-down procedural order and sequential evaluation of rules.

Final Thoughts

I've shown you Prolog as an implementation of classical logic, and why it's procedural nature interferes with this goal, but in all honesty Prolog has many more conventional features that allow you to do more "programmy" things like arithmetic and list operations.

If you want to explore more about the programming side of Prolog, I would recommend this tutorial. It goes into much more depth on unification as well, which is very important when using prolog as the procedural language it is.