Re: Bit ops on boolean arrays?

[David Manura <dm.lua@...>]

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"