new "empty" value/type in Lua?

classic Classic list List threaded Threaded
102 messages Options
123456
Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Philipp Janda
Am 28.06.2013 20:11 schröbte Tim Hill:

>
> On Jun 28, 2013, at 5:18 AM, Philipp Janda <[hidden email]> wrote:
>
>> Why do you care if it's an "array"? No matter what, you can access the values for the integer keys from 1 to n. If nil is not allowed as a value, Lua gives you a fast way to calculate that n. If nil may be in there somewhere, somebody better tell you where this table is supposed to end because that information is not obvious!
>
> Yes, it's NOT obvious. It could be MADE obvious by using "empty"
> instead of nil, in which case the "fast way to calculate n" would be
> MORE useful, which seems to me a good thing, doesn't it?
>
> Are you saying it's a bad idea to make arrays more useable?

No one is arguing that sentinel values cannot be useful. Using a
sentinel value in arrays with holes let's you use `#` and `ipairs`
(which you also can do using a metatable and an explict length field).
Lua already can do everything your proposed "empty" type would do. Why
do you want to force everyone to use the same sentinel value?

Btw., one sentinel is not always enough[1], and sentinel values are not
appropriate for every sparse array (e.g. some numerical algorithms for
solving differential equations generate large sparse matrices where only
the elements near the diagonal are nonzero).

   [1]:
https://github.com/siffiejoe/lua-multikey/blob/master/src/multikey.lua#L10

> Is it better to have 20 different workarounds to a common problem than one simple, clear, language supported fix?

If you want arrays with holes, there are basically only three different
workarounds:

1.  use nil for the holes
     pro: - saves memory for very sparse arrays
          - fits well with varargs and table.(un)pack.
          - no mapping from hole to nil required
     con: - needs explicit length field
          - needs metatable if you want `#` and `ipairs` to work

2.  use a sentinel value for holes
     pro: - can use `#` and `ipairs` without metatable magic
     con: - cannot handle large sparse arrays
          - does not mix well with {...} and table.pack( ... )

3.  use some specialized container class/object
     pro: - can't be mistaken for a raw table
          - can implement whatever policy you see fit
     con: - does not feel like a raw table


First: Arrays with holes are rare, and 1) already handles (all of) them
pretty well (with the exception of automatically calculated array
length), so much attention in terms of language features is probably a
waste of effort.
If you look for a general, "standard" (as in: used in Lua's standard
library) way, go for 1). You probably should use "n" for the array
length. If you cannot live with the slight inconvenience of handling the
array length yourself, go for 2). But even with a standardized "empty"
type/value, 2) will not make 1) obsolete. And it will not make other
sentinel values obsolete either.

Adding a type to the language is a big deal (much bigger than e.g. a
library function), and it would affect a lot of code ...

>
> --Tim
>

Philipp



Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Tim Hill
In reply to this post by Jerome Vuarand
The initial project used some project-specific stuff that very domain specific (I cannot be more detailed, as this is commercially a bit sensitive). As the second project began, we looked at experience gained and realized we would need a similar (again domain-specific) concept that was similar to "empty" (it wasn't called that in the projects).

So we created the generic "empty" and back-ported it to the first project, which simplified several algorithms and ended with a much, much cleaner division of labor between C and Lua code.

The only APIs were two small C functions exposed to Lua:
x = getEMPTY()
b = isEMPTY(x)

getEMPTY() returned, you guessed it, the empty value, while isEMPTY tested for it. We also, purely by convention, store an EMPTY value in the global EMPTY.

Armed with this simple bit of code, a lot of Lua code got very much more "well duh!" type code, which I really liked. One thing we ended up with was a very clean transport format for heterogenous data that could move rapidly between Lua and C code (and elsewhere) with very low impedance between the Lua representation and the C/etc format.

I think the concept is capable of abuse in a couple of ways:
1. Confusion between nil and empty. This is clearly an area that needs to be carefully addressed. We handled it by making it clear that empty was just another normal value (for example, it evaluates to true in a boolean context).
2. Potential memory "leaks" if empty is used instead of nil. If someone doesn't "get" it, then they may use empty instead of nil to try to remove elements from a table, resulting in stuck items that are never reclaimed. This probably speaks to the name "empty" not being the best. otoh in the hands of a bad developer, ANY feature can be mis-used.
3. The "infinite" recurse problem. At Roberto pointed out, if you add "empty", one day someone comes along and says "ok, we used empty and all the other types, can we now have a type that is different from all the other types AND empty?".

Anyway, it's pretty much been voted down, which is fine, though i'm not sure I agree with some of the reasons stated.

--Tim


On Jun 30, 2013, at 1:12 AM, Jerome Vuarand <[hidden email]> wrote:

So, in these three MAJOR projects, did you extend Lua to have that "empty"
value? Given the relatively small size of Lua compared to any project that can
be qualified as MAJOR in capitals, there was no reason not to.

Did you implement the "empty" value in the same way for the three projects?
Did the concept (and eventually the implementation) apply equally well to the
three projects?

What are the few extra APIs that you had to define?

Did you initially abuse the concept to later realize it was useful in some
cases, but not that much in others?

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Parke
On Sun, Jun 30, 2013 at 1:33 PM, Tim Hill <[hidden email]> wrote:
The only APIs were two small C functions exposed to Lua:
x = getEMPTY()
b = isEMPTY(x)

Hi Tim,

In terms of utility in your projects, how does the above solution compare to (hypothetically) extending Lua to force the "array" portion of a table at be least X large, on an adjustable, per table (or per metatable) basis?

In this hypothetical case, nil would mean empty, but you would not have to worry about the array portion collapsing due to sparsity.

In other words, other than avoiding unwanted table collapsing, are there other benefits to empty?

(I have no idea how much work it would be to make this hypothetical extension to Lua, nor how palatable other Lua users would find it.)

-Parke

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

harry gotterwald

jesus christ. this discussion is nauseating. and I thought /I/ was a lua zealot, but this is just rabid and irrational. nobody here seems to be getting the point at all. I am actually unsubscribing from this list over this.


On Sun, Jun 30, 2013 at 6:55 PM, Parke <[hidden email]> wrote:
On Sun, Jun 30, 2013 at 1:33 PM, Tim Hill <[hidden email]> wrote:
The only APIs were two small C functions exposed to Lua:
x = getEMPTY()
b = isEMPTY(x)

Hi Tim,

In terms of utility in your projects, how does the above solution compare to (hypothetically) extending Lua to force the "array" portion of a table at be least X large, on an adjustable, per table (or per metatable) basis?

In this hypothetical case, nil would mean empty, but you would not have to worry about the array portion collapsing due to sparsity.

In other words, other than avoiding unwanted table collapsing, are there other benefits to empty?

(I have no idea how much work it would be to make this hypothetical extension to Lua, nor how palatable other Lua users would find it.)

-Parke


Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Tim Hill
In reply to this post by Parke
I think the primary benefit is having an array work like an array. So if you could essentially have a "writer" mark an array as of size X, and then let the "reader" use "#" to get this, that would also work.

Both "empty" and declarative array sizes provide a way for a structure creator to communicate to a reader information about the structure, using a mechanism (the # operator) favored by Lua. To my mind all the workarounds fall into two categories:
-- A private contract that communicates this outside of # … which seems to suggest that # is not very useful.
-- Using a metatable to create custom behavior, which preserves # semantics but requires the writer to perform considerably more work.

My feeling was that simply adding a standard way to do this avoided both of these work-arounds.

Anyway, clearly the issue has been decided, though perhaps by a less than impressive process.

--Tim


On Jun 30, 2013, at 3:55 PM, Parke <[hidden email]> wrote:

On Sun, Jun 30, 2013 at 1:33 PM, Tim Hill <[hidden email]> wrote:
The only APIs were two small C functions exposed to Lua:
x = getEMPTY()
b = isEMPTY(x)

Hi Tim,

In terms of utility in your projects, how does the above solution compare to (hypothetically) extending Lua to force the "array" portion of a table at be least X large, on an adjustable, per table (or per metatable) basis?

In this hypothetical case, nil would mean empty, but you would not have to worry about the array portion collapsing due to sparsity.

In other words, other than avoiding unwanted table collapsing, are there other benefits to empty?

(I have no idea how much work it would be to make this hypothetical extension to Lua, nor how palatable other Lua users would find it.)

-Parke


Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Miles Bader-2
In reply to this post by Tim Hill
Tim Hill <[hidden email]> writes:
> "empty", to my mind, is just a value stored as a placeholder so that
> an array stays an array when it has "holes" .. perhaps what's
> messing people around is my use of the name "empty" .. perhaps
> "hole" might be better (? "black hole").

Er, how about "placeholder"

That emphasizes the fact that it's essentially a normal "thing" with
no particular meaning or use other than being put places...

[Of course, then people would start using it for stuff... >< ]

-miles

--
Conservative, n. A statesman enamored of existing evils, as opposed to a
Liberal, who wants to replace them with new ones.

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

steve donovan
On Mon, Jul 1, 2013 at 10:23 AM, Miles Bader <[hidden email]> wrote:
Er, how about "placeholder"

Much better word than 'sentinel' in my opinion. It isn't a fancy concept. I agree with Roberto that we already have a standard value for this purpose; false.


Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Dirk Laurie-2
In reply to this post by Tim Hill
2013/7/1 Tim Hill <[hidden email]>:

> My feeling was that simply adding a standard way to do this avoided both of
> these work-arounds.

Inspired by all this, I wrote a module called 'empty'.

$ lua -l empty
Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio
> x={1,2,empty,empty,5}
> =x[3]
empty
> type(x[3])
> =type(x[3])
empty

I'm not telling anybody how it works. Maybe it invokes a totally different
interpreter that fakes the official appearance. Maybe it's pure Lua.
Maybe it's a C module.

What, apart from the fact that you need to require it, makes it fall
short of what is desired? Only the fact that the official Lua does
not have it and does not document it?

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Miles Bader-2
In reply to this post by steve donovan
steve donovan <[hidden email]> writes:
>> Er, how about "placeholder"
>
> Much better word than 'sentinel' in my opinion. It isn't a fancy concept. I
> agree with Roberto that we already have a standard value for this purpose;
> false.

false is what I normally use, but every once in a while I have a case
where I also want to store boolean values.

Of course, in that case, I just make my own out-of-band value...

-miles

--
Non-combatant, n. A dead Quaker.

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Thomas Jericke
In reply to this post by Philipp Janda

>
>> Is it better to have 20 different workarounds to a common problem
>> than one simple, clear, language supported fix?
>
> If you want arrays with holes, there are basically only three
> different workarounds:
>
> 1.  use nil for the holes
>     pro: - saves memory for very sparse arrays
>          - fits well with varargs and table.(un)pack.
>          - no mapping from hole to nil required
>     con: - needs explicit length field
>          - needs metatable if you want `#` and `ipairs` to work
>
> 2.  use a sentinel value for holes
>     pro: - can use `#` and `ipairs` without metatable magic
>     con: - cannot handle large sparse arrays
>          - does not mix well with {...} and table.pack( ... )
>
> 3.  use some specialized container class/object
>     pro: - can't be mistaken for a raw table
>          - can implement whatever policy you see fit
>     con: - does not feel like a raw table
>
Actually I think if 1. would become part of the standard library it
wouldn't be a workaround.

Lets assume there would be a sparse array library. It would not replace
the current one, as the current is maybe good for some uses (I hardly
use it myself to be honest).

The new "array" library would always use a metatable to store the length
and would not use a sentinel. This new library defines __len and
__ipairs etc.

What I suggest, is to actually use solution 1. but make it official. To
make it official would avoid the chaos of different implementations.

I would prefer this solution as it it solves the problem you have at the
very point where it appears, in the array. If you introduce an "empty"
type you have to expect that this empty type will pop up at all the
other places within the language. And why solution 1? It's the only
solution that is able to story any values and lets one use the array
type as a normal table.

--
Thomas


Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Eike Decker
2013/7/1 Thomas Jericke <[hidden email]>:

>
>>
>> If you want arrays with holes, there are basically only three different
>> workarounds:
>>
>> 1.  use nil for the holes
>>     pro: - saves memory for very sparse arrays
>>          - fits well with varargs and table.(un)pack.
>>          - no mapping from hole to nil required
>>     con: - needs explicit length field
>>          - needs metatable if you want `#` and `ipairs` to work
>>
>> 2.  use a sentinel value for holes
>>     pro: - can use `#` and `ipairs` without metatable magic
>>     con: - cannot handle large sparse arrays
>>          - does not mix well with {...} and table.pack( ... )
>>
>> 3.  use some specialized container class/object
>>     pro: - can't be mistaken for a raw table
>>          - can implement whatever policy you see fit
>>     con: - does not feel like a raw table
>>
> Actually I think if 1. would become part of the standard library it wouldn't
> be a workaround.
>
> Lets assume there would be a sparse array library. It would not replace the
> current one, as the current is maybe good for some uses (I hardly use it
> myself to be honest).
>
> The new "array" library would always use a metatable to store the length and
> would not use a sentinel. This new library defines __len and __ipairs etc.
>
(...)

I hope to make here a substantial different contribution on the entire
discussion here.
Couldn't a lot of ambiguity and unexpected behavior avoided by keeping
nil but introducing two new functions to the table library called
"table.has(t,key)" and "table.delete(t,key,[to])" - and dropping the
deletion via assigning nil?

I consider this a mix of Tim's request and the counter arguments
against another new value.
To sum it up, here's the behavior:
- nil is a valid key / value in a table and creates a new allocation
- the value of any key that does not exist in a table is nil
- a key/value can be deleted from a table with a function call that
takes care of erasing that value (we actually have table.remove which
has however a different meaning)
- Existence of a key can be checked with a special function call
Implications:
- arrays can contain nil and the #length operator works as expected
even when nil is involved
- a distinction between nil/empty can be made without introducing a new value
- unpack works as expected (see other mail by Mark Melling who was
confused here - just one example of many)
- Deletion is a more "conscious" operation that is not depended on
function argument values or whatever

I can understand both sides of arguments brought up in the entire
discussion here (I didn't read it all) but I think my points here
could make sense for both parties.

Cheers,
Eike

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Roberto Ierusalimschy
> Couldn't a lot of ambiguity and unexpected behavior avoided by keeping
> nil but introducing two new functions to the table library called
> "table.has(t,key)" and "table.delete(t,key,[to])" - and dropping the
> deletion via assigning nil?

At last something new and worth a discussion. Does anyone see problems/
incompatibilities/etc. with this?

(But what is "[to]"?)

Keep in mind that #t would still be undefined for arrays with holes,
but holes would be much less frequent...

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Coda Highland
On Mon, Jul 1, 2013 at 11:04 AM, Roberto Ierusalimschy
<[hidden email]> wrote:

>> Couldn't a lot of ambiguity and unexpected behavior avoided by keeping
>> nil but introducing two new functions to the table library called
>> "table.has(t,key)" and "table.delete(t,key,[to])" - and dropping the
>> deletion via assigning nil?
>
> At last something new and worth a discussion. Does anyone see problems/
> incompatibilities/etc. with this?
>
> (But what is "[to]"?)
>
> Keep in mind that #t would still be undefined for arrays with holes,
> but holes would be much less frequent...
>
> -- Roberto
>

The only incompatibility I can see is that "t[#t] = nil" no longer
works as a "pop" operation for a stack-like array; you'd have to use
"table.delete(t, #t)" instead.

Also, I think "[to]" there is for a range delete, like
"table.delete(t, 3, 5)" removes elements 3, 4, and 5.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Rena
In reply to this post by Roberto Ierusalimschy

On Jul 1, 2013 2:05 PM, "Roberto Ierusalimschy" <[hidden email]> wrote:
>
> > Couldn't a lot of ambiguity and unexpected behavior avoided by keeping
> > nil but introducing two new functions to the table library called
> > "table.has(t,key)" and "table.delete(t,key,[to])" - and dropping the
> > deletion via assigning nil?
>
> At last something new and worth a discussion. Does anyone see problems/
> incompatibilities/etc. with this?
>
> (But what is "[to]"?)
>
> Keep in mind that #t would still be undefined for arrays with holes,
> but holes would be much less frequent...
>
> -- Roberto
>

This seems like a good idea, but I feel like it might complicate the internals a bit. Are you proposing that nil is able to be stored in tables, and keys can be removed only by table.delete()? (In that case, why is #t still undefined when holes are present? Or are nil keys no longer holes?) That could be useful, but also a bit confusing as it means a key set to nil and a key that was never set (or was deleted) are different things, but both have a nil value.

Personally I was always fond of the method used in previous versions (and that seems to be making a comeback with table.pack) - treat "array" as a special case of table. An array would have a field "n" telling how many elements are in it. Then iterating, inserting, deleting etc would just be from 1 to n regardless of the contents. (You could even still add or clear elements manually as long as you take care to keep n up to date.) In other words, it's table.getn/setn, but with n being an ordinary field in the table rather than a special attribute that can only be accessed through helper functions.

This could already be done without any changes to the language by an 'array' module, though that still leaves table.remove, table.insert etc which could be a bit confusing. (Such a module could also offer the ability to set a metatable that would "magically" keep n up to date, or leave you to manage it yourself.)

Although I feel like this is a new topic entirely - the original question was about having keys with nil values, and I'm not sure whether that refers to integer keys in the middle of an array, or named keys - the solutions differ. The OP had mentioned wanting to be able to map a database column to a Lua table transparently and needing a portable, standardized "null but not nil" value to store in those tables to indicate that the column exists but has a value of null in that row.

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Petite Abeille
In reply to this post by Roberto Ierusalimschy

On Jul 1, 2013, at 8:04 PM, Roberto Ierusalimschy <[hidden email]> wrote:

>> Couldn't a lot of ambiguity and unexpected behavior avoided by keeping
>> nil but introducing two new functions to the table library called
>> "table.has(t,key)" and "table.delete(t,key,[to])" - and dropping the
>> deletion via assigning nil?
>
> At last something new and worth a discussion. Does anyone see problems/
> incompatibilities/etc. with this?

I, for one, find this an unnecessary and taxing complication, pandering to a minority taste.

Unnecessarily because, if one care enough about it, one can use placeholders and/or metamethods to shape a table whichever way one sees fit.
Taxing because, under such a schema, what used to be a primitive, immediate table operation ( t[ k ] = nil ) has become an esoteric, indirect library operation ( table.delete( t, k ) ).
Minority taste because, while not beyond useful every now and then, it's not worth the overall quotidian complications.

A bit of the perfect (full fledge nil support) being the enemy of the good (primitive key removal).

Just my 2¢.


Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Tim Hill
In reply to this post by Dirk Laurie-2
That way really my only point .. that such a "blessing" will help interoperability. It was never HOW to implement such a feature privately … that's easy. It was just "I *think* this might be useful to have as an agreed-upon way to do something".

Think about booleans in C; they don't exist as a 1st class type, but they DO have an agreed-upon standard representation (that compilers understand). If we didn't have that, every project would define it's own arbitrary true and false, and each project, by itself, would work fine. But then each 3rd party library you use would have a different standard, and you would have to have conversion logic to transition between their arbitrary boolean and yours; for each and every library. Urgh!

My feeling, based upon some pretty heavy use of Lua, was that marking array elements as "unused", or "empty" or "placeholder" (whatever you want to call it) fell (perhaps only just) into that category too, though from the discussion here the consensus seems to be that this is not the case.

--Tim

On Jul 1, 2013, at 1:40 AM, Dirk Laurie <[hidden email]> wrote:

What, apart from the fact that you need to require it, makes it fall
short of what is desired? Only the fact that the official Lua does
not have it and does not document it?

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Javier Guerra Giraldez
In reply to this post by Roberto Ierusalimschy
On Mon, Jul 1, 2013 at 1:04 PM, Roberto Ierusalimschy
<[hidden email]> wrote:
>> Couldn't a lot of ambiguity and unexpected behavior avoided by keeping
>> nil but introducing two new functions to the table library called
>> "table.has(t,key)" and "table.delete(t,key,[to])" - and dropping the
>> deletion via assigning nil?
>
> At last something new and worth a discussion. Does anyone see problems/
> incompatibilities/etc. with this?


I'm not sure i would like this better than the current behavior or
not, but it's a _very_ different behavior.

in fact, this feels a little like Python's dictionaries.  i don't mean
that every difference between Python and Lua is automatically a win
for Lua and lose for Python, but such change would certainly make Lua
a lot closer to Python than where it is today.

also, i guess this would have massive incompatibilities, unless it's
an optional behavior....  maybe a "sticky" flag in the metatable (akin
to the 'weak' flags), meaning that key/value pairs stick around until
you explicitly remove them...



--
Javier

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Coda Highland
In reply to this post by Rena
On Mon, Jul 1, 2013 at 11:36 AM, Rena <[hidden email]> wrote:

> On Jul 1, 2013 2:05 PM, "Roberto Ierusalimschy" <[hidden email]>
> wrote:
>>
>> > Couldn't a lot of ambiguity and unexpected behavior avoided by keeping
>> > nil but introducing two new functions to the table library called
>> > "table.has(t,key)" and "table.delete(t,key,[to])" - and dropping the
>> > deletion via assigning nil?
>>
>> At last something new and worth a discussion. Does anyone see problems/
>> incompatibilities/etc. with this?
>>
>> (But what is "[to]"?)
>>
>> Keep in mind that #t would still be undefined for arrays with holes,
>> but holes would be much less frequent...
>>
>> -- Roberto
>>
>
> This seems like a good idea, but I feel like it might complicate the
> internals a bit. Are you proposing that nil is able to be stored in tables,
> and keys can be removed only by table.delete()? (In that case, why is #t
> still undefined when holes are present? Or are nil keys no longer holes?)

Under this proposal, nils are no longer holes.

> That could be useful, but also a bit confusing as it means a key set to nil
> and a key that was never set (or was deleted) are different things, but both
> have a nil value.

You can tell the difference with table.has().

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Tim Hill

On Jul 1, 2013, at 12:05 PM, Coda Highland <[hidden email]> wrote:

Under this proposal, nils are no longer holes.

That could be useful, but also a bit confusing as it means a key set to nil
and a key that was never set (or was deleted) are different things, but both
have a nil value.

You can tell the difference with table.has().

Depending on how # behaved, you might also be able to tell with just (i <= #t) ?

I find this whole idea interesting, though it does make the meaning of nil more confusing in a table. I suspect the end-game for this model is declarative array sizes .. not sure what I think of this, as that does look more like just using a private "n" stored in the table somewhere.

--Tim

Reply | Threaded
Open this post in threaded view
|

Re: new "empty" value/type in Lua?

Coda Highland
On Mon, Jul 1, 2013 at 12:11 PM, Tim Hill <[hidden email]> wrote:
>>> That could be useful, but also a bit confusing as it means a key set to nil
>>> and a key that was never set (or was deleted) are different things, but both
>>> have a nil value.
>> You can tell the difference with table.has().
> Depending on how # behaved, you might also be able to tell with just (i <=
> #t) ?

table.has() is a generic mechanism for all tables, not just arrays --
a sparse array or a freeform table could still have nil-valued entries
as distinct from nonexistent entries.

/s/ Adam

123456