2013-05-16 – Mixfix parsing / chain-associative operators

Earlier this evening I was reading about parsing user-defined mixfix operators in Agda.

Mixfix operators are actually quite common though they are usually called something else. The Danielsson and Norell paper describes operators using a notation in which underscores are placeholders for the operands, so (using examples from C) we have

There are also circumfix operators, of which the most common example is (_) which boringly does nothing. Mathematical notation has some more fun examples, such as ceiling ⎡_⎤ and floor ⎣_⎦.

Mixfix operators have a combination of fixities. C has a few examples:

You can also regard function call syntax as a variable-arity mixfix operator :-)

The clever part of the paper is how it handles precedence in a way that is reasonably easy for a programmer to understand when defining operators, and which allows for composing libraries which might have overlapping sets of operator definitions.

One thing that their mixfix parser does not get funky about is associativity: it supports the usual left-, right-, and non-associative operators. One of my favourite syntactic features is chained relational operators, as found in BCPL and Python. (For fun I added the feature to Lua - see this and the following two patches.) You can write an expression like

    a OP b OP c OP d
which is equivalent to
    a OP b && b OP c && c OP d
except that each operand is evaluated at most once. (Though unfortunately BCPL may evaluate inner operands twice.) This is not just short-cutting variable-arity comparison because the operators can differ.

So I wonder, are there other examples of chain-associative operators? They might have a different underlying reduction operator instead of &&, perhaps, which would imply different short-cut behaviour.

Perhaps an answer would come to mind if I understood more of the category-theory algebraic functional programming stuff like bananas and lenses and what have you...

⇐ 2013-05-03 ⇐ Two compelling applications for universal surveillance ⇐ ⇒ Guilty pleasures ⇒ 2013-06-02 ⇒