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

Re: NAND & NOR now n-ary; Bug in BITWISE-EQV? implementation

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.



> 
> > 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?  Does a 1 bit in the result mean
> that all arguments have the same value for that bit?  Or does it
> mean even-parity (odd-parity being computed by xor)?  What's your
> reference?

One reference is common lisp.  The immediate reference is the part of
the srfi that lists eqv as an associative operator, and hence the
definition of (eqv a b c) is (eqv (eqv a b) c), which is eqv to (eqv a
(eqv b c)).  It follows that xor tests for an odd number of truths and
eqv tests for an even number of falses, so either can be expressed in
terms of the other like so:

  (define (bitwise-eqv . args)
    (bitwise-not (apply bitwise-xor (map bitwise-not args))))

  (define (bitwise-xor . args)
    (bitwise-not (apply bitwise-eqv (map bitwise-not args))))

I agree with Olin (and Common Lisp) that these symmetric associative
operations are the correct base functions to include in the library.
If you want to check for an even number of truths or odd number of
falses, you can easily get that by complementing the result of one of
these two operations.

The fact that (= x1 x2 x3 ...) means (and (= x1 x2) (= x2 x3 ...))
creates a reasonable expectation that (bitwise-eqv x1 x2 x3) might
mean (bitwise-and (bitwise-eqv x1 x2) (bitwise-eqv x2 x3 ...)).  For
this reason, perhaps xnor would be a better name than eqv.  Perhaps it
would be useful to also have a bitwise= with the variadic behavior
analogous to =:

  (define (bitwise= . args)
    (bitwise-or (apply bitwise-and args)
                (apply bitwise-and (map bitwise-not args))))

-al

P.S. (bitwise-xor 3 10) is not 10.  (No, I didn't check all the
examples in the draft, so that should be done.)