On Tuesday 12 April 2005 22:36, Patrick R. Michaud wrote:
> On Tue, Apr 12, 2005 at 09:15:13PM -0400, John Macdonald wrote:
> > On Tuesday 12 April 2005 20:45, Darren Duncan wrote:
> > > At 8:27 PM -0400 4/12/05, John Macdonald wrote:
> > > >The mathematical definition of xor for two arguments is "true if
> > > >exactly one argument is true, false otherwise".
> > >
> > > Yes.
> > >
> > > >When that gets
> > > >generalized to multiple arguments it means "true if an odd number
> > > >of the arguments are true, false otherwise".
> > >
> > > Is this the official mathematics position?
> >
> > It's simply chaining a series of 2-arg xor's together. As it happens, the
> > result of such chaining comes out as "odd number true" and has the nice
> > properties of being commutative [a xor b === b xor a] and associative
> > [((a xor b) xor c) === (a xor (b xor c))].
>
> It's entirely possible that I have my mathematics messed up here,
> but C<xor> doesn't seem to me to be entirely associative, at least not
> as I commonly think of associativity. Consider
>
> $x = (((0 xor 2) xor 4) xor 6); # ((a xor b) xor c) == 6
>
> $y = ((0 xor 2) xor (4 xor 6)); # (a xor (b xor c)) == 2
You're both messed up your math and you've mixed the boolean
xor function up with the extension of it to an array of bits that is used
for integer xor. When you xor integers, you are really xor'ing each
of the bit positions in the integers in parallel, using the boolean xor
function for each bit independently.
You can see the same boolean/integer difference in perl5 with:
(4&2) is 0
(4&&2) is 4
Meanwhile, with your example (using integer xor):
(((0 xor 2) xor 4) xor 6)
is ((2 xor 4) xor 6)
is (6 xor 6)
is 0
((0 xor 2) xor (4 xor 6))
is (2 xor (4 xor 6))
is (2 xor 2)
is 0
The same example, using boolean xor:
(((0 xor 2) xor 4) xor 6)
--> (((false xor true) xor true) xor true)
--> ((true xor true) xor true)
--> (false xor true)
--> true
((0 xor 2) xor (4 xor 6))
--> ((false xor true) xor (true xor true))
--> (true xor (true xor true))
--> (true xor false)
--> true
While boolean xor and integer xor give different results (just as boolean
and integer AND gave different results in my example above) they are
both perfectly associative.
The issue for perl, in the boolean xor case, is which particular true value
will be returned (I'd prefer 6 my self, simply by not changing the numbers
to true and false, but rather leaving them as their numerical values and then
having xor return the non-false value if there is exactly one, or returning
0 otherwise. However, *that* interpretation reduces the associativity
because adding parentheses can change which component value is returned
for a true result as shown by your example:
(((0 xor 2) xor 4) xor 6)
--> ((2 xor 4) xor 6)
--> (0 xor 6)
--> 6
((0 xor 2) xor (4 xor 6))
--> (2 xor (4 xor 6))
--> (2 xor 0)
--> 2
Both return a true value, but it is a different true value.
