Proposal: change the Bits instance for Bool to align with other basic types and support branchless calculations

Gershom B gershomb at
Mon Sep 29 16:21:33 UTC 2014

On Mon, Sep 29, 2014 at 11:19 AM, David Feuer <david.feuer at> wrote:
> Do we currently have a convincing case for using *anything* in Bits
> polymorphically? As far as I can tell, the primary purpose of Bits is to
> provide a uniform interface to fast bitwise operations on short bitvectors
> (e.g., Int, Word, etc.) with enough flexibility thrown in to handle things
> like multi-word bitvectors, and a few other things with varying degrees of
> grace. Your intuition (which seems generally to be very good) obviously
> suggests otherwise. I'd be perfectly happy to put this proposal on hold for
> at least a year to let you figure out what it is that *you* think Bits
> should be, under two conditions:
> 1. We add non-short-circuiting and, or, and xor, by some names, somewhere.
> 2. We explicitly document that the short-circuiting behavior of Bits
> operations for Bool is as yet completely unspecified and subject to change
> without notice.

I don't think that bits is designed to "provide a uniform interface to
fast bitwise operations on short bitvectors". It is designed to
provide uniform operations over datatypes that can be treated as a
sequence of bits. In general, it seems to do this just fine. All
operations we define in our core libraries, should, by default, have
two properties: 1) They are efficient, 2) They are maximally defined;
i.e. they produce bottom as infrequently as possible. The latter
property, in general, should constrain the former. This proposal is to
make a default implementation violate my expectations by asking, in
the name of _sometimes_ efficiency, that it be less general than it
can be, and produce nonterminating results when _otherwise_ it might

I don't think either condition is necessary. If somebody wants "extra
strict" operations on bool, they can define those in an external
package. I don't feel it is a common enough use case to go into base.
Furthermore, I don't see explicitly documenting that something is
subject to change when it may well be that its fine and there's no
reason to change it.

I can think of three uses for the Bool instance for bits. First,
because `xor` may be a more clear name than (/=) for a use of Bool.
Second, to test a generic operation on Bits in a minimal context as a
"sanity check". Third, because I may wish to write _logical
operations_ in a manner polymorphic over my "bool-like" type. In the
first two cases, the existing behaviour is fine. In the last case, it
is a net positive.

In the continued absence of any good arguments for why we _should_
make this change, at this point I'm a firm -1.


More information about the Libraries mailing list