52 349 Logic Programming

Chapter 6 - Prolog: Terminology & Semantics

§6.0 Introduction §6.3 Semantics of Prolog
§6.1 "Terms" in Prolog §6.3.1 Declarative Semantics
§6.1.1 Constants §6.3.2 Procedural Semantics
§6.1.2 Variables §6.3.3 The Marriage Example
§6.1.3 Compound Terms §6.4 Summary of Terminology
§6.2 Other Phraseology

Previous Reading: Computational Space & Non-Determinism

§6.0 Introduction

As should be clear by now, Prolog

Prolog = Programming in logic

is not the only form of logic programming

This came from the 1977 success of David [D.H.D] Warren in implementing efficiently on a DEC 10 the earlier ideas of Colmerauer (in Marseilles) and Kowalski (then in Edinburgh).

Beware Kowalski's later LISP-like syntax!

§6.1 "Terms" in Prolog

Not surprisingly given its FOPL roots, Prolog has a single basic data type, the term, covering both programs and data.

Terms comprise any appropriate sequence of characters ended by a period followed by a layout character (such as a new line)

Terms come in three varieties:

§6.1.1 Constant Terms

Constants are themselve split into two varieties, Numbers and Atoms.



§6.1.2 Variables

Variables resemble in form the first version of atoms given above, except that

The scope of each variable is the whole of the clause (or logical line) in which it appears

mother (Mum, Kid) :-
parent (Mum, Kid).

Prolog works by establishing that one occurrence of a variable needs unifying or instantiating, then propagating that value throughout the clause.

Note a useful exception!

mother(Mum) :- mother(Mum, _).

§6.1.3 Compound Terms

Compound Terms (otherwise called "structures" or "functors") have two properties:


mother(Mum, Kid).

Note that the compound terms

mother/2 mother/1
are wholly distinct: for terms to match, they must have the same name and the same arity.

Note also

§6.2 Other Prolog Phraseology

Each group of terms - to a terminating period - forms a "clause".

A collection of clauses with the same head (defined below) forms a "procedure"

Logical rules have as principal functor the predeclared :- /2

Logical facts are "unit clauses"

male(paul) :- true.

A "goal" is simply an instance of a clause - normally met in the context of a question, where we seek to establish the truth of the goal.

The other types of clause include

Note also comments

§6.3 The Semantics of Prolog

One aim of Prolog - not achieved - was declarative freedom

This gives us a separation between declarative semantics and procedural semantics.

Consider, following Ross, possible text on the side of a carton of juice:

"Do not open this side"

"Open other side""

Both are valid ... but they're very different.

§6.3.1 Prolog's Declarative Semantics

Declarative Semantics are concerned with what we are trying to achieve with some program

For example, in declarative terms

P:- Q, R.


From Q and R you can infer P
If Q and R are true, then so is P

Warren produced a recursive definition of this:

The declarative semantics of Prolog are that -

a goal is true if
it is the head of some clause instance and each of the goals (if any) in the body of that clause instance is true,
where an instance of a clause (or term) is obtained by substituting,
for each of its zero or more variables, a new term for all occurrences of the variable.

Work through that statement and contrast it with what follows!

§6.3.2 Prolog's Procedural Semantics

Procedural Semantics are concerned with how we achieve the objective of some program.

For example, in procedural terms

P:- Q, R.


To establish [solve] P,
first establish Q,
then establish R.

Thus procedural semantics are concerned with the method of operation of the interpreter

The procedural semantics of Prolog are thus essentially simple

(1) To execute a goal,
first search the program clauses in order of appearance

(i.e. top-down)
to find all the clauses for the predicate of which the goal is an instance
(in practice, the clauses will have been indexed by the interpreter,
when they were read in)
then try these instances, in order.

(2) To execute a goal using a particular clause instance,
first match (or attempt to unify) the goal with the clause's head.

If this fails,
consider the next clause instance
(or the goal fails if there are no more).

If it succeeds,
propagate the consequential instantiations of variables throughout the clause,
then attempt to execute each of the goals in the clause's body, working from left to right.

(3) If unable to execute one of the goals in the body,
then backtrack to find the most recent
(successful!) goal for which there might be another solution.

When (and if) this is achieved,
resume forward tracking,
with a new set of instantiations in place.

This sequence of forwards, backwards, forward trackings (points 2, 3) is at the heart of the interpreter's operation.

(4) Any goal is deemed to have succeeded
when a matching clause instance head had been found
and all the goals in the body have been successfully executed.

Otherwise the goal is deemed to have failed.

This recursive definition derives from Ross.

Understanding procedural semantics matters:

§6.3.3 A Practical Example

Consider two very similar programs:

married(paul, judy). rule married(A, B):-
married(B, A).
married(A, B):-
married(B, A). married(paul, judy).
?- married(paul,X). ?- married(paul,X).

Declaratively, these are very similar


§6.4 Summary of the Basics of Prolog

© Paul Goldfinch 1997 Next Chapter Return to 52 349 Menu