Exploring Prolog – day 2

Recursion

The chapter starts off with a recursive ancestor function. If it wasn’t recursive, I’m sure it’d be a huge chain of function calls instead, and the length of the chain would depend on just how deep you’d like to search. I imagine it would be a pain to maintain that list.

First thing I notice here is how a rule is defined twice. How does Prolog differentiate between these two? The book mentions that 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.”

I think in this context, a clause simply means implementation of a rule. So there are two manners to execute a rule: a simple lookup of the father, or a recursive lookup, and once one is successfully executed, there’s no need to execute the other. The book also says: “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.”

“zeb” is an ancestor of “john_boy_jr”. If I call “ancestor(zeb, john_boy_jr).”, I get a true. I think what happens is, behind the scenes, it calls the first clause which returns a false, it then calls the second clause. “father(X, Z)” returns a list of descendants of zeb, in this case just john_boy_sr. This is then used in the recursive ancestor call like “ancestor(john_boy_sr, john_boy_jr).” and will start evaluating from the first clause again. This time that evaluates to true, therefore, zeb indeed is john_boy_jr’s ancestor. It feels like the first clause in this case is the base case of the recursive function.

At first, I had difficulties understanding this. But writing it out step by step like this makes more sense to me. I now know that a rule can have multiple clauses and how recursion works.

Finally, the book also mentions we can use variables in a query, such as ” ancestor(zeb, Who).”. It immediately dawned on me that the previous day I mistook “What” for a keyword. Rather, it’s just a variable named “What” for context’s sake. In this context, the author decided to use “Who” instead because we’re talking about people. Unsurprisingly, I got the descendants of zeb, then the descendants of zeb’s descendants, and so on.

Lists and Tuples

There’s not much to be said here. From what I gather by reading this book, a tuple is a list but has a fixed size and is written with (), e.g. “(1, 2, 3)”. Meanwhile lists have a pipe operator which can separate it into a “head” and “tail”:

I imagine that you can “iterate” through a list if you recursively keep splitting a list into a “head” and “tail” until you have nothing left. In fact, I did exactly that.

Which outputs:

Self study

Like day 1, I will put the challenges and solutions in a file.
(To be continued)

Leave a Reply

Your email address will not be published. Required fields are marked *