Add functions for bitwise operations

[hanche]

What new feature should Elvish have?

Now that we have os:stat returning a field perm which is a unix-style permission bit pattern, we could also use better tools to interrogate such bit patterns. Hence the need for functions like bitwise AND, OR, and friends.

Perhaps this should be restricted to non-negative integers. But it could work for arbitrary-precision negative integers, assuming that negative numbers are assumed to be represented in twos-complement form, with an implicit infinite sequence of leading 1 bits. If so, a bitwise NOT operation can also be implemented. Even if the end user is not going to use this directly for negative numbers, that could be useful for the bitwise version of AND $x (NOT $y) and similar constructs.

I don't know what would be good names for the proposed functions. But in analogy with the string comparison functions ==s, <s and so forth, one possibility is +b for bitwise OR, *b for bitwise AND, and -b for bitwise subtraction – -b $a $b … would return the bits set in $a but not in $b etc., with a unary variant for bitwise NOT. Or maybe we could just use uppercase names AND, OR, NOT?

Potentially, the operators could short-circuit just like the logical operators, so that, e.g., *b 1 2 (fail foo) would succeed and return zero.

The question of bitwise operators was briefly raised in chat by Tw on 2023-11-01.

Output of "elvish -version"

0.21.0-dev.0.20240320152034-dfe675a0b467

Code of Conduct

• I agree to follow Elvish's Code of Conduct.

[krader1961]

While I would like to see numeric bitops implemented there are considerable challenges for doing so in Elvish given its numeric model. What does it mean to perform a bitop on a rational number such as num 3/5? Should it throw an exception? What about an inexact-num (aka float64)? And while and, or, not are useful it seems to me we would also want to support shifting left and right and possibly rotation.

Perhaps this should be restricted to non-negative integers.

Why? While shifting or rotating a negative int introduces interesting questions given the Elvish numeric model simply masking such a value has a straightforward definition and implementation. And dealing with negative integers is straightforward with easily describe behavior if limited to platform ints and floats; i.e., excluding big ints and rationals. But this raises the bigger question of how to do this since, even if we limit the implementation to platform ints and floats, there is the question of how to deal with 32 versus 64 bit ints since Elvish deliberately doesn't expose that information. So we still have to deal with the fact that ints requiring more than 32 bits might be represented as "big ints". This is why I opened issue #1731 to propose that all public ints be represented as 64 bit ints if possible -- even on platforms where the native int size is 32 bits. That would allow the scope of this issue to be limited to native ints (and possibly floats) -- excluding big ints and rationals.

[xiaq]

I think bitwise operations should work for all exact integers (int and big.Int).

[xiaq]

As for naming... I would opt for more boring and verbose names in a new bitwise: module: bitwise:and, bitwise:or and so on.

[krader1961]

I think bitwise operations should work for all exact integers (int and big.Int).

I agree. It is easy and obvious how to implement bitwise "and", "or", and shift left/right for int and big.Int. Defining rotation (circular shift) for the big.Int case isn't practical, but rotation of an int is an operation rarely used outside of specialized applications such as cryptography. Its absence in Elvish is extremely unlikely to be an issue for users of the language. If and when someone points out a compelling need for an integer bitwise rotation command how to implement it can be revisited. The other bitwise ops are useful enough that implementing them is worthwhile to do as soon as possible.

[hanche]

Perhaps this should be restricted to non-negative integers.

Why? While shifting or rotating a negative int introduces interesting questions given the Elvish numeric model simply masking such a value has a straightforward definition and implementation.

When I wrote that, I wasn't sure how negative bignums relate to bitpatterns in the go language. Reading the documentation did not clarify the matter to me. In fact, reading the docs for Bits I am left with the impression that go represents bignums as the absolute value and a separate sign. And that leaves you wonder what exactly are the bits of a negative bignum?

However, I have now run some experiments putting my mind at rest. For example, it appears that the bignum –1 does have all its bits equal to 1, as one might hope. It might not be so in the implementation, but that is how it behaves when you actually call the relevant functions in the math/big module, and that is what counts.