Prolog is a logic programming language, first invented by researchers in France around 1972. In fact the name Prolog comes from the phrase "programming in logic". In the logic programming paradigm, a program consists of a set of logical statements. In fact Prolog is actually a theorem prover: given a statement, it attempts to prove that it can be true. Prolog's syntax and semantics are closely related to first-order logic, which you may have studied in another class.
To be more precise, Prolog is based on a Turing-complete subset of first-order logic in which every program is a sequence of Horn clauses. However, we will not deeply study the logical foundation of Prolog in this course. Our focus will be on using the language, i.e. writing programs to accomplish our goals.
As I mentioned in the lecture, in our class we will use SWI-Prolog, which you should install on your own machine now. To start the Prolog REPL, run the command "swipl":
$ swipl Welcome to SWI-Prolog (threaded, 64 bits, version 9.0.4) SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software. Please run ?- license. for legal details. For online help and background, visit https://www.swi-prolog.org For built-in help, use ?- help(Topic). or ?- apropos(Word). 1 ?-
Data in Prolog is represented as terms. For now, a term may be
an atom, which is a string beginning with a lowercase letter and containing letters, digits and '_'. Examples: red, blue, dog, cat, house. All atoms are distinct, i.e. not equal to each other.
a variable, which begins with an uppercase letter and may contain letters, digits, and '_'. Examples: X, Y, Color.
We will learn about other kinds of terms soon.
The built-in
predicate '=' is true when two terms are equal.
?- red = red. true. ?- red = blue. false.
dif(X, Y) is true when X and Y
are different, i.e. not equal.
?- dif(red, blue). true. ?- dif(red, red). false.
Prolog includes these Boolean operators:
, (Boolean AND)
; (Boolean OR)
?- red = blue, blue = blue. false. ?- red = blue; blue = blue. true.
A Prolog query may include variables. Prolog attempts to prove that the query is true for some values of the given variables. In other words, the variables are existentially quantified. If the query can be true, Prolog reports the values that make it so.
?- X = red. X = red. ?- X = red, X = blue. false. ?- (X = red; X = blue), (Y = green; Y = yellow). X = red, Y = green ; X = red, Y = yellow ; X = blue, Y = green ; X = blue, Y = yellow.
A query may succeed multiple times, as in the last query above. When there may be multiple solutions, Prolog prints the first solution, then waits for user input. At this point you have two choices:
Type ';' to ask Prolog to look for another solution. It will continue searching, and will print the next solution if it can find one, otherwise 'false'.
Type '.' if you don't want to look for more solutions, and want to return to the REPL prompt.
Notice that Prolog solved this query by performing a depth-first search. First it saw the subgoal '(X = red; X = blue)'. This is a disjunction, i.e. two subgoals separated by the OR (;) operator. Any disjunction in Prolog introduces a choice point, i.e. a place where Prolog's search can go in one of two directions. So first Prolog assumes that X = red. Then it considers each of the values (Y = green; Y = yellow), and reports a solution for each of them:
X = red, Y = green ; X = red, Y = yellow ;
After that, Prolog backtracks to the choice point for X. It now chooses the value X = blue, and the proceeds again to the subgoal (Y = green; Y = yellow), reporting two more solutions:
X = blue, Y = green ; X = blue, Y = yellow.
Here are some more queries involving multiple variables:
?- (X = blue; X = red), (Y = red; Y = green), X = Y. X = Y, Y = red ?- (X = blue; X = red), (Y = red; Y = green), dif(X, Y). X = blue, Y = red ; X = blue, Y = green ; X = red, Y = green.
This last query had three solutions. As always, Prolog found them via a depth-first search. For each combination of X and Y, the subgoal dif(X, Y) runs. For most such combinations, this subgoal succeeds and a solution is printed. However, when X = red and Y = red this subgoal fails, i.e. is false. At that point Prolog cuts off the search and backtracks to the last choice point.
Unlike most programming languages, Prolog has no built-in concept of functions. Instead, it has predicates, also known as relations.
A predicate in Prolog has a name and zero or more arguments. A predicate's name begins with a lowercase letter. Predicates are defined in a source file using a series of clauses.
One kind of clause is a fact. A fact contains a predicate name plus zero or more arguments, which are terms.
For example, here is a series of facts that define several predicates named 'green', 'blue', 'animal' and 'frog'. All of these predicates take a single argument. In this code, the arguments 'grass', 'frog' and so on are atoms.
green(grass). green(frog). blue(sky). blue(water). animal(frog). animal(dog). animal(cat). plant(tree). plant(grass).
Let's put these facts into a source file 'nature.pl', then load it into the 'swipl' interpreter:
$ swipl nature.pl ?- green(grass). % is grass green? true. % yes ?- green(X). % is some X green? X = grass ; % X could be grass... X = frog. % or a frog ?- green(X), animal(X). % is there some green animal X? X = frog. % yes, X is a frog
Here are several facts that define a predicate 'capital' that takes two arguments:
capital(prague, czech_rep). capital(berlin, germany). capital(bratislava, slovakia).
Let's make some queries involving this predicate:
?- capital(prague, czech_rep). % is Prague the capital of the Czech Republic? true. % yes ?- capital(X, czech_rep). % what is the capital of the Czech Republic? X = prague. % it is Prague ?- capital(prague, X). % what is Prague the capital of? X = czech_rep. % the Czech Republic
We see that we may run a predicate in any direction. In other words, we may specify values for one (or more arguments), and ask Prolog to find values for the other arguments that cause the predicate to be true. In this way Prolog predicates are quite different from functions in procedural languages, which can run in only one direction.
Another kind of clause is a rule, which
consists of a head and a body, separated by the symbol
':-' . The symbol ':-' means 'if', i.e.
logical implication. Specifically,
A :- B
means "A is true if B is true", or "B implies A". In this statement, A is the head and B is the body.
For example, let's return to the facts about nature that we wrote above. Let's define a new predicate 'alive' using two rules:
alive(X) :- animal(X). alive(X) :- plant(X).
The first rule says "If X is an animal, then X is alive". Or, equivalently, "all animals are alive". Similarly, the second rule says "all plants are alive".
Logically speaking, the variable X in these rules is universally quantified. In other words, the rule is a statement about all X.
Now we can make queries using this predicate:
?- alive(X). % what is alive? X = frog ; X = dog ; X = cat ; X = tree ; X = grass. ?- alive(X), green(X). % what is alive and green? X = frog ; X = grass.
It's also possible to write the predicate 'alive' on a single line:
alive(X) :- animal(X); plant(X).
This is exactly equivalent to the two-clause version above.
We may also combine several facts into a single rule. Consider the predicate 'animal' that we wrote above:
animal(frog). animal(dog). animal(cat).
This rule is equivalent:
animal(X) :- X = frog; X = dog; X = cat.
Here is a family tree of part of the Czech royal family from hundreds of years ago:
In this picture, "Charles" is King Charles IV. Men are blue, and women are pink. The notation A → B means "A is the parent of B". For example, Charles's parents were John and Elizabeth B.
Let's express this tree as a series of Prolog facts:
male(john). male(charles). male(wenceslaus). male(sigismund). female(elizabeth_b). female(anne). female(elizabeth_p). female(margaret). female(barbara). female(elizabeth_l). parent(john, charles). parent(elizabeth_b, charles). parent(anne, wenceslaus). parent(charles, wenceslaus). parent(charles, margaret). parent(elizabeth_p, margaret). parent(charles, sigismund). parent(elizabeth_p, sigismund). parent(sigismund, elizabeth_l). parent(barbara, elizabeth_l).
We may now write a query asking who was Charles's mother:
?- parent(X, charles), female(X). % who is Charles's parent and is female? X = elizabeth_b.
To generalize this idea, let's write a predicate mother(M, P) that is true if M is the mother of P:
mother(M, P) :- parent(M, P), female(M).
Now we can write the above query more simply:
?- mother(M, charles). M = elizabeth_b.
Here are two more predicates expressing family relations:
% C is a child of P. child(C, P) :- parent(P, C). % G is a grandparent of P. grandparent(G, P) :- parent(G, X), parent(X, P).
We may interpret the 'grandparent' predicate as follows. For any G and P, G is the grandfather of P if there is some X such that G is the parent of X, and also X is the parent of P. In other words, the variables G and P are universally quantified. The variable X, which appears only in the body of the rule, is existentially quantified.
Let's write a predicate ancestor(P, Q) which is true if P is an ancestor of Q, i.e. a parent, grandparent, great-grandparent, …
ancestor(P, Q) :- parent(P, Q). % base case ancestor(P, Q) :- parent(P, X), ancestor(X, Q). % recursive case
This predicate is recursive, because in the second rule 'ancestor()' appears in the body, i.e. the predicate calls itself.
The first rule above says "If P is a parent of Q, then P is an ancestor of Q". The second says "If P is a parent of some X, and X is an ancestor of Q, then P is an ancestor of Q".
It works:
?- ancestor(A, margaret). % who are Margaret's ancestors? A = charles ; A = elizabeth_p ; A = john ; A = elizabeth_b ; false. ?- ancestor(elizabeth_p, P). % who are Elizabeth P's descendents? P = margaret ; P = sigismund ; P = elizabeth_l ; false.
Now suppose that we swap the order of the goals in the recursive case, so that it looks like this:
ancestor(P, Q) :- ancestor(X, Q), parent(P, X). % recursive case
This has no effect on the logical meaning of the rule. However, now the queries above will produce some results, then fail to terminate:
?- ancestor(elizabeth_p, P). P = margaret ; P = sigismund ; P = elizabeth_l ; ERROR: Stack limit (1.0Gb) exceeded
We see that reordering goals may affect whether Prolog's search strategy will succeed. In general, I recommend that you place the recursive call last when writing a recursive predicate, which will help with termination.
Let's return to the previous version, which worked correctly:
ancestor(P, Q) :- parent(P, Q). % base case ancestor(P, Q) :- parent(P, X), ancestor(X, Q). % recursive case
Here is another variation of the predicate:
ancestor(P, Q) :- parent(P, Q). % base case ancestor(P, Q) :- parent(X, Q), ancestor(P, X). % recursive case
It also works fine:
?- ancestor(elizabeth_p, P). % who are Elizabeth P's descendents? P = margaret ; P = sigismund ; P = elizabeth_l ; false.
The two versions are logically equivalent. However, for certain queries one may be more efficient than another. For example, consider the query 'ancestor(elizabeth_p, D)'. In the first version of the predicate, the query will match the recursive rule with P = elizabeth_p, Q = D. It will then solve parent(P, X), which is equivalent to parent(elizabeth_p, X). So it will find all of elizabeth_p's children. For each of those children X, it will recursively call ancestor(X, Q), continuing the downward search.
Now consider the second version of the predicate. Once again, the query will match the recursive rule with P = elizabeth_p, Q = D. It will then solve parent(X, Q). Neither X nor Q is bound to a value, so this will return all parent/child pairs X and Q. For each such pair, it will then recursively call ancestor(P, X), which is equivalent to ancestor(elizabeth_p, X). Effectively the search will proceed upward from every child anywhere in the family tree, looking to see if elizabeth_p is an ancestor of that child. This is less efficient.
On the other hand, the query 'ancestor(A, margaret)' will be more efficient with the second version of the predicate than the first. So it's really not possible to say that one version is more efficient than the other in general.