CODEWITHSUNDEEP
luaiterator
Garfield the Dummy
Garfield the Dummy

Reputation: 347

Is the following Lua iterator stateless?

I'm confused with the concepts of stateless iterators. As an exercise I write an iterator to print all non-empty substrings of a given string. The code is as follows.

local function iter(state, i)
    local str = state.str
    if type(str) ~= "string" or str == "" then return nil end
    if state.ending > #str then return nil end

    local start = state.start
    local ending = state.ending

    if start == ending then
        state.ending = ending + 1
        state.start = 1
    else
        state.start = start + 1
    end

    return string.sub(str, start, ending)
end

function allSubstrings(str)
    return iter, { str = str, start = 1, ending = 1 }, nil
end

for substr in allSubstrings("abcd123") do
    print(substr)
end

I use a table { str = str, start = 1, ending = 1 } as the so-called invariant state, but I have to change the fields in this table in the iter local function. So is this iterator stateless or with complex states? If it's not stateless, is there a way to implement this functionality with a stateless iterator?

Thank you.

Upvotes: 3

Views: 519

Answers (3)

Oka
Oka

Reputation: 26355

This is not a stateless iterator, and is indeed an iterator with complex state.

In stateless iterators there is only one control variable, and it should be treated as a pure value throughout the iterator.

You could consider using closures to implement this. Not quite stateless, but does use upvalues over table lookups, which should be more efficient.

local function allSubstrings (str)
    if type(str) ~= "string" or str == "" then
        return function () end -- NOP out on first iteration
    end

    local length = #str
    local start, ending = 1, 1

    return function ()
        if ending > length then return nil end

        local st, ed = start, ending

        if start == ending then
            ending = ending + 1
            start = 1
        else
            start = start + 1
        end

        return string.sub(str, st, ed)
    end
end

for substr in allSubstrings("abcd123") do
    print(substr)
end

Upvotes: 2

siffiejoe
siffiejoe

Reputation: 4271

The PIL-chapter about stateless iterators states:

As the name implies, a stateless iterator is an iterator that does not keep any state by itself. Therefore, we may use the same stateless iterator in multiple loops, avoiding the cost of creating new closures.

In code that means that both for loops in:

f, s, var = pairs( t )
for k,v in f, s, var do print( k, v ) end
for k,v in f, s, var do print( k, v ) end

should produce the same output. This only works if neither the invariant state s nor any upvalues of the iterator function f change during the iteration, or else the second for loop would have different starting conditions than the first loop.

So, no, your iterator is not a stateless iterator because you change the invariant state during iteration.

There is a way to make your iterator stateless (and the popular Lua library luafun uses this technique extensively): keep all mutable state in the loop control variable var (even if you need to allocate a fresh table in each allocation step):

local function iter( str, var )
  if type( str ) ~= "string" or str == "" then return nil end
  if var[ 2 ] > #str then return nil end
  local start, ending = var[ 1 ], var[ 2 ]
  if start == ending then
    return { 1, ending+1 }, string.sub( str, start, ending )
  else
    return { start+1, ending }, string.sub( str, start, ending )
  end
end

function allSubstrings2( str )
  return iter, str, { 1, 1 }
end

for _,substr in allSubstrings2( "abcd123" ) do
  print( substr )
end

Drawbacks are that the first iteration variable var (the loop control variable) has no useful meaning for the user of the iterator, and since you have to allocate a table for each iteration step, "avoiding the cost of creating new closures" for another loop doesn't matter much.

luafun does it anyway, because it does not have the ability to recreate an iterator tuple (it is passed via function arguments from outside code), and for some algorithms you absolutely need to run the same iteration multiple times.

An alternative to this approach would be to concentrate all mutable state in the "invariant state" s (all upvalues to f must be immutable), and provide a way to copy/clone this state for later iterations:

f, s, var = allSubstrings("abcd123")
s2 = clonestate( s )
for str in f, s, var do print( str ) end
for str in f, s2, var do print( str ) end

This is still not a stateless iterator, but it is more memory-efficient than the stateless iterator with heap-allocated loop control variable, and it allows you to restart an iteration.

Upvotes: 4

Vlad
Vlad

Reputation: 5857

PIL book calls that 'Iterators with Complex State'
http://www.lua.org/pil/7.4.html

Upvotes: 0

Related Questions