%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