Re: Bit ops on boolean arrays?

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

David Manura makes a useful point about the problem of using bool
arrays as table keys.  The main reason I suggested doing bit ops on
bool arrays is that at an abstract level, bit ops actually treat their
arguments as bool arrays rather than as numbers.  Their implementation
as numbers is a kludge.  Perhaps Eduardo Ochs's suggestion to
represent them as strings would work well in terms of both usability
and implementation.  The only problem I see with the string
representation is that the length of all bool arrays would have to be
a multiple of 8, although that issue could be resolved by reserving a
few bits at the beginning of the string to hold a count from 0 to 7 of
the number of bits in the last string byte that were actually in use.

Happy New Year to all,

-- Dave Slate


On Thu, 30 Dec 2010 21:54:00 -0500 David Manura <dm.lua@math2.org> wrote:

> On Thu, Dec 30, 2010 at 10:14 AM, David J. Slate <dslate@speakeasy.net> wrote:
> > Note that the concept of bool arrays [as tables] does not require
> > any change to the semantics of Lua
> 
> For one thing, tables are often not very useful as table keys.  Do you
> want to use bit arrays as table keys?  This fails even if an __eq
> metamethod is defined: t[{true,false}] = true; assert(t[{true,false}])
> ..
> 
> > 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.
> 
> I've wondered about that too, and we could continue making everything
> a nail and our "hammer" be the Lua table, like strings are for Tcl
> [1].  Therefore, eliminate the string data type from the language and
> replace it with tables of bytes, so "hello" would just be syntactic
> sugar for {104,101,108,108,111}.  Replace numbers with tables of
> booleans representing arbitrary precision numbers similar to [2].
> Eliminate the "function" data type, and just store the bytecodes,
> locals, and upvalues in a regular Lua table with a __call metamethod.
> Then in some way we'd hope to alter the Lua table implementation
> (ltable.c) to keep everything efficient "behind the scenes".  Is it
> worth it?
> 
> Lua's data types do have some important differences between them.
> Tables/functions/threads/strings/heavy-userdata are heap allocated
> (garbage collected) and in terms of error handling are subject to
> memory allocation failure, while boolean/number/light-userdata/nil
> types are very lightweight, often fitting in fixed size registers
> (typically 32 or 64 bits on a real or virtual CPU), as seen in the
> definition of TValue below.  String are immutable and have the initial
> overhead of interning, but subsequent comparisons are fast, while
> tables and functions have a unique identity (e.g. rawequal({}, {}) is
> false), which implies the above point about table keys.
> 
>   #define TValuefields	Value value; int tt
>   typedef union {
>     GCObject *gc;
>     void *p;
>     lua_Number n;
>     int b;
>   } Value;
>   typedef struct lua_TValue {
>     TValuefields;
>   } TValue;
> 
> Traditionally, bit arrays fall more closely into the same category
> here as the other lightweight types: nil, boolean, lightuserdata, and
> particularly numbers.   Lua already eliminates the distinction between
> integers and float numbers.  You could indeed utilize all 64-bits of
> one of the 64-bit light values, although you lose the convenience of
> having bit arrays, integers, and floating point numbers all be the
> same thing without any conversion.
> 
> [1] http://wiki.tcl.tk/3018
> [2] http://lua-users.org/wiki/LibrariesAndBindings - under
> "High-precision / Arbitrary precision"