wiki.visual-prolog.com - User contributions [en]

Fundamental Prolog Part 2

2007-12-20T13:11:37Z

DmitriRybakov: /* Recursion Using Functors */

{{FundamentalPrologNavbar}}

In this tutorial you will learn about some more fundamental ideas of Prolog programming; continuing from where we left off in the Part 1 of this tutorial (Fundamental Prolog). In this tutorial, we are going to concentrate on how data is ''modeled'' in Prolog, before we can perform actions on them. Hence, there are not much examples concerning code execution here. We are assuming that you are already familiar with the issues concerning '''execution strategy''' and how '''side effects''' convert the logic of a Prolog program into the desired '''results'''.

As in the [[Fundamental Prolog Part 1|Part 1]] of this tutorial, we shall continue to use the '''PIE''' environment to develop and learn Prolog. We shall get into the '''Visual Prolog IDE''' only in the latter parts of this series.

==Functors==

In Part 1 of the tutorial, all the people were represented as "Bill", "John" and "Pam" etc. Now "Bill", "John" and "Pam" are just the names of the individuals. The values of the names are simple data types or '''simple domains'''. In the case of the names of the people, the '''simple domain''' was a '''string'''. Other '''simple domains''' would be '''numbers''' (e.g.: '''123''' or '''3.14'''), '''symbols''' (e.g.: '''xyz''' or '''chil_10'''), and '''characters''' (e.g.: ''''5'''' or ''''c'''').

However, individuals are represented by more characteristics than just their names. What if we need to represent all those characteristics together, instead of representing just their names? That means, we need some mechanism to represent '''compound domains'''; a collection of simpler '''domains''' held together.

In the first part of this tutorial, we had tried putting together several characteristics of individuals together, (like the '''name''' and the '''gender'''), by inserting facts into the PIE system that concentrated on '''entities''' instead of relationships. Thus we had given the following facts to the system:

<vip>person("Bill", "male").
person("John", "male").
person("Pam", "female").</vip>

However, there is another elegant method to sharpen our focus on the '''entities''' being represented.

We can package both the Name and the Gender into a package using a formalization known as a '''compound domain'''. The entire package can then be represented using a logical variable inside any Prolog clause, just like any other variables. For example, the above facts can be generically represented in a '''compound domain''' thus:

<vip>person(Name, Gender)</vip>

Note that the above statement is neither a fact nor a predicate. Logically, it states that there is some '''compound domain''' called '''person''' in the system, each of which has two characteristics, represented by the logical variables Name and Gender. The word ''person'' is known as a '''functor''', and the variables are its '''arguments'''. We shall now package our facts using these '''functors'''.

As a '''compound domain''' always has a '''functor''', we shall henceforth use the term '''functor''' in this tutorial, to represent the respective '''compound domain.'''

For now, let us modify the first example of the previous tutorial, so that we use our newly defined '''functor''' ''person'''''.'''

Please note that in the '''PIE''' (Prolog Inference Engine) that we are using, we can directly use a '''compound domain''' without any prior intimation to the Prolog engine (for example. we need NOT define a predicate or a fact called ''person'' for our code to work).

[[Image:Fundamental_Prolog_2_fig1.jpg]]

If you study the two facts for the father relationship, you would notice that the persons described are richer than what was done before (The earlier code is commented out in-between the tokens '''/*''' and '''*/''' .). This time, each person is described with both the person's name '''and''' his/her gender, using the person '''functor''', whereas in the earlier tutorial (Fundamental Prolog (Part1)) we were only using the person's name.

After you have written the new code, ensure that the PIE engine is reset. Use '''Engine -> Reset.''' Then, you re-consult the code using '''Engine -> Reconsult.'''

As before, on a blank line in the '''Dialog''' window type a goal (without the "?" sign- in front).

For example:

[[Image:Fundamental_Prolog_2_fig2.jpg]]

When the caret is placed at the end of the line, press the '''Enter''' key on your keyboard. '''PIE''' will now consider the text from the beginning of the line to the caret as a goal to execute. You should see the following result:

[[Image:Fundamental_Prolog_2_fig3.jpg]]

Now, you will notice that the results that are yielded are richer than what you got previously (See Tutorial 04: Fundamental Prolog (Part 1)).

==Refining Further==

If you take a look at the grandfather predicate, you would notice that it has a subtle bug: A person would have two grandfathers: one from the mother's side and one from the father's side, but the grandfather predicate as defined earlier would only yield the grandfather on the father's side.

Hence the grandfather predicate should be re-written as follows:

<vip>grandFather(Person, TheGrandFather):-
parent(Person, ParentOfPerson),
father(ParentOfPerson, TheGrandFather).</vip>

In this predicate the logic states that a father of ''any'' parent could be the grandfather of the person in consideration.

For that predicate to work, we need to define a predicate called father using the person '''functor.''' This predicate would troll through a database of facts explaining the "''parents''" defined in the system. This is a more elegant method for finding out the fathers, instead of presenting them as facts (as shown previously) because later on we can extend this concept to find out "''mothers''" in a similar fashion.

This can be done in either of the following ways:

<vip>/*1st version */
father(P, F) :-
parent(P, F),
F = person(_, "male"). %Line 2</vip>

or

<vip>/* 2nd version */
father(P, person(Name, "male")) :-
parent(P, person(Name, "male")).</vip>

The logic behind both the versions is the same, but the manner in which the logic is indicated to the Prolog engine is different. In the first version, the code in Prolog systematically examines each parent fact asserted into the code, and sees if the first logical variable (P) matches that passed down from the predicate head. If the variable does match, it checks if the second argument consists of a person '''functor''', whose second argument is the string literal "male".

This example shows one important feature of '''functors''': The arguments of a '''functor''' can be taken apart and examined using regular Prolog variables and bound values (like the string literal in this example) If you see Line 2 (Look at the side of the comment ''%Line 2'' in the code for the first version), you would notice that we have used an anonymous variable (the underscore) for the first argument of the person '''functor''' as we are (in that predicate) not interested in the name of the father.

The second version also does the same thing as the first one. But this time, as the set of parent facts is examined; on arriving at the correct value for P, the code halts and returns the correct '''functor''' data back to the predicate head, ''provided the second argument of that '''functor''' is the string literal "male"''. If you note, the functor was NOT bound to any intermediate Prolog variable, as it was done in the first version.

The second version is much terser than the first one, and sometimes this method of writing the code can be less legible to beginners.

Let us now use this code in a complete example, where we will give a suitable set of person'''' facts:

[[Image:Fundamental_Prolog_2_fig3b.jpg]]

Now, after you re-consult the above code into '''PIE''', and give the following goal:

<vip>grandFather(person'("Pam", "female"), W)</vip>

the results would be as follows:

[[Image:Fundamental_Prolog_2_fig3c.jpg]]

==Functors and Predicates==

Technically, a '''functor''' represents a logical function that binds several domains together. In simpler words, a '''functor''' is a mechanism that teaches the Prolog Engine how to put together data from its component parts. It effectively puts parts of the data into a common box. You can also retrieve the parts subsequently, whenever required (like seen the previous examples). It may look like a Prolog fact or a predicate call, but it is not. It's just a piece of data, which you can handle in much the same way as a string or a number.

Please note that a '''functor''' has nothing to do with a function in other programming languages. It does not stand for some computation to be performed. It simply identifies the '''compound domain''' and holds its arguments together.

When you study the above example, you would notice that nothing special need to be done when logical variables are used to stand in for data represented by '''functors'''. The logical variable that is used to stand in for such data, is written just like any other logical variable: A word starting with a capital letter. Thus, if we take a look at the ''grandFather'' predicate in the example in this tutorial; you would notice that nothing has changed when you compare it with the same predicate that was defined in the earlier tutorial (Fundamental Prolog (part 1)). After all, the logic of that predicate has not changed. So, you would not find any changes to the variables used inside that predicate.

The biggest advantage of using '''a functor''' is that you are free to change the internal arguments of the '''functor''' without changing much of the predicates that uses such a '''functor''' as you keep revising the code.

That means, if you decide (in a later version of the code you are writing) to have one more argument for the ''person'', you still need not change anything in the ''grandfather'' predicate.

==Functors as Arguments==

In the previous section, the person '''functor''' was having two arguments: the Name and the Gender. Both happened to be simple domains i.e. '''constants''' such as "Bill" and, "male". However, there is nothing that prevents us from putting a '''functor''' itself as an '''argument''' of another '''functor'''.

Suppose, you wanted to define a '''functor''' for a ''couple'' (i.e. a husband and a wife). This is an example of how you would use such a '''functor''':

<vip>myPredicate(ACouple):-
ACouple = couple(person(Husband, "male"), person(Wife, "female")),
...</vip>

In this example, you would notice that the '''functor''' is defined by two '''functors''', each of which is a mixture of '''variables''' and '''constants'''. This can be done to reflect the logic of the data being represented. The logic used here is that a husband is always a "male" and wife is always a "female"; and a couple consists of a husband and a wife. All of which is consistent with the most common interpretation of what one means by a ''couple''.

Though in '''PIE''' you cannot predefine the kind of grammar '''functors''' can actually have; in '''Visual Prolog''' you can make such definitions. The advantage of defining a '''functor''' in such a manner is that later, when you create actual data using this '''functor''', the Prolog engine will always check if the data being created was consistent with the grammar that data was supposed to adhere to.

This comes to another characteristic of '''functors''': the ''couple'' '''functor''' has been defined with two arguments and the '''position''' of these arguments reflects their logical association. It was explained in the first part of this tutorial, that the positions of the arguments of predicates have to be formalized by the programmer, who designs the code. Once formalized; the same positional formalization should be consistently used.

The same strategy applies to the creation of '''functors''' too: In the case of the ''couple'' '''functor''', it so happened that we decided to represent the husband as the first argument, and the wife as the second one. Once this is done, then whenever data is created using such a '''functor''', then we need to ensure that the husband is always at the first position, and the wife in the second (in spite of what the women's lib people may say!)

Now, when we look back on the ''couple '' '''functor''', someone can correctly argue that if were so sure that the first argument is always a husband (who is always a male), and the second one is always a wife (who is always a female) then what is the need for making the arguments of the ''couple '' '''functor''' also as '''functors'''? Hence, an example with a more simplified ''couple '' '''functor''' would be as follows:

<vip>myPredicate(ACouple):-
ACouple=couple(Husband, Wife),
...</vip>

Hence; let us revert back to using '''functors''' for the husband and wife... but this time we will use them, because we are not sure which position is for the husband and which is for the wife.

<vip>myPredicate(Couple):-
Couple = couple(person(PersonsName, PersonsGender), person(SpouseName, SpouseGender)),
...</vip>

In the above '''functor''', both the following examples make logical sense:

<vip>myPredicate(C1):-
C1=couple(person("Bill", "male"), person("Pam", "female")),
...

/* or */
myPredicate(C2):-
C2=couple(person("Pam", "female"), person("Bill", "male")),
...</vip>

It should be pointed out that in the PIE (and many other Prolog Engines), there is no way to indicate whether a functor will receive simple domain or compound domain arguments, by looking at the variables that define the functor. This stems from the fact that in '''PIE''', '''compound domains''' are directly used, without being declared anywhere, other than in the mind of the programmer.

For example, if you wanted to use a '''compound domain''' as:

<vip>person(Name, Gender)</vip>

then '''PIE''' would as easily accept a logical variable such as:

<vip>regardingAPerson(Somebody):-
Somebody =
person("Pam",
person("Pam",
person("Pam",
person("Pam", "female")
)
)
),
...</vip>

which actually does not make any logical sense, in the current context. Luckily, '''Visual Prolog''', does a much better job of differentiating between '''simple domains''' and '''compound domains''', so, when you get to the latter tutorials, you would not have any such problems.

==Recursion Using Functors==

When data is described using '''functors''', it can be treated like any other piece of data. For example, you can write a predicate that can be made to recursively search through data which used '''compound domains''' using '''functors'''.

Let us get back briefly to the ancestor predicate, which we had used in the first part of the tutorial.

In order to determine if somebody is an ancestor of someone else, we used a recursive definition for the predicate, i.e. a definition that is defined in terms of itself. like this:

<vip>ancestor(Person, Ancestor) :- parent(Person, Ancestor).
ancestor(Person, Ancestor) :- parent(Person, P1), ancestor(P1, Ancestor).</vip>

This declaration states that a parent is an ancestor, and that an ancestor to a parent is also an ancestor. If you examine the variables in the above definition, it can very well stand for either '''simple domains''' or '''compound domains.'''

Let us define the data thus:

<vip>parent(person("Bill", "male"), person("John", "male")).
parent(person("pam", "female"), person("Bill", "male")).</vip>

If we now ask '''PIE''' to solve the following goal,

<vip>P=person("pam", "female"), ancestor(P, Who)</vip>

...this is what we will get:

[[Image:Fundamental_Prolog_2_fig4.jpg]]

The '''PIE''' engine has recursively examined the parent facts to reveal the two possible solutions to the answer. By the way, in the above query, you would also notice that we have bound a variable P to the person '''compound domain''' when specifying the goal to '''PIE'''. This was done to make the code more readable but it also demonstrates the fact that we can bind a piece of data specified as a '''compound domain''' into any Prolog variable.

==Strategies for Using Functors==

Software will be only as good as allowed by the modeled data. By the term ''modeling'', we mean the establishment of a relationship between the subset of the outside real-world that is being tackled with the internal data structures of the software. If the modeling of data is poor, then it is likely that the software will also be poor; or at best, inefficient. This is true of any software written in any programming language. That was the reason in the latter part of the earlier tutorial (Fundamental Prolog (part 1)), we had tried to focus on the '''entities''' and tried to correct the situation by inserting richer facts. Similarly, we introduced the concept of '''functors''' in this tutorial to get even more clarity on the data regarding '''entities''' that are being modeled.

The advantage of Prolog is that it allows easy '''description''' of the real-world data in a form that can be internally utilized by the code in an efficient manner. Simultaneously, it also makes the code very readable by fellow programmers who are working together on a project.

'''Functors''' can be used to create any type of '''compound domain''' to help in this modeling process. You would have to carefully examine the various parts of real-world data that you plan to process and convert them using '''functors''' (and other data types that you would encounter in future tutorials) keeping in mind their usage in all critical parts of the software. Some data structures that were useful in one area of the software may prove to be a hindrance in other areas.

You should take a holistic approach while zeroing in on the '''functors''' (and other data structures) you plan to use in your software. Pause and look around at all the corners of your software. Only then should you code the necessary '''functors'''.

Just thinking carefully about the data structures is not the only thing that is required. You would also need to (often simultaneously) write/modify the various goals and sub-goals (i.e. predicates) and then use the data developed thus far in those predicates. The '''side effects''' of attaining those goals and sub-goals would make your software work and you can get valuable feedback with which you can further refine your data structures.

In this tutorial, we have not fleshed out a software design holistically. We have only nibbled at bits and pieces of data which establishes the '''feel''' for some kind of real-world data concerning relationship between people (''parents'', ''grandparents'', ''families'', ''ancestors'' etc.) In forthcoming tutorials, we will use this experience to establish a '''red thread''' that connects all these tutorials together; eventually ending up with a useful software that requires such data structures.

==Conclusion==

In this lesson we learnt that data can comprise of '''simple domains''', or they can be '''compound domains''' represented using '''functors'''. We found that the arguments of '''functors''' must be positionally consistent with the logic they were meant to represent. We understood that a '''functor''' need not have just simple domains as arguments, but it can also have other '''functors''' as arguments. We then learnt that data represented as '''functors''' can be used like any regular Prolog variable, and we can even perform all operations; including recursion, on such data.

We also learnt that we must spend time modeling our subset of the real world for which we are developing the software, and get a feel for the data. We should simultaneously experiment with the predicates that you may wish to use with the data that is being modeled, so that they can be refined further.

==References==

[[Category:Tutorials]]

Fundamental Prolog Part 1

2007-12-20T13:10:43Z

DmitriRybakov: /* Program Control */

{{FundamentalPrologNavbar}}

In this '''Prolog tutorial''' you will learn about the very fundamental ideas of Prolog language programming.

Visual Prolog is object oriented, strictly typed and mode checked.
You will of course have to master all this to write Visual Prolog programs.
But in this tutorial we will focus on the ''core'' of the code, i.e. the Prolog code when disregarding classes, types and modes.

For this purpose we will use the PIE example that is included in the Visual Prolog distribution PIE might be also [http://www.visual-prolog.com/vip/example/pie/pie.htm downloaded] from the WEB as an executable.
PIE is a "classical" Prolog interpreter, by using this you can learn and experiment with Prolog without at all being concerned with classes, types, etc.

== Horn Clause Logic ==

Visual Prolog and other Prolog language dialects are based on Horn Clause logic.
Horn Clause logic is a formal system for reasoning about things and the way they relate to each other.

In natural language I can express a statement like:

<pre>John is the father of Bill.</pre>

Here I have two "things": John and Bill, and a "relation" between these, namely that one is the father of the other.
In Horn Clause Logic I can formalize this statement in the following way:

<vip>father("Bill", "John").</vip>

father is a predicate/relation taking two arguments, where the second is the father of the first.

'''Notice''' that '''''I '''''have chosen that the '''second''' person should be the father of the '''first'''.
I might as well have chosen it the other way around: The order of the arguments is the choice of the "designer" of the formalization.
However, once you have chosen, you must be consistent.
So in '''my''' formalization the father must '''always''' be the second person.

I have chosen to represent the persons by their names (which are string literals).
In a more complex world this would not be sufficient because many people have same name.
But for now we will be content with this simple formalization.

With formalizations like the one above I can state any kind of family relation between any persons.
But for this to become really interesting I will also have to formalize '''''rules''''' like this:

<vip>X is the grandfather of Z, if X is the father of Y and Y is the father of Z</vip>

where X, Y and Z are persons.
In Horn Clause Logic I can formalize this rule like this:

<vip>grandFather(Person, GrandFather) :-
father(Person, Father), father(Father, GrandFather).</vip>

I have chosen to use '''''variable''''' names that help understanding better than X, Y and Z.
I have also introduced a predicate for the grandfather relation.
Again I have chosen that the grandfather should be the second argument.
It is wise to be consistent like that, i.e. that the arguments of the different predicates follow some common principle.
When reading rules you should interpret :- as '''''if''''' and the comma that separates the relations as '''''and'''''.

Statements like "John is the father of Bill" are called '''''facts''''', while statements like "X is the grandfather of Z, if X is the father of Y and Y is the father of Z" are called '''''rules'''''.

With facts and rules we are ready to formulate theories.
A '''''theory''''' is a collection of facts and rules.
Let me state a little theory:

<vip>father("Bill", "John").
father("Pam", "Bill").

grandFather(Person, GrandFather) :-
father(Person, Father),
father(Father, GrandFather).</vip>

The purpose of the theory is to answer questions like these:

<vip>Is John the father of Sue?
Who is the father of Pam?
Is John the grandfather of Pam?
...</vip>

Such questions are called goals.
And they can be formalized like this (respectively):

<vip>?- father("Sue", "John").
?- father("Pam", X).
?- grandFather("Pam", "John").</vip>

Such questions are called '''''goal clauses''''' or simply '''''goals'''''.
Together ''facts'', ''rules'' and ''goals'' are called Horn clauses, hence the name Horn Clause Logic.

Some goals like the first and last are answered with a simple ''yes'' or ''no''.
For other goals like the second we seek a '''''solution''''', like X = "Bill".

Some goals may even have many solutions.
For example:

<vip>?- father(X, Y).</vip>

has two solutions:

<vip>X = "Bill", Y = "John".
X = "Pam", Y = "Bill".</vip>

A Prolog program is a theory and a goal.
When the program starts it tries to find a solution to the goal in the theory.

== PIE: Prolog Inference Engine ==

Now we will try the little example above in PIE, the Prolog Inference Engine that comes with Visual Prolog.
You can also [http://www.visual-prolog.com/vip/example/pie/pie.htm download] it from the web.

Before we start you should install and build the PIE example.

*Select "Install Examples" in the Windows start menu ('''Start -> Visual Prolog -> Install Examples''').
*Open the PIE project in the VDE and '''run''' the program, as it is described in <a href="../tut01/default.htm">Tutorial 01: Environment Overview</a>.

When the program starts it will look like this:

[[Image:Fundamental_Prolog_1_PIE.png|Prolog Inference Engine]]

Select '''File -> New''' and enter the father and grandFather clauses above:

[[Image:Fundamental_Prolog_1_GrandFather.png|Grand Father example]]

While the editor window is active choose '''Engine -> Reconsult'''.
This will load the file into the engine.
In the '''''Dialog''''' window you should receive a message like this:

<pre>Reconsulted from: ....\pie\Exe\FILE4.PRO</pre>

Reconsult loads whatever is in the editor, '''''without''''' saving the contents to the file, if you want to save the contents use '''File -> Save'''.

'''File -> Consult''' will load the disc contents of the file regardless of whether the file is opened for editing or not.

Once you have "consulted" the theory, you can use it to answer goals.

On a blank line in the '''''Dialog''''' window type a goal (without the '''?-''' in front).

For example:

[[Image:Fundamental_Prolog_1_goal1.png|Typing a goal]]

When the caret is placed at the end of the line, press the '''Enter''' key on your keyboard.
PIE will now consider the text from the beginning of the line to the caret as a goal to execute.
You should see a result like this:

[[Image:Fundamental_Prolog_1_goal2.png|Goal result]]

== Extending the family theory ==

It is straight forward to extend the family theory above with predicates like mother and grandMother.
You should try that yourself.
You should also add more persons.
I suggest that you use persons from your own family, because that makes it lot easier to validate, whether some person is indeed the grandMother of some other person, etc.

Given mother and father we can also define a parent predicate.
You are a parent if you are a mother; you are also a parent if you are a father.
Therefore we can define parent using two clauses like this:

<vip>parent(Person, Parent) :- mother(Person, Parent).
parent(Person, Parent) :- father(Person, Parent).</vip>

The first rule reads (recall that the second argument corresponds to the predicate name):

Parent is the parent of Person, if Parent is the mother of Person

You can also define the parent relation using semicolon ";" which means or, like this:

<vip>parent(Person, Parent) :-
mother(Person, Parent);
father(Person, Parent).</vip>

This rule reads:

Parent is the parent of Person, if Parent is the mother of Person '''''or''''' Parent is the father of Person

I will however advise you to use semicolon as little as possible (or actually not at all).
There are several reasons for this:

*The typographical difference "," and ";" is very small, but the semantic difference is rather big. ";" is often a source of confusion, since it is easily misinterpreted as ",", especially when it is on the end of a long line.
*Visual Prolog only allows to use semicolon on the outermost level (PIE will allow arbitrarily deep nesting).

Try creating a sibling predicate! Did that give problems?

You might find that siblings are found '''twice'''.
At least if you say: Two persons are siblings if they have same mother, two persons are also siblings if they have same father.
I.e. if you have rules like this:

<vip>sibling(Person, Sibling) :- mother(Person, Mother), mother(Sibling, Mother).
sibling(Person, Sibling) :- father(Person, Father), father(Sibling, Father).</vip>

The first rule reads:

Sibling is the sibling of Person, if Mother is the mother of Person '''''and''''' Mother is the mother of Sibling

The reason that you receive siblings twice is that most siblings both have same father and mother, and therefore they fulfill both requirements above.
And therefore they are found twice.

We shall not deal with this problem now; currently we will just accept that some rules give too many results.

A fullBlodedSibling predicate does not have the same problem, because it will require that both the father and the mother are the same:

<vip>fullBlodedSibling(Person, Sibling) :-
mother(Person, Mother),
mother(Sibling, Mother),
father(Person, Father),
father(Sibling, Father).</vip>

== Prolog is a Programming Language ==

From the description so far you might think that Prolog is an expert system, rather than a programming language.
And indeed Prolog can be used as an expert system, but it is designed to be a programming language.

We miss two important ingredients to turn Horn Clause logic into a programming language:

*Rigid search order/program control
*Side effects

== Program Control ==

When you try to find a solution to a goal like:

<vip>?- father(X, Y).</vip>

You can do it in many ways.
For example, you might just consider at the second fact in the theory and then you have a solution.

But Prolog does not use a "random" search strategy, instead it always use the same strategy.
The system maintains a '''''current goal''''', which is always solved from '''left to right'''.

I.e. if the current goal is:

<vip>?- grandFather(X, Y), mother(Y, Z).</vip>

Then the system will always try to solve the sub-goal grandFather(X, Y) before it solves mother(Y, Z), if the first (i.e. left-most) sub-goal cannot be solved then there is no solution to the overall problem and then the second sub-goal is not tried at all.

When solving a particular sub-goal, the facts and rules are always tried from '''top to bottom'''.

When a sub-goal is solved by using a rule, the right hand side replaces the sub-goal in the current goal.

I.e. if the current goal is:

<vip>?- grandFather(X, Y), mother(Y, Z).</vip>

And we are using the rule

<vip>grandFather(Person, GrandFather) :- father(Person, Father), father(Father, GrandFather).</vip>

to solve the first sub-goal, then the resulting current goal will be:

<vip>?- father(X, Father), father(Father, Y), mother(Y, Z).</vip>

Notice that some variables in the rule have been replaced by variables from the sub-goal.
I will explain this in details later.

Given this evaluation strategy you can interpret clauses much more '''''procedural'''''. Consider this rule:

<vip>grandFather(Person, GrandFather) :- father(Person, Father), father(Father, GrandFather).</vip>

Given the strict evaluation we can read this rule like this:

To solve grandFather(Person, GrandFather) '''first''' solve father(Person, Father) '''and then '''solve father(Father, GrandFather).

Or even like this:

When grandFather(Person, GrandFather) is '''''called''''', first '''''call''''' father(Person, Father) and then '''''call''''' father(Father, GrandFather).

With this '''''procedural '''''reading you can see that predicates correspond to procedures/subroutines in other languages.
The main difference is that a Prolog predicate can return several solutions to a single invocation or even '''''fail'''''.
This will be discussed in details in the next sections.

== Failing ==

A predicate invocation might not have any solution in the theory.
For example calling parent("Hans", X) has no solution as there are no parent facts or rules that applies to "Hans".
We say that the predicate call '''''fails'''''.
If the goal fails then there is simply no solution to the goal in the theory.
The next section will explain how failing is treated in the general case, i.e. when it is not the goal that fails.

== Backtracking ==

In the procedural interpretation of a Prolog program "or" is treated in a rather special way.
Consider the clause

<vip>parent(Person, Parent) :-
mother(Person, Parent);
father(Person, Parent).</vip>

In the logical reading we interpreted this clause as:

Parent
is the parent of Person '''if'''
Parent is the mother of
Person '''or'''
Parent is the father of Person.

The "or" introduces two possible solutions to an invocation of the parent predicate.
Prolog handles such multiple choices by first trying one choice and later (if necessary) '''''backtracking''''' to the next alternative choice, etc.

During the execution of a program a lot of alternative choices (known as '''''backtrack points''''') might exist from earlier predicate calls.
If some predicate call fails, then we will backtrack to the last backtrack point we met and try the alternative solution instead.
If no further backtrack points exists then the overall goal has failed, meaning that there was no solution to it.

With this in mind we can interpret the clause above like this:

When parent(Person, Parent) is called first record a backtrack point to the second alternative solution (i.e. to the call to father(Person, Parent)) and then call mother(Person, Parent)

A predicate that has several classes behave in a similar fashion.
Consider the clauses:

<vip>father("Bill", "John").
father("Pam", "Bill").</vip>

When father is invoked we first record a backtrack point to the second clause, and then try the first clause.

If there are three or more choices we still only create one backtrack point, but that backtrack point will start by creating another backtrack point.
Consider the clauses:

<vip>father("Bill", "John").
father("Pam", "Bill").
father("Jack", "Bill").</vip>

When father is invoked, we first record a backtrack point.
And then we try the first clause.
The backtrack point we create points to some code, which will itself create a backtrack point (namely to the third clause) and then try the second clause.
Thus all choice points have only two choices, but one choice might itself involve a choice.

'''Example''' To illustrate how programs are executed I will go through an example in details.
Consider these clauses:

<vip>mother("Bill", "Lisa").

father("Bill", "John").
father("Pam", "Bill").
father("Jack", "Bill").

parent(Person, Parent) :-
mother(Person, Parent);
father(Person, Parent).</vip>

And then consider this goal:

<vip>?- father(AA, BB), parent(BB, CC).</vip>

This goal states that we want to find three persons AA, BB and CC, such that BB is the father of AA and CC is a parent of BB.

As mentioned we always solve the goals from left to right, so first we call the father predicate.
When executing the father predicate we first create a backtrack point to the second clause, and then use the first clause.

Using the first clause we find that AA is "Bill" and BB is "John".
So we now effectively have the goal:

<vip>?- parent("John", CC).</vip>

So we call parent, which gives the following goal:

<vip>?- mother("John", CC); father("John", CC).</vip>

You will notice that the variables in the clause have been replaced with the actual parameters of the call (exactly like when you call subroutines in other languages).

The current goal is an "or" goal, so we create a backtrack point to the second alternative and pursuit the first.
We now have two active backtrack points, one to the second alternative in the parent clause, and one to the second clause in the father predicate.

After the creation of this backtrack point we are left with the following goal:

<vip>?- mother("John", CC).</vip>

So we call the mother predicate.
The mother predicate fails when the first argument is "John" (because it has no clauses that match this value in the first argument).

In case of failure we backtrack to the last backtrack point we created.
So we will now pursuit the goal:

<vip>?- father("John", CC).</vip>

When calling father this time, we will again first create a backtrack point to the second father clause.

Recall that we also still have a backtrack point to the second clause of the father predicate, which corresponds to the first call in the original goal.

We now try to use the first father clause on the goal, but that fails, because the first arguments do not match (i.e. "John" does not match "Bill").

Therefore we backtrack to the second clause, but before we use this clause we create a backtrack point to the third clause.

The second clause also fails, since "John" does not match "Pam", so we backtrack to the third clause.
This also fails, since "John" does not match "Jack".

Now we must backtrack all the way back to the first father call in the original goal; here we created a backtrack point to the second father clause.

Using the second clause we find that AA is "Pam" and BB is "Bill".
So we now effectively have the goal:

<vip>?- parent("Bill", CC).</vip>

When calling parent we now get:

<vip>?- mother("Bill", CC); father("Bill", CC).</vip>

Again we create a backtrack point to the second alternative and pursuit the first:

<vip>?- mother("Bill", CC).</vip>

This goal succeeds with CC being "Lisa".
So now we have found a solution to the goal:

<vip>AA = "Pam", BB = "Bill", CC = "Lisa".</vip>

When trying to find additional solutions we backtrack to the last backtrack point, which was the second alternative in the parent predicate:

<vip>?- father("Bill", CC).</vip>

This goal will also succeed with CC being "John".
So now we have found one more solution to the goal:

<vip>AA = "Pam", BB = "Bill", CC = "John".</vip>

If we try to find more solutions we will find:

<vip>AA = "Jack", BB = "Bill", CC = "John".
AA = "Jack", BB = "Bill", CC = "Lisa".</vip>

After that we will experience that everything will eventually fail leaving no more backtrack points.
So all in all there are four solutions to the goal.

== Improving the Family Theory ==

If you continue to work with the family relation above, you will probably find out that you have problems with relations like ''brother'' and ''sister'', because it is rather difficult to determine the sex of a person (unless the person is a father or mother).

The problem is that we have chosen a bad way to formalize our theory.

The reason that we arrived at this theory is because we started by considering the '''''relations''''' between the entities.
If we instead first focus on the '''''entities''''', then the result will naturally become different.

Our main entities are persons.
Persons have a name (in this simple context will still assume that the name identifies the person, in a real scale program this would not be true).
Persons also have a sex.
Persons have many other properties, but none of them have any interest in our context.

Therefore we define a person predicate, like this:

<vip>person("Bill", "male").
person("John", "male").
person("Pam", "female").</vip>

The first argument of the person predicate is the name and the second is the sex.

Instead of using mother and father as facts, I will choose to have parent as facts and mother and father as rules:

<vip>parent("Bill", "John").
parent("Pam", "Bill").

father(Person, Father) :- parent(Person, Father), person(Father, "male").</vip>

Notice that when father is a "derived" relation like this, it is impossible to state ''female'' fathers.
So this theory also has a built-in consistency on this point, which did not exist in the other formulation.

== Recursion ==

Most family relations are easy to construct given the principles above.
But when it comes to "infinite" relations like ''ancestor'' we need something more.
If we follow the principle above, we should define ancestor like this:

<vip>ancestor(Person, Ancestor) :- parent(Person, Ancestor).
ancestor(Person, Ancestor) :- parent(Person, P1), parent(P1, Ancestor).
ancestor(Person, Ancestor) :- parent(Person, P1), parent(P1, P2), parent(P2, Ancestor).
...</vip>

The main problem is that this line of clauses never ends.
The way to overcome this problem is to use a recursive definition, i.e. a definition that is defined in terms of itself. like this:

<vip>ancestor(Person, Ancestor) :- parent(Person, Ancestor).
ancestor(Person, Ancestor) :- parent(Person, P1), ancestor(P1, Ancestor).</vip>

This declaration states that a parent is an ancestor, and that an ancestor to a parent is also an ancestor.

If you are not already familiar with recursion you might find it tricky (in several senses).
Recursion is however fundamental to Prolog programming.
You will use it again and again, so eventually you will find it completely natural.

Let us try to execute an ancestor goal:

<vip>?- ancestor("Pam", AA).</vip>

We create a backtrack point to the second ancestor clause, and then we use the first, finding the new goal:

<vip>?- parent("Pam", AA).</vip>

This succeeds with the solution:

<vip>AA = "Bill".</vip>

Then we try to find another solution by using our backtrack point to the second ancestor clause.
This gives the new
goal:

<vip>?- parent("Pam", P1), ancestor(P1, AA).</vip>

Again "Bill" is the
parent of "Pam",
so we find P1=
"Bill", and then we have the goal:

<vip>?- ancestor("Bill", AA).</vip>

To solve this goal we first create a backtrack point to the second ancestor clause and then we use the first one.
This gives the following goal:

<vip>?- parent("Bill", AA).</vip>

This goal has the gives the solution:

<vip>AA = "John".</vip>

So now we have found two ancestors of "Pam":
* "Bill" and
* "John".

If we use the backtrack point to the second ancestor clause we get the following goal:

<vip>?- parent("Bill", P1), ancestor(P1, AA).</vip>

Here we will again find that
"John" is the parent of
"Bill", and thus that
P1 is
"John".
This gives the goal:

<vip>?- ancestor("John", AA).</vip>

If you pursuit this goal you will find that it will not have any solution.
So all in all we can only find two ancestors of
"Pam".

Recursion is very powerful but it can also be a bit hard to control.
Two things are important to remember:

*the recursion must make progress
*the recursion must terminate

In the code above the first clause ensures that the recursion can terminate, because this clause is not recursive (i.e. it makes no calls to the predicate itself).

In the second clause (which is recursive) we have made sure, that we go one ancestor-step further back, before making the recursive call.
I.e. we have ensured that we make some progress in the problem.

== Side Effects ==

Besides a strict evaluation order Prolog also has side effects.
For example Prolog has a number of predefined predicates for reading and writing.

The following goal will write the found ancestors of "Pam":

<vip>?- ancestor("Pam", AA), write("Ancestor of Pam : ", AA), nl().</vip>

The ancestor call will find an ancestor of "Pam" in AA.

The write call will write the string literal "Ancestor of Pam : ", and then it will write the value of AA.

The nl call will shift to a new line in the output.

When running programs in PIE, PIE itself writes solutions, so the overall effect is that your output and PIE's own output will be mixed.
This might of course not be desirable.

A very simple way to avoid PIE's own output is to make sure that the goal has no solutions.
Consider the following goal:

<vip>?- ancestor("Pam", AA), write("Ancestor of Pam : ", AA), nl(), fail.</vip>

fail is a predefined call that always fails (i.e. it has no solutions).

The first three predicate calls have exactly the same effect as above: an ancestor is found (if such one exists, of course) and then it is written.
But then we call fail this will of course '' fail''. Therefore we must pursuit a backtrack point if we have any.

When pursuing this backtrack point, we will find another ancestor (if such one exists) and write that, and then we will fail again.
And so forth.

So, we will find and write all ancestors. and eventually there will be no more backtrack points, and then the complete goal will fail.

There are a few important points to notice here:

*The goal itself did not have a single solution, but nevertheless all the solutions we wanted was given as side effects.
*Side effects in failing computations are not undone.

These points are two sides of the same thing.
But they represent different level of optimism.
The first optimistically states some possibilities that you can use, while the second is more pessimistic and states that you should be aware about using side effects, because they are not undone even if the current goal does not lead to any solution.

Anybody, who learns Prolog, will sooner or later experience unexpected output coming from failing parts of the program.
Perhaps, this little advice can help you: Separate the "calculating" code from the code that performs input/output.

In our examples above all the stated predicate are "calculating" predicates.
They all calculate some family relation.
If you need to write out, for example, "parents", create a separate predicate for writing parents and let that predicate call the "calculating" parent predicate.

== Conclusion ==

In this tutorial we have looked at some of the basic features of Prolog.
You have seen '''''facts''''', '''''rules''''' and '''''goals'''''.
You learned about the '''''execution strategy '''''for Prolog including the notion of '''''failing''''' and '''''backtracking'''''.
You have also seen that backtracking can give '''''many results '''''to a single question.
And finally you have been introduced to '''''side effects'''''.

== See also ==

* [[Fundamental Prolog Part 2]]

==References==

[[Category:Tutorials]]