[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Holes
- From: Dirk Laurie <dpl@...>
- Date: Thu, 16 Dec 2010 21:14:55 +0200
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
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
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.