Hi,

I am trying to learn Prolog, and I came across an exercise in my book (Bratko, Artificial Intelligence) which was not adequately explained. The program is this:

The book wants to know what Prolog will answer to the query

Well, it answers C = one. However, I am not really understanding why, and I need to grasp this concept to move on. Would someone help me by explaining?

Thanks in advance.

Edit: I should add that I do think I see basically what is going on, but I would like a real explanation to make sure I understand exactly how it works. This is what I am thinking:

Clause 3 is matched.
X is instantiated to (s(s(s(1))).
Clause 3 is matched again.
X = 1.
N = 1.
C = one.

However, I am a bit uncomfortable with the first part, because I didn't know (s(s(s(1))) was something that could be used as a variable. Help appreciated.

Each time, Prolog tries to match whatever it can to the expression it tries to prove. So we have
to prove and the following four statements:
The thirst three do not match since s(s(s(s(s(s(1)))))) does not match any of 1, s(1) or s(s(1)). The fourth one, s(s(s(X))), however matches with X equal s(s(s(1))) (and furthermore N equal C). So using this transformation we end up with
Now, the same process repeats, and again only the fourth rule matches, this time with X equal 1. This reduces the problem to proving:
This matches the first rule perfectly, with C equal one, and so the original statement is true for C equal one.

1 members found this post helpful.

Okay, thanks. That's pretty much what I thought it was doing. But I still have the same confusion about why the s(s(s(X))) can be used as a variable. I thought it was a predicate definition. I guess I am not really sure what determines what Prolog can match and what it can't.

Thanks again.

Consider this: the notion of "a variable," in Prolog, is not at all the same as it is in a "traditional, algorithmic" programming language. Instead, it's the meaning taken straight from predicate calculus. The symbol "X" appears in two places in rule #4, once on the left-hand side of the rule and again on the right, thus associating the two symbolically. When Prolog succeeds in matching the rule, "X" is equated (for the purposes of matching ...) with "whatever matched."

1 members found this post helpful.

Two statements match in Prolog as long as there exists some mapping of variables in those statements which transforms them to the same statement. So for instance:

• 1 matches 1 since it's the same thing.
• X matches 1 since you can bind X to 1 to end up with the same thing.
• a(X, b(X)) matches a(1, b(1)) since again you can bind X to 1 to end up with the same thing.
• a(X, b(X)) matches a(c(1), b(c(1)) since you can bind to c(1) to end up with the same thing.
• s(s(s(X))) matches s(s(s( s(s(s(1))) ))) since you can bind s(s(s(1))) to X to end up with the same thing.

In more detail, let's look at a(X, b(X)) matching a(c(1), b(c(1))):

• Since the outer relation, a, matches both sides, it is stripped, and it's arguments are matched, i.e. (i) X is matched against c(1) and (ii) b(X) is matched against b(c(1)).
• Since X is a variable, matching (i) is trivial, and simply results in binding X to c(1).
• When matching (ii), the outer relation, b, matches both sides, so it's stripped, and it's arguments are matched, i.e. X is matched against c(1).
• To satisfy this, X would have to be bound to c(1), but X is already bound, so it must be confirmed that the binding can occur. To do that, the current binding must be matched against the new desired one, i.e. c(1) must be matched against c(1).
• This is of course trivially satisfied.

This way, you and up with a positive match and variable X being bound to c(1).

In your original example, we are getting:

• f(s(s(s(s(s(s(1)))))), C) is matched, using fourth rule, to f(s(s(s(X¹))), N¹). Let the index in superscript indicates that this is a local variable. This is satisfied with binding a local X¹ variable to s(s(s(1))) and local N¹ variable to C.
• Expanding the fourth rule, we now need to prove f(X¹, N¹) with the above bindings in effect.
• So we're matching f(X¹, N¹) against f(s(s(s(X²))), N²). This would be satisfied by binding X¹ to s(s(s(X²))) and N¹ to N². But since X¹ and N² already have bindings, it must be validated that the old and new binding match:
  • s(s(s(1))) (which is value bound to X¹) is matched against s(s(s(X²))), which is satisfied by binding X² to 1,
  • C (which is value bound to N¹) is matched against N², which is trivially satisfied by binding N² to C.
• Expanding the fourth rule, we now need to prove f(X², N²) with the above bindings in effect.
• So finally, we're using the first rule and match f(X², N²) against f(1, one). This would be satisfied by binding X² to 1 and N² to one, but again, X² and N² already have bindings, so those need to be validated:
  • 1 (which is value bound to X²) is matched against 1, which is trivially satisfied.
  • C (which is value bound to N²) is matched against one, which is satisfied by binding C to one.
• Since the first rule has no preconditions, it immediately evaluates to True value and we end up with an active binding of C to one.

NB: I haven't used Prolog in a long while, so my terminology is most likely incorrect. Also some of the details may be wrong, but I hope this gives some intuition about what is happening.

1 members found this post helpful.

Thank you, Mina86, that was a very good explanation, and a good reference for later as well. I believe I understand completely now. I wish the book had gone into such detail.

I think the main confusion I had was that due to the multiple parentheses in s(s(s(1))), I somehow had the intuition that was was occurring in Prolog with the matching of that term might be happening in more than one step. I didn't think you could match "through" parentheses, as it were. Now I see that you can. I guess that just comes from studying imperative languages and even Lisp.

Thanks again to both responders. Prolog is great.

Indeed, "the parentheses have nothing in-particular to do with it." All of the syntax has been parsed-away, and internal data structures have been built to represent their abstract meaning, before the Prolog engine gets underway in earnest.