names, trivial ops, variadic extensions & bitwise-= shivers@xxxxxx (24 Jul 2002 04:39 UTC)
Re: names, trivial ops, variadic extensions & bitwise-= Alma Mater Petrofsky (24 Jul 2002 23:04 UTC)

Re: names, trivial ops, variadic extensions & bitwise-= Alma Mater Petrofsky 24 Jul 2002 23:04 UTC

> From: xxxxxx@cc.gatech.edu
>     From: Aladdin Petrofsky <xxxxxx@petrofsky.org>

>     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.
>
> Yes, as a name, XNOR generalises well to the n-ary case: I'm
> confused completely independent of the number of arguments passed to
> the function.

Right.  Clearly, NXOR would be the more logical name, since we're
NOTing the result of XOR, rather than excluding something from the
result of NOR.  In the n-ary case, NXORC would more fully indicate
that it is the NOT of the XOR of the complements of all the arguments.
(Similarly, OR and AND could be named OR and NORC, or NANDC and AND.)
Perhaps the most symmetric names would be XOR and IAND: XOR is like OR
with the both-true case excluded, and IAND is like AND with the
both-false case included.  I suggested the backwards XNOR only because
it seems that the hardware logic folks long ago settled on it.  I
suppose this is because "not or" has a handy contraction that happens
to already be in the dictionary, but getting people to accept
"nexclusive or" would be difficult.  I guess they weren't as shy about
coining the word NAND because at least "and" is a conjunction, like
"or".  (There are precedents for adding an n to an adjective, but
that's a whole nother story.)

> I hope, in passing, that anyone who ever does anything with dyadic
> boolean functions in the future, uses these names.

If one of the things that person does with dyadic boolean functions is
to extend them to be variadic, he won't want to use ARG2 as the name
of the associative LAST function, so your hope will more likely be
realized if you choose the more generic name.

> This is getting way too complicated. I guess the issue is that,
> while there are only 16 dyadic boolean functions, there are just
> lots and lots and lots of variadic boolean functions, and once we
> start considering variadics, we go right off the side of a
> cliff. Consider, for example, if we went with BITWISE-FIRST and
> BITWISE-LAST. Then mightn't we also want BITWISE-SEVENTH, and maybe
> a few more? Same reasoning applies to n-ary variants of andc1,
> andc2, orc1 and orc2 -- maybe we need andc7 and a few more. Just say
> no.

For each of the 16 dyadic functions, there are multiple ways to extend
it to be variadic.  For example, EQV can be extended to test if all
the arguments are the same; XOR can be extended to test if there is
exactly one true argument; AND can be extended to test if there is
more than one true argument; OR can be extended to test if there is no
more than one false argument.  That doesn't mean we can't choose the
single most sensible variadic extension for each dyadic function.  For
the eight associative functions, the best choice would seem to be the
result of folding the dyadic function across the arguments.  For the
other eight (which include NOR and NAND), I think the best choice
would be the simplest combination of a single not gate with a single
variadic associative gate.  Those rules lead to these specifications
for the four associative trivial operations and the eight
non-associative operations:

(define (bitwise-const0 . args) 0)
(define (bitwise-const1 . args) -1)
(define (bitwise-first n . rest) n)
(define (bitwise-last . args) (apply bitwise-first (reverse args)))

(define (bitwise-nor    . args) (bitwise-not (apply bitwise-or    args)))
(define (bitwise-nand   . args) (bitwise-not (apply bitwise-and   args)))
(define (bitwise-nfirst . args) (bitwise-not (apply bitwise-first args)))
(define (bitwise-nlast  . args) (bitwise-not (apply bitwise-last  args)))

(define (bitwise-or-cfirst  n . rest) (apply bitwise-or  (bitwise-not n) rest))
(define (bitwise-and-cfirst n . rest) (apply bitwise-and (bitwise-not n) rest))
(define (bitwise-or-clast  . args) (apply bitwise-or-cfirst  (reverse args)))
(define (bitwise-and-clast . args) (apply bitwise-and-cfirst (reverse args)))

The practice of inverting one argument of many has precedent in the
standard - and / functions.  (Okay, those functions actually invert
*all but* one argument, which is a little different.  If they had been
correctly designed to invert one argument of many then the desired
result for the one-argument case (inversion) would have naturally
resulted, rather than having to be a special case.)

> Where do these more exotic dyadic boolean functions get used? One
> example is the graphical bitblt operation, which is parameterised by
> a dyadic boolean that says how to combine the source bit with the
> destination bit.

In such systems, I thought the trivial operations (i.e. those that
ignore one or both arguments) were used at least as often as the
nontrivial asymmetric operations.

-al