Foundations · Lesson 3 of 43

Syntax and execution model

Terms, atoms, clauses, goals, SLD resolution and backtracking, precisely.

This lesson fixes the vocabulary used by logic programming, and then describes in one place how a Prolog computation proceeds.

Prolog terms

Variables are alphanumeric strings starting with an uppercase letter or an underscore. The underscore alone, _, is the anonymous variable, a sort of don't care variable. An underscore followed by a string, like _Tmp, is a normal variable during resolution, but it does not need to be exposed in the computed substitution.
Functors are alphanumeric strings starting with a lowercase letter. This holds for both proper functors (f(a)) and constants (a).
Terms are built recursively out of functors and variables, as in logic programming.

So term, Var, f(X) and p(Y, f(a)) are Prolog terms, while term, var, f(a) and p(x, y) are Prolog ground terms (terms with no variables).

?- T = p(Y, f(a)), ground(T)

?- T = p(x, f(a)), ground(T)

?- var(_), var(Anything), nonvar(f(a)), nonvar(term)

Prolog atoms

In logic programming the word atom has a precise meaning: an atom (or atomic formula) is built by applying a predicate to terms. Predicates are alphanumeric strings starting with a lowercase letter, exactly like functors.

So predicate, f(X) and p(Y, f(a)) are atoms in this sense, and predicate, f(a) and p(x, y) are ground atoms.

Towards meta-programming

parent(lino, joey), taken out of context, could represent either a ground atom or a ground term. Is that an issue, or a feature? It is a feature: it paves the way towards meta-programming, where programs treat other programs as data.

Prolog clauses

A clause is a Horn clause of the form A :- B1, ..., Bn. where A, B1, ..., Bn are Prolog atoms.

A is the head of the clause, and B1, ..., Bn is its body;
:- denotes logic implication, and . is the terminator.

There are three kinds of clause:

kind	shape	notes
fact	`A.`	a clause with no body (n = 0)
rule	`A :- B1, ..., Bn.`	a clause with at least one atom in the body (n > 0)
goal	`:- B1, ..., Bn.`	a clause with no head and at least one atom in the body (n > 0), often written `?- B1, ..., Bn.`

A program is a sequence of Prolog clauses, interpreted as a conjunction of clauses. It constitutes a logic theory made of Horn clauses written according to the Prolog syntax.

parent(joey, luca).                       % a fact
parent(lino, joey).                       % a fact
grandparent(G, N) :- parent(G, P), parent(P, N).   % a rule

?- grandparent(lino, Who)

In the notebook, the cell above is the program (facts and rules) and each query cell is a goal.

Prolog execution

What a computation is

Given a Prolog program P and the goal ?- p(t1, t2, ..., tm) (also called a query), let X1, X2, ..., Xn be the variables in the terms t1, ..., tm. The meaning of the goal is to query P and find whether there are values for X1, ..., Xn that make p(t1, ..., tm) true.

So the aim of a Prolog computation is to find a substitution σ = {X1/s1, ..., Xn/sn} such that P ⊨ p(t1, t2, ..., tm)σ. That substitution is what Prolog prints as an answer.

The search strategy

As a logic programming language, Prolog adopts SLD resolution. As a search strategy, Prolog applies resolution in a strictly linear fashion:

goals are replaced left to right, sequentially;
clauses are considered in top-to-bottom order;
subgoals are considered immediately once set up.

The result is a depth-first search strategy.

Backtracking

To achieve completeness, Prolog saves a choicepoint for every alternative still to be explored, and goes back to the nearest choicepoint available in case of failure. This is automatic backtracking.

colour(red).
colour(green).
colour(blue).

?- colour(C)

?- colour(C), C \= red, !

Each answer above comes from a different choicepoint of colour/1: Prolog commits to the first clause, and returns to the saved choice when you ask for more.

Prolog implementations

This notebook runs SWI-Prolog, compiled to WebAssembly, in your browser. Other systems exist too.

SWI-Prolog is the framework used by this notebook. Home: swi-prolog.org, GitHub: github.com/SWI-Prolog, online: SWISH. In SWISH you write the program on the left, the goal at the bottom right, and press Ctrl-Enter.

The other free implementation is GNU Prolog, and a commercial one is SICStus Prolog.

Exercise: Facts, rules and goals

Write a program with two facts likes(mia, tea) and likes(zoe, tea), and one rule pair(A, B) that holds when A and B like the same thing and are different people.