5 ms·

Lua doesn't have a separate "array" type, as arrays are just a special case of key->value where the key is always a positive integer. While this is nice (it sim

Lua doesn't have a separate "array" type, as arrays are just a special case of key->value where the key is always a positive integer. While this is nice (it simplifies the language yet Lua tables are incredibly versatile), it does indeed make it a little more work to translate structures to languages/serializations that distinguish between the two types, if the serializer needs to guess at runtime (e.g. if you don't have a predefined schema). I can't comment on the efficiency of whatever this implementation is doing, I haven't read the code. It does sound a little expensive. Also it's not always 100% clear which the correct mapping is, unless the developer explicitly picks one. For example, a serializer has no way to determine whether '{}' is intended to be an empty array or an empty hash. Another common gotcha, e.g. when translating to JSON, is that Lua does not restrict the types of keys (while JSON objects only support string keys), so boolean true/false are possible keys, for example, which cannot be translated to JSON directly.

matheusmoreira 2y ago
I ended up drawing the same conclusion while implementing my language. An insertion ordered hash table turned out to be just a normal array of values where the keys map to array indexes instead. Other than speed, I'm struggling to think of a good reason to keep the dedicated array type...
- cmovq 2y ago
  Note that the lua VM still optimizes tables that look like arrays by storing values in the array separate from the hash table [1]. [1]: https://www.lua.org/gems/sample.pdf https://www.lua.org/gems/sample.pdf
  - matheusmoreira 2y ago
    This is really interesting. So it doesn't hash integer keys, it uses them directly as indexes in a separate array. How is order maintained between the two arrays though?
    - wruza 2y ago
      Badly. In addition to https://news.ycombinator.com/item?id=41146240 https://news.ycombinator.com/item?id=41146240 Lua has two iterators: for k, v in pairs(t) do … end for i, v in ipairs(t) do … end ipairs just counts from 1 to n until t[n] == nil. Pairs returns all keys (array’s too) in an order that is undefined. Merged dict and array looks neat on syntactic level but really is pita to deal with. It’s a questionable design in itself, and then you go outside and realize that you’re incompatible with everything else cause {} and [] are two different things.
      - matheusmoreira 2y ago
        Yeah, I assumed as much... Looks like order just isn't maintained at all. Stopping at the first nil is pretty confusing and surprising to me, it implies a loop over an array full of nils would not iterate even once which makes no sense. Javascript does it right: array length is the greatest numerical index in the object plus one. Abstraction seemed neat at first but completely fell apart in the details. Many such cases. Looks like a true vector type is a good idea after all. > Merged dict and array looks neat on syntactic level but really is pita to deal with. It doesn't have to be that way. An insertion ordered hash table also contains an array part, it's just that it's completely internal to the implementation. It behaves just like a normal hash table, but internally the keys hash to indexes in the array part. The order of the hashes is undefined but the order of the key-value pairs in the array part is defined to be the order they were inserted into the table. It's really neat and it seems to work really well. It behaves exactly like an array if used like one. It definitely isn't an array though: integer keys are not offsets, they are hashed like every other key type. This doesn't seem like a huge problem to me. The lack of this property seems to be the root cause of the complexity of Lua's tables. It's tempting to think of these insertion ordered hash tables as some kind of superset of arrays. Just like it's tempting to think of hypergraphs as supersets of graphs, of graphs as supersets of trees, and of trees as supersets of linked lists. I haven't learned of any cracks in this abstraction, at least not yet. The reason to prefer less general data structures always seems to be performance, not correctness. Offsetting a pointer is faster than hashing some bytes, indexing two arrays, comparing keys for equality and then offsetting a pointer.
- VWWHFSfQ 2y ago
  Interesting side-effect of newer Python dictionaries preserving insertion order too. Explained by Hettinger here: https://www.youtube.com/watch?v=npw4s1QTmPg https://www.youtube.com/watch?v=npw4s1QTmPg
  - matheusmoreira 2y ago
    I learned it from his email to the Python mailing list! https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... https://github.com/lone-lang/lone/commit/da13b67a61248b832b264a3d293f05438dca283d https://github.com/lone-lang/lone/commit/da13b67a61248b832b2... I didn't know he had done a presentation about it, thank you for posting that video!
0cf8612b2e1e 2y ago
The biggest Lua gotcha is that accessing a missing element is not an error. Requires a hack to distinguish “really null”.
- VWWHFSfQ 2y ago
  most often seen with something like JSON serialization where JSON null will result in the key being completely absent from the Lua table, thus re-encoding into JSON will be missing that key entirely instead of existing but with a null value. It's why almost every serialization library will have userdata values to represent "null" and things like empty arrays instead of empty objects. Still love Lua though.
  - Dylan16807 2y ago
    Actual Javascript is even worse, "undefined" and "not defined" are two different things, in addition to null.
    - wruza 2y ago
      It’s really “not exists”, although js’s own lexicon uses “define property” instead of “create property”. They don’t hesitate to “delete” it though. Apart from names, I find explicit models easier to work with and they allow for better designs. E.g. in Lua if t has mt.__index = {x=1}, then t.x == nil is non-representable, because t.x = nil deletes t.x and now .x proxies into index, which returns 1. In javascript, since existence is a separate thing, you can assign literally any value to t.x and it will not be proxied to a prototype until you delete t.x. This has a whole cascade of consequences that make your meta life easier. Undefined vs null is still a mess though, but not because the two exist, but because standard APIs use and return them mostly arbitrarily.
      - Dylan16807 2y ago
        No matter what system you use, there are always unrepresentable states like that. If you have javascript-style properties, then t.x cannot represent "the object lacks property x". I'm fine not having explicit property existence, and prefer throwing out the complexity needed to support it. Maybe I'm underestimating the usefulness, but I think in most situations I'd be happy with either setting to false or using a plain old initial value instead of __index, and in the rest of cases I could get the same effect by having __newindex disable __index for that key.

matheusmoreira 2y ago

I ended up drawing the same conclusion while implementing my language. An insertion ordered hash table turned out to be just a normal array of values where the keys map to array indexes instead. Other than speed, I'm struggling to think of a good reason to keep the dedicated array type...

cmovq 2y ago
Note that the lua VM still optimizes tables that look like arrays by storing values in the array separate from the hash table [1]. [1]: https://www.lua.org/gems/sample.pdf https://www.lua.org/gems/sample.pdf
- matheusmoreira 2y ago
  This is really interesting. So it doesn't hash integer keys, it uses them directly as indexes in a separate array. How is order maintained between the two arrays though?
  - wruza 2y ago
    Badly. In addition to https://news.ycombinator.com/item?id=41146240 https://news.ycombinator.com/item?id=41146240 Lua has two iterators: for k, v in pairs(t) do … end for i, v in ipairs(t) do … end ipairs just counts from 1 to n until t[n] == nil. Pairs returns all keys (array’s too) in an order that is undefined. Merged dict and array looks neat on syntactic level but really is pita to deal with. It’s a questionable design in itself, and then you go outside and realize that you’re incompatible with everything else cause {} and [] are two different things.
    - matheusmoreira 2y ago
      Yeah, I assumed as much... Looks like order just isn't maintained at all. Stopping at the first nil is pretty confusing and surprising to me, it implies a loop over an array full of nils would not iterate even once which makes no sense. Javascript does it right: array length is the greatest numerical index in the object plus one. Abstraction seemed neat at first but completely fell apart in the details. Many such cases. Looks like a true vector type is a good idea after all. > Merged dict and array looks neat on syntactic level but really is pita to deal with. It doesn't have to be that way. An insertion ordered hash table also contains an array part, it's just that it's completely internal to the implementation. It behaves just like a normal hash table, but internally the keys hash to indexes in the array part. The order of the hashes is undefined but the order of the key-value pairs in the array part is defined to be the order they were inserted into the table. It's really neat and it seems to work really well. It behaves exactly like an array if used like one. It definitely isn't an array though: integer keys are not offsets, they are hashed like every other key type. This doesn't seem like a huge problem to me. The lack of this property seems to be the root cause of the complexity of Lua's tables. It's tempting to think of these insertion ordered hash tables as some kind of superset of arrays. Just like it's tempting to think of hypergraphs as supersets of graphs, of graphs as supersets of trees, and of trees as supersets of linked lists. I haven't learned of any cracks in this abstraction, at least not yet. The reason to prefer less general data structures always seems to be performance, not correctness. Offsetting a pointer is faster than hashing some bytes, indexing two arrays, comparing keys for equality and then offsetting a pointer.
VWWHFSfQ 2y ago
Interesting side-effect of newer Python dictionaries preserving insertion order too. Explained by Hettinger here: https://www.youtube.com/watch?v=npw4s1QTmPg https://www.youtube.com/watch?v=npw4s1QTmPg
- matheusmoreira 2y ago
  I learned it from his email to the Python mailing list! https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... https://github.com/lone-lang/lone/commit/da13b67a61248b832b264a3d293f05438dca283d https://github.com/lone-lang/lone/commit/da13b67a61248b832b2... I didn't know he had done a presentation about it, thank you for posting that video!

0cf8612b2e1e 2y ago

The biggest Lua gotcha is that accessing a missing element is not an error. Requires a hack to distinguish “really null”.

VWWHFSfQ 2y ago
most often seen with something like JSON serialization where JSON null will result in the key being completely absent from the Lua table, thus re-encoding into JSON will be missing that key entirely instead of existing but with a null value. It's why almost every serialization library will have userdata values to represent "null" and things like empty arrays instead of empty objects. Still love Lua though.
- Dylan16807 2y ago
  Actual Javascript is even worse, "undefined" and "not defined" are two different things, in addition to null.
  - wruza 2y ago
    It’s really “not exists”, although js’s own lexicon uses “define property” instead of “create property”. They don’t hesitate to “delete” it though. Apart from names, I find explicit models easier to work with and they allow for better designs. E.g. in Lua if t has mt.__index = {x=1}, then t.x == nil is non-representable, because t.x = nil deletes t.x and now .x proxies into index, which returns 1. In javascript, since existence is a separate thing, you can assign literally any value to t.x and it will not be proxied to a prototype until you delete t.x. This has a whole cascade of consequences that make your meta life easier. Undefined vs null is still a mess though, but not because the two exist, but because standard APIs use and return them mostly arbitrarily.
    - Dylan16807 2y ago
      No matter what system you use, there are always unrepresentable states like that. If you have javascript-style properties, then t.x cannot represent "the object lacks property x". I'm fine not having explicit property existence, and prefer throwing out the complexity needed to support it. Maybe I'm underestimating the usefulness, but I think in most situations I'd be happy with either setting to false or using a plain old initial value instead of __index, and in the rest of cases I could get the same effect by having __newindex disable __index for that key.