Re: ipairs in Lua 5.3.0-alpha

[Jan Behrens <jbe-lua-l@...>]

My initial statement was:

On Wed, 13 Aug 2014 22:33:23 +0200
Jan Behrens <jbe-lua-l@public-software-group.org> wrote:

> [...]
> because the way the for-loop works in Lua, we may only pass one Lua
> value (the second value of the triplet) as state. Unless luaB_ipairs
> creates either a closure or a table that contains the length
> information (and thus the termination point of the iteration), we
> cannot remember the length and will have to redetermine it during every
> iteration step. Creating tables or closures, however, would have an
> even greater perfomance impact.

On Thu, 14 Aug 2014 21:31:33 -0700
Tim Hill <drtimhill@gmail.com> wrote:

> 
> On Aug 14, 2014, at 8:26 PM, Jan Behrens <jbe-lua-l@public-software-group.org> wrote:
> 
> > 
> > for n = 1, 10000 do
> >  for i, v in some_func, {t, #t}, 0 do
> >    -- do something with i and v here
> >  end
> > end
> > ========================================
> > 
> > This construct will create 10000 tables (which need to be collected by
> > the garbage collector later).
> 
> So create the table outside the outer loop and re-initialize it for each pass in the inner loop.
> 
> ?Tim
> 

That would work for my example code above where I can decide where and
when to create the table (and where I know about the program behavior).

But how to create a generic function iterate_from_to(tbl, from, to) that
returns an iterator triplet which iterates from "from" to "to"?

It might look as follows (don't do this in real world programs, since
the iterator will be not re-entrant):

========================================
do
  local state = {}
  local function iteraux(s, i)
    local t, n = table.unpack(s)
    if i < n then
      i = i + 1
      return i, t[i]
    else
      return nil
    end
  end

  -- caution: the following iterator is not re-entrant
  function iterate_from_to(tbl, from, to)
    state[1] = tbl
    state[2] = to
    return iteraux, state, from - 1
  end
end

t1 = {"a", "b", "c", "d", "e", "f"}
t2 = {"alpha", "beta"}

-- this works:
for i, v in iterate_from_to(t1, 2, 4) do print(i, v) end
-- 2  b
-- 3  c
-- 4  d

-- this does not work as expected and returns only 2 rows:
for i, v in iterate_from_to(t1, 2, 4) do
  for j, w in iterate_from_to(t2, 1, 2) do
    print(i, v, j, w)
  end
end
-- 2  b  1  alpha
-- 2  b  2  beta
========================================

Of course, one could do more tricks, e.g. keep track of the level of
nested iteratons and then do something like:

========================================
do
  local state = {}
  local level = 0
  local function iteraux(s, i)
    local t = s[2*level-1]
    local n = s[2*level]
    if i < n then
      i = i + 1
      return i, t[i]
    else
      level = level - 1  -- one level less
      return nil
    end
  end

  -- caution: if a loop breaks prematurely,
  -- the following iterator is still not re-entrant
  function iterate_from_to(tbl, from, to)
    level = level + 1
    state[2*level-1] = tbl
    state[2*level] = to
    return iteraux, state, from - 1
  end
end

t1 = {"a", "b", "c", "d", "e", "f"}
t2 = {"alpha", "beta"}

-- this works:
for i, v in iterate_from_to(t1, 2, 4) do print(i, v) end
-- 2  b
-- 3  c
-- 4  d

-- this works too:
for i, v in iterate_from_to(t1, 2, 4) do
  for j, w in iterate_from_to(t2, 1, 2) do
    print(i, v, j, w)
  end
end
-- 2  b  1  alpha
-- 2  b  2  beta
-- 3  c  1  alpha
-- 3  c  2  beta
-- 4  d  1  alpha
-- 4  d  2  beta

-- this doesn't work as expected:
for i, v in iterate_from_to(t1, 2, 4) do
  for j, w in iterate_from_to(t2, 1, 2) do
    print(i, v, j, w)
    -- we want to break the inner j,w loop:
    if w == "alpha" then break end
  end
end
-- the "level" variable is not decremented on break,
-- hence resulting in an output of:
-- 2  b  1  alpha
-- (premature ending of the outer i,v loop)
========================================

Again, a correct way to deal with this would be:

========================================
do
  local function iteraux(s, i)
    local t, n = table.unpack(s)
    if i < n then
      i = i + 1
      return i, t[i]
    else
      return nil
    end
  end
  function iterate_from_to(tbl, from, to)
    return iteraux, {tbl, to}, from - 1
  end
end

t1 = {"a", "b", "c", "d", "e", "f"}
t2 = {"alpha", "beta"}

-- now this works as expected:
for i, v in iterate_from_to(t1, 2, 4) do
  for j, w in iterate_from_to(t2, 1, 2) do
    print(i, v, j, w)
    -- we want to break the inner j,w loop:
    if w == "alpha" then break end
  end
end
-- and prints three lines:
-- 2  b  1  alpha
-- 3  c  1  alpha
-- 4  d  1  alpha
========================================

So only the last approach works as expected in all cases. However, it
creates a table for each call of the "iterate_from_to" function.

I don't have any other idea for creating a re-entrant safe iterator that
doesn't create any table or closure. Even if there exists one, it might
look even more complicated than the first two examples above and be
even less efficient.


In normal programming, it might not be a big issue to create tables or
closures. I love to create them :-)  Especially in Lua!  But I wouldn't
like ipairs(...) to always create a closure or table when working on
tables or userdata values with an __ipairs metamethod.

I hope this explains my concerns better.


Regards
Jan