.NH
PROGRAMMING IN LOGIC - THE PROLOG LANGUAGE
.LP
This section provides an introduction to the syntax and semantics
of  a certain subset of logic (`definite clauses', also known as `Horn
clauses'), and indicates how this subset forms the basis of Prolog.
.NH 2
Syntax, Terminology And Informal Semantics
.LP
.NH 3
Terms
.LP
The data objects of the language are called  \fIterms\fR.   A term  is
either a \fIconstant\fR, a \fIvariable\fR or a \fIcompound term\fR.
.LP
The constants include \fIintegers\fR such as:

.ce
0 1   999   \-512
.LP
In UNSW@Prolog, integers are restricted to the range \-2^31  to
2^31\-1 on the VAX and \-2^15 to 2^15\-1 on the PDP\-11. AmigaDOS
uses 32-bit integers which gives it the same range as the VAX.
.LP
Constants include reals such as:-
.ce
0.0   1.0   34.45  -23.45   3.45e-02
.LP
In  prolog, reals have the same range as float in C. Printing reals will only
give 4 decimal place accuracy.
.LP
Constants also include \fIatoms\fR such as:

.ce
a void   =   := `Algol-68'   []
.LP
The symbol for an atom can be any sequence of characters, which should
be  written  in quotes if there is possibility of confusion with other
symbols (such as variables, integers). As in conventional  programming
languages,  constants  are definite elementary objects, and correspond
to proper nouns in natural language.
.LP
Variables are distinguished by an initial capital  letter  or  by
the initial character `_', eg.

.ce
X Value A   A1  _3   _RESULT
.LP
If a variable is only referred to once, it does not need to  be  named
and  may  be written as an `anonymous' variable indicated by a single
underline character: `_'
.LP
A variable should be thought of as  standing for  some  definite  but
unidentified object.   This is  analogous to the use of a pronoun in
natural language.  Note that a variable  is  not  simply  a  writeable
storage  location  as  in  most programming languages;  rather it is a
local name for some data object.
.LP
The structured data objects of  the  language  are  the compound
terms.   A  compound term  comprises  a
\fIfunctor\fR (called the \fIprincipal\fR
functor of the term) and a  sequence of  one  or  more  terms  called
\fIarguments\fR.
A functor is characterised by its \fIname\fR, which is an atom,
and its \fIarity\fR or number of arguments.  For example the  compound  term
whose  functor is named `point' of arity 3, with arguments X, Y and Z,
is written:
.DS C
point(X, Y, Z)
.DE
Note that an atom is considered to be a functor of arity 0.
.LP
Functors are generally  analogous  to  common  nouns  in  natural
language.   One  may think  of  a  functor  as  a record type and the
arguments of a compound term as the  fields  of  a  record. Compound
terms are usefully pictured as trees.  For example, the term:
.DS C
s(np(john), vp(v(likes), np(mary)))
.DE
would be pictured as the structure:
.nf
.PS
scale=100
define m0 |
[ box invis ht 144 wid 152 with .sw at 0,0
"\fR\s10\&vp\f1\s0" at 72,134
line  from 72,128 to 16,88 
line  from 16,24 to 16,64 
"\fR\s10\&v\f1\s0" at 16,74
"\fR\s10\&likes\f1\s0" at 20,10
line  from 72,128 to 128,88 
"\fR\s10\&np\f1\s0" at 128,74
line  from 128,64 to 128,24 
"\fR\s10\&mary\f1\s0" at 132,10
] |

box invis ht 184 wid 280 with .sw at 0,0
m0 with .nw at 128,144
line  from 112,168 to 200,144 
line  from 24,128 to 24,88 
"\fR\s10\&np\f1\s0" at 24,134
"\fR\s10\&s\f1\s0" at 112,174
line  from 112,168 to 24,144 
"\fR\s10\&john\f1\s0" at 24,74
.PE
.fi
.LP
Sometimes it is convenient to write certain functors as \fIoperators\fR
\- 2\-ary functors may be declared as \fIinfix\fR operators and 1\-ary functors
as \fIprefix\fR or \fIpostfix\fR operators.  Thus it is possible to write, eg.
.DS C
X+Y     (P;Q)     X<Y +X     P;
.DE
instead of:
.DS C
+(X, Y)   ;(P, Q)   <(X, Y) +(X)   ;(P)
.DE
The use of operators is described fully in Section 1.4.
.LP
An important class of data structures are the \fIlists\fR.   These  are
essentially  the  same  as  the  lists  of Lisp.  A list either is the
atom:

.ce
[]

representing the empty list, or is a compound term  with
two  arguments  which  are  respectively the head and tail of the
list.  Thus  a  list of  the  first three  natural numbers  is
is written, in a special list notation, as:
.DS C
[1, 2, 3]
.DE
The special list notation in the case when the tail of  a  list  is  a
variable is exemplified by:
.DS C
[X, ..L] [a, b, ..L]
.DE
For compatibility with Prolog-10 the notation:
.DS C
[X\||\|L] [a, b | L]
.DE
may also be used.
.NH 3
Programs
.LP
A fundamental unit of a logic program is the
\fIgoal\fR  or  \fIprocedure call\fR.
Examples are:
.DS C
gives(tom, apple, teacher)   reverse([1, 2, 3], L)   X < Y
.DE
.LP
A goal is merely a special kind of term,  distinguished  only  by  the
context  in  which it appears in the program.  The (principal) functor
of a goal is called a \fIpredicate\fR.  It corresponds roughly to a verb  in
natural language, or to a procedure name in a conventional programming
language.
.LP
A logic \fIprogram\fR consists  simply  of  a sequence  of  statements
called   \fIsentences\fR,  which  are  analogous  to  sentences  of  natural
language.  A sentence comprises a \fIhead\fR and a \fIbody\fR.   The  head  either
consists  of a  single  goal  or  is  empty.   The body consists of a
sequence of zero or more goals (ie.  it too may be empty). If the head
is not empty, the sentence is called a \fIclause\fR.
.LP
If the body of a clause is non-empty,  the  clause  is  called  a
\fInon-unit clause\fR, and is written in the form:
.DS C
\fBP\fR :\- \fBQ\fR, \fBR\fR, \fBS\fR.
.DE
where \fBP\fR is the head goal and \fBQ\fR, \fBR\fR and \fBS\fR are the goals
which make  up the body.
We can read such a clause either \fIdeclaratively\fR as:

.ce
`\fBP\fR is true if \fBQ\fR and \fBR\fR and \fBS\fR are true.'

or \fIprocedurally\fR as:

.ce
`To satisfy goal \fBP\fR, satisfy goals \fBQ\fR, \fBR\fR and \fBS\fR.'

.LP
If the body of a clause is empty, the clause  is  called  a  \fIunit\fR
\fIclause\fR, and is written in the form:

.ce
\fBP\fR.

where \fBP\fR is the head goal.  We interpret this declaratively as:

.ce
`\fBP\fR is true.'

and procedurally as:
.ce
`Goal \fBP\fR is satisfied.'

.LP
A sentence with an empty head is called a \fIdirective\fR, of which the
most important kind is called a \fIquestion\fR and is written in the form:

.ce
\fBP\fR, \fBQ\fR ?

where \fBP\fR and \fBQ\fR are the goals of the body.
Such  a  question is  read
declaratively as:

.ce
`Are \fBP\fR and \fBQ\fR true?'

and procedurally as:

.ce
`Satisfy goals \fBP\fR and \fBQ\fR.'

.LP
Sentences generally contain variables.  Note  that  variables  in
different  sentences are completely independent, even if they have the
same name \- ie.  the `lexical scope' of a variable  is  limited  to  a
single  sentence.   Each  distinct  variable in  a sentence should be
interpreted as  standing  for  an  arbitrary entity,  or  value.   To
illustrate  this,  here  are some  examples of  sentences containing
variables, with possible declarative and procedural readings:
.DS I
(1)     employed(X) :\- employs(Y, X).

`Any X is employed if any Y employs X.'

`To find whether a person X is employed,
find whether any Y employs X.'

(2)     derivative(X, X, 1).

`For any X, the derivative of X with respect to X is 1.'

`The goal of finding a derivative for the expression X
with respect to X itself is satisfied by the result 1.'

(3)     ungulate(X), aquatic(X) ?

`Is it true, for any X, that X is an ungulate and X is
aquatic?'

`Find an X which is both an ungulate and aquatic.'
.DE
.LP
In any program, the \fIprocedure\fR for a particular predicate  is  the
sequence  of clauses  in  the  program  whose  head goals  have that
predicate as principal functor.  For example,  the  procedure  for  a
ternary   predicate  `append'  might  well  consist  of the  two
clauses:
.DS I
append([X, ..L1], L2, [X, ..L3]) :\- append(L1, L2, L3).
append([], L, L).

.DE
where `append(L1, L2, L3)' means `the list L1 appended with the
list L2 is the list L3'.
.LP
Certain predicates are predefined by \fIbuilt\-in procedures\fR supplied
by   the   Prolog   system. Such  predicates  are  called  \fIevaluable
predicates\fR.
.LP
As we have seen, the goals in the body of a sentence are linked
by the operator `,' which can be interpreted as conjunction (`and').
It is sometimes convenient to use an additional operator `\||\|', standing
for disjunction (`or'). (The precedence of `\||\|' is such that it
dominates `,' but is dominated by `:\-'). An example is the clause:
.DS I
grandfather(X, Z) :\-
     (mother(X, Y) | father(X, Y)), father(Y, Z).
.DE
which can be read as:
.DS I
`For any X, Y and Z,
     X has Z as a grandfather if
     either the mother of X is Y or the father of X is Y,
     and the father of Y is Z.
.DE
.LP
Such uses of disjunction can always be eliminated by defining an
extra predicate \- for instance the previous example is equivalent to:
.DS I
grandfather(X, Z) :\- parent(X, Y), father(Y, Z).
parent(X, Y) :\- mother(X, Y).
parent(X, Y) :\- father(X, Y).
.DE
\- and so disjunction will not be mentioned further in the following,
more formal, description of the semantics of clauses.
.LP
\fINote:\fR For compatibility with Prolog-10 `;' may also be used
to represent \fIor\fR.
.NH 2
Declarative And Procedural Semantics
.LP
The semantics of definite clauses should be fairly clear from the
informal  interpretations already given.  However it is useful to have
a precise definition.  The \fIdeclarative semantics\fR of  definite  clauses
tells  us  which  goals  can be  considered true according to a given
program, and is defined recursively as follows.
.LP
A goal is \fItrue\fR 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 \fIinstance\fR of a clause (or term) is
obtained  by  substituting,  for each of zero or more of its
variables, a new term for all occurrences of the variable.
.LP

For example, if a program contains the  preceding  procedure  for
\&`append', then the declarative semantics tells us that:

.ce
append([a], [b], [a, b])

is true, because this goal is the head of a certain  instance  of  the
first clause for `append', namely,

.ce
append([a], [b], [a, b]) :\- append([], [b], [b]).

and we know that the only goal in the body of this clause instance  is
true,  since it is an instance of the unit clause which is the second
clause for `append'.
.LP
Note that the declarative semantics makes  no  reference  to  the
sequencing of goals within the body of a clause, nor to the sequencing
of clauses within a program. This sequencing information is, however,
very relevant  for  the  \fIprocedural semantics\fR  which Prolog gives to
definite clauses.  The procedural semantics defines  exactly how  the
Prolog  system  will execute a goal, and the sequencing information is
the means by which the Prolog programmer directs the system to execute
his  program in a sensible way.  The effect of executing a goal is to
enumerate, one by one, its true instances.  Here then is  an informal
definition of the procedural semantics.
.LP
To \fIexecute\fR a goal, the system searches for the first  clause
whose   head   \fImatches\fR or  \fIunifies\fR  with  the goal. The
\fIunification\fR process finds the  most  general
common  instance  of  the  two  terms, which is unique if it
exists. If a match is found, the matching  clause  instance
is  then \fIactivated\fR by executing in turn, from left to right,
each of the goals (if any) in its body. If at any time the
system  fails to find a match for a goal, it \fIbacktracks\fR, ie.
it rejects the most recently activated clause,  undoing any
substitutions made by the match with the head of the clause.
Next it reconsiders the original goal  which  activated the
rejected clause, and tries to find a subsequent clause which
also matches the goal.
.LP
For example, if we execute the goal expressed by the question:

.ce
append(X, Y, [a, b]) ?

we  find  that  it  matches  the  head  of  the   first   clause   for
\&`append', with X instantiated to [a,@..X1]. The new variable X1 is
constrained by the new goal produced, which is the recursive procedure
call:

.ce
append(X1, Y, [b])

Again  this  goal  matches  the  first  clause,  instantiating  X1  to
[b,@..X2], and yielding the new goal:

.ce
append(X2, Y, [])

Now this goal will only match the second clause, instantiating both X2
and  Y to []. Since there are no further goals to be executed, we have
a solution:
.DS I
X = [a, b]
Y = []
.DE
ie.  a true instance of the original goal is:

.ce
append([a, b], [], [a, b])

If this solution is rejected, backtracking will generate  the  further
solutions:
.DS I
X = [a]
Y = [b]

X = []
Y = [a, b]
.DE
in that order, by re\-matching, against the second clause for `append',
goals already solved once using the first clause.
.NH 2
The Cut Symbol
.LP
Besides the sequencing of goals and clauses, Prolog provides  one
other  very  important  facility  for  specifying control information.
This is the \fIcut\fR symbol, written `!'. It is  inserted in  the  program
just like  a  goal, but is not to be regarded as part of the logic of
the program and should be ignored as far as the declarative  semantics
is concerned.
.LP
The  effect  of the  cut  symbol  is  as  follows.   When  first
encountered  as  a  goal,  cut  succeeds immediately.  If backtracking
should later return to the cut, the effect  is  to  fail  the  `parent
goal',  ie.  that goal which matched the head of the clause containing
the cut, and caused the clause to be activated.  In other  words,  the
cut  operation \fIcommits\fR the system to all choices made since the parent
goal was invoked, and causes other alternatives to be discarded.   The
goals  thus  rendered  `determinate' are  the parent goal itself, any
goals occurring before the cut in the clause containing the  cut,  and
any  subgoals  which were  executed during the  execution of those
preceding goals.
Examples:
.DS I
(1)     member(X, [X, ..L]) :\- !.
        member(X, [Y, ..L]) :\- member(X, L).
.DE
The only result produced by executing:

.ce
member(X, [a, b, c]) ?

is X@=@a, the other two potential solutions being discarded.
.DS I
(2)     compile(S, R) :\- parse(S, T), !, translate(T, R).
.DE
The procedure `compile' only calls `translate' for the first solution
produced by `parse'. Alternative solutions which `parse' might produce
are discarded.
.NH 2
Operators
.LP
The Prolog syntax caters for operators  of  three  main kinds  \-
infix, prefix and postfix.  Each operator has a \fIprecedence\fR, which is a
number from  1  to  1200.  The  precedence  is  used to  disambiguate
expressions  where  the  structure  of  the  term  denoted is not made
explicit through the use  of  brackets.   The  general  rule,  in  an
otherwise ambiguous subexpression, is that it is the operator with the
HIGHEST precedence that is the principal functor.  Thus if `+'  has  a
higher precedence than `/', then

.ce
a+b/c     a+(b/c)

are equivalent. Note that parentheses are necessary if you wish to write:
.ce
(a+b)/c
.LP
If there are two operators in the subexpression having  the  same
highest  precedence, the ambiguity must be resolved from the \fItypes\fR of
the operators.  The possible types for an infix operator are:

.ce
xfx     xfy     yfx
.LP
With an operator of type `xfx', it is a requirement that both  of  the
two  subexpressions which are the arguments of the operator must be of
LOWER precedence  than  the  operator  itself,  ie. their  principal
functors  must  be  of  lower  precedence, unless the subexpression is
explicitly  bracketed  (which  gives it  zero  precedence). With  an
operator of type `xfy', only the first or left-hand subexpression must
be of lower precedence;  the second can be of the SAME  precedence  as
the main operator;  and vice versa for an operator of type `yfx'.
.LP
For example, if the operators `+' and `\-' both  have  type  `yfx'
and are of the same precedence, then the expression:

.ce
a \- b + c
is valid, and means:

.ce
(a\-b)+c

Note that the expression would be invalid if the  operators  had  type
\&`xfx', and would mean:

.ce
a\-(b+c)

if the types were both `xfy'.
.LP
The possible types for a prefix operator are:

.ce
fx    fy

and for a postfix operator they are:

.ce
xf    yf

The meaning of the types should be clear by  analogy with  those  for
infix  operators.   As  an example, if `\-' were declared as a prefix
operator of type `fy', then:
.ce
\- \- P

would be permissible. If  the  type  were
\&`fx', the preceding expression would not be legal, although:

.ce
\- P

would still be a permissible form.
.LP
In UNSW@Prolog, a functor named \fIname\fR is declared  as  an
operator of type \fItype\fR and precedence \fIprecedence\fR by the command:

.ce
op(\fIprecedence, type, name\fR)!

The argument \fIname\fR can also be a list of names of operators of the same
type and precedence.
.LP
It is possible to have more than one operator of the  same  name,
so long as they are of different kinds, ie.  infix, prefix or postfix.
An operator of any kind may be redefined by a new declaration  of  the
same kind. This  applies equally to operators which are provided as
\fIstandard\fR in UNSW@Prolog, namely:
.DS I
op(1200, xfx, :\-)!
op(1200,  fx, [:\-, ?\-])!
op(1200,  xf, [?, !])!
op(1100, xfy, ['\||\|', ';'])!
op(1050, xfy, ->)!
op(700,  xfx, [=, ==, /=, is, <, >, <=, >=])!
op(700,   fx, [load, unload, trace, untrace, ed, ef, em])!
op(500,  yfx, [+, \-])!
op(500,   fx, [+, \-])!
op(400,  yfx, [*, /])!
op(300,  xfx, mod)!
.DE
Note that the  arguments  of  a  compound  term  written  in
standard  syntax must be expressions of precedence BELOW 1000. Thus it
is necessary to bracket the expression `P:\-Q' in:

.ce
assert((P:\-Q))


.LP
Note carefully the following syntax restrictions, which serve  to
remove potential ambiguity associated with prefix operators.
.br
(1) In a term written in standard syntax, the  principal  functor  and
its  following  `('  must  NOT be separated by any intervening spaces,
newlines etc.  Thus:
.ce
point@@(X, Y, Z)
is invalid syntax.
.br
(2) If the argument of a prefix operator starts with a `(',  this  `('
must be  separated  from  the operator by at least one space or other
non-printable character.  Thus:

.ce
:\-(p | q) , r.

is invalid syntax, and must be written as eg.

.ce
:\-@@(p | q) , r.

(3) If a prefix  operator  is  written  without  an  argument,  as  an
ordinary  atom,  the atom  is  treated  as  an expression of the same
precedence as the prefix operator, and  must therefore  be  bracketed
where necessary.  Thus the brackets are necessary in:

.ce
X = (?\-)
.LP
A further source of ambiguity in Prolog is  arises from the ability
to define infix and prefix operators with the same name.
In some Prolog systems, these operators would be considered identical.
In UNSW Prolog, this is not the case.
For example, in C, there is a prefix operator `++' and also a postfix
operator `++' which have slightly different functions.
If we declare:
.DS I
op(300, fx, ++)!
op(300, xf, ++)!
.DE
Then we are creating two completely distinct atoms (which
are also distinct from the atom `++' which is not an operator).
If an operator is to be referred to outside of its normal
context as a principal functor of a compound term then, the
operator must be preceded by a type name.
For example:
.DS I
X =.. [infix +, 1, 2]?
X = 1 + 2
.DE
This uses the infix operator `+' to create a new compound term
using the `univ' predicate.
Similarly:
.DS I
X =.. [prefix ++, x]?
X = ++ x

X =.. [postfix ++, x]?
X = x ++
.DE
