]> Binary Operators

Binary Operators

In principle, the following denotational form is just an expression with assertions; however, I have rather a lot to say about such denotations – even merely about how they are written, much less how they are used and the theory that springs from them – so they get a page all of their own.

Although I do allow that diverse other denotational forms may be construed as binary operators, the form interposing symbols, indicating how to combine, between values is most common and gives rise to many familiar mathematical expressions. For examples of binary operators, see &unite;, &intersect; and &on; applied to relations; and read about arithmetic.

value binop value [ binop value …]

in which each value must be a (text denoting) a value; and each binop is a symbol (e.g. +, −, ×, /, \ or *) to which context has given meaning as a binary operator. The text asserts that the values the value texts denote are in fact amenable to whatever mode of combination the given binary operators expresses; it denotes a value resulting from such combination.

Where more than one binop is used, especially where they are not all the same symbol, context may specify rules for selecting a sub-text of an instance of this template, starting and ending in separate values, to be interpreted as an instance of this template (which, by construction, it is), with the larger text then treating this sub-text as a simple value, thereby leaving the larger text with fewer values and, effectively, removing the binary operators of the sub-text from the view of the larger text's parsing as a match of this template. Repeated application of such rules typically reduces each application of this template to the point where it uses a single binary operator, or only a few closely related binary operators, whose specification suffices to settle any remaining questions concerning how to evaluate the expression. The result may, all the same, support several allowed ways to evaluate the expreession, in which case the expression is potentially ambiguous (although, usually, the diverse ways to evaluate it shall all lead to equivalent answers).

The values combined are known as operands of the operators that combine them. Each value is an operand of a binop either on its right or in its left; when several values are combined, the details of which operator actually acts on which value, however, depend on how the text as a whole is broken down into sub-texts matching the present template. The values denoted by those sub-texts are also operands; in general, the number of operands is twice the number of operators, while the number of values is only one more than the number of operators.

Implicit decomposition

As noted above, when more than two values are combined, there may be several ways to read a text of this form. Each reading (as outlined above) is equivalent to enclosing a portion of the text, starting just before one value and ending just after another, in parentheses. By construction, the enclosed portion then does match the template above; and, unless the enclosure is the whole text, when it is treated as a single value, the original text matching the template, with the given sub-text read as this single value, does still match the template. Rules for how to parse a text matching the template above can thus be stated in terms of implicit enclosures of this kind – for example constraining which placements of the opening and closing parentheses are allowed or specifying how the operators are to be partitioned by the enclosures.

Some operators constrain such implicit enclosure to not open between the operator and its right operand, or to not close between the operator and its left operand; the former happens for subtraction and for the right-division operator /, while the latter happens for the left-division operator \. Such a constraint can, however, be over-ruled by an enclosure within which all operators are of higher precedence (see below) than the one imposing the constraint.

The other main constraint on the insertion of implicit enclosures is known as operator precedence and described in terms of some operators, with higher precedence, binding more tightly to their operands than others, with lower precedence. The usual example of this is that multiplicative operators bind more tightly than additive ones: a+b.c is always read as a +(b.c) because the multiplication of b and c has high precedence of the addition of a to the result of that multiplication. Where raising to a power is expressed via an operator, this in turn binds more tightly than multiplicative operators.

The implicit procedure here is, in any given sequence alternating operands and operators, to identify the most tightly binding (highest precedence) operators; these may be several binding equally tightly, several uses of the same operator or just one use of one tightly bound operator. Place parentheses around each maximal sequence that alternates operands with these operators; each such sequence begins with an operand that either has no operator to its left or has a less tightly binding operator on its left; it likewise ends with an operand that either has a less tightly binding operator or no operator on its right. All operators within each such enclosure bind equally tightly – so context still has to address how these operate, if there is more than one. The usual rules for parenthesised sub-texts then apply, causing each to be understood as a single expression; as the enclosed text matches the binary operator template, each (implicitly) parenthesised sub-text denotes a value. By this means, the most tightly binding operands are exercised in sub-texts matching the template, each of which is then understood as an operand in whatever remains of the original sequence of operands and operators; if any operators remain, some less tightly binding (lower precedence) operator is now the most tightly binding and we can repeat the process until we are left with a simple value.

When actually computing the value of an expression, this procedure leads to evaluating the more-enclosed expressions (either because they were explicitly enclosed or because of implicit enclosures induced by precedence rules) earlier than the less-enclosed ones. As a result, the decomposition into sub-texts described here is also described as controlling the evaluation order of the expression.

Different relatives

Note that comparisons look a lot like binary operator expressions, but express assertions about values where binary operator expressions (albeit possibly making some assertions in the process) denote composite values. In particular, when more than two values (hence more than one symbol) is involved, this difference in meaning makes a significant difference to the reading, between comparisons and binary operators.

For example, where a+b+c either adds a to b, then adds the result to c, or adds a to the result of adding b to c, a comparison a=b=c or a≤b<c compares a to b and b to c; it does not compare a to the result of comparing b to c, nor does it compare, to c, the result of comparing a to b. When we compare a to b, the result is (at least in principle, when decidable) either true or false; comparing true or false to c is quite a different matter from comparing b to c. (There are computer programming languages, such as C and those based on it, that model comparison operators as binary operators; such languages actually do interpret a three-way comparison as comparison of one operand wtih the truth value obtained from the other comparison. This, however, is at odds with the orthodox usage of comparisons in mathematics – which my specification of the denotational forms for comparisons follow in this regard.) So, although comparisons and binary operators have the same form, they are distinguished by context giving the relevant symbols meaning either as binary operators or as comparators – and hopefully to no one symbol as both !

Each binary operator is a symbol; it is worth noting that the words and and or act, along with the punctuator , (comma), very similarly to binary operators, combining assertions to produce assertions. However, I explicitly don't formalise that in terms of the binary operator template. Instead, the template for comparisons requires sub-texts denoting values and combines them to make an assertion, while the binary operator template wants values – not assertions – so has to be resolved first; thus all binary operators bind more tightly than any comparison. I thus treat the case of equation, where the values are asserted equal and the denotation denotes the value they both have, the same way; so all binary operators bind more tightly than equation as well as other comparisons. The assertions made by comparisons and equations can then be combined using and, or and commas – which bind more loosely, something they wouldn't be able to do were they binary operators.

Valid CSSValid XHTML 1.1 Written by Eddy.