[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Bug report in length of simple table
- From: Miroslav Janíček <mira.janicek@...>
- Date: Thu, 15 Sep 2016 01:42:27 +0200
> On 15 Sep 2016, at 0:15, Ross Berteig <Ross@CheshireEng.com> wrote:
>
> On 9/14/2016 2:16 PM, Miroslav Janíček wrote:
>>> On 14 Sep 2016, at 16:04, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
>>> ...
>>> Note that any table has at least one border.
>>> Note also that keys that are not a non-negative integer
>>> do not interfere with the notion of borders.
>>
>> Are these two notes correct?
>>
>> It seems to me that a table with non-nil values for all positive
>> integer keys {1 … math.maxinteger}, *and* a non-nil value for the key
>> (math.maxinteger + 1) would not have a border.
>
> I'm not sure there are practical versions of Lua where that table could actually exist. It would have to be built with a small enough integer type that a table with half of all possible integral keys could fit within (virtual) memory.
Bah, that’s an implementation detail ;)
But you’re of course right — we probably won’t see systems that could handle such tables for 64-bit integers in our lifetimes. However, I think it’s perfectly possible to have such a table with 32-bit integers, even today.
(As a side note: in my reading of the Lua Reference
Manual I haven’t been able to conclusively discard the
possibility that computing sequence length involves
invoking the __index metamethod. I know it sounds silly,
but I think that a Lua implementation that would do that
would still be “legal” according to the manual. Now, in
such an implementation, the __index metamethod
function (t, k) if k > 0 then return k; else return nil; end end
would do the trick for any integer width.)
But anyway, that wasn’t really the point. The point is that under this definition, it seems that there exists a sequence that does not have a length.
I think the fix could be quite simple, along the following lines:
* if t[1] == nil, then 0 is a border;
* let MAX be the maximum value for an integer, then MAX
is a border if t[MAX] ~= nil;
* for all positive integers i, if t[i] ~= nil and t[i+1] == nil,
then i is a border.
Plus: a table is a sequence if and only if it has exactly one border.
> That said, I'm not certain that the definition of sequence cares about whether the keys are specifically integer type numbers. So the number math.maxinteger will be 2^63-1, and 2^63 can be exactly represented in 64-bit float. 2^63+1 cannot, and that is probably where the fuzzy non-border happens.
I must admit I’m not exactly sure what you mean. Suppose the table contains a non-nil value for the key with the mathematical value of 2^63 (a float), and a non-nil value for (2^63 - 1). Should (2^63 - 1) be a border?
M.