Re: New array type? (was: 'table' as fallback for tables)

classic Classic list List threaded Threaded
74 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

steve donovan
On Wed, Jul 6, 2016 at 12:52 AM, Hisham <[hidden email]> wrote:
> Amusingly, I was told off-list by another Lua user (who's more
> experienced than me) that after reading my post they went "oh-oh" and
> double-checked their own code as well. :)

My apologies for using you as 'the surprised expert user' example ;)

So yes, unpack/pack ought to be symmetrical. It would be cool if #
reported the actual size (since we can make # return anything
sensible, I don't think there's a universal definition). Once that's
in place then the `n` field becomes an implementation detail. The
table functions start respecting this, and nirvana is achieved.

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

steve donovan
On Wed, Jul 6, 2016 at 8:25 AM, steve donovan <[hidden email]> wrote:
> in place then the `n` field becomes an implementation detail. The
> table functions start respecting this, and nirvana is achieved.

Alas, but freedom from the wheel of death and rebirth is always harder
than it first seems.

The table returned from table.pack() now has a metatable (for __len)
and inevitably it will be passed to Lua code which doesn't respect
this. For example, pl.List will take a table (_assumed_ to be a
sequence) and slap its own metatable on it, rebranding it as a List
[0]. The carefully-crafted __len is lost in translation.

[0] the name is the result of initial Python-nostalgia, which has faded.

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Soni "They/Them" L.


On 06/07/16 05:15 AM, steve donovan wrote:

> On Wed, Jul 6, 2016 at 8:25 AM, steve donovan <[hidden email]> wrote:
>> in place then the `n` field becomes an implementation detail. The
>> table functions start respecting this, and nirvana is achieved.
> Alas, but freedom from the wheel of death and rebirth is always harder
> than it first seems.
>
> The table returned from table.pack() now has a metatable (for __len)
> and inevitably it will be passed to Lua code which doesn't respect
> this. For example, pl.List will take a table (_assumed_ to be a
> sequence) and slap its own metatable on it, rebranding it as a List
> [0]. The carefully-crafted __len is lost in translation.
>
> [0] the name is the result of initial Python-nostalgia, which has faded.
>
table.list(t) -> setmetatable(t, listmt); local i = 0; for k,v in
pairs(t) do if math.type(k) == "integer" and k > i then i = k end end
t._N = i --[[ alternatively, put it in the registry in a weak table, to
avoid conflicts with user keys ]]
table.remove(t) -> if debug.getmetatable(t) == listmt then t._N = t._N-1
end --[[ remove key and move everything over 1 ]]
table.insert(t) -> if debug.getmetatable(t) == listmt then t._N = t._N+1
end --[[ move everything over 1 and add key ]]
listmt -> {__newindex=--[[function to update _N if the new key is bigger
than current _N]], __len=function(t) return t._N end,
__metatable="list"} --[[ this would be stored in the registry, not sure
if there'd be a way to un-listify a list ]]

This would probably be the easiest way to do it such that some tables
would act like arraylists, it'd also replace that module you're talking
about. However, for performance reasons, we'd need a way to mass-remove
and mass-insert keys. (as in _N = _N-count instead of for i=1,count do
_N=_N-1 end)

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.


Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Tim Hill

> On Jul 6, 2016, at 9:06 AM, Soni L. <[hidden email]> wrote:
>
>
>
> On 06/07/16 05:15 AM, steve donovan wrote:
>> On Wed, Jul 6, 2016 at 8:25 AM, steve donovan <[hidden email]> wrote:
>>> in place then the `n` field becomes an implementation detail. The
>>> table functions start respecting this, and nirvana is achieved.
>> Alas, but freedom from the wheel of death and rebirth is always harder
>> than it first seems.
>>
>> The table returned from table.pack() now has a metatable (for __len)
>> and inevitably it will be passed to Lua code which doesn't respect
>> this. For example, pl.List will take a table (_assumed_ to be a
>> sequence) and slap its own metatable on it, rebranding it as a List
>> [0]. The carefully-crafted __len is lost in translation.
>>
>> [0] the name is the result of initial Python-nostalgia, which has faded.
>>
> table.list(t) -> setmetatable(t, listmt); local i = 0; for k,v in pairs(t) do if math.type(k) == "integer" and k > i then i = k end end t._N = i --[[ alternatively, put it in the registry in a weak table, to avoid conflicts with user keys ]]
> table.remove(t) -> if debug.getmetatable(t) == listmt then t._N = t._N-1 end --[[ remove key and move everything over 1 ]]
> table.insert(t) -> if debug.getmetatable(t) == listmt then t._N = t._N+1 end --[[ move everything over 1 and add key ]]
> listmt -> {__newindex=--[[function to update _N if the new key is bigger than current _N]], __len=function(t) return t._N end, __metatable="list"} --[[ this would be stored in the registry, not sure if there'd be a way to un-listify a list ]]
>
> This would probably be the easiest way to do it such that some tables would act like arraylists, it'd also replace that module you're talking about. However, for performance reasons, we'd need a way to mass-remove and mass-insert keys. (as in _N = _N-count instead of for i=1,count do _N=_N-1 end)
>

All this just to fix sequences? As I noted before, the root cause here is that a sequence should be able to contain nil values. If it did, none of these work-arounds would be needed.

—Tim



Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Soni "They/Them" L.


On 06/07/16 04:02 PM, Tim Hill wrote:

>> On Jul 6, 2016, at 9:06 AM, Soni L. <[hidden email]> wrote:
>>
>>
>>
>> On 06/07/16 05:15 AM, steve donovan wrote:
>>> On Wed, Jul 6, 2016 at 8:25 AM, steve donovan <[hidden email]> wrote:
>>>> in place then the `n` field becomes an implementation detail. The
>>>> table functions start respecting this, and nirvana is achieved.
>>> Alas, but freedom from the wheel of death and rebirth is always harder
>>> than it first seems.
>>>
>>> The table returned from table.pack() now has a metatable (for __len)
>>> and inevitably it will be passed to Lua code which doesn't respect
>>> this. For example, pl.List will take a table (_assumed_ to be a
>>> sequence) and slap its own metatable on it, rebranding it as a List
>>> [0]. The carefully-crafted __len is lost in translation.
>>>
>>> [0] the name is the result of initial Python-nostalgia, which has faded.
>>>
>> table.list(t) -> setmetatable(t, listmt); local i = 0; for k,v in pairs(t) do if math.type(k) == "integer" and k > i then i = k end end t._N = i --[[ alternatively, put it in the registry in a weak table, to avoid conflicts with user keys ]]
>> table.remove(t) -> if debug.getmetatable(t) == listmt then t._N = t._N-1 end --[[ remove key and move everything over 1 ]]
>> table.insert(t) -> if debug.getmetatable(t) == listmt then t._N = t._N+1 end --[[ move everything over 1 and add key ]]
>> listmt -> {__newindex=--[[function to update _N if the new key is bigger than current _N]], __len=function(t) return t._N end, __metatable="list"} --[[ this would be stored in the registry, not sure if there'd be a way to un-listify a list ]]
>>
>> This would probably be the easiest way to do it such that some tables would act like arraylists, it'd also replace that module you're talking about. However, for performance reasons, we'd need a way to mass-remove and mass-insert keys. (as in _N = _N-count instead of for i=1,count do _N=_N-1 end)
>>
> All this just to fix sequences? As I noted before, the root cause here is that a sequence should be able to contain nil values. If it did, none of these work-arounds would be needed.
Without bloating the table type too much. It's better to add this to the
table library instead of adding it to the table type. It'll also be
easier to handle on the C side of things as you won't have to redesign
the whole Lua VM for a completely redesigned table type.

Actually, if the whole Lua VM were to be redesigned, it'd stop being Lua
5.x, instead becoming Lua 6.x. And it'd be slower and heavier, because
then you'd track size for all tables, not just the tables that need it.
>
> —Tim
>
>
>

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.


Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Tim Hill

On Jul 6, 2016, at 12:09 PM, Soni L. <[hidden email]> wrote:


Without bloating the table type too much. It's better to add this to the table library instead of adding it to the table type. It'll also be easier to handle on the C side of things as you won't have to redesign the whole Lua VM for a completely redesigned table type.

Actually, if the whole Lua VM were to be redesigned, it'd stop being Lua 5.x, instead becoming Lua 6.x. And it'd be slower and heavier, because then you'd track size for all tables, not just the tables that need it.


As I pointed out previously, the overhead is a single 64-bit integer per table. Although this might imply an 8 byte overhead, in fact this is free on all major platforms that I know of (Windows, Linux, iOS, Android) since the granularity of heap allocation means that there is no additional memory allocation at all. So there is no overhead at all, apart from setting a C integer to zero when a table is allocated. Nor is there overhead when adding/deleting table keys (even integer keys).

Why do you think a VM redesign is necessary ?

—Tim


Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Coda Highland
On Wed, Jul 6, 2016 at 10:08 PM, Tim Hill <[hidden email]> wrote:

>
> On Jul 6, 2016, at 12:09 PM, Soni L. <[hidden email]> wrote:
>
>
> Without bloating the table type too much. It's better to add this to the
> table library instead of adding it to the table type. It'll also be easier
> to handle on the C side of things as you won't have to redesign the whole
> Lua VM for a completely redesigned table type.
>
> Actually, if the whole Lua VM were to be redesigned, it'd stop being Lua
> 5.x, instead becoming Lua 6.x. And it'd be slower and heavier, because then
> you'd track size for all tables, not just the tables that need it.
>
>
>
> As I pointed out previously, the overhead is a single 64-bit integer per
> table. Although this might imply an 8 byte overhead, in fact this is free on
> all major platforms that I know of (Windows, Linux, iOS, Android) since the
> granularity of heap allocation means that there is no additional memory
> allocation at all. So there is no overhead at all, apart from setting a C
> integer to zero when a table is allocated. Nor is there overhead when
> adding/deleting table keys (even integer keys).
>
> Why do you think a VM redesign is necessary ?
>
> —Tim

I think part of the issue here is that there are a number of competing
suggestions flying around. Another part is that memory overhead isn't
the only way that something can get heavier.

To ensure that ALL tables track their length under all possible
operations... well, it might be hyperbolic to say it would be a VM
"redesign" but it WOULD require quite a lot of modification, with
possible . And due to the inherent ambiguity in whether some actions
are meant to alter the length of a table (is "t[#t] = nil" setting the
last element of a fixed-size array to nil, or is it reducing the size
of the array? is "t[#t+1] = 1" a push operation or is it writing out
of bounds?) it would require changing the semantics of the language.
And outside of the question of memory allocation, the efficiency
tradeoff (make length calculation cheaper in exchange for making
mutations more expensive) is probably not the right choice for
general-purpose use.

The counterproposal being made is to use the existing language
features to define a type that has a specific set of behaviors for the
scenarios where those behaviors are explicitly desired without making
modifications that would affect the language more broadly.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

steve donovan
On Thu, Jul 7, 2016 at 8:30 AM, Coda Highland <[hidden email]> wrote:
> The counterproposal being made is to use the existing language
> features to define a type that has a specific set of behaviors for the
> scenarios where those behaviors are explicitly desired without making
> modifications that would affect the language more broadly.

Exactly. Like the pack/unpack case.

Personally I wear Dirk's "Lua works for me" T-shirt (if it weren't so
damn cold in the mornings) and I look after a lot of Lua. The urge to
keep nils in tables other than varargs does not happen to me. It would
be cool if #t was O(1), however.

steve d.

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Dirk Laurie-2
2016-07-07 9:08 GMT+02:00 steve donovan <[hidden email]>:

> On Thu, Jul 7, 2016 at 8:30 AM, Coda Highland <[hidden email]> wrote:
>> The counterproposal being made is to use the existing language
>> features to define a type that has a specific set of behaviors for the
>> scenarios where those behaviors are explicitly desired without making
>> modifications that would affect the language more broadly.
>
> Exactly. Like the pack/unpack case.
>
> Personally I wear Dirk's "Lua works for me" T-shirt (if it weren't so
> damn cold in the mornings) and I look after a lot of Lua. The urge to
> keep nils in tables other than varargs does not happen to me. It would
> be cool if #t was O(1), however.

That T-shirt happens to be in the wash this morning ...

We've had several threads and I can't without re-reading everything
give credit where credit is due, but the following ideas for fixed-length
tables seem to be useful enough to keep in mind.

1. The __len metafield could contain an integer, not a function.
2. That could be used to flag the table as a fixed-length array
that may contain nils.
3. Supply __newindex metamethod if you want to treat an assignment
outside the range of a fixed-length table as an error.
4. This will automatically cause table.insert to be an error.
5. The semantics of table.insert could be revised so that in the case
of a fixed-length table, no assigment beyond __len is made, but an
error is signalled if the last element is not nil.
6. Automatic resizing of a fixed-length array could be replaced
by doing it only on request (e.g. a function table.resize).

This does not seem to be too large for a PowerPatch.

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Daurnimator
On 7 July 2016 at 17:15, Dirk Laurie <[hidden email]> wrote:
> We've had several threads and I can't without re-reading everything
> give credit where credit is due, but the following ideas for fixed-length
> tables seem to be useful enough to keep in mind.
>
> 1. The __len metafield could contain an integer, not a function.

No. You don't want a metatable per array/list/sequence

> 2. That could be used to flag the table as a fixed-length array
> that may contain nils.
> 3. Supply __newindex metamethod if you want to treat an assignment
> outside the range of a fixed-length table as an error.
> 4. This will automatically cause table.insert to be an error.
> 5. The semantics of table.insert could be revised so that in the case
> of a fixed-length table, no assigment beyond __len is made, but an
> error is signalled if the last element is not nil.
> 6. Automatic resizing of a fixed-length array could be replaced
> by doing it only on request (e.g. a function table.resize).
>
> This does not seem to be too large for a PowerPatch.


None of this needs to be a patch.

See http://lua-users.org/lists/lua-l/2016-06/msg00409.html

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

steve donovan
In reply to this post by Dirk Laurie-2
On Thu, Jul 7, 2016 at 9:15 AM, Dirk Laurie <[hidden email]> wrote:
> give credit where credit is due, but the following ideas for fixed-length
> tables seem to be useful enough to keep in mind.

It seems a specialized case to me?

> 1. The __len metafield could contain an integer, not a function.

But that makes sense...

> 2. That could be used to flag the table as a fixed-length array
> that may contain nils.

OK, I see, like varargs...

> 3. Supply __newindex metamethod if you want to treat an assignment
> outside the range of a fixed-length table as an error.
> 4. This will automatically cause table.insert to be an error.
> 5. The semantics of table.insert could be revised so that in the case
> of a fixed-length table, no assigment beyond __len is made, but an
> error is signalled if the last element is not nil.
> 6. Automatic resizing of a fixed-length array could be replaced
> by doing it only on request (e.g. a function table.resize).

OK, I do see the point. This will cover most of the cases.

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Tim Hill
In reply to this post by Coda Highland

> On Jul 6, 2016, at 11:30 PM, Coda Highland <[hidden email]> wrote:
>
>
> I think part of the issue here is that there are a number of competing
> suggestions flying around. Another part is that memory overhead isn't
> the only way that something can get heavier.
>
> To ensure that ALL tables track their length under all possible
> operations... well, it might be hyperbolic to say it would be a VM
> "redesign" but it WOULD require quite a lot of modification, with
> possible . And due to the inherent ambiguity in whether some actions
> are meant to alter the length of a table (is "t[#t] = nil" setting the
> last element of a fixed-size array to nil, or is it reducing the size
> of the array? is "t[#t+1] = 1" a push operation or is it writing out
> of bounds?) it would require changing the semantics of the language.
> And outside of the question of memory allocation, the efficiency
> tradeoff (make length calculation cheaper in exchange for making
> mutations more expensive) is probably not the right choice for
> general-purpose use.

Understood, which was why my suggestion was to simply make the length user-defined and that was that for the language per se. No magical changes to length as a result of manipulating table contents. Just a user-settable length that can be read via #t, and respects metatables. Storage overhead we’ve discussed, code overhead is tiny, and in fact deletes the current code behind #t replacing it with a simple read of a stored value (in O(1) time).

Now, it *might* be desirable to have some library functions automatically set the length. For example, pack(), insert(), delete(), so yes there are some library changes. But there is no VM re-design and certainly no impact on the C API. Even these changes are pretty trivial.

However, as has been noted, lots of code breaks, which is not nice at all. If it were not for this I’d push hard for a simple scheme like this one. Let’s face it, the whole issue of #t and sequences and nils comes up again and again and again here .. it really is one of the least intuitive parts of Lua.

—Tim



Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

steve donovan
In reply to this post by Daurnimator
On Thu, Jul 7, 2016 at 9:25 AM, Daurnimator <[hidden email]> wrote:
> None of this needs to be a patch.
>
> See http://lua-users.org/lists/lua-l/2016-06/msg00409.html

That's simple enough. So the question is, why isn't it sufficient?

For pack/unpack to work it has to be part of base Lua of course

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Daurnimator
On 7 July 2016 at 17:32, steve donovan <[hidden email]> wrote:
> On Thu, Jul 7, 2016 at 9:25 AM, Daurnimator <[hidden email]> wrote:
>> None of this needs to be a patch.
>>
>> See http://lua-users.org/lists/lua-l/2016-06/msg00409.html
>
> That's simple enough. So the question is, why isn't it sufficient?

Because it means everyone has to agree on *one* sequence library.
And lua developers are a herd of cats.

I'm happy to whip it into shape a bit more; give it a readme and a
rockspec if people think that my library there is *the* solution.

(Compare to the other 'basic' data structure library I maintain:
https://github.com/daurnimator/fifo.lua)

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Dirk Laurie-2
In reply to this post by Tim Hill
2016-07-07 9:26 GMT+02:00 Tim Hill <[hidden email]>:
> Let’s face it, the whole issue of #t and sequences and nils
> comes up again and again and again here .. it really is one
> of the least intuitive parts of Lua.

tinsert, tremove and sort only came in with Lua 3.2, when
getn also came in. Tables could have a field 'n' which getn would
return; otherwise it would make a full traversal of all keys of the
table in search of the largest numerical key. 'tinsert' and 'tremove'
updated 'n' if it was present.

At that stage it was intuitive enough, I'd say, and offered almost
exactly what some of us are clamouring for now. Most of us still
have Lua 5.0 somewhere, I expect (e.g. Ubuntu 14.04 offers
the package `lua50`) so maybe we should just shut up and
use that.

Omitting 'n' was clearly an inefficient use of 'getn', and was
replaced in Lua 5.1 by the nondeterministic length operator
(at that stage stated to have the property no longer promised,
that it occurs at a frontier between non-nil and nil) which gives
the right answer if the table is a sequence. Thus the burden of
using the (newly packaged) table library correctly was shifted
to the user. That is where the trouble started.

We've been searching for the proper approach all through 5.1.x,
5.2.x and 5.3.x (for example, having table.insert(tbl,whatever,-5)
throw an error came in at a minor release) and we are not yet
back to having available what all versions from 3.2.x to 5.0.x had,
except by newbie-unfriendly mechanisms like setting
metamethods or monkeypatching the table library.

So I guess we had better keep arguing, so that Lua 6.0, when
it comes, meets universal acclaim.

In that spirit, I offer another suggestion.

1. Make the intuitive Lua 5.0 behaviour (to use the largest numeric
key of tbl as #tbl) the default. No presently documented property of
the # operator is violated.

2. Instead of 'n', which offends some people, use a secret key
which a modified 'next' (and therefore 'pairs') will not show.

3. New table functions:

table.frontier(tbl[,k])  Returns the k-th frontier of tbl, that is,
an integer n>=0 such that t[n+1] is nil but either n=0 or t[n]
is not nil. If k is omitted, any frontier of t may be returned.

table.getlength(tbl)  Returns the value, if any, to be returned
by #tbl when no __len metamethod has been specified.

table.setlength(tbl,n) Sets n as the value to be returned by
#tbl when no __len metamethod has been specified.

The current O(log n) but nondeterministic #t is obtained by

   setmetatable(tbl,table.frontier)

Users sophisticated enough to wield 'setmetatable' can
be expected to be able to comprehend 'table.frontier' too.

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Soni "They/Them" L.
In reply to this post by Tim Hill


On 07/07/16 04:26 AM, Tim Hill wrote:

>> On Jul 6, 2016, at 11:30 PM, Coda Highland <[hidden email]> wrote:
>>
>>
>> I think part of the issue here is that there are a number of competing
>> suggestions flying around. Another part is that memory overhead isn't
>> the only way that something can get heavier.
>>
>> To ensure that ALL tables track their length under all possible
>> operations... well, it might be hyperbolic to say it would be a VM
>> "redesign" but it WOULD require quite a lot of modification, with
>> possible . And due to the inherent ambiguity in whether some actions
>> are meant to alter the length of a table (is "t[#t] = nil" setting the
>> last element of a fixed-size array to nil, or is it reducing the size
>> of the array? is "t[#t+1] = 1" a push operation or is it writing out
>> of bounds?) it would require changing the semantics of the language.
>> And outside of the question of memory allocation, the efficiency
>> tradeoff (make length calculation cheaper in exchange for making
>> mutations more expensive) is probably not the right choice for
>> general-purpose use.
> Understood, which was why my suggestion was to simply make the length user-defined and that was that for the language per se. No magical changes to length as a result of manipulating table contents. Just a user-settable length that can be read via #t, and respects metatables. Storage overhead we’ve discussed, code overhead is tiny, and in fact deletes the current code behind #t replacing it with a simple read of a stored value (in O(1) time).
>
> Now, it *might* be desirable to have some library functions automatically set the length. For example, pack(), insert(), delete(), so yes there are some library changes. But there is no VM re-design and certainly no impact on the C API. Even these changes are pretty trivial.
>
> However, as has been noted, lots of code breaks, which is not nice at all. If it were not for this I’d push hard for a simple scheme like this one. Let’s face it, the whole issue of #t and sequences and nils comes up again and again and again here .. it really is one of the least intuitive parts of Lua.
You need to think of Lua tables as C strings.
>
> —Tim
>
>
>

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.


Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

steve donovan
On Thu, Jul 7, 2016 at 1:18 PM, Soni L. <[hidden email]> wrote:
> You need to think of Lua tables as C strings.

Apt comparison, but not every user of Lua knows how C strings work,
and how you can 'lose' stuff behind an embedded nul character.

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Dibyendu Majumdar
In reply to this post by Jonathan Goble
On 1 July 2016 at 02:01, Jonathan Goble <[hidden email]> wrote:

> Most languages have two distinct types for sequences and associative
> arrays. Lua has just one type, the table, which is really good at the
> latter, but doesn't do a very good job at the former. The ongoing
> discussion proves that there is a need for a real sequence type
> capable of holding `nil`, but I just don't think there is a good,
> clean way for Lua, as it stands right now, to do that short of
> creating a new type for sequences and deprecating tables for that
> purpose (they would remain useful for associative arrays, of course).
>
> A new type would have many advantages, chief among them elimination of
> the need to store the length as a field in the table or metatable
> (since the length would now be known and tracked by the C internals),
> and elimination of the question of how to set the initial length from
> a constructor (since array constructors probably wouldn't allow
> explicit keys/indices).
>

Hi, in Ravi (Lua 5.3 derivative) I support arrays of integers and numbers.
I have extended the table structure to store additional information.
This includes - a flag to indicate whether the table is regular table, or
number array, or integer array. The length of the array, plus actual array
data. For integer and number arrays I store the data separately to ensure it
is just like a C array.

There are some difficulties in implementing arrays in Lua without breaking
backwards compatibility. First difficulty how to know an array is being
constructed. In Ravi I solve this in two ways:

a) Type annotation allows users' intention to be made clear.
b) I also provide API functions table.numarray() and table.intarray() to return
preconstruced arrays of fixed size.

With standard Lua, assuming that the table internals and VM internals are
enhanced as I have done in Ravi - then the API function approach might work.

The second difficulty is how Lua handles tables, and what NIL means. In the case
of number and int array in Ravi there is no concept of a NIL element.
All elements
are initialized (to user supplied value or zero).

Perhaps the easy solution might be to only support fixed length
arrays, and thereby
allow NILs as valid values.

Finally in Ravi I disallow meta functions __index, __newindex and
__len on arrays
as they do not make sense in the context of an array.

A downside to the Ravi approach is that every access to a table
element has an extra
if condition as we need to check whether the table is a regular table
or an array. But this
cost is negligible, In Ravi of course when type annotations are
available, this cost is
eliminated but that will not be possible in regular Lua.

Regards
Dibyendu

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Thomas Jericke
In reply to this post by Soni "They/Them" L.
On 07/07/2016 01:18 PM, Soni L. wrote:

>
>
> On 07/07/16 04:26 AM, Tim Hill wrote:
>>> On Jul 6, 2016, at 11:30 PM, Coda Highland <[hidden email]> wrote:
>>>
>>>
>>> I think part of the issue here is that there are a number of competing
>>> suggestions flying around. Another part is that memory overhead isn't
>>> the only way that something can get heavier.
>>>
>>> To ensure that ALL tables track their length under all possible
>>> operations... well, it might be hyperbolic to say it would be a VM
>>> "redesign" but it WOULD require quite a lot of modification, with
>>> possible . And due to the inherent ambiguity in whether some actions
>>> are meant to alter the length of a table (is "t[#t] = nil" setting the
>>> last element of a fixed-size array to nil, or is it reducing the size
>>> of the array? is "t[#t+1] = 1" a push operation or is it writing out
>>> of bounds?) it would require changing the semantics of the language.
>>> And outside of the question of memory allocation, the efficiency
>>> tradeoff (make length calculation cheaper in exchange for making
>>> mutations more expensive) is probably not the right choice for
>>> general-purpose use.
>> Understood, which was why my suggestion was to simply make the length
>> user-defined and that was that for the language per se. No magical
>> changes to length as a result of manipulating table contents. Just a
>> user-settable length that can be read via #t, and respects
>> metatables. Storage overhead we’ve discussed, code overhead is tiny,
>> and in fact deletes the current code behind #t replacing it with a
>> simple read of a stored value (in O(1) time).
>>
>> Now, it *might* be desirable to have some library functions
>> automatically set the length. For example, pack(), insert(),
>> delete(), so yes there are some library changes. But there is no VM
>> re-design and certainly no impact on the C API. Even these changes
>> are pretty trivial.
>>
>> However, as has been noted, lots of code breaks, which is not nice at
>> all. If it were not for this I’d push hard for a simple scheme like
>> this one. Let’s face it, the whole issue of #t and sequences and nils
>> comes up again and again and again here .. it really is one of the
>> least intuitive parts of Lua.
> You need to think of Lua tables as C strings.
I dislike C strings for the very same reasons. BTW strlen does not work
like #table, it always finds the first \0.
--
Thomas

Reply | Threaded
Open this post in threaded view
|

Re: New array type? (was: 'table' as fallback for tables)

Dibyendu Majumdar
In reply to this post by Dibyendu Majumdar
On 7 July 2016 at 13:07, Dibyendu Majumdar <[hidden email]> wrote:

> On 1 July 2016 at 02:01, Jonathan Goble <[hidden email]> wrote:
>> Most languages have two distinct types for sequences and associative
>> arrays. Lua has just one type, the table, which is really good at the
>> latter, but doesn't do a very good job at the former. The ongoing
>> discussion proves that there is a need for a real sequence type
>> capable of holding `nil`, but I just don't think there is a good,
>> clean way for Lua, as it stands right now, to do that short of
>> creating a new type for sequences and deprecating tables for that
>> purpose (they would remain useful for associative arrays, of course).
>>
>> A new type would have many advantages, chief among them elimination of
>> the need to store the length as a field in the table or metatable
>> (since the length would now be known and tracked by the C internals),
>> and elimination of the question of how to set the initial length from
>> a constructor (since array constructors probably wouldn't allow
>> explicit keys/indices).
>>
>
> Hi, in Ravi (Lua 5.3 derivative) I support arrays of integers and numbers.
> I have extended the table structure to store additional information.
> This includes - a flag to indicate whether the table is regular table, or
> number array, or integer array. The length of the array, plus actual array
> data. For integer and number arrays I store the data separately to ensure it
> is just like a C array.
>
> There are some difficulties in implementing arrays in Lua without breaking
> backwards compatibility. First difficulty how to know an array is being
> constructed. In Ravi I solve this in two ways:
>
> a) Type annotation allows users' intention to be made clear.
> b) I also provide API functions table.numarray() and table.intarray() to return
> preconstruced arrays of fixed size.
>
> With standard Lua, assuming that the table internals and VM internals are
> enhanced as I have done in Ravi - then the API function approach might work.
>
> The second difficulty is how Lua handles tables, and what NIL means. In the case
> of number and int array in Ravi there is no concept of a NIL element.
> All elements
> are initialized (to user supplied value or zero).
>
> Perhaps the easy solution might be to only support fixed length
> arrays, and thereby
> allow NILs as valid values.
>
> Finally in Ravi I disallow meta functions __index, __newindex and
> __len on arrays
> as they do not make sense in the context of an array.
>
> A downside to the Ravi approach is that every access to a table
> element has an extra
> if condition as we need to check whether the table is a regular table
> or an array. But this
> cost is negligible, In Ravi of course when type annotations are
> available, this cost is
> eliminated but that will not be possible in regular Lua.
>

I should add that in Ravi accessing a non-existing element results in
error and not NIL as a NIL value is not valid for an integer or
number. Perhaps this is better behaviour for arrays anyway. Also only
integer values are permitted as indices.

Regards

1234