52 349 Logic Programming
Chapter 6 - Prolog: Terminology & Semantics
Computational Space & Non-Determinism
As should be clear by now, Prolog
Prolog = Programming in logic
is not the only form of logic programming
- but it is probably the best established
- and the Edinburgh syntax the best known
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!
- which can still be found (and is perfectly proper)
- but is not compatible with the notation used here.
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)
- although the ending is omitted when used in association with other terms
- Note that there is an important practical consequence of this definition: if you omit the layout character at the end of a file of Prolog (as many people do!), then the last term will be ignored. Whence the advice always to end a file with a comment!
Terms come in three varieties:
Constants are themselve split into two varieties, Numbers and Atoms.
- are, even now, highly implementation dependent
- all systems allow integers
- most allow decimals
- many allow some form of exponent notation
- often there is a facility to change base; for example
- 27 = 33 can be written as 3'1000
- which is a horrendous overloading of the single quote, giving vast scope for an interpreter to misinterpret typing errors!
- as a calculating system, Prolog compares quite well with COBOL ... except when you have to, don't!
- are the text constants
- they normally comprise
a lower case letter, followed by zero or more letters, numbers and underscores (other characters may be available, for example $, -, #)
any sequence of characters wholly enclosed in single quotes.
- examples are
- 'Paul Goldfinch'
- by convention, the following are also regarded as atoms
Variables resemble in form the first version of atoms given above, except that
- they start eitherwith an upper case letter or with an underscore
- examples are
The scope of each variable is the whole of the clause (or logical line) in which it appears
- ... remember the implicit "for all" around each clause ?
- more precisely, the whole of the instance of the clause in which it appears.
- for example, in
mother (Mum, Kid) :-
parent (Mum, Kid).
the whole clause is the scope of "Mum"
- thus everywhere in a clause each occurrence of a variable name stands for the same non-variable term
- In the example, if one occurrence of Mum is instantiated to, say, mary, then so are they all.
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!
- the "anonymous variable" _ (that is, the underscore on its own)
- which has every occurrence distinct from every other
- and can be thought of as "don't care"
- Trivial example, re-using previous code example?
mother(Mum) :- mother(Mum, _).
Compound Terms (otherwise called "structures" or "functors") have two properties:
(which looks like the first form of an atom)
(number of arguments)
- has name mother and arity 2
- referred to, and (except in code listing) often written, as mother/2
Note that the compound terms
are wholly distinct: for terms to match, they must have the same name and the same arity.
Each group of terms - to a terminating period - forms a "clause".
A collection of clauses with the same head (defined below) forms a "procedure"
- a close similarity with, say, C
... but similarity of purpose is not reflected in similarity of form
Logical rules have as principal functor the predeclared :- /2
- they are called "non-unit clauses"
- their first argument is the "head" of the clause
- the others form the "body", the second argument
Logical facts are "unit clauses"
- think of them as rules with a head but no body
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
- Clauses with an empty head and principal functor ?- /1
- which are run to investigate a goal
- and lead to a report of any instantiations required to establish the truth of a goal
- clauses with an empty head and principal functor :- /1
- which are run immediately the interpreter reads them
- for example, to reconsult another file, perhaps of procedures required by the following code.
Note also comments
- everything between a pair of */
- or from % to the end of the line
- the two forms seldom nest!
One aim of Prolog - not achieved - was declarative freedom
- the ability to make statements and to achieve proofs
without regard to the procedures which had to be followed.
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"
- A declarative observation
- Making no assumptions about whether or not you want to open it
"Open other side""
- A procedural observation
- Telling you how to go about the opening
(and assuming that you want to!)
Both are valid ... but they're very different.
Declarative Semantics are concerned with what we are trying to achieve with some program
- They are a statement of meaning,
which you may or may not wish to test
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!
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
- and follow from our choice in Prolog of the standard search strategy for applying our inference rule
The procedural semantics of Prolog are thus essentially simple
- Though lengthy to explain!
||To execute a goal,
first search the program clauses in order of appearance
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.
||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.
||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.
||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.
- It gives us also an insight into how we should think of the effect of backtracking on the instantiation of variables
- It is common but misleading to think of instantiations being "undone" when backtracking occurs
- It is more correct, and conceptually easier, to think of the system "reverting" to that state in which those variables had yet to be instantiated.
Understanding procedural semantics matters:
- it is impossible otherwise to write successful Prolog programs!
- declarative correctness is insufficient!
- in particular, simple clauses almost always should go first.
Consider two very similar programs:
Declaratively, these are very similar
... possibly they are identical!
- the first one quickly suggests X = judy (and goes on doing so - why?)
- the second loops helplessly until it runs out of available stack space.
- §6.1 Everything in Prolog is a term
- Terms are
- §6.1.1 Constants (Numbers or Atoms)
- §6.1.2 Variables
- §6.1.3 Compound Terms
- All distinguished by syntactic shape
- §6.2 Procedures have one or more clauses
- Clauses have (in general) heads and bodies
- We have goals, questions, directives
- §6.3 Declaratives versus Procedural Semantics
- Nature of backtracking
- §6.3.3 Programs which are declaratively correct but procedurally flawed