Basic Data Structures and Syntax

We have already seen how prolog programs consist of facts, rules and questions. Facts declare things that are always true. Rules declare things that are true depending on some conditions. They consist of a head and a body. For example the rule ``a(X) :- b(X), c(X).'' has head ``a(X)'' and body ``b(X), c(X)''. Its head is true if the goals in its body are all true. (Facts can be viewed as rules without a body). Facts and/or rules can be used to define relations (or predicates). These can be of different arities (ie, have different numbers of arguments). For example, lectures/2 is the binary relation lectures, and might be defined by the three facts lectures(alison, ai), tt lectures(phil, databases), and lectures(gilbert, hci).

Questions are used to find out if something is true (and what the associated variable bindings would be to make it true). Facts, rules and questions are all prolog clauses and must end with a full stop.

The fundamental data structure in Prolog is the term. Prolog terms include:

Atoms

such as sparrow, x, 'Alison Cawsey', a102, -. These generally represent specific single entities in the world and cannot be separated into parts. They normally begin with a lower-case letter, but arbitrary characters can be used if they are quoted. Symbols (such as ``-'') and sequences of symbols (e.g., ``:-'') are also atoms.

Numbers

such as 29, 1.2, 3000, -2.

Variables

such as X, Person, _Var. Variables begin either with a capital letter or an underline character.

Structured Objects:

such as:

book(title(lord_of_the_rings), author(tolkien))
bicycle(owner(alison), parts(gears(number(18), type(shimano))))

These consist of a functor (e.g., book, bicycle), and some arguments. The arguments may in turn be any prolog term.

[Note that prolog atoms may be declared as operators. Arithmetic opertors such as * and + are examples. They can then be used to form prolog terms like 1+3. We could write a conventional functor/argument structure like +(1, 3), but its much more convenient to write this as 1+3. However that arithmetic expressions are NOT evaluated unless you force evaluation with the built in prolog predicate ``is'', for example.]

Complex structures like the ones above are useful if we want to carry around some information about a related collection of objects, or an object with many parts, for example. We can get at the parts of a complex term by matching it against a query (discussed further below). So, if we had the following Prolog program:

   book(title(lord_of_the_rings), author(tolkien)).

   has_famous_author(Title) :-
      book(title(Title), author(Author)),
      famous(Author).

and asked the query:

   ?- has_famous_author(lord_of_the_rings).

Prolog would first MATCH the query with the HEAD of the rule, so that Title is bound to lord_of_the_rings. Then it would try to satisfy book(title(lord_of_the_rings), author(Author)). This would be matched with the first fact, and Author would be bound to tolkien. Then it would try to satisfy famous(tolkien), which would match the second fact, so it would all be satisfied, and Prolog would return with yes.

Note how Prolog has used pattern matching to ``get at'' one bit of a complex Prolog fact (the author). We'll look at matching more closely below.