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

The boolean eqv function & n-ary generalisation of associative ops



    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