XOR does not work that way.

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

XOR does not work that way.

Thread Next

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

Thread Next