• Subject: Re: Lua next version
• From: Eduardo Ochs <eduardoochs@...>
• Date: Tue, 23 Jun 2009 21:21:51 -0300

Maybe we just need some terminology...
Here are some ideas:

A table T is an "array", or a "pure array", or an "array, possibly
with holes" when its non-nil entries all have keys whose values are
positive integers. See the function table.maxn
(<http://www.lua.org/manual/5.1/manual.html#pdf-table.maxn>).

A table T is a "regular array" when there is a non-negative integer,
#T (see <http://www.lua.org/manual/5.1/manual.html#2.5.5>), such
that all the non-nil entries in T have keys that are integers in the
interval [1, T.n], and for none of these integers we have T.n == nil.

A table T is an "old-styled array" when it has a field T.n whose
value is a non-negative integer, and all its other non-nil entries
have keys which are integers in the interval [1, T.n].

The "shortest array part" of a table T is composed of its entries
with keys 1, 2, ..., until just before the first nil.

The "longest array part" of a table T is composed of its entries
with keys 1, 2, ..., table.maxn(T).

The following functions (untested!) can be used to check the
pure-array-ness and the regular-array-ness of tables:

function ispurearray(T)
local n = table.maxn(T)
for k,v in pairs(T) do
if type(k) ~= "number" or k < 0 or k > n or k ~= math.floor(k) then
return false
end
end
return true
end

function isregulararray(T)
local n = 1
for k,v in pairs(T) do
if T[n] == nil then return false end
n = n + 1
end
return true
end

And these functions pack a list of arguments - including trailing
nils! - as old-styled arrays, and unpack old-styled arrays into lists:

function oldstylepack(...)
return { n=select("#", ...), ... }
end

function oldstyleunpack(T)
return unpack(T, 1, T.n)
end

For more on old-styled arrays look for the occurrences of "arg.n",
"getn" and "vararg" in <http://www.lua.org/manual/4.0/manual.html>,
and also in the old PiL: <http://www.lua.org/pil/5.2.html>.

There's another notion of "array" too... the article
<http://www.tecgraf.puc-rio.br/~lhf/ftp/doc/jucs05.pdf> explains that
nowadays Lua tables are represented internally as an "array part" plus
a "non-array part" - but as far as I know this is totally transparent
to a user working in pure Lua, and there is no way to obtain the size
of this "(internal) array part" from pure Lua... in
<http://www.lua.org/source/5.1/ltable.c.html> these parts are called
simply the "array part" and the "hash part" of the table...

One thing that is very confusing to beginners is that Lua - the
program, i.e., the interpreter, the libraries, etc - doesn't care
***AT ALL*** whether a table is or is not a pure array, a regular
array, or an old-styled array... for Lua-the-program all these things
are just tables, and table.maxn has a definite behavior on them, and #
has a behavior that is slightly less definite, but still
well-documented enough, and that is well-defined on tables whose
shortest array part and their longest array parts are the same; in
particular, #T is well-defined when T is a "regular array"...

So, we have several different notions of the "size" of a table T:

1) table.maxn(T), the size of its longest array part (including its
nil entries)

2) the size of its shortest array part;

3) #T, that may be the size of shortest array part of T, or
table.maxn(T), that is the size of its longest array part, or
some integer in between, subject to the conditions T[#T] ~= nil
and T[#T + 1] == nil;

4) the total number of keys - or key/value pairs - in T,

5) the size of its internal array part, or that size plus the size
of the "hash part", or some measure in bytes for that;

6, 7...) etc, etc...

Usually the "size" of T is #T, but the fact is that people get

Eduardo Ochs
eduardoochs@gmail.com
http://angg.twu.net/

On Tue, Jun 23, 2009 at 8:43 PM, Miles Bader<miles@gnu.org> wrote:
> bb <bblochl@arcor.de> writes:
>> The problem is the provided possibility of generating  tables with
>> holes. I do not see any indispensable advantage in making holes in
>> arrays or lists or tables involuntary - is there any advantage?  I do not
>> even see a real application for holes in any array or in any list, say
>> in any table by intention.
>
> One obvious case where holes are desired is when you're _not_ treating a
> table as an array, but simply as a key-value mapping; when you happen to
> add entries with integer keys, they may end up in the array part of the
> table -- likely resulting in holes.  In such a case you wouldn't want
> Lua to act differently than it does today (e.g., by signalling an error,
> or "filling in" the holes or something).
>
> Thus, given Lua's "transparent dual nature" tables, holes are necessary.
>
> Anyway, if your application doesn't need holes, then don't make holes.
>
> [You could ask for a "dedicated array" data type, but that would be a
> fairly big change to Lua's intentionally very simple model, and it's not
> at all clear that the result would be better.  You could also, of
> course, make your own userdata array datatype, and that would suffice in
> many cases.]
>
> -Miles
>
> --
> Come now, if we were really planning to harm you, would we be waiting here,
>  beside the path, in the very darkest part of the forest?
>
>

• Follow-Ups: