How Logic Programming Works

Ovid on 2005-07-29T02:31:50

I was looking at Luke Palmer's Logic module on the CPAN and it got me to thinking a bit about logic programming in general, as opposed to the specific implementation of Prolog I've been focusing on. To implement logic programming, you basically have to implement two things, backtracking and unification.

You already understand backtracking from regular expressions. If you fail to find a match (in our case, if we fail to unify two data structures), back up to the last point in the string (stack) where we can make a different decision and try again. It's pretty straightforward.

Unification is also fairly simple. You know it from makefiles or SQL, but we'll look at logic programming in particular. Imagine that you have two five element lists:

( 1, 2, undef, undef,     5 )
( 1, 2,     3,     4, undef )

Imagine that undef means "unknown". We can unify those two lists because every element that is known corresponds in the two lists. This leaves us with a list of the integers one through five.

( 1, 2, 3, 4, 5 )

However, what happens if the last element of the first list is unknown?

( 1, 2, undef, undef, undef )
( 1, 2,     3,     4, undef )

We can still unify the two lists. In this case, we get the same five element list, but the last item is unknown.

( 1, 2, 3, 4, unknown )

Logic programming works by pushing these lists onto a stack and walking through the stack and seeing if you can unify everything (sort of). But how to unify from one item to the next? We assign names to the unknown variables and if we can unify them. When we get to the next item in the stack, we check to see if any named variables have been unified. If so, we unify the individual variables prior to trying to unify items with their counterparts in our lists.

Thats a bad explanation, so here's how it works. Imagine the following "knowledge base" of lists:

(parent, sally, tom)
(parent, bill, tom)
(parent, tom, sue)
(parent, alice, sue)
(parent, sarah, tim)

(male, bill)
(male, tom)
(male, tim)

Now let's assume we have a rule which states that someone is a father if they are a parent and they are male. Maybe we'd define it something like this (imagine that the angle brackets mean "read this and say 'if'"):

(
  ,
  (parent, $person, $anyone),
  (male, $person)
)

Taking the first term in the rule, the logic engine might try to unify this with the first fact in the knowledge base, "(parent, sally, tom)". $person unifies with "sally" and $anyone unifies with "tom". We then push this information onto a stack. If subsequent facts fail to unify and we come back here, because there are still more facts we can try, we set a "choice point" in the stack telling us which fact we last tried. If we come back and see a chioce point, we move on to the next fact and try again.

Moving on to the next term in the rule, "(male, $person)", we know that "sally" is unified to $person, so we now try to unify "(male, sally)" with all of the corresponding rules in the knowledge base. Since we can't, the logic engine backs up to the last item where we could make a new choice and sees "(parent, bill, tom)". $person gets unified with "bill" and $anyone gets unified with "tom". Then in moving to the next rule we see that we unify with "(male, bill)". Now, we check the first item in the rule and see that it's "(father, $person)" and the logic engine reports that "bill" is a father.

Note that we can then force the engine to backtrack and by continuously following this procedure, we can determine who all of the fathers are. ($anyone is ignored and in Prolog, it's marked with an underscore: "_". This means that it's an anonymous variable whose value we really don't care about.)

And that's how logic programming works. Simple, eh?