Prolog/Putting it Together

This section serves both to combine the knowledge from the previous chapters and to review it. Prolog is first explained in more detail, true to its basic structure, and then a small program is presented that combines the knowledge from the previous chapters.

Prolog

A Prolog program consists of a database of rules. These rules are loaded into the compiler. The user can then run queries on the database. The compiler will try to prove that the query is true.

Everything in Prolog is described in logic (Prolog logic is variant of classic predicate- or first order logic). Starting from the atoms (the smallest bits) these are the most important logical symbols that make up a Prolog program or query.

constants

These consist of one or more lowercase characters, starting with a letter. A constant is not made up of other Prolog symbols (it's an atom) and it does not represent anything in the Prolog world except itself. A good way to think of atoms is as the objects of the prolog world. They have no meaning attached to them. Examples of valid constants:

foo
cd_p0345
a
dirk

Variables

Variables are containers. They can represent pretty much any Prolog structure, from constants to predicates. Variables consist of one or more lower- or uppercase characters, starting with an uppercase letter. It's important to note that variables function differently in Prolog than in most programming languages. You do not assign a value to them and then use them, various values are assigned to them by Prolog when you run a query to try and make the query true. Examples of valid variables:

B
Parent
Result

Predicates

Predicates consist of a functor (one or more lowercase characters, starting with a letter), possibly followed by a number of terms between brackets, separated by commas. A predicate is either true or false, based on its terms. Examples of valid predicates:

childof(Child, Father)
predicate(dog(x), cat(Y))
architect(a_vandelay)
termless_predicate

Functions

A function is built up the same way as a predicate, but instead of being false or true, it can represent anything a variable can represent. For instance, the function sqrt(A), will return the square root of whatever number A represents.

Atomic Sentences

An atomic sentence is the smallest part in a prolog program that can take on the meaning true or false. All predicates are atomic sentences. Some other Prolog statements, such as unification (=) are atomic sentences as well. Examples of atomic sentences:

childof(george_w_b, george_b)
A = tan(B, C) + D

Sentences (and connectives)

Sentences are Prolog constructions that can take on the meaning true or false. Atomic Sentences are of course sentences. Other sentences (i.e., non-atomic ones) are comprised of atomic sentences joined together by connectives. The most important connective in Prolog is , (the "and" connective). If a sentence joins two atomic sentences with a comma, the sentence will be true if (and only if) both atomic sentences are true. Most sentences in Prolog are just a number of predicates with comma's between them, indicating that all atomic sentences need to be true for this sentence to be true. Note: The other connectives, important though they are, will come up later. Examples of sentences.

childof(a, b), male(a), female(b)
A = B * 3, even(A)
dog(poochie), cat(scratchy), mouse(itchy)

Rules

A rule is a special type of sentence. It has a predicate on the left, and a sentence on the right separated by :-. It's concluded by a period. Sentences are the lines in a Prolog program. A rule states that the predicate is true if the sentence is true. If there are variables in the rule, then the predicate is true for any instantiation of the variables for which the sentence is true. A rule with no sentence after the predicate (and thus, no :-) is called a fact and is considered true as is. Every sentence in a Prolog program is a rule.

Examples of rules.

mother(A) :- has_child(A), female(A).
car(porsche).
equal(X, X).

Terms

A term is any Prolog construct representing an object. Constants and functions are always terms and variables can represent terms.

Other Prolog concepts are explained in the Glossary.

The Prolog Compiler

The Prolog compiler allows users to run queries on a database of rules (a Prolog program). Queries are special types of rules, with no predicate before the :-. Once a query is entered, Prolog will check if it's true, given that the rules in the database are true. If the query has variables, Prolog will attempt to find an instantiation of the variables that will make the query true.

This instantiating of variables is based on the process of unification. If Prolog is trying to verify the query :- a(X). and encounters the rule a(a). in the database, it will unify the variable X with the constant a. In other words, it will instantiate the variable X to the value a. Since a(a) is true, Prolog will return X = a as a solution. Unification takes two predicates and sees if one can be used to instantiate the variables of the other. The following two predicates unify:

p(A, y)
p(z, B)
unification: A = z, B = y

As do these:

q(A, [y,z,C])
q(x, B)
unification: A = x, B = [y,z,C]

However, these will not unify:

q(A, A)
q(x, y)

This is because A can be x or y, but not both. These on the other hand:

q(A, B)
q(x, x)

will unify, because two different variables can be bound to the same constant.

If Prolog is trying to verify the query :- b(X). and encounters the rule b(A) :- c(A). It will unify the variable X to the variable A. Neither of the variables are instantiated yet (i.e., have values assigned to them) but they are bound to each other, they can only be instantiated to the same value. Prolog will now add c(A) to its list of queries to verify. If it encounters the rule c(c) :- d. in the database, it will (temporarily) instantiate A with c, and try to verify d. If d succeeds, Prolog will return X = c as a solution to the original query, if Prolog can't find anything in the database that makes d true, Prolog will forget this rule and try to make c(A) true some other way. This is known as backtracking.

An example program

The following program checks if the sum of a list of numbers equals zero:

sum_is_zero(List) :- 
	sum(List, Sum),			% Sum is the sum of the List
	Sum = 0.			% Sum needs to be 0


sum([], 0).				% the sum of an empty list is always 0 (stop predicate)

sum([FirstNumber|Tail], Sum) :-		% The list is split into its first number and its tail
	sum(Tail, TailSum),		% TailSum is the sum of the tail
	Sum is FirstNumber + TailSum.	% Add the first number to that to get the Sum of the list.

The first rule in the program is pretty straightforward. It sums the list, using the sum predicate, and checks if it's equal to zero. The second two rules constitute the sum predicate. The first rule is the stop predicate. It simply states that an empty list has a sum of 0. The second rule first splits its list into a FirstNumber (the first number in the list, the 'head') and a Tail (the rest of the list). It calculates the sum of the tail recursively, and adds the first number to the sum of the tail.

Some queries:

?- sum_is_zero([1, -1]).
Yes

?- sum_is_zero([1, 1, -2]).
Yes

?- sum([-1.5, 2.7849, 3.383724], A).
A = 4.66862 ;
No

?- sum([-1.5, 2.7849, 3.383724], 42).
No

Exercises

(1) Which of the following predicate pairs unify? If they do, give the instantiation of the variables, if they don't, explain why not.

1 child_of(M, P)
  child_of(martha, doug)
2 dog(A)
  dog(B)
3 f(X, Y, e, Z)
  f(a, b, d, c)
4 r(D, F)
  r(p, c(martha, D))

---

previous:Math, Functions and Equality next:Cuts and Negation