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.
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.
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.
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.
Written by Eddy.