NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation shivers@xxxxxx (21 Jul 2002 17:14 UTC) Re: NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation Marc Feeley (21 Jul 2002 17:45 UTC) Re: NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation Aladdin Petrofsky (21 Jul 2002 19:09 UTC) The boolean eqv function & n-ary generalisation of associative ops shivers@xxxxxx (21 Jul 2002 19:07 UTC) Re: The boolean eqv function & n-ary generalisation of associative ops Alfresco Petrofsky (21 Jul 2002 19:57 UTC)

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

```