Virgin tables

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

Virgin tables

Dirk Laurie
All the trouble people have with the table length function and
the table library, well over 100 posts by now, come down to one
thing, and one thing only:

    The functions designed for use on tables without holes
    don't actually give an error message when applied to
    tables with holes.

Now it is very Lua-like to treat a programmer as a responsible
adult, but perhaps just a tiny bit of supervision may be useful.

I suggest this:
    a function called table.virgin(t), returning 'true' if the
    table t has never had a hole and 'false' otherwise.

Advantages:

*   In a virgin table, #t is virtuous: it equals both the largest
    numeric index and the number of entries with numeric keys.
*   If you are very strict, you can replace table.insert etc by
    versions that will warn you when you try to use the function
    on a non-virgin table.  
*   It's an O(1) function.  Virginity is lost by t[k]=nil for
    k<#t and by t[k]=non_nil for k>#t+1, both easy to test.
*   #t would be O(1) for all virgin tables.  (At present, many
    numeric entries may actually reside in the hash part of the
    table, and then #t takes O(log n) time.)

Disadvantages:

*   It would be inefficient if not in the standard library.  

Now of course it would be possible for a non-virgin table, after
undergoing certain operations, to be free of holes again.  To cover
the case where there is reason to believe that might be true, there
could also be a function table.absolve(t), that would test whether t
is hole-free and in that case restore the property of virginity.

Dirk


Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

KHMan
On 12/30/2010 1:56 PM, Dirk Laurie wrote:

> All the trouble people have with the table length function and
> the table library, well over 100 posts by now, come down to one
> thing, and one thing only:
>
>      The functions designed for use on tables without holes
>      don't actually give an error message when applied to
>      tables with holes.
>
> Now it is very Lua-like to treat a programmer as a responsible
> adult, but perhaps just a tiny bit of supervision may be useful.
> [snip]

Then they will forget to check for virginity and complain very
loudly on this list why the table is not a virgin. Ha ha ha. :-)
:-) Beginning to sound like a Richard Branson gimmick. :-p

Nay, people need to put in the hours to get the experience. No
such thing as an expert who didn't invest in the time and effort.

Put it another way: How much nanny supervision do we need before
we make everyone happy? Impossible to please everyone these
days... the other side has to do some leg work too.

[Just "IMHO" opinions, I do think you should keep the ideas
flowing, I have no problems with that :-)]

--
Cheers,
Kein-Hong Man (esq.)
Kuala Lumpur, Malaysia

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Mark Hamburg
A simpler answer is to provide an array namespace. In fact, the table namespace should probably become the array namespace with the addition perhaps of a call metamethod on the namespace so that you can use it as a constructor. arrays have an explicit length (stored somewhere) and appropriate metamethods to maintain it.

Mark


Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

steve donovan
On Thu, Dec 30, 2010 at 8:26 AM, Mark Hamburg <[hidden email]> wrote:
> A simpler answer is to provide an array namespace....arrays have an explicit length (stored somewhere) and appropriate metamethods to maintain it.

It's a question of using the appropriate data structure for the job.
[1] is a reasonably robust array with bounds-checking, where setting
nil is prohibited so that no holes can happen. It uses newproxy() to
make the object so that the table functions cannot be used on it.

With a little work this can also be made a type-safe array, so one can
approach the Platonic Ideal of a Pascal array.

OK, so it obviously is going to be less efficient. But the old Irish
programming principle applies: Slow but sure, and fail noisily!

steve d.

[1] https://gist.github.com/759589 [2]
[2] Yes, I should use http://snippets.luacode.org/, but it barfed at
this code. [3]
[3] I have complained to the maintainer, who happens to be myself.

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Rena
On Thu, Dec 30, 2010 at 01:28, steve donovan <[hidden email]> wrote:

> On Thu, Dec 30, 2010 at 8:26 AM, Mark Hamburg <[hidden email]> wrote:
>> A simpler answer is to provide an array namespace....arrays have an explicit length (stored somewhere) and appropriate metamethods to maintain it.
>
> It's a question of using the appropriate data structure for the job.
> [1] is a reasonably robust array with bounds-checking, where setting
> nil is prohibited so that no holes can happen. It uses newproxy() to
> make the object so that the table functions cannot be used on it.
>
> With a little work this can also be made a type-safe array, so one can
> approach the Platonic Ideal of a Pascal array.
>
> OK, so it obviously is going to be less efficient. But the old Irish
> programming principle applies: Slow but sure, and fail noisily!
>
> steve d.
>
> [1] https://gist.github.com/759589 [2]
> [2] Yes, I should use http://snippets.luacode.org/, but it barfed at
> this code. [3]
> [3] I have complained to the maintainer, who happens to be myself.
>
>

I had been pondering the idea of having #t just return nil if the
table has holes so people will get the idea that it's undefined.

--
Sent from my toaster.

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Luiz Henrique de Figueiredo
In reply to this post by Dirk Laurie
> *   It's an O(1) function.  Virginity is lost by t[k]=nil for
>     k<#t and by t[k]=non_nil for k>#t+1, both easy to test.

How is it O(1)? Do you have a sample implementation?

> *   #t would be O(1) for all virgin tables.  (At present, many
>     numeric entries may actually reside in the hash part of the
>     table, and then #t takes O(log n) time.)

Like I said before, full arrays can have part of their data stored
in the hash part:
        http://lua-users.org/lists/lua-l/2010-12/msg00400.html

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

David Kastrup
In reply to this post by Dirk Laurie
Dirk Laurie <[hidden email]> writes:

> All the trouble people have with the table length function and
> the table library, well over 100 posts by now, come down to one
> thing, and one thing only:
>
>     The functions designed for use on tables without holes
>     don't actually give an error message when applied to
>     tables with holes.
>
> Now it is very Lua-like to treat a programmer as a responsible
> adult, but perhaps just a tiny bit of supervision may be useful.
>
> I suggest this:
>     a function called table.virgin(t), returning 'true' if the
>     table t has never had a hole and 'false' otherwise.

Could you choose another name for that concept?  I find the association
of virginity with holes rather inappropriate.

Also, there may be tables that have become externally as well as
internally indistinguishable from virgin, even though they have had a
history involving holes.

So something like "linear" or, if you must, "pure" would seem more
appropriate.

--
David Kastrup


Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Alexander Gladysh
On Thu, Dec 30, 2010 at 14:30, David Kastrup <[hidden email]> wrote:
> Dirk Laurie <[hidden email]> writes:

> Could you choose another name for that concept?  I find the association
> of virginity with holes rather inappropriate.

The name is inappropriate, I second that.

> Also, there may be tables that have become externally as well as
> internally indistinguishable from virgin, even though they have had a
> history involving holes.

> So something like "linear" or, if you must, "pure" would seem more
> appropriate.

Um. If table has a hole, it is not a pure table? Looks weird.

Linear table seems to be more or less OK.

That being said, I believe that this subject of holes received too
much attention in the list lately.

Can we maybe discuss something more rational?

The problem is not with the language design (alternatives are worse,
as was discussed many times here), the problem is with user education.
Better to spend energy in that direction than to break lances about
the characteristic language feature that would not change in
foreseeable future.

Alexander.

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Roberto Ierusalimschy
In reply to this post by Dirk Laurie
> All the trouble people have with the table length function and
> the table library, well over 100 posts by now, come down to one
> thing, and one thing only:
>
>     The functions designed for use on tables without holes
>     don't actually give an error message when applied to
>     tables with holes.

And the reason we have well over 100 posts by now comes down to one
thing only: most people do not read those past 100 posts, or do not
understand what some of them say. So they keep repeating proposals that
are either not implementable in an efficient way (despite claims to the
opposite) or that do not actually solve the problem.

-- Roberto


uki
Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

uki


2010/12/30 Roberto Ierusalimschy <[hidden email]>
> All the trouble people have with the table length function and
> the table library, well over 100 posts by now, come down to one
> thing, and one thing only:
>
>     The functions designed for use on tables without holes
>     don't actually give an error message when applied to
>     tables with holes.

And the reason we have well over 100 posts by now comes down to one
thing only: most people do not read those past 100 posts, or do not
understand what some of them say. So they keep repeating proposals that
are either not implementable in an efficient way (despite claims to the
opposite) or that do not actually solve the problem.

-- Roberto


-- 
local tab = {1,2,3,4,5, [666]=6}

print('table length = ',#tab)
print('table maxn = ',table.maxn(tab))
print('table isvirgin ',table.maxn(tab)==#tab)
--
I don't think that 'virgin' feature should be added, because it already is implemented :)

And about the name for that function, I chuckled whan I saw it ;)
Though it might be better to not name it that way.

Cheers,
--
Łukasz Gruner
Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Axel Kittenberger
> print('table isvirgin ',table.maxn(tab)==#tab)

And again another # pitfall. This might or might not return true for
tables with holes!

I wonder how many more bugs will be out there due to people expecting
# to be in this or that way, other than the random indix when called
upon a table with hole.

Personally I too consider for a language that presents itself as easy
and the code looking tidy, the # notion an unfortunate stumbling block
I'm sure many more people will get their nose bloody.

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Steve Litt
On Thursday 30 December 2010 07:30:31 Axel Kittenberger wrote:

> > print('table isvirgin ',table.maxn(tab)==#tab)
>
> And again another # pitfall. This might or might not return true for
> tables with holes!
>
> I wonder how many more bugs will be out there due to people expecting
> # to be in this or that way, other than the random indix when called
> upon a table with hole.
>
> Personally I too consider for a language that presents itself as easy
> and the code looking tidy, the # notion an unfortunate stumbling block
> I'm sure many more people will get their nose bloody.

Which brings us full circle to when somebody asked me why one should have
obj.setx("whatever") instead of just setting x. obj.setx("whatever") could see
whether obj["x"] exists, and if not increment obj["numberOfElements"] so that
obj["numberOfElements"] represents the true number of elements. But the minute
a hurried and uninformed maintenance programmer sets an element directly
(obj.x="whatever"), all bets are off and the program breaks far away from the
maintenance programmer's mistake.

Hey, I'm not saying that level of encapsulation is always the right way to go,
but it does have its purposes.

SteveT

Steve Litt
Recession Relief Package
http://www.recession-relief.US
Twitter: http://www.twitter.com/stevelitt


Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Alexander Gladysh
On Thu, Dec 30, 2010 at 15:49, Steve Litt <[hidden email]> wrote:
> On Thursday 30 December 2010 07:30:31 Axel Kittenberger wrote:

>> Personally I too consider for a language that presents itself as easy
>> and the code looking tidy, the # notion an unfortunate stumbling block
>> I'm sure many more people will get their nose bloody.

> Which brings us full circle to when somebody asked me why one should have
> obj.setx("whatever") instead of just setting x. obj.setx("whatever") could see
> whether obj["x"] exists, and if not increment obj["numberOfElements"] so that
> obj["numberOfElements"] represents the true number of elements. But the minute
> a hurried and uninformed maintenance programmer sets an element directly
> (obj.x="whatever"), all bets are off and the program breaks far away from the
> maintenance programmer's mistake.

You should politely explain to this programmer that he is wrong (level
of politeness and means of explanation, of course, depend on the
corporate culture and the amount of damage). Otherwise we'd come to,
say, rewriting os.execute, so it would not accept a fork bomb as an
argument.

Besides, the proper way of protection here is a proxy metatable, not
setx() method.

That being said, I must note that I'm for the maximum feasible
strictness and validation myself — as long as it is practical — but
you have to draw a line somewhere. Otherwise you will come into
stasis.

Alexander.

uki
Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

uki
In reply to this post by Axel Kittenberger


2010/12/30 Axel Kittenberger <[hidden email]>
> print('table isvirgin ',table.maxn(tab)==#tab)

And again another # pitfall. This might or might not return true for
tables with holes!

I wonder how many more bugs will be out there due to people expecting
# to be in this or that way, other than the random indix when called
upon a table with hole.

Personally I too consider for a language that presents itself as easy
and the code looking tidy, the # notion an unfortunate stumbling block
I'm sure many more people will get their nose bloody.



Please correct me if I'm wrong:
* if table has no holes # works
* if table has holes you don't know what # will return (it might return proper length or lenght of the first 'block' up till the first hole)
Do I understand this properly?

--
Łukasz Gruner
Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

"J.Jørgen von Bargen"
Am 30.12.2010 14:14, schrieb uki:
> Please correct me if I'm wrong:
> * if table has no holes # works
> * if table has holes you don't know what # will return (it might
> return proper length or lenght of the first 'block' up till the first
> hole)
> Do I understand this properly?
You missed one:
... or the last index of any fragment

But I have one other question:

Assuming a table which is virgin, how does virgin_table[0]=something
affect # ? Is this predictable?

Regards, Jørgen

uki
Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

uki
2010/12/30 "J.Jørgen von Bargen" <[hidden email]>
Am 30.12.2010 14:14, schrieb uki:

Please correct me if I'm wrong:
* if table has no holes # works
* if table has holes you don't know what # will return (it might return proper length or lenght of the first 'block' up till the first hole)
Do I understand this properly?
You missed one:
... or the last index of any fragment
[...] 

Thanks,

Then there is absolutely no way to check if the table has holes, except by iterating through the whole table.
So if you didn't create that table, you shouldn't use # on it.

I think I finally understand why everyone is so agitated by this issue. 
From a lua-newbie perspective, I think that it would be logical to have # throw an error when it can't return 'proper' length.

*Makes mental note to be _very_ carefull with using '#' *
--
Łukasz Gruner
Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Henning Diedrich
In reply to this post by Roberto Ierusalimschy
On 12/30/10 12:49 PM, Roberto Ierusalimschy wrote:

... keep repeating proposals that
are either not implementable in an efficient way (despite claims to the
opposite) or that do not actually solve the problem.

Has it been pointed out, if/why it would be costly to throw an error for #t if a list t ever had holes?

Can't find that in the thread.

Thanks,
Henning
Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Patrick Mc(avery
With only a basic understanding of metatables and environments I have no
business posting to this thread but if you will forgive the ignorance.....

Would it be possible to craft a mechanism to flag whether or not a table
had holes? The flag could be set once a hole was created. This way the
whole table would not have to be iterated later. Is this not just a
true-false issue? surely the performance hit would be minimal.

Could I also propose the "solid" to refer to tables without holes

Thanks-Patrick

P.S does anyone know if a list of Lua gotchas was every generated from
the thread a couple of weeks ago, I learned a lot from it.

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Luiz Henrique de Figueiredo
In reply to this post by Henning Diedrich
> Has it been pointed out, if/why it would be costly to throw an error for
> #t if a list t ever had holes?

The message by uki before yours says it all: "there is absolutely no way to
check if the table has holes, except by iterating through the whole table."

Reply | Threaded
Open this post in threaded view
|

Re: Virgin tables

Henning Diedrich
On 12/30/10 3:41 PM, Luiz Henrique de Figueiredo wrote:
Has it been pointed out, if/why it would be costly to throw an error for 
#t if a list t ever had holes?
The message by uki before yours says it all: "there is absolutely no way to
check if the table has holes, except by iterating through the whole table."
I was asking, 'had', thinking of a flag for that, as Patrick just elaborated.

Henning

[message repost with intact thread subject]
1234