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)

names, trivial ops, variadic extensions & bitwise-= shivers@xxxxxx 24 Jul 2002 04:39 UTC

    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.

    > 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

    > That is the *core idea* underlying that part of the library.

    In one sense, the srfi "provides a name" for bitwise-const0, etc., but
    in the words of the srfi these operations are "not provided".

    In a previous email you said that providing these would be "beyond the
    pale", but now you say they are part of "the *core idea*".

    I could go either way, but I'm a little confused by your rhetoric.

Good point. Ok, let me flesh out the path from the rhetoric to the
reality. The SRFI *names* all sixteen dyadic boolean functions:
    and or nand nor xor eqv andc1 andc2 orc1 orc2
    const0 const1 arg1 arg2 not1 not2
We can then consider the Scheme procedures which lift these functions
to bitwise mappings over integers. Six of these are trivial and uninteresting,
not worth binding to Scheme identifiers. The other ten, however, are worth
providing, with standard bindings -- and they also are the ones that need
compiler- or interpreter-primitive implementations.

So we start with a core idea, flesh it out, then trim the fat. That's how I
square my rhetoric with the design.

I hope, in passing, that anyone who ever does anything with dyadic boolean
functions in the future, uses these names. Conventions are your friend, and
the more you observe them, the better they are to you.

    ... four [of the trivial ops] are associative [and hence have n-ary
    associative extensions].  Appropriate specifications (ignoring errors)
    would be:

      (define (bitwise-const0 . args) 0)
      (define (bitwise-const1 . args) -1)
      (define (bitwise-arg1 arg1 . args) arg1)
      (define (bitwise-arg2 arg1 . args)
	(if (null? args) arg1 (apply bitwise-arg2 args)))
      (define (bitwise-not1 x y) (bitwise-not x))
      (define (bitwise-not2 x y) (bitwise-not y))

    In light of its associative extension, perhaps bitwise-arg2 is a bad
    name, just as bitwise-eqv is a misleading name once you extend it to
    more than two arguments.  Maybe bitwise-arg1 and bitwise-arg2 should
    be bitwise-first and bitwise-last.

    Also, bitwise-not1 and bitwise-not2, although nonassociative, do have
    obvious extensions to n-arity (as do nand and nor), if you rename them
    to bitwise-not-first and bitwise-not-last.  The same goes for andc1,
    andc2, orc1, and orc2.

    I think I agree with your initial instinct that all associative
    operations should be variadic and all nonassociative ones should not.

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.

- There's no way to make andc1, andc2, orc1 & orc2 n-ary that fits into
  a limited but general framework. So leave them dyadic.
- If we punt the trivial ops, we don't have to fool with making *them* n-ary.
- We can make nand & nor n-ary, which is reasonable.
- Or we can retreat to the simple world of associative-only n-aries.

I'm going to stick with plan c, but would like to hear voices beyond mine
and Al Addin's.

    From: Jim Blandy <xxxxxx@red-bean.com>
    Would it also be useful to have an operation
      (bitwise-= a ...)
    in which bit i is set in the result if bit i is the same in all the
    inputs?  You can't get this function by folding, since you have to
    propagate three states for each bit: consensus 1, consensus 0, and no
    consensus.

Al Fresco gave a nice definition, synthesizing BITWISE-= from and/or/not:
    (bitwise-or (apply bitwise-and args)
                (apply bitwise-and (map bitwise-not args))))

Yeah, it's interesting to contemplate adding it. I considered it briefly. But
I decided it isn't sufficiently important to warrant inclusion. When was the
last time you needed *n-ary* BITWISE-= ? Note that it coincides with
BITWISE-EQV for the dyadic case, so we're covered there. I am also put off by
the fact that it *looks* like BITWISE=, which has the appearance of the
bitstring equality function, otherwise known as = (since bitstrings are just
integers).

You might ask, in turn: well, when was the last time you needed BITWISE-ANDC1
-- *that* made the cut. Well, yes. But that springs from this whole path I
laid out at the beginning of this msg: start with the notion of defining the
*set* of dyadic boolean functions. Throw out the *really* trivial ones,
provide all the rest, and there you are: andc1 snuck in along with and, or,
xor, eqv, nand & nor.

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.

   The library *does* provide a name for what you're calling
   bitwise-const0.  It's `0'.

Heh? (bitwise-const0 4 9 -15) => 0, but (0 4 9 -15), uh, doesn't.

I have worked comments from all this discussion into the latest version, which
I have placed at
    http://www.cc.gatech.edu/srfi/srfi-33.txt
and will soon appear at the official SRFI-33 site
    http://srfi.schemers.org/srfi-33/
once Francisco Solsona, the hardest-working editor in rock 'n roll, has
copied it over.
    -Olin