PROLOG: algorithm = logic + search

First some terminology for first-order predicate logic.
The language of first-order logic is assembled in several layers:

LAYER 0: CONSTANTS AND VARIABLES
- In Prolog, constants are 
  * any string consisting of alphanumeric characters and underscore (_)
    that begins with a lowercase letter (called *atoms*)
  * any number.
- Variables are such strings that begin with '_' or an uppercase letter.

Examples:
X = cat.
X = my_cat.
X = 3.
X = Y.
cat = dog.
Cat = Dog.

LAYER 1: TERMS
These are inductively defined as the smallest set containing:
  - constants and variables
  - applications of any n-ary *functor* to any n terms
    (called *compound terms*)
Examples:
X = f(cat,dog).
X = f(Cat,dog).
X = 3 + 4.  % Compound terms are not evaluated!
X is 3 + 4.  % But is/2 will evaluate arithmetic expressions

Note: Prolog functions have arity, but do not specify argument and
result types.  Prolog is a weakly typed language, meaning that Prolog
distinguishes numbers and variables from other terms in certain
contexts (like RHS of is/2), but is otherwise untyped/monotyped.

LAYER 2: ATOMIC FORMULAE
These consist of an n-ary relation (also called *predicate*) applied to
n terms.

Examples:
cat(tom).
mouse(jerry).
eats(tom,jerry).
chases(fido,cat).
chases(fido,tail(fido)).

Note: formulae look a lot like terms because of Prolog's weak typing.  But
formulae are either true or false; terms denote entities in the world.

All of these are *ground*, i.e., there are no variables in them. One
can speak of ground terms also, e.g., f(a,b), but not f(X,b).

This is also an atomic formula:
X = fido.

=/2 is a binary predicate with infix notation.

In Prolog, atomic formulae can be used in three ways:
- As *facts*: in which they assert truth,
- As *queries*: in which they enquire about truth,
- As components of more complicated statements (see below).

This prompt:
?- 
means that Prolog is asking you for a query.  Prolog's built-in knowledge
of facts is very limited, so normally you must assert the truth of some
facts.  *Programs* assert facts.

?- [program].

This special query loads the program 'program.pl' into memory as a
side-effect (in Prolog-ese, we *consult* the program).  Now we can ask
queries:

?- cat(tom).
?- mouse(jerry).
?- eats(tom,jerry).
?- chases(fido,tail(fido)).
?- chases(X,tail(X)).

Prolog takes free variables in queries to be EXISTENTIALLY quantified.
?- cat(X), mouse(X). % wide scope