9.4.1 Properties of operators

By now, we have seen several times already that, in certain cases, Prolog let's us use a more user friendly notation than what it will use as its internal representation. The notation for arithmetic operators was an example. Internally, Prolog will use is(11,+(2,*(3,3))), but we can write 11 is 2 + 3 * 3. Such functors that can be written in between their arguments are called infix operators. Other infix operators in Prolog are for example :-, -->, ;, ',', =, =.., == and so on. Infix operators are called infix operators, because they are written between their arguments. There are also prefix operators that are written before their argument, and postfix operators which are written after their argument. ?- for example is a prefix operator, and so is the one-place - which is used to represent negative numbers as in 1 is 3 + -2.

When we learned about arithmetic in Prolog, we saw that Prolog knows about the conventions for disambiguating arithmetic expressions. So, when we write 2 + 3 * 3 for example, Prolog knows that we mean 2 + (3 * 3) and not (2 + 3) * 3. But how does Prolog know this? Every operator has a certain precedence. The precedence of + is greater than the precedence of *. That's why + is taken to be the main functor of the expression 2 + 3 * 3. (Note that Prolog's internal representation +(2,*(3,3)) is not ambiguous.) Similarly, the precedence of is is higher than the precedence of +, so that 11 is 2 + 3 * 3 is interpreted as is(11,+(2,*(3,3))) and not as +(is(11,2),*(3,3)) (which wouldn't make any sense, by the way). In Prolog precedence is expressed by numbers. The higher this number, the greater the precedence.

But what happens when there are several operators with the same precedence in one expression? We said that above that Prolog finds the query 2 =:= 3 == =:=(2,3) confusing, because it doesn't know how to bracket the expression (is it =:=(2,==(3,=:=(2,3))) or is it ==(=:=(2,3),=:=(2,3))?). The reason for why Prolog is not able to decide which is the correct bracketing is of course that == and =:= have the same precedence.

What about the following query, though?

?- X is 2 + 3 + 4.

Does Prolog find it confusing? No, Prolog correctly answers X = 9. So, which bracketing did Prolog choose: is(X,+(2,+(3,4))) or is(X,+(+(2,3),4))? It chose the second one as can be tested with the following queries.

?- 2 + 3 + 4 = +(2,+(3,4)).
?- 2 + 3 + 4 = +(+(2,3),4).

Prolog uses information about the associativity of + here to disambiguate the expressions. + is left associative, which means that the expression to the right of + must have a lower precedence than + itself, whereas the expression on the left may have the same precedence as +. The precedence of an expression is simply the precedence of its main operator or 0, if it is enclosed in brackets. The main operator of 3 + 4 is +, so that interpreting 2 + 3 + 4 as +(2,+(3,4)) would mean that the expression to the right of the first + has the same precedence as + itself, which is illegal. It has to be lower.

The operators ==, =:=, and is are defined to be non-associative which means that both of their arguments must have a lower precedence. Therefore, 2 =:= 3 == =:=(2,3) is illegal, since no matter how you bracket it, you'll get a conflict: 2 =:= 3 has the same precedence as ==, and 3 == =:=(2,3) has the same precedence as =:=.

The type of an operator (infix, prefix, or postfix), its precedence, and its associativity are the three things that Prolog needs to know to be able to translate the user friendly, but potentially ambiguous operator notation into Prolog's internal representation.

Patrick Blackburn, Johan Bos and Kristina Striegnitz
Version 1.2.5 (20030212)