[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-33@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*Subject*: The boolean eqv function & n-ary generalisation of associative ops*From*: shivers@xxxxxxxxxxxxx*Date*: Sun, 21 Jul 2002 15:07:26 -0400*Delivered-to*: srfi-33@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*In-reply-to*: <200207211714.g6LHEDo01095@xxxxxxxxxxxxxxxxxx>(shivers@xxxxxxxxxxxxx)*References*: <200207211714.g6LHEDo01095@xxxxxxxxxxxxxxxxxx>*Reply-to*: shivers@xxxxxxxxxxxxx

From: Marc Feeley <feeley@xxxxxxxxxxxxxxxx> > 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

**Follow-Ups**:**Re: The boolean eqv function & n-ary generalisation of associative ops***From:*Alfresco Petrofsky

**bitwise-=***From:*Jim Blandy

**The big picture***From:*shivers

**References**:**NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation***From:*shivers

- Prev by Date:
**Re: NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation** - Next by Date:
**Re: NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation** - Previous by thread:
**Re: NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation** - Next by thread:
**Re: The boolean eqv function & n-ary generalisation of associative ops** - Index(es):