4.3 Day 2: Fifteen Minutes to Wapner

Grumpy Judge Wapner from The People’s Court is an obsession of the central character in Rain Man. Like most autistics, Raymond obsesses over all things familiar. He latched on to Judge Wapner and The People’s Court. As you’re plowing through this enigmatic language, you might be ready for things to start to click. Now, you might be one of the lucky readers who has everything click for them right away, but if you don’t, take heart. Today, there are definitely “fifteen minutes to Wapner.” Sit tight. We will need a few more tools in the toolbox. You’ll learn to use recursion, math, and lists. Let’s get going.

Recursion

Ruby and Io were imperative programming languages. You would spell out each step of an algorithm. Prolog is the first of the declarative languages we’ll look at. When you’re dealing with collections of things such as lists or trees, you’ll often use recursion rather than iteration. We’ll look at recursion and use it to solve some problems with basic inferences, and then we’ll apply the same technique to lists and math.

Take a look at the following database. It expresses the extensive family tree of the Waltons, characters in a 1963 movie and subsequent series. It expresses a father relationship and from that infers the ancestor relationship. Since an ancestor can mean a father, grandfather, or great grandfather, we will need to nest the rules or iterate. Since we’re dealing with a declarative language, we’re going to nest. One clause in the ancestor clause will use ancestor. In this case, ancestor(Z, Y) is a recursive subgoal. Here’s the knowledge base:

father is the core set of facts that enables our recursive subgoal. The rule ancestor/2 has two clauses. When you have multiple clauses that make up a rule, only one of them must be true for the rule to be true. Think of the commas between subgoals as and conditions and the periods between clauses as or conditions. The first clause says “X is the ancestor of Y if X is the father of Y.” That’s a straightforward relationship. We can try that rule like this:

Prolog reports true, john_boy_sr is an ancestor of john_boy_jr. This first clause depends on a fact.

The second clause is more complex: ancestor(X, Y) :- father(X, Z), ancestor(Z, Y). This clause says X is an ancestor of Y if we can prove that X is the father of Z and we can also prove that same Z is an ancestor of Y.

Whew. Let’s use the second clause:

Yes, zeb is an ancestor of john_boy_jr. As always, we can try variables in a query, like this:

And we see that zeb is an ancestor for john_boy_jr and john_boy_sr. The ancestor predicate also works in reverse:

That’s a beautiful thing, because we can use this rule in our knowledge base for two purposes, to find both ancestors and descendants.

A brief warning. When you use recursive subgoals, you need to be careful because each recursive subgoal will use stack space, and you can eventually run out. Declarative languages often solve this problem with a technique called tail recursion optimization. If you can position the recursive subgoal at the end of a recursive rule, Prolog can optimize the call to discard the call stack, keeping the memory use constant. Our call is tail recursive because the recursive subgoal, ancestor(Z, Y), is the last goal in the recursive rule. When your Prolog programs crash by running out of stack space, you’ll know it’s time to look for a way to optimize with tail recursion.

With that last bit of housekeeping out of the way, let’s start to look at lists and tuples.

Lists and Tuples

Lists and tuples are a big part of Prolog. You can specify a list as [1, 2, 3] and a tuple as (1, 2, 3). Lists are containers of variable length, and tuples are containers with a fixed length. Both lists and tuples get much more powerful when you think of them in terms of unification.

Unification, Part 2

Remember, when Prolog tries to unify variables, it tries to make both the left and right sides match. Two tuples can match if they have the same number of elements and each element unifies. Let’s take a look at a couple of examples:

Two tuples unify if all the elements unify. The first tuples were exact matches, the second tuples did not have the same number of elements, and the third set did not have the same elements in the same order. Let’s mix in some variables:

It doesn’t really matter which sides the variables are on. They unify if Prolog can make them the same. Now, for some lists. They can work like tuples:

The last two examples are interesting. [X, X, Z] and [2, 2, 3] unified because Prolog could make them the same with X = 2. [1, 2, 3] = [X, X, Z] did not unify because we used X for both the first and second positions, and those values were different. Lists have a capability that tuples don’t. You can deconstruct lists with [Head|Tail]. When you unify a list with this construct, Head will bind to the first element of the list, and Tail will bind to the rest, like this:

[Head|Tail] won’t unify with an empty list, but a one-element list is fine:

You can get complicated by using various combinations:

Prolog matched the a and unified the rest with Tail. Or we can split this tail into the head and tail:

Or grab the third element:

_ is a wildcard and unifies with anything. It basically means “I don’t care what’s in this position.” We told Prolog to skip the first two elements and split the rest into head and tail. The Head will grab the third element, and the trailing _ will grab the tail, ignoring the rest of the list.

That should be enough to get you started. Unification is a powerful tool, and using it in conjunction with lists and tuples is even more powerful.

Now, you should have a basic understanding of the core data structures in Prolog and how unification works. We’re now ready to combine these elements with rules and assertions to do some basic math with logic.

Lists and Math

In our next example, I thought I’d show you an example of using recursion and math to operate on lists. These are examples to do counting, sums, and averages. Five rules do all the hard work.

The simplest example is count. Use it like this:

The rules are trivially simple. The count of an empty list is 0. The count of a list is the count of the tail plus one. Let’s talk about how this works, step by step:

• We issue the query count(What, [1]), which can’t unify with the first rule, because the list is not empty. We move on to satisfying the goals for the second rule, count(Count, [Head|Tail]). We unify, binding What to Count, Head to 1, and Tail to [].

• After unification, the first goal is count(TailCount, []). We try to prove that subgoal. This time, we unify with the first rule. That binds TailCount to 0. The first rule is now satisfied, so we can move on to the second goal.

• Now, we evaluate Count is TailCount + 1. We can unify variables. TailCount is bound to 0, so we bind Count to 0 + 1, or 1.

And that’s it. We did not define a recursive process. We defined logical rules. The next example is adding up the elements of a list. Here’s the code for those rules again:

This code works precisely like the count rule. It also has two clauses, a base case and the recursive case. The usage is similar:

If you look at it imperatively, sum works exactly as you would expect in a recursive language. The sum of an empty list is zero; the sum of the rest is the Head plus the sum of the Tail.

But there’s another interpretation here. We haven’t really told Prolog how to compute sums. We’ve merely described sums as rules and goals. To satisfy some of the goals, the logic engine must satisfy some subgoals. The declarative interpretation is as follows: “The sum of an empty list is zero, and the sum of a list is Total if we can prove that the sum of the tail plus the head is Total.” We’re replacing recursion with the notion of proving goals and subgoals.

Similarly, the count of an empty list is zero; the count of a list is one for the Head plus the count of the Tail.

As with logic, these rules can build on each other. For example, you can use sum and count together to compute an average:

So, the average of List is Average if you can prove that

• the sum of that List is Sum,

• the count of that List is Count, and

• Average is Sum/Count.

And it works just as you’d expect:

Using Rules in Both Directions

At this point, you should have a fairly good understanding of how recursion works. I’m going to shift gears a little bit and talk about a tight little rule called append. The rule append(List1, List2, List3) is true if List3 is List1 + List2. It’s a powerful rule that you can use in a variety of ways.

That short little bit of code packs a punch. You can use it in many different ways. It’s a lie detector:

It’s a list builder:

It does list subtraction:

And it computes possible splits:

So, one rule gives you four. You may think that building such a rule will take a lot of code. Let’s find out exactly how much. Let’s rewrite the Prolog append, but we’ll call it concatenate. We’ll take it in several steps:

1. Write a rule called concatenate(List1, List2, List3) that can concatenate an empty list to List1.

2. Add a rule that concatenates one item from List1 onto List2.

3. Add a rule that concatenates two and three items from List1 onto List2.

4. See what we can generalize.

Let’s get started. Our first step is to concatenate an empty list to List1. That’s a fairly easy rule to write:

No problem. concatenate is true if the first parameter is a list and the next two parameters are the same.

It works:

Onto the next step. Let’s add a rule that concatenates the first element of List1 to the front of List2:

For concatenate(List1, List2, List3), we break List1 into the head and tail, with the tail being an empty list. We’ll break our third element into the head and tail, using List1’s head and List2 as the tail. Remember to compile your knowledge base. It works just fine:

Now, we can define another couple of rules to concatenate lists of lengths 2 and 3. They work in the same way:

So, what we have is a base case and a strategy where each subgoal shrinks the first list and grows the third. The second stays constant. We now have enough information to generalize a result. Here’s the concatenate using nested rules:

That terse little block of code has an incredibly simple explanation. The first clause says concatenating an empty list to List gives you that List. The second clause says concatenating List1 to List2 gives you List3 if the heads of List1 and List3 are the same, and you can prove that concatenating the tail of List1 with List2 gives you the tail of List3. The simplicity and elegance of this solution are a testament to the power of Prolog.

Let’s see what it would do with the query concatenate([1, 2], [3], What). We’ll walk through unification at each step. Keep in mind that we’re nesting the rules, so each time we try to prove a subgoal, we’ll have a different copy of the variables. I’ll mark the important ones with a letter so you can keep them straight. With each pass, I’ll show what happens when Prolog tries to prove the next subgoal.

• Start with this:

  concatenate([1, 2], [3], What)

• The first rule doesn’t apply, because [1, 2] is not an empty list. We unify to this:

  concatenate([1|[2]], [3], [1|Tail2-A]) :- concatenate([2], [3], [Tail2-A])

  Everything unifies but the second tail. We now move on to the goals. Let’s unify the right side.

• We try to apply the rule concatenate([2], [3], [Tail2-A]). That’s going to give us this:

  concatenate([2|[]], [3], [2|Tail2-B]) :- concatenate([], [3], Tail2-B)

  Notice that Tail2-B is the tail of Tail2-A. It’s not the same as the original Tail2. But now, we have to unify the right side again.

• concatenate([], [3], Tail2-C) :- concatenate([], [3], [3]) .

• So, we know Tail2-C is [3]. Now, we can work back up the chain. Let’s look at the third parameter, plugging in Tail2 at each step. Tail2-C is [3], which means [2|Tail2-2] is [2, 3], and finally [1|Tail2] is [1, 2, 3]. What is [1, 2, 3].

Prolog is doing a lot of work for you here. Go over this list until you understand it. Unifying nested subgoals is a core concept for the advanced problems in this book.

Now, you’ve taken a deep look at one of the richest functions in Prolog. Take a little time to explore these solutions, and make sure you understand them.

What We Learned in Day 2

In this section, we moved into the basic building blocks that Prolog uses to organize data: lists and tuples. We also nested rules, allowing us to express problems that you might handle with iteration in other languages. We took a deeper look at Prolog unification and how Prolog works to match up both sides of a :- or =. We saw that when we’re writing rules, we described logical rules instead of algorithms and let Prolog work its way through the solution.

We also used math. We learned to use basic arithmetic and nested subgoals to compute sums and averages.

Finally, we learned to use lists. We matched one or more variables within a list to variables, but more importantly, we matched the head of a list and the remaining elements with variables using the [Head|Tail] pattern. We used this technique to recursively iterate through lists. These building blocks will serve as the foundations of the complex problems we solve in day 3.

Day 2 Self-Study

Find:

• Some implementations of a Fibonacci series and factorials. How do they work?

• A real-world community using Prolog. What problems are they solving with it today?

If you’re looking for something more advanced to sink your teeth into, try these problems:

• An implementation of the Towers of Hanoi. How does it work?

• What are some of the problems of dealing with “not” expressions? Why do you have to be careful with negation in Prolog?

Do:

• Reverse the elements of a list.

• Find the smallest element of a list.

• Sort the elements of a list.