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

[Anthony Cowley]

Part of what distinguishes Bits here is specifically what we're discussing. There is some level of agreement that there should be a non-short-circuiting operation on Bool somewhere, and the proposal points out that such a thing fits into Bits quite well because it is consistent with other Bits instances. It happens that this also suits my intuition about the use of bitwise operations, and that turning to Bits suggests that the programmer is digging a bit deeper into a representation than is perhaps usual. Since different folks have different intuitions, however, I think a vote is the only useful way forward.

To be clear, I very much like the idea of having generalized and- (and or-)like operations that are short-circuiting, and appreciate that the dearth of operator symbols is a nuisance (my EDSLs are indeed littered with various and'-ish corruptions). But it is not apparent to me that the right solution should involve a redesign of Bits as you've sketched. This is hard, though: while I sympathize with you not wanting to moot your future proposal yet, this veers rather close to a kind of individual veto power that I'm not sure is fair. I don't think there is any specific rush for the original proposal, so would it be possible to try to tackle both of these issues in the near future so that we might aim for a better holistic solution?

Anthony


> On Sep 29, 2014, at 10:46 AM, Edward Kmett <ekmett at gmail.com> wrote:
> 
> We currently as a culture tolerate wildly varying strictness in Num's (+), Applicative's (<*>), Monoid's mappend, etc.
> 
> Keep in mind the strictness analyzer isn't going to see through those (or this) when you are working polymorphically.
> 
> Should we require every Monoid's mappend to be strict in both to maybe get a few percentage points improvement on fold when you have a strict container? 
> 
> After all only finitary containers exist, right?
> 
> But you can foldMap over an infinite list with the subset of Monoids that are lazy in their right argument. Folks don't seem to have a problem employing Foldable/Monoid in this scenario in practice, or using foldr to build a lazy natural when they want to do a lazy list length comparison for a list that might be infinite.
> 
> What distinguishes Bits in this regard?
> 
> -Edward
> 
>> On Mon, Sep 29, 2014 at 10:14 AM, Anthony Cowley <acowley at seas.upenn.edu> wrote:
>> On Sun, Sep 28, 2014 at 11:06 PM, Gershom B <gershomb at gmail.com> wrote:
>> > Did I miss in this thread an actual use-case for strict and/or for Bool such that it might occur in a tight inner loop? Absent such a use case, I’m -1 on this proposal. If I wanted to use something that I felt had strict bitwise behaviour, I’d never reach for a bool, no matter what operator set I was working with. My instinct would be to reach for a Word8 or the like, since on any real implementation it would take up the same space regardless?
>> >
>> > Essentially, to my laziness-infected brain, the current instance obeys the principle of least surprise, and the proposed instance violates the sort of wall of “abstraction intuitions” I’ve built up regarding when I should and shouldn’t expect lazy behaviour.
>> >
>> > -g
>> 
>> The problem is that Bool is the odd duck with respect to the Data.Bits
>> operations, so the only way your intuition would serve you is if you
>> were sure you would only be working with Bool, in which case the
>> question is why you were reaching for Data.Bits.
>> 
>> Anthony
>> 
>> 
>> >
>> >
>> > On September 27, 2014 at 1:59:43 PM, David Feuer (david.feuer at gmail.com) wrote:
>> >> Currently, the (.&.) and (.|.) methods for Bool are short-circuiting,
>> >> defined like this:
>> >>
>> >> instance Bits Bool where
>> >> (.&.) = (&&)
>> >>
>> >> (.|.) = (||)
>> >>
>> >> Unlike the instances for Int, Word, etc., this gives short-circuiting
>> >> behavior (conditionally lazy in the second operand). Unfortunately, this
>> >> requires a conditional branch to implement, which can sometimes be bad.
>> >> Since (&&) and (||) are readily available to anyone who wants
>> >> short-circuiting, I propose that we use the following instead. Note that
>> >> the Bits class does not specify anything about this aspect of instance
>> >> behavior.
>> >>
>> >> x .&. y = tagToEnum# (dataToTag# x `andI#` dataToTag# y)
>> >>
>> >> x .|. y = tagToEnum# (dataToTag# x `orI#` dataToTag# y)
>> >>
>> >> The rest of the operations look like this:
>> >>
>> >> x `xor` y = tagToEnum# (dataToTag# x `xorI#` dataToTag# y)
>> >>
>> >> complement x = tagToEnum# (dataToTag# x `xorI#` 1#)
>> >>
>> >> shift x s = testBit x s
>> >>
>> >> rotate x _ = x
>> >>
>> >> -- I don't think we gain anything changing this one.
>> >> bit 0 = True
>> >> bit _ = False
>> >>
>> >> testBit x b = tagToEnum# (dataToTag# x `andI#` (dataToTag# b ==# 0#))
>> >>
>> >> bitSizeMaybe _ = Just 1
>> >>
>> >> bitSize _ = 1
>> >>
>> >> isSigned _ = False
>> >>
>> >> popCount x = I# (dataToTag# x)
>> >>
>> >> instance FiniteBits Bool where
>> >> finiteBitSize _ = 1
>> >> countTrailingZeros x = I# (dataToTag# x `xorI#` 1#)
>> >> countLeadingZeros x = I# (dataToTag# x `xorI#` 1#)
>> >> _______________________________________________
>> >> Libraries mailing list
>> >> Libraries at haskell.org
>> >> http://www.haskell.org/mailman/listinfo/libraries
>> >>
>> >
>> > _______________________________________________
>> > Libraries mailing list
>> > Libraries at haskell.org
>> > http://www.haskell.org/mailman/listinfo/libraries
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140929/5e74026b/attachment-0001.html>