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

This page is part of the web mail archives of SRFI 33 from before July 7th, 2015. The new archives for SRFI 33 contain all messages, not just those from before July 7th, 2015.

*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):