The boolean eqv function & n-ary generalisation of associative ops
shivers@xxxxxx 21 Jul 2002 19:07 UTC
From: Marc Feeley <xxxxxx@IRO.UMontreal.CA>
> I also discovered a bug in the spec for n-ary eqv. This is true:
> (eqv i j) = (not (xor i j))
> But it does not generalise to the n-ary case. That is, it is *NOT TRUE*
> that
> (eqv i ...) = (not (xor i ...))
Are you sure? I've always thought that (eqv i ...) = (not (xor i ...)) .
What does eqv mean anyway?
EQV is the boolean equals predicate: x eqv y is true iff x=y:
x y x=y
-----------
#f #f #t
#f #t #f
#t #f #f
#t #t #t
It's pretty easy to see that this is the same as "not (x xor y)."
Ok, so far, so good.
Now draw up a little three-input / eight-row truth table, and you
will see that eqv is associative, but that its associative n-ary
generalisation is *not* the same as "(not (xor x y z))". Too bad.
x y z x=(y=z) (x=y)=z ~(x xor y xor z)
----------------------------------------------------
(#f #f #f): #f #f #t
(#f #f #t): #t #t #f
(#f #t #f): #t #t #f
(#f #t #t): #f #f #t
(#t #f #f): #t #t #f
(#t #f #t): #f #f #t
(#t #t #f): #f #f #t
(#t #t #t): #t #t #f
Now, any time we have an associative two-argument function, it's a good
idea to make it n-ary. Consider +, for example. If you see
(+ a b c)
you don't have to wonder, "Is that a+(b+c) or is that (a+b)+c?" It's the same.
(It's the same in Scheme anyway... not in C. But we digress.) It's annoying
in Scheme to ask people to write
(+ (+ a b) c)
or
(+ a (+ b c))
when there's *no distinction* and
(+ a b c)
is so much clearer and easier to read... especially when a, b & c are
complex expressions themselves. So we do the n-ary generalisation.
OK, eqv is associative, so we should go ahead and make it n-ary, so that
people can write the simpler and easier to read
(bitwise-eqv a b c d)
instead of the equivalent
(bitwise-eqv a (bitwise-eqv b (bitwise-eqv c d)))
(echhh) just as with +.
BUT, just because
(bitwise-eqv (bitwise-eqv a b) c) = (bitwise-eqv a (bitwise-eqv b c))
that does not mean that
(bitwise-eqv a b c) = (bitwise-not (bitwise-xor a b c))
It doesn't. See the truth table above.
OK?
Just for a little context, play this game: ask yourself, "How many functions
are there from two booleans to a boolean?" Go ahead; work it out. Then you will
see that SRFI 33 provides a name for every one of them, and defines one
operation for each such function mapping that function over a pair of
semi-infinite bit strings: bit x bit -> bit.
That is the *core idea* underlying that part of the library. Generalising
to n-ary bitstring ops where convenient is icing on the cake.
-Olin