Re: Holes

[Dirk Laurie <dpl@...>]

On Thu, Dec 16, 2010 at 07:26:13PM +0200, Joshua Phillips wrote:
> On Mon 13/Dec/2010, Mark Hamburg wrote:
> > Here is another potential solution to the "holes" problem:
... 
> > 1. Define a new value type HOLE or NIL or NULL or whatever. 
> This will cause a large amount of complication, just to change the
> behaviour of the '#' operator on tables, and some of the table
> functions, without actually changing them.
> 
> You want to create a new type with a value that behaves as non-nil, and
> yet is almost completely invisible. This is bound to make debugging fun!
> If the HOLE type is made visible to Lua code, then it wouldn't be so
> bad... but then you can use an existing type, like false, or a
> particular table value (create an empty table and use it as a unique
> value), depending on what is needed.
> 
> Perhaps a better idea to solve the '"holes" problem' is to store the
> largest number key with each table, so that table.maxn can be O(1),
> but adding new number keys would be a little slower.
> This will increase the space overhead of each table though, which might
> hurt performance elsewhere.
> 

Summary of the thread as I see it:

1. The '#' operator is designed for use with tables whose numeric keys
    have no holes.  Everybody agrees that in that case it does exactly
    what is needed.
2. When applied to a table that does not contain holes, the '#' operator
    may nevertheless be applied, but its result is no longer easily
    predictable.  It has the not totally useless property that t[#t+1] 
    is nil, but either #t is 0 or t[#t] is nil.
3. In the applications favoured by the posters, that property of '#' is
    totally useless, and they either want the next version of Lua to
    change the meaning of '#', or to offer an additional function that
    happens to coincide with the one that would be useful for their
    particular application.
4. The most popular candidates for this new function or alternative '#'
    are (1) actual number of non-nil numeric keys (2) largest non-nil
    numeric key ever assigned (3) largest non-nil numeric key actually
    still present (as '#'; it is already available as table.maxn) 
    (4) largest non-nil numeric key before the first hole.
5. table.maxn as well as (4) require O(n) algorithms.
6. Some posters seem to think that there is an exploitable distinction
    between a non-existent key k in a table t, and a key k for which an
    actual value 'nil' has been stored in a real memory location t[k].


Quotes from "Programming in Lua, 2nd edition" that I deem relevant:

1. "Therefore, you should avoid using the length operator on arrays
    that may have holes." -- p16
2. "Lua gives you the power; you build the mechanism." -- p115
3. "The default value of any field in a regular table is nil.  It is
    easy to change this default value with metatables." -- p124
4. "The table library comprises auxiliary functions to manipulate
    tables as arrays." -- p171


Conclusions:

1. No example based on demonstrating capricious behaviour of the length 
    operator or a function from the table library when applied to an 
    array with holes proves anything more than that an attempt has been 
    made to do something Roberto has specifically warned against.
2. All these brilliant suggestions can be implemented totally within
    Lua itself without changing the specification of the language.


Dirk