Lua 5.1+ and variable-argument tables

[Adam D. Moss]

Hi!

I seem to recall someone (lhf?) mentioning that Lua 5.1's behaviour
might change in some way regarding the implicit creation of vararg
tables from '...' argument lists.

Are there any more details on what direction this might take in
the future? I'm currently rationalising my app's use of these
vararg tables in situations where they need to be passed to another
vararg-using function, after discovering that my app is spending
25% of its lua-time in unpack(). Since this rationalisation
involves changing a lot of code, I'd rather change things in a
way that is performant and syntax-friendly to whatever varargs
changes might be coming along.

Thanks,
--Adam

[Roberto Ierusalimschy]

Post by Adam D. Moss
I seem to recall someone (lhf?) mentioning that Lua 5.1's behaviour
might change in some way regarding the implicit creation of vararg
tables from '...' argument lists.
Are there any more details on what direction this might take in
the future? [...]

In 5.1 the "..." will be itself an expression that results in the
variable arguments of a vararg function. So, the equivalent of
<<unpack(arg)>> will be simply "...". If you really want a table
with all parameters, you can collect them with <<{...}>>.

To keep compatibility, a vararg function that does not use any "..."
will still build its arg parameter.

-- Roberto

[Adam D. Moss]

Post by Roberto Ierusalimschy

Post by Adam D. Moss
I seem to recall someone (lhf?) mentioning that Lua 5.1's behaviour
might change in some way regarding the implicit creation of vararg
tables from '...' argument lists.
Are there any more details on what direction this might take in
the future? [...]

In 5.1 the "..." will be itself an expression that results in the
variable arguments of a vararg function. So, the equivalent of
<<unpack(arg)>> will be simply "...". If you really want a table
with all parameters, you can collect them with <<{...}>>.

Thanks, that's very interesting! So as I understand it, '...'
essentially becomes a way to read the contents of a slice of
the stack.

Thanks,
--Adam

[Roberto Ierusalimschy]

'...' essentially becomes a way to read the contents of a slice of
the stack.

A very controlled way to read a very specific slice of the stack :)

-- Roberto

[Wim Couwenberg]

If you really want a table with all parameters, you
can collect them with <<{...}>>.

Unfortunately, this does not record the *number* of
arguments. A subsequent unpack call will clip at the
first nil entry. Does it make sense to add a `pack'
function to the base lib that sets the `n' field (as
the arg table did)?

--
Wim


__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

[Roberto Ierusalimschy]

Does it make sense to add a `pack' function to the base lib that sets
the `n' field (as the arg table did)?

We plan to add a function that returns its number of arguments, so
you can write

local arg = table.setn({...}, newfunction(...))

It is more verbose than a function that packs and sets n at once, but
there will be times where we do not want to pack.

We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

for i=1,newfunction(...) do
local a = select(i, ...)
dosomethingwith(a)
end

With all overheads of function calls and parameter passing, this loop
is much faster than packing the arguments, for few arguments (less than
four or five).

select is also useful for other purposes, like

local e = select(2, string.find(...))

-- Roberto

[Asko Kauppi]

I like the 'select()' approach, thumbs up!

It's better than the first(), second(), third() and so approach which I
now use, cluttering the global namespace less and still doing the work.

-ak

19.8.2004 kello 23:47, Roberto Ierusalimschy kirjoitti:

Does it make sense to add a `pack' function to the base lib that sets

Post by Roberto Ierusalimschy

the `n' field (as the arg table did)?

We plan to add a function that returns its number of arguments, so
you can write
local arg = table.setn({...}, newfunction(...))
It is more verbose than a function that packs and sets n at once, but
there will be times where we do not want to pack.
We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like
for i=1,newfunction(...) do
local a = select(i, ...)
dosomethingwith(a)
end
With all overheads of function calls and parameter passing, this loop
is much faster than packing the arguments, for few arguments (less than
four or five).
select is also useful for other purposes, like
local e = select(2, string.find(...))
-- Roberto

[Diego Nehab]

Hi,

Post by Roberto Ierusalimschy
We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

I would prefer a skip() function that simply discarded the first 'n'
arguments. Then you can enclose in () and have the effect of select().

[]s,
Diego.

[Rici Lake]

Post by Diego Nehab
Hi,

Post by Roberto Ierusalimschy
We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

I would prefer a skip() function that simply discarded the first 'n'
arguments. Then you can enclose in () and have the effect of select().

Seems like there is at least massive support for this one. (It was also
in the long missive I sent earlier, but I'll reinforce it here.)

I still prefer the functional tuples, though...

R.

[Asko Kauppi]

What are "functional tuples"...? ;P *looking stupid*

Post by Rici Lake
I still prefer the functional tuples, though...

[Rici Lake]

Sorry, I guess I should have been clearer about that. This was a thread
from some months ago.

A tuple is (for me in this context) an immutable list of objects.
Functional tuples are a representation of tuples as functions; the
function returns the tuple'd objects as a multiple return.

A simple pure-lua implementation: (leaving out the "select" feature)

function tuple(...) return function() return unpack(arg) end end
foo = tuple(2, 3, 4)
=foo()

2 3 4

But one can do it *much* more efficiently in C: the following tiny patch
is a very simple implementation, but arguably lacks sufficient
error-checking.
Implementing tail (or select, but I think tail is better) means actually
writing the tuple function instead of using lua_pushupvalues but it's
only
a couple more lines of code.

The end result is a tuple represented as a simple lua_CFunction with a
vector
of objects (but limited in size because nupvalues is a byte).

Some less simple implementations are in the mailing list archives.

R.

-------PATCH-----------
diff -r -u lua-5.0.2/src/lib/lbaselib.c
lua-5.0.2-simpletuple/src/lib/lbaselib.c
--- lua-5.0.2/src/lib/lbaselib.c 2004-03-03 19:45:13.000000000 -0500
+++ lua-5.0.2-simpletuple/src/lib/lbaselib.c 2004-05-10
10:34:32.000000000 -0500
@@ -504,6 +504,11 @@

/* }====================================================== */

+static int l_tuple (lua_State *L) {
+ lua_pushcclosure(L, lua_pushupvalues, lua_gettop(L));
+ return 1;
+}
+

static const luaL_reg base_funcs[] = {
{"error", luaB_error},
@@ -531,6 +536,7 @@
{"dofile", luaB_dofile},
{"loadstring", luaB_loadstring},
{"require", luaB_require},
+ {"tuple", l_tuple},
{NULL, NULL}
};

[Asko Kauppi]

The () enclosing is a BAAD THING. Really.

I _know_ it, and still I've messed up with it once. It should be banned
from Lua, forever! There's too many C people using Lua, and in C that
does nothing.

-ak (don't reply - this is a dejavu thread..)


20.8.2004 kello 02:03, Diego Nehab kirjoitti:

Hi,

Post by Diego Nehab

Post by Roberto Ierusalimschy
We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

I would prefer a skip() function that simply discarded the first 'n'
arguments. Then you can enclose in () and have the effect of select().
[]s,
Diego.

[Michael Roth]

Hello,

Diego Nehab wrote:

|>>We also plan a new function select(i, ...), that returns its i-th
|>>argument. So you can loop over the varargs with something like
|
|
| I would prefer a skip() function that simply discarded the first 'n'
| arguments. Then you can enclose in () and have the effect of select().

What about a more general solution:

select(i,..) --> slice(i, i, ...)
skip(i, ...) --> slice(i, ...)
first(...) --> slice(1, 1, ...)
first(i, ...) --> slice(1, i, ...)
tail(...) --> slice(2, ...)
last(...) --> slice(-1, ...)
last(i, ...) --> slice(-i, ...)


Michael Roth

[Michael Roth]

Michael Roth wrote:

| What about a more general solution:
|
| select(i,..) --> slice(i, i, ...)
| skip(i, ...) --> slice(i, ...)
| first(...) --> slice(1, 1, ...)
| first(i, ...) --> slice(1, i, ...)
| tail(...) --> slice(2, ...)
| last(...) --> slice(-1, ...)
| last(i, ...) --> slice(-i, ...)

Maybe, 'first' should be really called 'head'.

A usage of these might be...

function call(...)
return head(...)(tail(...))
end

;-)


Michael Roth

[David Given]

Michael Roth wrote:
[...]

Post by Michael Roth
Maybe, 'first' should be really called 'head'.

I'm really not keen on the idea of cluttering up the global namespace
with lots of new functions; it's full enough as it is.

As this is a low-level, fundamental feature, it does make sense to have
it part of the syntax rather than a library extension... is there any
reason why the [] operator can't be extended?

(...)[1] --- pick the first element
(...)[-1] --- pick the last element
(...)[4, 3] --- pick a range of elements

The (...) could be made implicit without introducing ambiguities, which
means that you can do things like...

for i=1, 10 do
print([i])

Which, you'll have to admit, is slightly neater than using a function,
as well as making it more obvious that you're doing something strange.

[John Belmonte]

Post by Michael Roth
select(i,..) --> slice(i, i, ...)
skip(i, ...) --> slice(i, ...)
first(...) --> slice(1, 1, ...)
first(i, ...) --> slice(1, i, ...)
tail(...) --> slice(2, ...)
last(...) --> slice(-1, ...)
last(i, ...) --> slice(-i, ...)

Excuse my old complaint about counting from 1 and closed ranges, but how
about a slice starting from i of length 0?

-John

[Roberto Ierusalimschy]

skip(i, ...) --> slice(i, ...)
first(...) --> slice(1, 1, ...)

How would you know whether the second "1" is a counter or the first
value from `...´?

-- Roberto

[Doug Rogers]

Post by Roberto Ierusalimschy

skip(i, ...) --> slice(i, ...)
first(...) --> slice(1, 1, ...)

How would you know whether the second "1" is a counter or the first
value from `...´?

Couldn't the compiler/interpreter put the proper backend in for this?

Maybe I'm missing something here. Are the dots above literals meant to
represent what is currently called 'arg', or do you intend to be able to use

Post by Roberto Ierusalimschy
print(slice(1, 2, 3, 4, 5))

3 4

Either name slice() or select() works. But I like Michael Roth's all-in-one
version to handle first, last, etc.

[Michael Roth]

Doug Rogers wrote:
| On Friday 20 August 2004 09:55, Roberto Ierusalimschy wrote:
|
|>>skip(i, ...) --> slice(i, ...)
|>>first(...) --> slice(1, 1, ...)
|
|>How would you know whether the second "1" is a counter or the first
|>value from `...´?
|
| Couldn't the compiler/interpreter put the proper backend in for this?
|
| Maybe I'm missing something here. Are the dots above literals meant to
| represent what is currently called 'arg', or do you intend to be able
to use
| 'slice()' for things such as:
|
| > print(slice(1, 2, 3, 4, 5))
| 3 4
|
| Either name slice() or select() works. But I like Michael Roth's
all-in-one
| version to handle first, last, etc.

Maybe the easist would be that the slice() needs always the start end
end position. Then you have to write -1 as the end:

select(i, ...) --> slice(i, i, ...)
skip(i, ...) --> slice(i, -1, ...)
first(...) --> slice(1, 1, ...)
first(i, ...) --> slice(1, i, ...)
tail(...) --> slice(2, -1, ...)
last(...) --> slice(-1, -1, ...)
last(i, ...) --> slice(-i, -1, ...)

and so on. In the case of index overflows an empty list should returned.


Michael Roth

[Doug Rogers]

Post by Michael Roth
Maybe the easist would be that the slice() needs always the start end

Exactly what I was thinking. Let the parser (or first(), etc.) handle which
values get put in as the first two arguments of slice().

Doug

[Edgar Toernig]

Post by Roberto Ierusalimschy
We also plan a new function select(i, ...), that returns its i-th
argument.

Could you make that "returns its i-th and all following arguments"?

Names: argn and argi? Or, plain english: count and select. Or pick?

Ciao, ET.

[Rici Lake]

Rici coughs and points out that functional tuples wouldn't have the
problem Wim pointed to, and would be a more general solution.

Outline proposal:

Possible syntax: (replace [...] with preferred punctuation if desired.)

-- make a tuple
tuple = [a, multipleReturns()]
st, fin, [caps] = string.find(str, pat)

-- get a tuple as trailing parameter
function foo(a, b, [caps])

-- expand a tuple
caps()

-- get the tail of a tuple
caps(3) -- starts with third element

-- get a particular element of a tuple
(caps(3)) -- normal Lua5 scalarization (see implementation note below)

-- syntax missing for (therefore probably library functions):
-- truncate a tuple
-- count elements in a tuple

-- Implementation notes.
This assumes that tuples are implemented as a callable object, which
does not seem completely outrageous to me; it is perhaps a tad odd that
tuples are indexed with () and tables with [] but the [] syntax
(currently) guarantees exactly one value.

The [] notation has one parsing irritation, which is that table
constructors can no longer be parsed with an LL(2) parser. The syntax
is not ambiguous, but it is not possible to know whether [...] is a
tuple array value or a computed hash key until the token following the
"]" is encountered. In some sense, this makes no difference, because in
either event the value needs to be computed and put on the stack;
however, it complicates implementation of reordering array elements. In
practice, I don't think this is much of a problem because it is fairly
rare to encounter {a, b, c = d, e}, and people who write that might
stand to be penalised by a couple of nanoseconds.

Thinking about this issue, it occurred to me that the obvious
implementation of table constructors if one didn't have the option of
rearranging assignment order was to store the "n" value in the table
header itself so that the VM opcode for adding array elements could
know where to append from. This would
likely be as fast as the current implementation, and would speed up
getn and setn a bit; it would also have the side effect of setting n
for all table constructors, which might or might not be a bad thing.
There would be a small overhead for storing the extra field in the
table header (and, irritatingly for me, an enormous overhead with the
FreeBSD allocator, which would reserve 64 bytes instead of 32 bytes for
the header; however, the dlmalloc, gnumalloc, and Windows allocators
would only incur a four-byte penalty.)

Allocating a tuple of this form is presumably slower than the stack
hack being proposed for the implementation of ... in 5.1. However, it
is significantly faster than creating a table, and it is a more
powerful construct than "..."; aside from the syntax, pretty well all
the mechanisms are in place (although the current mechanism limits the
size of a functional tuple to a fairly small number.)

The speed of allocating tuples on the heap rather than on the stack
will be related to the speed of the allocator used; I can't believe
that it would be a killer with a reasonable allocator (and you need a
reasonable allocator if you want Lua to run fast because it does a lot
of little alloc's -- upvalues spring to mind.)

Dumping the entire functional tuple (or the entire tail of the
functional tuple) looks a lot worse than it really is. In practice, one
might expect most
tuples to be reasonably small. In addition, Lua knows how many results
it is expecting, even though it does not pass this on to called
functions. Currently, the return values are on the stack at return
time, and the VM copies the desired number to the correct place (there
is always a copy because the original function slot is being
overwritten, at a minimum.) Since a functional tuple would simply be a
vector of Lua objects, this could be optimised by allowing the
functional tuple to return a pointer to its own vector instead of a
pointer to the stack; the VM would then copy only the desired number of
results from the vector. This optimisation does not look particularly
difficult to implement, and has the advantage of simplifying the
interface somewhat.

I think it might even be possible to lazily heapify tuples, but I don't
know if it would be worth it. Roughly speaking, the idea would be to
have a separate tuple stack where tuples were allocated. If a tuple was
ever either saved to a non-stack location, or a location on the stack
in a call-frame below its allocation frame (or possibly a repeat-block
frame below its allocation frame), the tuple would be heapified. Since
functional tuples as outlined above are immutable, it would not be
necessary to repoint existing stack references to the tuple. The tuple
stack would be simply truncated to its remembered location on exit from
a call-frame (or possibly repeat frame).

This same mechanism could be useful for other functional-type objects,
such as composed and curried functions.

Rici

[Edgar Toernig]

Post by Rici Lake
Rici coughs and points out that functional tuples wouldn't have the
problem Wim pointed to, and would be a more general solution.

Maybe. But the whole point of the change is to avoid allocating
a (usually short-living) heap object on each vararg-function
invocation.

Your tuple proposal just introduces a new datatype. All the
syntax extensions could equally well be implemented for tables.
Where's the tuple variant better than a regular table? Any
performance differences would only be implementation details.

Ciao, ET.

[Rici Lake]

Post by Edgar Toernig
Maybe. But the whole point of the change is to avoid allocating
a (usually short-living) heap object on each vararg-function
invocation.

I understand that. Personally I'd be more interested in an
optimisation which avoids allocating short-lived heap objects
for curried functions, for example.

The tuple proposal is an attempt to reduce the number of short-lived
heap objects created for vararg-function invocations from three to one.
That's maybe not as good as zero, but I think it has other advantages.

Post by Edgar Toernig
Your tuple proposal just introduces a new datatype. All the
syntax extensions could equally well be implemented for tables.
Where's the tuple variant better than a regular table? Any
performance differences would only be implementation details.

Well, the same could be said for the ... hack; the performance
difference is only an implementation detail. One could attempt to
optimise vararg calls through a different implementation which did
not alter the syntax at all.

Now, it's true that the tuple proposal is (more or less) a new datatype,
although it is actually implemented on top of an existing datatype
(that is, a C-function). The implementation, shorn of the new syntax,
is less than 10 lines of code.

In fact, my first thought here was, well why not just optimise tables
a bit more. That is surely possible. But functional tuples, even with a
naive implementation, turn out to be a massive performance win in a
number
of common problems.

For example, they provide a handy way to collect multiple return values,
an issue I believe you yourself noted in an earlier posting on the
subject
of ...

Also, they considerably simplify the implementation of tables which
logically
have multiple values; there are other ways of dealing with this, of
course,
but functional tuples (in my opinion) lead to cleaner implementations:
tables
of tables are of course possibly but they are bulky enough that one is
motivated to avoid them, while keeping each value in a separate table
is fast
but complicates the code.

So one question is, are functional tuples useful enough to add syntax
to the
language (and/or make some other adjustments)?

I combine that with another question: is the ... thing worth a fairly
considerable complication to the Lua core when functional tuples
provide a reasonably optimised solution to the varargs issue, along
with other issues?

On balance, my vote is with functional tuples. For what that's worth.

[Mark Hamburg]

Is it correct to summarize functional tuples as being essentially equivalent
to immutable, pure arrays -- i.e., tables that can't be changed and that
only have entries from 1 to n for some value of n?

Presumably, one could actually even have mutable tuples. You just can't
change the number of values in the tuple.

Mark

[Rici Lake]

Post by Mark Hamburg
Is it correct to summarize functional tuples as being essentially equivalent
to immutable, pure arrays -- i.e., tables that can't be changed and that
only have entries from 1 to n for some value of n?
Presumably, one could actually even have mutable tuples. You just can't
change the number of values in the tuple.

Yes, that would be the proposal.

As I mentioned at the end of the probably-too-long message from earlier
today, there are some potential optimisations which work better if the
tuple is immutable. On the other hand, there are probably some
applications (vector arithmetic springs to mind) which might like to be
able to update in place. I personally prefer the immutable flavour; but
it is certainly trivial to implement mutable tuples using the same
basic architecture, because iirc
lua_replace() works on pseudo-indices.

[marcus]

I'm +1 on tuples. It seems to me as a good generalization over parameter lists
and return lists (i like the ability to collect and unpack values without
creating tables). But i'm not sure about the details of the implemenation:
syntax, type/function names and some other things (- What about tuple
comparisons and hashing by value, like strings? - What's more useful: select or
"cdr"?)

[Edgar Toernig]

Post by Rici Lake

Post by Edgar Toernig
Maybe. But the whole point of the change is to avoid allocating
a (usually short-living) heap object on each vararg-function
invocation.

I understand that.

IMHO that's the most important point. If you accept heap allocation
during vararg-function invocation you can stick with tables. The
slight performance advantage of your tuple implementation could
be nullified by optimizing the appropriate parts of table creation.

Post by Rici Lake
Personally I'd be more interested in an
optimisation which avoids allocating short-lived heap objects
for curried functions, for example.

The currying is supposed to create a new object, isn't it?

The invocation of the curried function is another thing.
The implementation I posted some minutes ago does not allocate
any heap object when calling the curried function...

Post by Rici Lake
The tuple proposal is an attempt to reduce the number of short-lived
heap objects created for vararg-function invocations from three to one.

Hmmm... nitpicking: from the GC point of view a table is one
object (with one to three malloced areas).

Post by Rici Lake

Post by Edgar Toernig
Your tuple proposal just introduces a new datatype. All the
syntax extensions could equally well be implemented for tables.
Where's the tuple variant better than a regular table? Any
performance differences would only be implementation details.

Well, the same could be said for the ... hack; the performance
difference is only an implementation detail.

No. It's a conceptual difference. The ... "hack" is designed
to not allocate heap objects, the tuple solution is designed
to allocate a new object.

Post by Rici Lake
Now, it's true that the tuple proposal is (more or less) a new datatype,
although it is actually implemented on top of an existing datatype
(that is, a C-function). The implementation, shorn of the new syntax,
is less than 10 lines of code.

Afaics, only the syntax gives anything new. The tuples themself
give nothing new. They are only a subset of tables.

Post by Rici Lake
For example, they [tuples] provide a handy way to collect multiple
return values, an issue I believe you yourself noted in an earlier
posting on the subject of ...

I did. But it's not the tuple that makes it possible to collect
multiple return value but the new syntax.

Post by Rici Lake
I combine that with another question: is the ... thing worth a fairly
considerable complication to the Lua core when functional tuples
provide a reasonably optimised solution to the varargs issue, along
with other issues?

As I said, tuples require heap objects, the dots do not.

And I wouldn't call it a "considerable complication to the Lua core".
I can't speak about Lua5 but I added them to Sol (Lua4 based) and
it's not that hard (I simply move the varargs to the up-to-now
unused upper end of the stack).

Ciao, ET.

[Rici Lake]

Post by Edgar Toernig
IMHO that's the most important point. If you accept heap allocation
during vararg-function invocation you can stick with tables. The
slight performance advantage of your tuple implementation could
be nullified by optimizing the appropriate parts of table creation.

It's not that slight. You might be surprised. Here's a quick
pseudo-benchmark;
OS is FreeBSD 5.2.1, compiled with -O2 -fomit-frame-pointer

The tuple() function is the C version the patch for which is in an
earlier message.

I didn't hack the syntax in, so the test function calls tuple on the
arguments;

-- curried function expects a tuple

Post by Edgar Toernig
function tcurry(fn, a) return function(tup) return fn(a, tup()) end

end
-- standard varargs

Post by Edgar Toernig
function vcurry(fn, a) return function(...) return fn(a, unpack(arg))

end end
-- fixed arguments as a baseline

Post by Edgar Toernig
function fcurry(fn, a) return function(b, c, d) return fn(a, b, c, d)

end end
-- simple test function with four arguments

Post by Edgar Toernig
function f(a, b, c, d) return a, b, c, d end

-- Unfortunately, somewhat imprecise ansi-standard clock

Post by Edgar Toernig
function time(f, n)

local now = os.clock() for i = 1, n do f() end return os.clock() -

now

Post by Edgar Toernig

end

return time(function() local g = fcurry(f, 1); return g(2, 3, 4) end,

1e7)
18.421875

Post by Edgar Toernig
return time(function() local g = tcurry(f, 1); return g(tuple(2, 3,

4)) end, 1e7)
23.59375

Post by Edgar Toernig
return time(function() local g = vcurry(f, 1); return g(2, 3, 4) end,

1e7)
35.921875

So tupling is about 30% slower than the baseline, and varargs is about
twice as slow.

That was promising enough to make it worthwhile testing for real: I
changed adjust_varargs in ldo.c to the following: (this is 5.0.2)

static void adjust_varargs (lua_State *L, int nfixargs, StkId base) {
int i;
Closure *cl;
int actual = L->top - base; /* actual number of arguments */
if (actual < nfixargs) {
luaD_checkstack(L, nfixargs - actual);
for (; actual < nfixargs; ++actual)
setnilvalue(L->top++);
}
actual -= nfixargs; /* number of extra arguments */
cl = luaF_newCclosure(L, actual); /* create `arg' table */
cl->c.f = lua_pushupvalues;
for (i=0; i<actual; i++) /* put extra arguments into `arg' table */
setobj2n(&cl->c.upvalue[i], L->top - actual + i);
L->top -= actual; /* remove extra elements from the stack */
setclvalue(L->top, cl);
incr_top(L);
}

which makes arg into a tuple instead of a table. With that
modification, I got a tiny speed improvement (but the syntax is

Post by Edgar Toernig
function tcurry(fn, a) return function(...) return fn(a, arg()) end

end

Post by Edgar Toernig
function f(a, b, c, d) return a, b, c, d end
function time(f, n)

local now = os.clock() for i = 1, n do f() end return os.clock() -

now

Post by Edgar Toernig

end

return time(function() local g = tcurry(f, 1); return g(2, 3, 4) end,

1e7)
23.2109375

In short, for about 6 lines of code changed, a 35% speedup. It's hard
to imagine that the ... thing would be faster than the baseline, and
presumably the extra copying and stack management would take some time,
so we could guess that the alternative is considerably more change to
the code base for a 45% speedup. And I still say that tuples have extra
uses.

Post by Edgar Toernig
The currying is supposed to create a new object, isn't it?

Yes, but it might be a very short-lived object. Iterators and
mapping functions spring to mind.

Post by Edgar Toernig
Hmmm... nitpicking: from the GC point of view a table is one
object (with one to three malloced areas).

Well, it's only one object to mark but it's three objects to malloc()
and three objects to free(). I suspect that both malloc() and free()
take a lot more time than marking does. That's an implementation detail,
too, though. In fact, most of this is.

Post by Edgar Toernig
No. It's a conceptual difference. The ... "hack" is designed
to not allocate heap objects, the tuple solution is designed
to allocate a new object.

Whether an object is constructed on the heap or the stack is not
a conceptual difference, it is an implementation detail.

Post by Edgar Toernig
Afaics, only the syntax gives anything new. The tuples themself
give nothing new. They are only a subset of tables.

I suppose that is true. I guess I like the syntax :)

tuples differ in two ways from tables: one is that they are immutable
(in my proposal) which, in an imaginable implementation, would make them
internable and therefore quite different from tables. (Or, even if not
interned, compared by value and not by object identity.) The other
difference is that there size is fixed and known.

Post by Edgar Toernig
I did. But it's not the tuple that makes it possible to collect
multiple return value but the new syntax.

Fair enough. One could equally well propose the syntax:

a, b, {c} = f()

I would have no objections to that, really.

Post by Edgar Toernig
And I wouldn't call it a "considerable complication to the Lua core".
I can't speak about Lua5 but I added them to Sol (Lua4 based) and
it's not that hard (I simply move the varargs to the up-to-now
unused upper end of the stack).

That seems like a reasonable implementation technique.

[Mark Hamburg]

Post by Rici Lake
tuples differ in two ways from tables: one is that they are immutable
(in my proposal) which, in an imaginable implementation, would make them
internable and therefore quite different from tables. (Or, even if not
interned, compared by value and not by object identity.) The other
difference is that there size is fixed and known.

With respect to memory allocation, I think much of the benefit of tuples
could probably be gained by avoiding some trips to malloc and free by
caching particularly common object sizes. So, that argument hasn't been a
compelling reason for supporting tuples.

The notion of interned tuples, however, is quite appealing since it could
simplify and reduce the memory consumption for various things like function
result caching.

Finally, if tuples were introduced as a base concept, then I think unpack
should probably work on both tuples and tables. Similarly, ipairs should
work on tuples. At the same time, I wouldn't expect these to work on
arbitrary function closures.

Mark

[Asko Kauppi]

I was starting to think of this (implementing tuples in LuaX) and was
mentally browsing through cases where function/tuple should be
differentiated.

But it will be possible to test:

if v==tuple then -- if our value is the one and only function (don't
care of the upvalues)

and not only:

if type(v)=="function" then -- since there won't be a type "tuple"

Am I getting it right? :)

Post by Mark Hamburg
At the same time, I wouldn't expect these to work on
arbitrary function closures.

[Edgar Toernig]

Post by Rici Lake

Post by Edgar Toernig
IMHO that's the most important point. If you accept heap allocation
during vararg-function invocation you can stick with tables. The
slight performance advantage of your tuple implementation could
be nullified by optimizing the appropriate parts of table creation.

It's not that slight. You might be surprised. Here's a quick
pseudo-benchmark;
[...]
In short, for about 6 lines of code changed, a 35% speedup. It's hard
to imagine that the ... thing would be faster than the baseline, and
presumably the extra copying and stack management would take some time,
so we could guess that the alternative is considerably more change to
the code base for a 45% speedup. And I still say that tuples have extra
uses.

The problem with benchmarks :-) You're mostly testing GC performance.
Let me show some other numbers: (3rd column is GC-runs)

currying happens within the loop:
empty heap:
4args 6.94 1592
dots 7.03 1592
tuple 10.19 3496
table 14.91 5291
filled heap (with 10000 {a=1} tables):
4args 8.75 31
dots 8.88 31
tuple 13.85 69
table 21.42 105

currying outside of the loop - only actual varag handling tested:
empty heap
4args 2.48 0
dots 2.62 0
tuple 5.81 1908
table 10.57 3703
filled heap (with 10000 {a=1} tables):
4args 2.48 0
dots 2.62 0
tuple 7.34 37
table 14.26 73

-- 4args is with 4 fixed arguments (baseline)
-- dots is the new vararg method (the "... hack")
-- tuple is varargs via tuple (upvalues of c-closure)
-- table is varargs via table (with Lua4 tables - no array part)

As you can see, nearly half of the time your test spends in
creating and collecting the curried function (10.19 vs 5.81).

And while the dots are only ~2 times faster than tuples
(2.62 vs 5.81) with a nearly empty heap it gets worse when
the heap gets bigger (2.62 vs 7.34) as the dots version
has no dependency on heap size.

The times for the table version aren't nice. I guess mostly
because of the old Lua4 tables without an arry part and a
bigger memory footprint which gives more GC cycles.

Post by Rici Lake
Whether an object is constructed on the heap or the stack is not
a conceptual difference, it is an implementation detail.

Oh, it is a difference. There is no "..." object. There's
only a syntax to access the varargs. You see the difference
in the benchmark above :-)

Post by Rici Lake

Post by Edgar Toernig
But it's not the tuple that makes it possible to collect
multiple return value but the new syntax.

a, b, {c} = f()
I would have no objections to that, really.

Hehe, iirc I once suggested:

a, b, c[] = f() -- pack into c

function foo(a, b, c[]) -- define vararg function

foo(1, 2, c[]) -- unpack c

;-)

Ciao, ET.

[Rici Lake]

Post by Edgar Toernig

Post by Rici Lake
Whether an object is constructed on the heap or the stack is not
a conceptual difference, it is an implementation detail.

Oh, it is a difference. There is no "..." object. There's
only a syntax to access the varargs. You see the difference
in the benchmark above :-)

This same effect could be achieved with the single-bit reference
count which has been mooted several times. In this particular
case, no reference to the vararg object is ever present outside
of the stack, and a simple memory management optimisation could
avoid the gc effect.

Since arbitrary gc optimisations are possible, I continue to believe
that the heap vs. stack issue is an implementation detail.

Having said that, in the real world implementation details are
important.

R.

[Mark Hamburg]

I rather like that as a way of dealing with the magic name "arg".

It also simplifies some other things like writing cleanup wrappers using
pcall. For example one can then have:

function Mutex:do( func )
-- Execute func with locked mutex. Returns results of
-- executing func.
self:lock()
local success, result, others[] = pcall( func )
self:unlock()
if not success then error( result ) end
return result, others[]
end

Too bad it creates extra heap allocations.

This snippet also points to a moderately interesting idiom with respect to
pcall that isn't entirely easy or at least efficient to implement today.

Mark

Post by Edgar Toernig
a, b, c[] = f() -- pack into c
function foo(a, b, c[]) -- define vararg function
foo(1, 2, c[]) -- unpack c

[Edgar Toernig]

Post by Mark Hamburg
I rather like that as a way of dealing with the magic name "arg".

:-) From Sol's changelog:

| sol 0.25 Tue, 14 Nov 2000 18:54:30 +0100 by root
| Parent-Version: 0.24
| Version-Log: changed vararg syntax: '...' -> 'name[]'
|
| sol 0.24 Tue, 14 Nov 2000 17:38:16 +0100 by root
| Parent-Version: 0.23
| Version-Log: removed implicit 'self' parameter in function definitions

Post by Mark Hamburg
Too bad it creates extra heap allocations.

Yeah. That was the reason for:

| sol 0.116 Thu, 24 Apr 2003 04:27:29 +0200 by froese
| Parent-Version: 0.115
| Version-Log: new varargs - '...' as multi-value

Post by Mark Hamburg
This snippet also points to a moderately interesting idiom with respect to
pcall that isn't entirely easy or at least efficient to implement today.

With the new varargs you can implement it without heap allocations:

local function do2(self, success, ...)
self:unlock()
if not success then error(..., 2) end
return ...
end

function Mutex:do(...)
self:lock()
do2(self, pcall(...))
end

Not pretty but reasonable fast.

Ciao, ET.

[Mark Hamburg]

Definitely not pretty and probably hard for other programmers to follow.

It could be re-written as:

function Mutex:do( ... )
self:lock()
( function( self, success, ... )
self:unlock()
if not success then error( ..., 2 ) end
return ...
end )( self, pcall( ... ) )
end

I'm not sure that's prettier but it at least avoids the utility function
sitting around separately. On the other hand, I suspect that it will create
a new function closure each time it is called. I'd like to think that the
latter problem could be solved by the compiler noticing that the function
doesn't bind to any local values and hence could be transformed into the
code below, but that probably runs afoul of the ability to change the
environment of Mutex:do.

Mark

Post by Edgar Toernig
local function do2(self, success, ...)
self:unlock()
if not success then error(..., 2) end
return ...
end
function Mutex:do(...)
self:lock()
do2(self, pcall(...))
end
Not pretty but reasonable fast.

[Rici Lake]

By the way, the timings in that last post demonstrate the importance of
malloc/free over marking: mark is almost free since there is only one
live varargs tuple/table at any moment, but all of the blocks need to
be malloc()'d
and free()'d. Reducing the number of allocs per vararg from three to
one should reduce the memory management cost by 2/3, and that is pretty
well precisely what the benchmark demonstrated.

At the same time, it appears that the cost of varargs with the current
implementation is roughly the base cost of a function call; if the
function did anything complicated, the overhead would be a lot less
noticeable. So reducing
the overhead by 2/3 is probably sufficient.

R.

[Roberto Ierusalimschy]

In my view, tuples are a *big* change to the language, no matter the
size of its implementation (which is "an implementation detail", after
all).

That change would add lots of complexity to the language, at least
"hidden" complexity. As soon as we decided to add tuples to Lua, lots of
other decisions would follow, with lots of discussions for each of those
decisions. Among others (without much thinking): are tuples immutable?
if so, how should be the semantics of tupple equality? do tuples have
metatables? Why not? should we have a "foreach" function for tuples? A
"pair" iterator? Weak tuples? Each of these subjects (and many many
others) would eventually emerge in the list; several times, probably.

If the argument about efficiency is valid (the one about three
allocations versus one), I don't see why we cannot simply implement
tables more efficiently for those particular uses. First, as long as we
do not use a ".n" field, we are down to two allocations. (Would that
simple change give a 1/3 speedup?) Second, we could allocate tables with
a variable tail where it would keep its original array part (the one
specified in its constructor, if smaller than some [small] limit). That
would be enough to use only one block for those tables. (The main point
here is: how frequently we add new integer indices to tables created
with list constructors?)

About the "... hack", I do not see it as a hack at all (but of course
this is a matter of taste). It is a local change to the language, and it
solves at least two problems: it allows an easy way to pass parameters
to main chunks and it eliminates the magic name "arg" (or is it "args"?
I can't remember ;).

-- Roberto

[Asko Kauppi]

One of the reasons I chose Lua over Python (in 2002) was that I never
really got the hang of their tuples/tables/associated tables/etc. With
Lua, it was so bl**dy simple. :)

If changes are introduced, they should be such that the newcomer to Lua
doesn't (need to) notice them. A good measure is the number of pages
in the reference manual, imho.

-ak

Post by Roberto Ierusalimschy
In my view, tuples are a *big* change to the language, no matter the
size of its implementation (which is "an implementation detail", after
all).

[Rici Lake]

Post by Roberto Ierusalimschy
In my view, tuples are a *big* change to the language, no matter the
size of its implementation (which is "an implementation detail", after
all).

I personally have no problem with discussing implementation details :)

But let me be clear: the tuple proposal I made does not introduce a new
datatype. The datatype already exists: tuples are simply a function
closure.
The proposed syntactic changes simply allow a conventient way to create
them. So I don't see it as a major change.

The ... syntax, on the other hand, creates an odd sort of
pseudo-datatype
which is not a first-class object at all, but seems to require various
methods: count number of elements, slice (or some such), perhaps
iterate, etc.

My intuitive objection to ... is that it is not a first-class object,
and
so it seems to me inelegant. It doesn't really make the language more
expressive, so as far as I can see it's only point is to make one
particular
operation more efficient. Since tuples-as-functions do a reasonable job
of
optimising that particular operation, I see them as a plausible
alternative
which has the advantage of not introducing a new concept into the
language.

Post by Roberto Ierusalimschy
That change would add lots of complexity to the language, at least
"hidden" complexity. As soon as we decided to add tuples to Lua, lots of
other decisions would follow, with lots of discussions for each of those
decisions.

Adding tuples as an official datatype, different from function closures,
would raise these issues. I think immutable tuples with
equality-by-value
comparison would be a useful addition to the language, and I think some
discussion on this might be helpful. But I am not proposing it at this
time. Nonetheless, let me try to answer some of the questions.

Post by Roberto Ierusalimschy
Among others (without much thinking): are tuples immutable?

Mutable collections already exist in the form of tables. So the only
reason
to introduce a new datatype would be to take advantage of immutability.
Immutable vectors already exist in the language, but are restricted to
vectors of octets; in that sense, an immutable tuple could be seen as
a generalisation of (a different) existing datatype.

Post by Roberto Ierusalimschy
if so, how should be the semantics of tupple equality?

Immutable objects should be compared by value, I believe. This would be
a key advantage of immutable tuples. For example, it would allow their
use
as table keys. Currently, the only way to use a complex object as a
table
key (in this sense) is to serialise it into a character string, which is
quite awkward. As an example, implementing the LALR construction
algorithm
requires tables whose keys are essentially pairs of <state, item>.

Post by Roberto Ierusalimschy
Do tuples have metatables? Why not?

Do functions have metatables? No. Why not? I don't know. Should they?
Well, it would be useful from time to time, but I don't know that it is
a big deal. It would be nice to have some way to define binary
operators on
functions (compose, for example), but I've lived without it so far.
It might be nice to be able to __index or even __newindex a function,
but
you can (almost) always wrap it into a table to do that.

Post by Roberto Ierusalimschy
Should we have a "foreach" function for tuples? A "pair" iterator?

If there is some way of getting the length of the tuple, these are
very easy to write in Lua. A new tuple datatype would probably have some
primitive or library function which returned its length; but the
tuple-as-function implementation relies on the tuple function; one
possibility
would be the following tuple-function:

tuple() -- returns all values
tuple(j[, k]) -- returns the slice starting with j (default 1) and
and continuing to k (default end)
tuple(true) -- special case, returns length of tuple. (Could be
tuple(0))

Then the implementations of tuple.foreach and tuple.ipairs are quite
straight-forward.

However, I don't actually like "returns the length of the tuple". A
better
interface, imho, would be one which tells you whether the tuple was at
least
a particular length. Just a matter of taste, though.

Post by Roberto Ierusalimschy
Weak tuples?

If tuples are immutable, weak tuples are semantically questionable. Two
tuples
might suddenly become equal-by-value because different object members
became
unreachable and were turned into nil. Again, tables provide this
functionality.

Post by Roberto Ierusalimschy
Each of these subjects (and many many
others) would eventually emerge in the list; several times, probably.

Debate is good, no?

Post by Roberto Ierusalimschy
If the argument about efficiency is valid (the one about three
allocations versus one), I don't see why we cannot simply implement
tables more efficiently for those particular uses. First, as long as we
do not use a ".n" field, we are down to two allocations. (Would that
simple change give a 1/3 speedup?) Second, we could allocate tables with
a variable tail where it would keep its original array part (the one
specified in its constructor, if smaller than some [small] limit). That
would be enough to use only one block for those tables. (The main point
here is: how frequently we add new integer indices to tables created
with list constructors?)

All very true. I think tables could be optimised even more... but of
course
it is possible that such optimisations would be counterproductive in
other
cases.

Post by Roberto Ierusalimschy
About the "... hack", I do not see it as a hack at all (but of course
this is a matter of taste). It is a local change to the language, and it
solves at least two problems: it allows an easy way to pass parameters
to main chunks and it eliminates the magic name "arg" (or is it "args"?
I can't remember ;).

Indeed, it is a matter of taste. And of course it is your taste which is
most important.

I don't see passing parameters to main chunks being particular
difficult now;
the only issue is that it is a trifle inefficient. And personally, I
would
prefer a syntax which allows for named varargs, which is why I proposed:

function foo(a, b, [rest])

Of course, if rest were going to be a
vararg-table-as-currently-implemented,
that should be:

function foo(a, b, {rest})

Extending that to assignment statements is a very small step (and
actually
quite easy to implement in 5.0.2, at least.)

[Asko Kauppi]

*becoming more interested into this..*

Is there a patch (against Lua 5.x) available that I could use in LuaX
to try this out?

-ak

Post by Rici Lake

Post by Roberto Ierusalimschy
In my view, tuples are a *big* change to the language, no matter the
size of its implementation (which is "an implementation detail", after
all).

I personally have no problem with discussing implementation details :)
But let me be clear: the tuple proposal I made does not introduce a
new datatype. The datatype already exists: tuples are simply a
function closure.
...

[Asko Kauppi]

Post by Rici Lake
I don't see passing parameters to main chunks being particular
difficult now;

Then how do you do it?

I use a global 'arg' (doesn't have to be that name, but makes sense..)
and I do feel it's clumsy.

Especially annoying is the fact that in pure Lua5, the script cannot
know it's location. Imho, it should (could) get it at 'arg[0]'.
Anyhow, I feel the 'arg' thing should away.

-ak

(..or was it Karthago? ;)

[Roberto Ierusalimschy]

Post by Rici Lake
The ... syntax, on the other hand, creates an odd sort of
pseudo-datatype which is not a first-class object at all, [...]

The ... syntax does not create this pseudo-datatype. It already exists
in the language, in the form of multiple returns. I agree that its
second-class nature is not elegant, but it proved a quite useful and
efficient mechanism.

-- Roberto

[Rici Lake]

Post by Roberto Ierusalimschy

Post by Rici Lake
The ... syntax, on the other hand, creates an odd sort of
pseudo-datatype which is not a first-class object at all, [...]

The ... syntax does not create this pseudo-datatype. It already exists
in the language, in the form of multiple returns. I agree that its
second-class nature is not elegant, but it proved a quite useful and
efficient mechanism.

Well, tuple-as-function creates no new datatype either.

Actually, I think multiple return values are fantastic. I hate
programming
in languages that don't have them. But I don't think they are even a
second-class datatype, any more than parameter lists are a datatype (in
Lua).

"...", on the other hand, is providing a name for a non-object, which
is why
I called it a pseudo-datatype.

My argument is that tuples-as-functions are more useful and while
possibly not as efficient as ..., much more efficient than
varargs-as-tables, which is probably efficient enough (imho).

Tastes vary, of course.

Rici

[Asko Kauppi]

Short point on efficiency.

Within larger Lua wrappers (s.a. those for GUI libraries) I've noticed
that it is often meaningful to use varargs for passing "the rest of the
stuff" to C level functions. I won't go into details, just pointing
out thatt '...' can, in fact, be a commonly used operator, and having
it efficient is Good For Lua in general.

-ak

Post by Rici Lake
My argument is that tuples-as-functions are more useful and while
possibly not as efficient as ..., much more efficient than
varargs-as-tables, which is probably efficient enough (imho).