Bit ops on boolean arrays?

["David J. Slate" <dslate@...>]

Here is another idea about how to do bitwise operations in Lua:

A long time ago, in a galaxy far, far away, I used to write computer
programs to play chess.  Since then I have turned my attention to more
serious computer applications, primarily in the area of machine
learning, pattern recognition, and predictive analytics.  I discovered
Lua after it reached Version 5.1, and have found it to be both a very
nice language in general, and also a convenient and powerful tool for
interfacing to my core data analysis system, which is written in ANSI
C for efficiency.

Now I see that the upcoming Version 5.2 will include the library
"bit32" for supporting bit operations on integers.  Back in my
computer chess days, I (and numerous other chess programmers) used a
data structure called a "bit board" to represent subsets of the 64
squares on a chess board.  A bit board might represent all squares
occupied by white pawns, all squares attacked by the black queen, all
squares to which the white king can legally move, and so on, and
various concepts related to move generation and position evaluation
could be implemented using set-theoretic operations on bit boards.
Bit boards are conveniently implemented as 64-bit integers, and set
operations on them such as "and", "or" "xor", "complement", and
possibly element count as well, map directly to hardware instructions
for high efficiency.

Actually, since my chess programs imposed an order on the squares (by
ranks from "1" to "8" and within ranks by files from "a" to "h"), my
bit boards are better thought of as fixed-length arrays of boolean
values rather than sets.  This ordering meant that there were other
useful operations, such as finding the next square in a sparse set, or
mapping elements from one rank or file to another, which could usually
be represented efficiently in the hardware by bit shifting operations
and some kind of "leading zero count" instruction.

The point of all this is to suggest that a library of bit operations
in Lua could be designed that operated on arrays of booleans rather
than on 32-bit integers.  This would have the advantage of being more
general and at a higher level conceptually.  Since boolean arrays are
already supported by Lua using its general table object, the real
question is how to implement these operations efficiently.  The ideal
would be to use the same kind of trick that allows linear arrays to be
represented as associative tables while behind the scenes their array-
style usage is noted and appropriate optimizations are performed.  It
seems to me that this would be difficult to do with these arrays of
booleans, but could be facilitated by a function that explicitly
created boolean arrays of a specified size, e.g.

	boolarray( nbits, initializer)

where initializer defaulted to an array of nbits elements, all false.
Any bool arrays so created would be implemented as bit strings using
as many machine words as necessary to store nbits elements, and
functions in the bool-array library would perform their operations on
them efficiently using the appropriate hardware instructions.  If the
user happened to change a bool array into something else, by adding a
key outside the range of integers from 1 to nbits or by adding a non-
boolean value, then the array would be converted into an ordinary
array or table.

Note that the concept of bool arrays does not require any change to
the semantics of Lua, but would presumably require some changes to the
core code to support the bit-string implementation.

Any thoughts on the desirability or feasibility of this idea?

Thanks,

-- Dave Slate