4.1 Logic Programming

“Although there are other Logic Programming languages, by far the most widely used is Prolog. The name stands for PROgramming in LOGic.” - Max Bramer, Logic Programming with Prolog

There are many ways to think about what counts as computation.

In Imperative Programming, as exemplified in Java, C, C++, Python, and JavaScript, computation means updating values in memory, and a program is a sequences of such modifications.

In Functional Programming, as exemplified by languages like Haskell and Racket, computation means evaluating expressions to get their values, and a program is a single (big) expression whose value is the result of the computation.

In Logic Programming, as exemplified by languages like Prolog, computation means searching for a proof, and a program is a list of assumptions along with the desired conclusion.

From Predicate Logic to Prolog

The logical core of the programming language Prolog is exactly (a subset) of predicate logic. A program is simply a database of facts (logical formula) asserted to be true. We can think of these facts are our assumptions.

For example, a famous logical argument makes the following two assumptions: \[ \begin{array}{l} \forall x (\mathrm{man}(x)\to \mathrm{mortal}(x))\\[5pt] \mathrm{man}(\mathsf{Socrates})\\ \end{array} \] In Prolog, we would write these assumptions as follows:

mortal(X) :- man(X).
man(socrates).

Hints on reading this Prolog code:

• Each formula ends with a period.
• Predicate names (man and mortal) and constants (socrates) must start with a lowercase letter. Prolog variables (e.g., X) always start capitalized.
• The :- operator means “if”, i.e., right-to-left implication. (Because we’ve reversed the direction of the implication, man and mortal have swapped sides compared to the Predicate-Logic formula).
• We cannot write universal or extential quantifiers in Prolog, but implicitly each formula is understood to be universally quantified with all of its variables.

Once we have loaded these facts into Prolog we can then run a query to determine automatically whether a conclusion follows from our assumptions (?- is the prompt for our query):

?- mortal(socrates).

i.e., “Does it follow that Socrates is mortal?”, and Prolog will tell us:

true.

We can also do more interesting queries, e.g.,

?- mortal(P).

i.e., “Is there some person P that can be shown to be mortal?”, and Prolog will tell us yes, namely,

P = socrates.

(In our database of facts, each formula is implicitly universally quantified; when running queries, we can think of variables as being existentially quantified.)

Prolog as a Declarative Language

A language is said to be declarative if you can simply specify what you want, rather than how it is to be computed. On its best days, Prolog certainly seems quite declarative!

For example, it’s not too hard to find online lists of flavors that pair well together, but suppose we’re interested in finding three foods that go well with each other. We can compute this declaratively in Prolog as follows.

First, we create a database of facts and rules stating which foods pair well together. (Comments start with the % character.)

%
% Specific facts about food pairs
%
pairs(apple, walnut).       pairs(banana, coriander).
pairs(apple, honey).        pairs(strawberry, honey).
pairs(walnut, avocado).     pairs(strawberry, ginger).
pairs(walnut, banana).      pairs(strawberry, tea).
pairs(apple, banana).       pairs(tea, walnut).
pairs(banana, ginger).      pairs(tea, tomato).
pairs(banana, cloves).      pairs(tea, milk).
pairs(banana, strawberry).

%
% General rules about food pairing
%
pairs(X, X).         % every food X pairs with itself
pairs(_, coconut).   % any food pairs well with coconut

Where did this database come from? Well,

• Prof. Stone took the base facts from a much longer list found on the internet.
• It makes sense that any food should pair well with itself, but Prolog won’t assume this is true unless we explicitly say so. (Prolog doesn’t understand English, and it assumes we will specify all properties of the pairs predicate that are relevant.)
• The last rule might be considered dubious, but both Prof. Stone and I like coconut so we threw it in. (The underscore stands for “anything” or “we don’t care what goes here.”)

Next, we explain how to recognize an answer to our question:

% (for all X, Y, and Z),
%      X, Y, and Z form a yummy triple *if*
%         they go together pairwise and they are all different.
%
yummy_triple(X,Y,Z) :- pairs(X,Y), X \== Y,
                       pairs(Y,Z), Y \== Z,
                       pairs(X,Z), X \== Z.

In Prolog, the comma character means “and” and the \== operator means “not equal”. So this rule says “if (X pairs well with Y, and X is different from Y, and Y pairs well from Z, and Y is different from Z, and X pairs well with Y, and X is different from Z), then X, Y, and Z form a yummy triple.”

Finally, we can query Prolog to find examples of yummy triples:

?- yummy_triple(A,B,C).

and Prolog reports:

A = apple,
B = walnut,
C = banana

If we hit period or Enter, the query ends. But if we hit semicolon (rejecting that answer) then Prolog continues the query and reports another answer:

A = apple,
B = walnut,
C = coconut

If we continue hitting semicolon, we get even more answers: (apple, honey, coconut), (walnut, avacado, coconut), …, (banana, strawberry, ginger), …, (tea, milk, coconut), at which point Prolog can’t find any more answers and returns

false.

From Prolog back to Predicate Logic

It is worth noting that our database of facts and rules can be translated back into assumptions in Predicate Logic, namely:

\[ \begin{array}{l} \mathrm{pairs}(\mathsf{apple},\mathsf{walnut})\\[5pt] \mathrm{pairs}(\mathsf{apple},\mathsf{honey})\\[5pt] \vdots\\[5pt] \mathrm{pairs}(\mathsf{tea},\mathsf{milk})\\[10pt] \forall x\ \mathrm{pairs}(x,x)\\[5pt] \forall u\ \mathrm{pairs}(u, \mathsf{coconut})\\[10pt] \forall x\ \forall y\ \forall z\ \bigl((\mathrm{pairs}(x,y) \land x \neq y \land \mathrm{pairs}(y,z) \land y \neq z \land \mathrm{pairs}(x,z) \land x \neq z)\\ \mathrm{}\qquad\qquad\qquad\to \mathrm{yummy\_triple}(x,y,z)\bigr)\\ \end{array} \]

Another Example: The Family Tree

We can represent the following family tree as a collection of Prolog facts:

parent(homer, bart).   age(marge, 35). female(marge).  male(homer).
parent(marge, bart).   age(homer, 38). female(jackie). male(gomer).
parent(homer, lisa).   age(lisa, 8).   female(selma).  male(gemini).
parent(marge, lisa).   age(maggie, 1). female(patty).  male(glum).
parent(homer, maggie). age(bart, 10).  female(cher).   male(bart).
parent(marge, maggie). age(gomer, 41). female(lisa).   male(millhouse).
% etc.

and then add declarative rules defining other relationships:

% If Y is a parent of X, then X is the child of Y.
child(X, Y) :- parent(Y, X).

% If X is female and a parent of Y, then X is a mother of Y.
mother(X, Y) :- female(X), parent(X, Y).

% If X is a parent of Y, then X is an ancestor of Y.
anc(X, Y) :- parent(X, Y).

% Also, if Z is the parent of X and X is an ancestor of Z,
%    then X is an ancestor of Y.
anc(X, Y) :- parent(Z, Y), anc(X, Z).

Then we can query Prolog:

Alternatively, we could define more familial relationships:

% If X and Y share at least one parent (and are not the same person),
%   then we consider them siblings.
sib(X,Y) :- parent(P,X), parent(P,Y), X \== Y.

% if A is the female sibling of a parent P of N,
%   then A is the aunt of N.
aunt(A,N) :- parent(P,N), sib(P,A), female(A).

% If X is an ancestor of Y, then X and Y are related (genetically).
rel(X,Y) :- anc(X,Y).
% Also, if Y is an ancestor of X, then X and Y are related.
rel(X,Y) :- anc(Y,X).
% Also, if X and Y have a common ancestor A, then X and Y are related.
rel(X,Y) :- anc(A,X), anc(A,Y).

Previous: 3.6 Asymptotic Analysis

Next: 4.2 Unification