§6.0 Introduction

As should be clear by now, Prolog

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.

§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)

• 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

• variables

• compound terms

§6.1.1 Constant Terms

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

Numbers

• 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 = 3³ 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!

Atoms

• are the text constants

• they normally comprise

  either

  a lower case letter, followed by zero or more letters, numbers and underscores (other characters may be available, for example $, -, #)
  or
  any sequence of characters wholly enclosed in single quotes.

• examples are
  • abraham
  • by_12
  • 'Paul Goldfinch'

• by convention, the following are also regarded as atoms

  [ ... ]

  !

  ;

  { ... }

§6.1.2 Variables

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
  • Who
  • Why_12
  • _which

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

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
  ... which may not yet have been determined!

  ... and may never be determined!

• 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?

§6.1.3 Compound Terms

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

• name
  (which looks like the first form of an atom)

• arity
  (number of arguments)

Thus

• has name mother and arity 2

• referred to, and (except in code listing) often written, as mother/2

Note that the compound terms

Note also

• the arguments of compound terms are themselves terms

• atoms are just compound terms of arity zero

• that from the second of these follows a second practical rule of Prolog layout
  • (the first being the new line or similar which terminates a term)

  • never try to leave a space between the functor name and its opening left bracket

  otherwise your intended compound term will be read as an improperly terminated atom.

§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"

• 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

• thus

is simply shorthand for

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

• "questions"
  • 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

• "directives"
  • 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!

§6.3 The Semantics of Prolog

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.

§6.3.1 Prolog's Declarative Semantics

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

is,

Warren produced a recursive definition of this:

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

is,

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!

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

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.

§6.3.3 A Practical Example

Consider two very similar programs:

married(paul, judy).			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

... possibly they are identical!

Procedurally,

• 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.4 Summary of the Basics of Prolog

• §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