Re: Lua next version

[Eduardo Ochs <eduardoochs@...>]

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
confused about this too often... 8-\

Comments welcome, cheers,
  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.
> If your app has a bug so it makes holes inadvertently, then fix your app.
>
> [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?
>
>