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