Re: Lua 5.1+ and variable-argument tables

[Rici Lake <lua@...>]

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