Prolog is a logic programming language. 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.
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 8.2.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, (Y = green; Y = blue). X = red, Y = green ; X = red, Y = blue.
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.
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.
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.
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.