Vararg The Second Class Citizen

wiki

• Issue #1: Vararg Saving
• Issue #2: Combining Lists
• Issue #3: Selecting the First N Elements in List
• Issue #4: Appending One Element to a List
• Issue #5: Reversing a List
• Issue #6: The map Function
• Issue #7: The filter Function
• Issue #8: Iterating over Varargs

Issue #1: Vararg Saving

Lua 5.1 vararg (...) handling is a bit limited. For example, it doesn't permit things like this:

function tuple(...) return function() return ... end end

--Gives error "cannot use '...' outside a vararg function near '...'"

(Some comments on that are in LuaList:2007-03/msg00249.html .)

You might want to use such a function to temporarily store away the return values of a function call, do some other work, and then retrieve those stored return values again. The following function would use this hypothetical tuple function to add trace statements around a given function:

--Wraps a function with trace statements.

function trace(f)

  return function(...)

    print("begin", f)

    local result = tuple(f(...))

    print("end", f)

    return result()

  end

end



test = trace(function(x,y,z) print("calc", x,y,z); return x+y, z end)

print("returns:", test(2,3,nil))

-- Desired Output:

--   begin   function: 0x687350

--   calc    2       3       nil

--   end     function: 0x687350

--   returns:        5       nil

Still, there are ways to achieve this in Lua.

Solution: {...} and unpack

You could instead implement trace with the table construct {...} and unpack:

--Wraps a function with trace statements.

function trace(f)

  return function(...)

    print("begin", f)

    local result = {f(...)}

    print("end", f)

    return unpack(result)

  end

end



test = trace(function(x,y,z) print("calc", x,y,z); return x+y, z end)

print("returns:", test(2,3,nil))

-- Output:

--   begin   function: 0x6869d0

--   calc    2       3       nil

--   end     function: 0x6869d0

--   returns:        5

Unfortunately, it misses a nil return value since nil are not explicitly storable in tables , and particularly {...} does not preserve information about trailing nils (this is further discussed in StoringNilsInTables).

Solution: {...} and unpack with n

The following improvement on the previous solution properly handles nils:

function pack2(...) return {n=select('#', ...), ...} end

function unpack2(t) return unpack(t, 1, t.n) end



--Wraps a function with trace statements.

function trace(f)

  return function(...)

    print("begin", f)

    local result = pack2(f(...))

    print("end", f)

    return unpack2(result);

  end

end



test = trace(function(x,y,z) print("calc", x,y,z); return x+y, z end)

print("returns:", test(2,3,nil))

-- Output:

--   begin   function: 0x6869d0

--   calc    2       3       nil

--   end     function: 0x6869d0

--   returns:        5       nil

A variant noted by Shirik is

local function tuple(...)

  local n = select('#', ...)

  local t = {...}

  return function() return unpack(t, 1, n) end

end

Solution: nil Placeholders

The following approach swaps the nil's with placeholders that can be stored in tables. It's probably less optimal here, but the approach might be usable elsewhere.

local NIL = {} -- placeholder value for nil, storable in table.

function pack2(...)

  local n = select('#', ...)

  local t = {}

  for i = 1,n do

    local v = select(i, ...)

    t[i] = (v == nil) and NIL or v

  end

  return t

end



function unpack2(t)  --caution: modifies t

  if #t == 0 then

    return

  else

    local v = table.remove(t, 1)

    if v == NIL then v = nil end

    return v, unpack2(t)

  end

end



--Wraps a function with trace statements.

function trace(f)

  return function(...)

    print("begin", f)

    local result = pack2(f(...))

    print("end", f)

    return unpack2(result)

  end

end



test = trace(function(x,y,z) print("calc", x,y,z); return x+y, z end)

print("returns:", test(2,3,nil))

-- Output:

--   begin   function: 0x687350

--   calc    2       3       nil

--   end     function: 0x687350

--   returns:        5       nil

Here are more optimal implementations of pack2 and unpack2:

local NIL = {} -- placeholder value for nil, storable in table.

function pack2(...)

  local n = select('#', ...)

  local t = {...}

  for i = 1,n do

    if t[i] == nil then

      t[i] = NIL

    end

  end

  return t

end



function unpack2(t, k, n)

  k = k or 1

  n = n or #t

  if k > n then return end

  local v = t[k]

  if v == NIL then v = nil end

  return v, unpack2(t, k + 1, n)

end

See also StoringNilsInTables.

Solution: Continuation Passing Style (CPS)

Tables can be avoided if we use the Continuation passing style (CPS) ([Wikipedia]) as below. We could expect this to be a bit more efficient.

function trace(f)

  local helper = function(...)

    print("end", f)

    return ...

  end

  return function(...)

    print("begin", f)

    return helper(f(...))

  end

end



test = trace(function(x,y,z) print("calc", x,y,z); return x+y, z end)

print("returns:", test(2,3,nil))

-- Output:

--   begin   function: 0x686b10

--   calc    2       3       nil

--   end     function: 0x686b10

--   returns:        5       nil

The CPS approach was also used in the RiciLake's string split function (LuaList:2006-12/msg00414.html).

Solution: Code Generation

Another approach is code generation, which compiles a separate constructor for each tuple size. There is some initial overhead building the constructors, but the constructors themselves can be optimally implemented. The tuple function used previously can be implemented as such:

local function build_constructor(n)

  local t = {}; for i = 1,n do t[i] = "a" .. i end

  local arglist = table.concat(t, ',')

  local src = "return function(" .. arglist ..

              ") return function() return " .. arglist .. " end end"

  return assert(loadstring(src))()

end

function tuple(...)

  local construct = build_constructor(select('#', ...))

  return construct(...)

end

To avoid the overhead of code generation on each store, we can memoize the make_storeimpl function (for background see [Wikipedia:Memoization] and FuncTables).

function Memoize(fn)

  return setmetatable({}, {

    __index = function(t, k) local val = fn(k); t[k] = val; return val end,

    __call  = function(t, k) return t[k] end

  })

end



build_constructor = Memoize(build_constructor)

A more complete example of tuples implemented via code generation is in FunctionalTuples.

The code building/memoization technique and the above Memoize function are based on some previous related examples by RiciLake such as [Re: The Curry Challenge].

Note also that if your wrapped function raises exceptions, you would want to pcall as well (LuaList:2007-02/msg00165.html).

Solution: Functional, Recursive

The following approach is purely functional (no tables) and avoids code generation. It's not necessarily the most efficient as it creates a function per tuple element.

function helper(n, first, ...)

  if n == 1 then

    return function() return first end

  else

    local rest = helper(n-1, ...)

    return function() return first, rest() end

  end

end

function tuple(...)

  local n = select('#', ...)

  return (n == 0) and function() end or helper(n, ...)

end





-- TEST

local function join(...)

  local t = {n=select('#', ...), ...}

  for i=1,t.n do t[i] = tostring(t[i]) end

  return table.concat(t, ",")

end

local t = tuple()

assert(join(t()) == "")

t = tuple(2,3,nil,4,nil)

assert(join(t()) == "2,3,nil,4,nil")

print "done"

Solution: Coroutines

Another idea is with coroutines:

do

  local function helper(...)

    coroutine.yield()

    return ...

  end

  function pack2(...)

    local o = coroutine.create(helper)

    coroutine.resume(o, ...)

    return o

  end

  function unpack2(o)

    return select(2, coroutine.resume(o))

  end

end

A similar suggestion was posted in LuaList:2007-02/msg00142.html . That can be inefficient though (RiciLake notes that a minimal coroutine occupies slightly more than 1k plus malloc overhead, on freebsd it totals close to 2k, and the largest part is the stack, which defaults to 45 slots @ 12 or 16 bytes each).

It is not necessary to create a new coroutine on each call. The following approach is rather efficient, and the recursion uses a tail call:

local yield = coroutine.yield

local resume = coroutine.resume

local function helper(...)

  yield(); return helper(yield(...))

end

local function make_stack() return coroutine.create(helper) end



-- Example

local stack = make_stack()

local function trace(f)

  return function(...)

    print("begin", f)

    resume(stack, f(...))

    print("emd", f)

    return select(2, resume(stack))

  end

end

Solution: Upvalues in C Closure

Tuples can be implemented in C as a closure containing the tuple elements as upvalues. This is demonstrated in Section 27.3 of Programming In Lua, 2nd Ed [2].

Benchmarks

The speeds of the above solutions are compared in the following benchmark.

-- Avoid global table accesses in benchmark.

local time = os.time

local unpack = unpack

local select = select



-- Benchmarks function f using chunks of nbase iterations for duration

-- seconds in ntrials trials.

local function bench(duration, nbase, ntrials, func, ...)

  assert(nbase % 10 == 0)

  local nloops = nbase/10

  local ts = {}

  for k=1,ntrials do

    local t1, t2 = time()

    local nloops2 = 0

    repeat

      for j=1,nloops do

        func(...) func(...) func(...) func(...) func(...)

        func(...) func(...) func(...) func(...) func(...)

      end

      t2 = time()

      nloops2 = nloops2 + 1

   until t2 - t1 >= duration

    local t = (t2-t1) / (nbase * nloops2)

    ts[k] = t

  end

  return unpack(ts)

end



local function print_bench(name, duration, nbase, ntrials, func, ...)

  local fmt = (" %0.1e"):rep(ntrials)

  print(string.format("%25s:" .. fmt, name,

                      bench(duration, nbase, ntrials, func, ...) ))

end



-- Test all methods.

local function test_suite(duration, nbase, ntrials)

  print("name" .. (", t"):rep(ntrials) .. " (times in sec)")



  do -- This is a base-line.

    local function trace(f)

      return function(...) return f(...) end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("(control)", duration, nbase, ntrials, f, 1,2,3,4,5)

  end



  do

    local function trace(f)

      local function helper(...)

        return ...

      end

      return function(...)

        return helper(f(...))

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("CPS", duration, nbase, ntrials, f, 1,2,3,4,5)

  end



  do

    local yield = coroutine.yield

    local resume = coroutine.resume

    local function helper(...)

      yield(); return helper(yield(...))

    end

    local function make_stack() return coroutine.create(helper) end

    local stack = make_stack()

    local function trace(f)

      return function(...)

        resume(stack, f(...))

        return select(2, resume(stack))

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("Coroutine", duration, nbase, ntrials, f, 1,2,3,4,5)

  end



  do

    local function trace(f)

      return function(...)

        local t = {f(...)}

        return unpack(t)

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("{...} and unpack", duration, nbase, ntrials, f, 1,2,3,4,5)

  end



  do  

    local function trace(f)

      return function(...)

        local n = select('#', ...)

        local t = {f(...)}

        return unpack(t, 1, n)

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("{...} and unpack with n", duration, nbase, ntrials,

                f, 1,2,3,4,5)

  end



  do

    local NIL = {}

    local function pack2(...)

      local n = select('#', ...)

      local t = {...}

      for i=1,n do

        local v = t[i]

        if t[i] == nil then t[i] = NIL end

      end

      return t

    end

    local function unpack2(t)

      local n = #t

      for i=1,n do

        local v = t[i]

        if t[i] == NIL then t[i] = nil end

      end

      return unpack(t, 1, n)

    end

    local function trace(f)

      return function(...)

        local t = pack2(f(...))

        return unpack2(t)

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("nil Placeholder", duration, nbase, ntrials,

                f, 1,2,3,4,5)

  end



  do

    -- This is a simplified version of Code Generation for comparison.

    local function tuple(a1,a2,a3,a4,a5)

      return function() return a1,a2,a3,a4,a5 end

    end

    local function trace(f)

      return function(...)

        local t = tuple(f(...))

        return t()

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("Closure", duration, nbase, ntrials, f, 1,2,3,4,5)

  end



  do

    local function build_constructor(n)

      local t = {}; for i = 1,n do t[i] = "a" .. i end

      local arglist = table.concat(t, ',')

      local src = "return function(" .. arglist ..

                  ") return function() return " .. arglist .. " end end"

      return assert(loadstring(src))()

    end

    local cache = {}

    local function tuple(...)

      local n = select('#', ...)

      local construct = cache[n]

      if not construct then

        construct = build_constructor(n)

        cache[n] = construct

      end

      return construct(...)

    end

    local function trace(f)

      return function(...)

        local t = tuple(f(...))

        return t()

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("Code Generation", duration, nbase, ntrials,

                f, 1,2,3,4,5)

  end



  do

    local function helper(n, first, ...)

      if n == 1 then

        return function() return first end

      else

        local rest = helper(n-1, ...)

        return function() return first, rest() end

      end

    end

    local function tuple(...)

      local n = select('#', ...)

      return (n == 0) and function() end or helper(n, ...)

    end

    local function trace(f)

      return function(...)

        local t = tuple(f(...))

        return t()

      end

    end

    local f = trace(function() return 11,12,13,14,15 end)

    print_bench("Functional, Recursive", duration, nbase, ntrials,

                f, 1,2,3,4,5)

  end



  -- NOTE: Upvalues in C Closure not benchmarked here.



  print "done"

end



test_suite(10, 1000000, 3)

test_suite(10, 1000000, 1) -- recheck

Results:

(Pentium4/3GHz)

name, t, t, t (times in sec)

                (control): 3.8e-007 3.8e-007 4.0e-007

                      CPS: 5.6e-007 6.3e-007 5.9e-007

                Coroutine: 1.7e-006 1.7e-006 1.7e-006

         {...} and unpack: 2.2e-006 2.2e-006 2.4e-006

  {...} and unpack with n: 2.5e-006 2.5e-006 2.5e-006

          nil Placeholder: 5.0e-006 4.7e-006 4.7e-006

                  Closure: 5.0e-006 5.0e-006 5.0e-006

          Code Generation: 5.5e-006 5.5e-006 5.5e-006

    Functional, Recursive: 1.3e-005 1.3e-005 1.3e-005

done

The CPS is the fastest, followed by coroutines (both operated on the stack). Tables take a bit more time than the coroutine approach, though coroutines could be even faster if we didn't have the the select on the resume. Use of closures are a few times slower still (including when generalized with code generation) to an order of magnitude slower (if generalized with Functional, Recursive).

For a tuple size of 1, we get

name, t, t, t (times in sec)

                (control): 2.9e-007 2.8e-007 2.7e-007

                      CPS: 4.3e-007 4.3e-007 4.3e-007

                Coroutine: 1.4e-006 1.4e-006 1.4e-006

         {...} and unpack: 2.0e-006 2.2e-006 2.2e-006

  {...} and unpack with n: 2.4e-006 2.5e-006 2.4e-006

          nil Placeholder: 3.3e-006 3.3e-006 3.3e-006

                  Closure: 2.0e-006 2.0e-006 2.0e-006

          Code Generation: 2.2e-006 2.5e-006 2.2e-006

    Functional, Recursive: 2.5e-006 2.4e-006 2.2e-006

done

For a tuple size of 20, we get

name, t, t, t (times in sec)

                (control): 8.3e-007 9.1e-007 9.1e-007

                      CPS: 1.3e-006 1.3e-006 1.1e-006

                Coroutine: 2.7e-006 2.7e-006 2.7e-006

         {...} and unpack: 3.0e-006 3.2e-006 3.0e-006

  {...} and unpack with n: 3.7e-006 3.3e-006 3.7e-006

          nil Placeholder: 1.0e-005 1.0e-005 1.0e-005

                  Closure: 1.8e-005 1.8e-005 1.8e-005

          Code Generation: 1.9e-005 1.8e-005 1.9e-005

    Functional, Recursive: 5.7e-005 5.7e-005 5.8e-005

done

Notice that the times for table construction methods differ relatively little with respect to tuple size (due to the initial overhead of constructing a table). In contrast, use of closures entails run times that vary more significantly with tuple size.

Issue #2: Combining Lists

Problem: given two variable length lists (e.g. the return values of two functions, f and g, that each return multiple values), combine them into a single list.

This can be a problem because of the behavior of Lua to discard all but the first return value of a function unless it is the last item in a list:

local function f() return 1,2,3 end

local function g() return 4,5,6 end

print(f(), g()) -- prints 1 4 5 6

Besides the obvious solutions of converting the lists into objects such as tables (via the methods in Issue #1 above), there are ways to do this with only function calls.

Solution

The following combines lists recursively by prepending only one element at a time and delaying evaluation of one of the lists.

local function helper(f, n, a, ...)

  if n == 0 then return f() end

  return a, helper(f, n-1, ...)

end

local function combine(f, ...)

  local n = select('#', ...)

  return helper(f, n, ...)

end



-- TEST

local function join(...)

  local t = {n=select('#', ...), ...}

  for i=1,t.n do t[i] = tostring(t[i]) end

  return table.concat(t, ",")

end

local function f0() return end

local function f1() return 1 end

local function g1() return 2 end

local function f3() return 1,2,3 end

local function g3() return 4,5,6 end

assert(join(combine(f0, f0())) == "")

assert(join(combine(f0, f1())) == "1")

assert(join(combine(f1, f0())) == "1")

assert(join(combine(g1, f1())) == "1,2")

assert(join(combine(g3, f3())) == "1,2,3,4,5,6")

print "done"

Issue #3: Selecting the First N Elements in List

Problem: Return a list consisting of the first N elements in another list.

The select function allows selecting the last N elements in a list, but there is no built-in function for selecting the first N elements.

Solution

local function helper(n, a, ...)

  if n == 0 then return end

  return a, helper(n-1, ...)

end

local function first(k, ...)

  local n = select('#', ...)

  return helper(k, ...)

end



-- TEST

local function join(...)

  local t = {n=select('#', ...), ...}

  for i=1,t.n do t[i] = tostring(t[i]) end

  return table.concat(t, ",")

end

local function f0() return end

local function f1() return 1 end

local function f8() return 1,2,3,4,5,6,7,8 end

assert(join(first(0, f0())) == "")

assert(join(first(0, f1())) == "")

assert(join(first(1, f1())) == "1")

assert(join(first(0, f8())) == "")

assert(join(first(1, f8())) == "1")

assert(join(first(2, f8())) == "1,2")

assert(join(first(8, f8())) == "1,2,3,4,5,6,7,8")

print "done"

Note: if the number of elements is fixed, the solution is easier:

local function firstthree(a,b,c) return a,b,c end

assert(join(firstthree(f8())) == "1,2,3")  -- TEST

Code generation approaches can be based on this.

Issue #4: Appending One Element to a List

Problem: Append one element to a list.

Note that prepending one element to a list is simple: {a, ...}

Solution

local function helper(a, n, b, ...)

  if   n == 0 then return a

  else             return b, helper(a, n-1, ...) end

end

local function append(a, ...)

  return helper(a, select('#', ...), ...)

end

Note: if the number of elements is fixed, the solution is easier:

local function append3(e, a, b, c) return a, b, c, e end

Issue #5: Reversing a List

Problem: Reverse a list.

Solution

local function helper(n, a, ...)

  if n > 0 then return append(a, helper(n-1, ...)) end

end

local function reverse(...)

  return helper(select('#', ...), ...)

end

Note: if the number of elements is fixed, the solution is easier:

local function reverse3(a,b,c) return b,c,a end

Issue #6: The map Function

Problem: Implement the map [3] function over a list.

Solution

local function helper(f, n, a, ...)

  if n > 0 then return f(a), helper(f, n-1, ...) end

end

local function map(f, ...)

  return helper(f, select('#', ...), ...)

end

Issue #7: The filter Function

Problem: Implement the filter [4] function over a list.

Solution

local function helper(f, n, a, ...)

  if n > 0 then

    if f(a) then return a, helper(f, n-1, ...)

    else         return    helper(f, n-1, ...) end

  end

end

local function grep(f, ...)

  return helper(f, select('#', ...), ...)

end

Issue #8: Iterating over Varargs

Problem: Iterate over all elements in the vararg.

Solution

for n=1,select('#',...) do

  local e = select(n,...)

end

If you do not need nil elements, you can also use the following:

for _, e in ipairs({...}) do

   -- something with e

end

If you wish to use an iterator function without creating a garbage table every time, you can use the following:

do

  local i, t, l = 0, {}

  local function iter(...)

    i = i + 1

    if i > l then return end

    return i, t[i]

  end



  function vararg(...)

    i = 0

    l = select("#", ...)

    for n = 1, l do

      t[n] = select(n, ...)

    end

    for n = l+1, #t do

      t[n] = nil

    end

    return iter

  end

end



for i, v in vararg(1, "a", false, nil) do print(i, v) end -- test

-- Output:

--   1	1

--   2	"a"

--   3	false

--   4	nil

Other Comments

(none)

See Also

• LuaList:2004-08/msg00261.html "Lua 5.1+ and variable-argument tables"; including LuaList:2004-08/msg00408.html LuaList:2008-04/msg00205.html LuaList:2006-04/msg00120.html
• StoringNilsInTables - often varargs are converted to a table for manipulation since tables are first class objects, but the conversion to a table has limitations of its own, such as concerning nils and also efficiency.
• FunctionalTuples - discussion of a functional approach to implementing tuples
• One proposed solution is a new immutable tuple type -- see FeatureProposals