next up previous contents
Next: Associativity Notation Up: Operators Previous: Postfix


We will now look at the structure of some Prolog expressions:




We assume that it is always possible to represent a Prolog expression as a tree in an unambiguous way. Is this

which corresponds to happy(jim):- (healthy(jim),wealthy(jim)) or

which corresponds to (happy(jim):- healthy(jim)),wealthy(jim). We can see that the first version is the one we have taken for granted. We describe this situation by saying that ,/2 binds tighter than :-/2.

This relates to the way we are taught to calculate arithmetical expressions in that we are told that we do multiplication before addition (unless brackets are used to override this). But there is another way to think of things: how to construct the expression tree. In this case, we choose the root to be the operator that is `loosest' (in opposition to `tightest' for computational purposes).

The issue is decided by operator precedence.

To construct a tree which describes a Prolog expression we first look for the operator with the highest precedence (this is in some sense the opposite of the way we compute a function). If this operator is an infix one, we can divide the expression into a left hand one and a right hand one. The process is then repeated, generating left and right subtrees.

We still need to decide what to do with two operators of the same precedence. Should we regard

3 - 2 - 1

as one or the other of:

and, remember, that we are not yet talking about arithmetic evaluation!

We can use brackets to distinguish

(3 - 2) -1

3 - (2 - 1)

but we have a special way of distinguishing which interpretation we wish Prolog to make. In the above arithmetic example, the left hand tree has two subtrees hanging from the root ``-''. The left hand one has ``-'' as its root while the right hand one is not so allowed. We say that this interpretation of ``-'' is left associative.

The normal interpretation of ``-'' is left associative. The common left associative operators are:

Are there any right associative operators? Yes ---consider how we are to disambiguate


where ``a'', ``b'' and ``c'' are all legal Prolog subgoals.

The answer is that ,/2 is right associative. Usually, we do not have to concern ourselves with the details of this.

In all the previous cases we have allowed exactly one subtree to have, as its root, the same operator as the ``principal'' root. We can extend this to permit operators of the same precedence. Thus, since ``+'' and ``-'' have the same precedence, we know that both operators in

3 - 2 + 1

are left associative (and legal) and therefore the expression represents
(3 - 2) +1.

Sometimes, we do not wish to permit left or right associativity. For example, obvious interpretations of:

a:- b :- c

Y is Z+1 is 3

a --> b --> c

do not readily spring to mind. Therefore we make it possible to forbid the building of expressions of this sort.

next up previous contents
Next: Associativity Notation Up: Operators Previous: Postfix

Paul Brna
Mon May 24 20:14:48 BST 1999