Front page | perl.perl6.language | Postings from June 2009

## XOR does not work that way.

From:
Minimiscience
Date:
June 22, 2009 14:10
Subject:
XOR does not work that way.
Message ID:
35CB5738-B718-47F5-969E-35F9E6B02C2C@gmail.com
```S03 describes ^^ as a "short‐circuit exclusive‐or" operator which
returns true if & only if exactly one operand is true, short
circuiting after encountering two true values.  However, this
definition is only consistent with the mathematical definition of XOR
when the operation is being performed on no more than two operands,
yet ^^ has list associativity, implying that the Synopsis's
specification applies regardless of how many expressions are being
XORed together at once.  Moreover, assuming that S03's definition only
refers to XOR with two operands would make the specification seem very
poorly written, and short-circuiting would not accomplish anything at
all.

Under the mathematical definition, a series of boolean values chained
together (for lack of a better term) with XOR associate such that the
result of a single XOR pairing is passed as an operand to the adjacent
XOR.  (Because XOR is associative in the mathematical sense, treating
it as either left-associative or right-associative will always produce
the same result.)  It can be shown that the truth of the entire
expression is *not* equivalent to whether there is exactly one true
operand but rather to whether the number of true operands is odd (cf.
"1 ^ 1 ^ 1" in C or Perl 5).  Thus, in order to determine the truth
value of such a series, the truth value of *every* operand needs to be
evaluated, and so it is impossible to short-circuit.  (Interestingly,
assuming that it processes two operands at a time, the reduce operator
[^^] implements XOR correctly for more than two operands, even if
plain ^^ does not.)  An operator which returns true if & only if
exactly one of its operands is true would be a separate operation
entirely; the closest thing I can find in mathematics (OK, on
Wikipedia) is the minimal negation operator <http://en.wikipedia.org/wiki/Minimal_negation_operator
> when its arguments have been mapped through a logical NOT.

This problem also applies to the description of the "xor" operator,
though not to the bitwise XOR operators, as they make no claims to
unorthodox behavior and the proper behavior can be inferred from the
fact that they are left-associative.  The appropriateness of the ^
junctive operator is less clear, however; while the synopses don't
seem to refer to it as an exclusive-or operation (though I could be
wrong about that), and its list associativity allows it to be viewed
as wrapping a "one()" function around all of its operands, its
similarity in spelling to ^^ and the bitwise XOR operators (especially
the historical one) could be problematic.

To summarize: either bring ^^ and xor with more than two operands in
line with the mathematical definition (possibly by just making them
left-associative and rewriting the descriptions to match), or stop
calling them "exclusive or."

-- Minimiscience
```