Prolog infix operators of same precedence one xfy and the other yfx with two sequential operators

1k views Asked by At

In trying to understand just infix operators of the type xfy and yfx with the same precedence and in sequence I see that there are just four combinations.

using

a = xfy  right-associative
b = yfx  left-associative

There is

aa  e.g. 1 xfy 2 xfy 3   e.g. 1 ^ 2 ^ 3
ab  e.g. 1 xfy 2 yfx 3  
ba  e.g. 1 yfx 2 xfy 3  
bb  e.g. 1 yfx 2 yfx 3   e.g. 1 - 2 - 3

Now for (xfy xfy) aa the operators are both right associative.
For (yfx yfx) bb the operators are both left associate.

However for (xfy yfx) ab the (xfy) a operator is right associative and the (yfx) b operator is left associative. If I understand this correctly Prolog will evaluate this as:

Using a priority of 500 and x meaning < and y meaning <=

    xfy
    500
<500  <=500
  /     \
 1      yfx
        500
        / \
       2   3

and for (yfx xfy) ba I would expect

      500
      yfx
  <=500  <500
    /     \
  xfy      3
  500
  / \
 1   2

yet the ISO Prolog standard reads:

An operand with the same priority as a left-associative operator which precedes that operator need only be bracketed if the principal functor of the operand is a right-associative operator.

With notation:

An operand (xfy) a with the same priority (500) as a left-associative operator which precedes that operator (yfx) b need only be bracketed if the principal functor of the operand (xfy) a is a right-associative operator.

Did I understand this correctly? If so, why does (xfy yfx) ab need to bracketed while (yfx xfy) ba does not?

Also I looked for a practical example of two operators of the same precedence with one being xfy and the other being yfx, and only found one case for Seed7 mult and tiimes. If one could provide a more practical example for ab and ba that would be appreciated.

EDIT

After reading the answer by false this is my understanding.

Since this is only about associativity, the rules using < and <= do not apply.
Instead we use the meaning of Y = Yes, X = No.

Unbracketed term  Yes/No                 Equivalent bracketed term
--------------------------------------------------------------------------------------
1 xfy 2 xfy 3     1 No|Yes 2 No|Yes 3    1 xfy (2 xfy 3)     ** right-associative
1 xfy 2 yfx 3     1 No|Yes 2 Yes|No 3    1 xfy (2 yfx 3)     ** this is a special!
1 yfx 2 xfy 3     1 Yes|No 2 No|Yes 3    --------------      ** invalid: noone wants association
1 yfx 2 yfx 3     1 Yes|No 2 Yes|No 3    (1 yfx 2) yfx 3     ** left-associative

EDIT

In looking for an example that has xyf and yfx of the same priority that makes sense I found Meta-Interpreters which defines op(500,xfy,<==).

Valid
3 <==    1 +      2  
3 xfy    1 yfx    2  
3 No|Yes 1 Yes|No 2  

Invalid
1 +      2 <==    3
1 yfx    2 xfy    3
1 Yes|No 2 No|Yes 3

Valid and makes sense.
(1 + 2) <== 3
Prec 0  xfy Prec 0

Valid but does not make sense.
1       +  (2 <== 3)
Prec 0 yfx Prec 0

While the examples with parens are valid, it makes sense that you have to use parens to choose which one will make sense.

1

There are 1 answers

5
false On BEST ANSWER

(The notation you use is extremely confusing to me, writing operators without operands, so I will stick to the standard-notation which always shows the operators plus the arguments.)

As for associativity — and this is all about it — there is a simple rule-of-thumb. Look at the y and x meaning Yes and No. xfy "says" on its left side x. So it does not "want" to associate with operators of the same priority. And on the right side, it "says" y, thus Yes I want to associate. When there are two operators that both say yes "to each other", it is the first occurring (when reading left-to-right) which takes the second as argument. If you will, that case is handled like right associativity.

For this reason, with op(500,xfy,xfy), op(500,yfx,yfx) we have:

   Unbracketed term   Equivalent bracketed term
  -----------------------------------------------
    1 xfy 2 xfy 3        1 xfy (2 xfy 3)     ** right-associative
    1 xfy 2 yfx 3        1 xfy (2 yfx 3)     ** this is a special!
    1 yfx 2 xfy 3        --------------      ** invalid: noone wants association
    1 yfx 2 yfx 3        (1 yfx 2) yfx 3     ** left-associative

How well is that implemented? Look at this comparison starting with #147 of a similar situation. So all except SWI implement reading correctly. But for writing, there are some more systems that do not conform.

I think this clearly shows that there is rarely a situation where Prolog programmers depend on this case. In fact, the standard operator table does not have any case related to this problem.

For a real example, consider fy and yf intended to denote some bracket-like syntax. In fact, in pre-ISO time several systems had { and } defined in such a manner to be used in DCG or CLP(Q). Please note, that those two operators cannot entirely simulate "bracketing". As an example, consider

   Unbracketed term   Equivalent bracketed term
  -----------------------------------------------
    fy fy 1 yf yf       fy (fy ((1 yf) yf)

On the other hand, if one has a term of the form fy( fy(X) ) (note, it is in canonical syntax!), then X has to be either (fy)/1 or (yf)/1. Any other term would have to be rejected.