Why is the Prolog ',' operator right associative, while it is processed from left to right

Viewed 147

In prolog the ',' operator is typed as xfy, so right associative, while a series of terms separated by commas will be processed left to right. Why then is the operator right associative?

3 Answers

I think it's just a terminological nuance. If we query SWI-Prolog the relevant details

?- current_op(P,A,(,)).
P = 1000,
A = xfy.

?- write_canonical((a,b,c)).
','(a,','(b,c))

we are confirmed that 'right associative' is just an (arguable?) linguistic description of the proper expression structure, that allows us to visit the term with a simple left recursion.

The logical reading is clearly appropriate: for a,b,c to be true, we need that a be true and b,c be true.

The other answer is good. Just to point out that you seem to be misunderstanding what "right associativity" means in this context. Taking the Wikipedia page, and reading there, it says (quoting out of context so make sure to read the linked article):

right-associative (meaning the operations are grouped from the right)

and this is exactly what you see in your example. The example in the intro with ~ is, again quoting:

Consider the expression a ~ b ~ c. If the operator ~ has left associativity, this expression would be interpreted as (a ~ b) ~ c. If the operator has right associativity, the expression would be interpreted as a ~ (b ~ c).

and again this is exactly what we see.

When executing a conjunction such as write(a),write(b),write(c),write(d) in Prolog, there are really two steps involved:

  1. turning the textual representation into a tree structure
  2. traversing and interpreting the tree structure

Operator associativity in Prolog only affects (1). So, depending on the associativity of the comma (and any parentheses you may have), you get different trees:

op(1000,xfy,',')     op(1000,yfx,',')
a,b,c,d.             a,b,c,d.                (a,b),(c,d).

  ,                        ,                      ,
 / \                      / \                   /   \
a   ,                    ,   d                 ,     ,
   / \                  / \                   / \   / \
  b   ,                ,   c                 a   b  c  d
     / \              / \
    c   d            a   b

The interpretation of the comma-tree structure in step (2) always proceeds depth-first, left-to-right. This is built in and cannot be changed. And since all parse trees have the same left-to-right order of their leaf nodes, the order of subgoal execution is always a,b,c,d. The semantics are not affected by operator associativity and parenthesizing.

Related