As I had to admit in my last Prolog post, I'm no Prolog guru. I'd rather deserve the term newbie. However, I followed some math logic courses that make it all less harder. If you find something incorrect or if you don't understand something, comment it.
The first thing you have to keep in mind is that you don't really tell Prolog how to do something. You rather ask "him" (or her?) to prove something following the rules you gave.
Basic datatypes
In Prolog we have "Strings". We can also use terms like string or dog. However if they have capital letter, they are
variables, not simple terms.
We have list that is to say [], [a, b, c]. If we write
[H | T] H is the first element of the list, T a list containing all the remaining elements. If the list is [a, b, c], H is a and T is [b, c]
Computation model
Relations
Suppose you are working with a graph. Now suppose that you want to query the graph. As an example I report here a graph about elven genealogy in the LOTR world.The schema comes from
this site. If it is wrong, tell them, not me :)
For example there are different interpretation regarding Indis. Some say she's Ingwë's sister, some say she's the daughter of Ingwë's sister. We chose to say she's Ingwë's sister since I do not want to introduce a character with no name in our database :).
The House of Finarfin:
+ - - - - - +
: Ingwë
(sister) + - - - - - +
| | |
Finwë = Indis Olwë Elwë = Melian
| | |
Finarfin = Ëarwen Luthien
|
+----------------+----------------+---------+
| | | |
| | Aegnor |
Finrod = Amarië Angrod = Edhellos Galadriel = Celeborn
: | |
(descendants Orodreth Elrond = Celebrian
in Aman?) | |
+-------+------+ +------+---------+
| | | | |
Gil-galad Finduilas Elladan Elrohir Arwen
How would we represent this in an imperative language? We probably would have some kind of
class Elf
- gender (M/F)
- name (String)
- children (Elven)
- partner (Elf)
end
We could also have a kind of "double linked structure". This is probably wise since otherwise querying someone's father would be dramatically expensive.
class Elf
- gender (M/F)
- name (String)
- children (Elven)
- partner (Elf)
- mother (Elf)
- father (Elf)
end
In prolog we do not have such structure. We just tell "facts". A fact is a predicate that is always true. You can see how we define facts above. For example we are saying that aegnor is male.
male(aegnor).
male(angrod).
...
You can imagine this like
Elf Aegnor;Aegnor.name = "Aegnor";Aegnor.gender = M;...
Note that in Prolog everything is a Term, both data and program. Above I'm saying that aegnor is male. I assert that male(aegnor) is true.
This is the complete list of facts to define the above graph. If I were smarter I chose a smaller graph. However the list is long, but the imperative code to put into memory would not have been significantly shorter (yes, we could read it from file... where we would have had a list similar to the prolog version, :) )
female(amarie).
female(arwen).
female(celebrian).
female(earwen).
female(edhellos).
female(finduilas).
female(galadriel).
female(indis).
female(luthien).
female(melian).
male(aegnor).
male(angrod).
male(celeborn).
male(elladan).
male(elrohir).
male(elrond).
male(elwe).
male(finarfin).
male(finrod).
male(finwe).
male(gilgalad).
male(ingwe).
male(olwe).
male(orodreth).
parent(ingwe, olwe).
parent(ingwe, elwe).
parent(indis, finarfin).
parent(finwe, finarfin).
parent(olwe, earwen).
parent(elwe, luthien).
parent(melian, luthien).
parent(finarfin, finrod).
parent(earwen, finrod).
parent(finarfin, angrod).
parent(earwen, angrod).
parent(finarfin, aegnor).
parent(earwen, aegnor).
parent(finarfin, galadriel) .
parent(earwen, galadriel) .
parent(angrod, orodreth).
parent(edhellos, orodreth).
parent(galadriel, celebrian).
parent(celeborn, celebrian).
parent(orodreth, gilgalad).
parent(orodreth, finduilas).
parent(elrond, elladan).
parent(celebrian, elladan).
parent(elrond, elrohir).
parent(celebrian, elrohir).
parent(elrond, arwen).
parent(celebrian, arwen).
Rules
A rule is in the form:
goal(X) :- subgoal(X), subgoal2(X).
In the above goal(X) is true if and only if both subgoal(X) and subgoal2(X) are true. We say we
reducegoal to the two subgoals.
We will query something like:
goal(elrond).
and it will succeed if and only if both subgoal(elrond) and subgoal2(elrond). Notice this times we have constants and not variables.
Now it is time to define some interesting relation. A father is a male parent. A mother a female parent. In Prolog we write:
father(X, Y) :- parent(X, Y), male(X).
That is to say... X is father of Y if and only if X is parent of Y and X is male.
If we want to find Orodreth father, we query:
father(X, orodreth).
If is succeeds (and it does) in X there is Orodreth's father: Angrod. The imperative version of this would have been... orodreth.father. If we were wise enought (or had enough space) to use a double linked structure. If we didn't, well... we would have to traverse the graph.
We can also do the converse.
father(finarfin, X).
would return all the children of finarfin.
mother(X, Y) :- parent(X, Y), female(X).
son(X, Y) :- parent(Y, X), male(X).
daughter(X, Y) :- parent(Y, X), male(X).
These are other trivial relationship. Now suppose you want to find out all the ancestors of a given character. If you had the simpler structure, it is a pain in the ass. If you have the complete one, it is boring. Basically you have to tell the system to traverse the graph following father and mother links. Simple and tedious.
In fact what you are doing is the "transitive closure" of the parent relationship. In Prolog it is exactly how define in natural language. X is ancestor of Y if X is parent of Y or if X is parent of Z and z is ancestor of Y.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
All this relationships can be used to find the ancestors or the grandchildren. Or to verify if the relationship holds between two elves.
mother(galadriel, celebrian). returns yes, while mother(galadriel, arwen). returns no. You have to distinguish between defining facts and relationships and querying the system. This depends from your prolog interpreter: read a book, a tutorial, something. This is just a hint (and what I need to explain quicksort later on).
If you name this file elves.pl you can load it in swi-prolog with
[elves].
(remeber, no extention and end with a dot). Then you can just make queries. To define new predicates, put them in elves.pl and reload the file.
Some arithmetic...
We can consider the trivial algorithm to sum two numbers, provided we have an
INC and a DEC operation.
VAR A, B
WHILE B > 0
INC A
DEC B
END
This is quite obvious. If you (like me) hate those pseudo code examples, this is pure C.
unsigned int sum(unsigned int a, unsigned int b){
while(b) {
++a; --b;
}
return a;
}
It is quite interesting an example in a functional programming. This resembles the basic definition of addition if you are working with primitive recursive functions (S is the successor function and we omitted to write explicitly the i-th projection function).
sum( x, 0 ) = x
sum( x, y+1 ) = S(sum(x, y))
And this is Haskell (almost the same thing, a part from notations).
mysum :: Int -> Int -> Int
mysum x 0 = x
mysum x y = mysum x (y-1) + 1
In Prolog once again you follow the formal definition of sum in Set Theory. (That by the way is quite the same as above).
add(X, 0, X).add(0, Y, Y).add(X, Y, X1) :- succ(Y1, Y), add(X, Y1, X2), succ(X2, X1).
How this works? When I query something with add prolog will try to "match" against the arguments of the main goal. I don't want to be more precise about this "matching". It is called unification, and you are supposed to read a prolog tutorial to understand more about it.
add(5, 0, 5). will match the first rule: the second parameter is 0, and the other two are the very same term. Now let's consideradd(0, 5, X). . This could match the second rule. 0 matches 0. 5 matches Y. From this point for add to succeed, X must be 5 too. From swi-prolog:
2 ?- plus(0, 5, X).
X = 5
Yes
However, we said that we expect to use Prolog predicates in many different ways. Not only to sum two numbers, but also to find if given three numbers the third is the sum of the first two. We expect also that trivial predicates can be inverted. That is to say given a number and the "sum" find the number that summed to the first one gives the sum.
That is to say we expect to have the subtraction defined by only defining the sum. In fact this ain't magic. Prolog builtin plus predicate does exaclty this.
This is a copy and paste from the swi prolog terminal:
31 ?- plus(X, 4, 7).
X = 3
Yes
32 ?- plus(8, 9, Z).
Z = 17
Yes
33 ?- plus(3, Y, 1).
Y = -2
Yes
For those of you who are interested, we can define such a predicate this way, using builtin prolog arithmetic and some metalogical variables:
add(X, Y, Z) :- nonvar(X), nonvar(Y), Z is X+Y .
add(X, Y, Z) :- nonvar(X), nonvar(Z), Y is Z-X .
add(X, Y, Z) :- nonvar(Y), nonvar(Z), X is Z-Y .
nonvar returns true if and only if its argument is not a variable. That is to say, if instead of plus we used add, add(X, 4, 7). would have called the "third" predicate (for Y and Z are not variables, since they are "unified" -- substituted -- with 4 and 7). add(8, 9, Z). would have called the first predicate and add(3, Y, 1) the second.
But we can do something even smarter. First of all we recognize that the three clauses above are almost mutually exclusive. Two of the three clauses will fail if two of the three parameters are not variables. They will all succeed in the very same way if all three are not variables. They will all fail if only one is a variable.
So we can tell prolog: after you determined which is the variable, you can only use that rule. If none is a variable, use the first rule. We use "cuts". The rules become.
add(X, Y, Z) :- nonvar(X), nonvar(Y), !, Z is X+Y .
add(X, Y, Z) :- nonvar(X), nonvar(Z), !, Y is Z-X .
add(X, Y, Z) :- nonvar(Y), nonvar(Z), !, X is Z-Y .
Cuts are a complex subject. I'm not going to treat them here. Now I introduce a predicate between.
between(+Low, +High, ?Value)
Low and High are integers, High >=Low. If Value is an integer,
Low=< Value=< High. When Value is a variable it is successively
bound to all integers between Low and High. If High is inf
or infinite between/3 is true iff Value>= Low, a feature that is
particularly interesting for generating integers from a certain
value.
At this point we add this clauses:
add(X, Y, Z) :- nonvar(Z), !, between(0, Z, X), add(X, Y, Z).
add(X, Y, Z) :- nonvar(Y), !, between(0, inf, X), add(X, Y, Z).
add(X, Y, Z) :- nonvar(X), !, between(0, inf, Y), add(X, Y, Z).
Now you are able given one variable to generate pairs that satisfy the relationship (in fact pairs of positive numbers only).
Now let define prod.
prod(X, Y, Z) :- nonvar(X), nonvar(Y), !, Z is X*Y .
prod(X, Y, Z) :- nonvar(X), nonvar(Z), !, Y is Z/X .
prod(X, Y, Z) :- nonvar(Y), nonvar(Z), !, X is Z/Y .
prod(X, Y, Z) :- nonvar(Z), !, between(1, Z, X), prod(X, Y, Z).
prod(X, Y, Z) :- nonvar(Y), !, between(1, inf, X), prod(X, Y, Z).
prod(X, Y, Z) :- nonvar(X), !, between(1, inf, Y), prod(X, Y, Z).
Now it's time to define division. Do you know the euclidean algorithm? I suppose so. However, you don't need to know it. All you need to know is that dividing x for y you are looking for two numbers q and r such that
- x = y * q + r
- 0 <= r < y>
And in Prolog it is:
div(X, Y, 0, X) :- abs(X) < abs(Y).
div(X, Y, Q, R) :- prod(Y, Q, T1), T1 =< X, add(T1, R, X) ,
R >= 0, abs(R) < abs(Y).
This does not work when X and Y have not the same sign. However this depends from the way I defined prod. You should be able to make it work.
