[NoW] About numeric for-loop

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

[NoW] About numeric for-loop

Egor Skriptunoff-2
"NoW" means "Nitpicking on Wednesdays"
(unimportant questions about Lua design and implementation)

Let's start with two simple examples:
   for x = -2^53, -2^53 do print(x) end
   for x = 1e100, 1e100 do print(x) end
Did you expect such results?

There is a problem in numeric "for"-loop: Lua internally exceeds the range of values specified by user.
 
The loop
   for x = a, b, c do ... end
is currently executed as follows:
   y = a - c
   while true do
      y = y + c
      if y <?= b then
         set x = y and execute the loop body
      else
         break
      end
   end
 
The range specified by user is: a <= x <= b
Lua exceeds it in the beginning (first value of y = a-c)
and in the end (the last value of y might be b+c).
It might happen that a-c+c ~= a
It might also happen that b+c == b
User intuitively implies the correctness of addition and comparison operators for values inside the range a <= x <= b
He might not expect that Lua performs calculations beyond this range.
 
Another not-a-good-thing is that Lua uses subtraction in numeric "for"-loop (the loop is supposed to always add and never subtract).
This would prevent generalization of numeric "for"-loop (Sony L. some time ago asked for this useful feature).
Addition and comparison metamethods should be enough to perform generalized numeric "for"-loop with arbitrary user objects.
Such objects must implement operations "obj+obj", "obj==obj", "obj<obj" and "obj<0".
The last one is needed to determine whether the loop is "increasing" (step>0) or "decreasing" (step<0).
 
 
My suggestion is to implement numeric "for"-loop in more accurate way:
- don't use subtraction;
- don't make addition when upper limit is already reached.
 
 
The loop
   for x = a, b, c do ... end
should be executed as follows:
   y = a
   while y <? b do
      set x = y and execute the loop body
      y = y + c
   end
   if y == b then
      set x = y and execute the loop body
   end
 
Lua VM instructions would be the following:
 
[1] FORPREP
[2] loop body
[3] FORLOOP
[4] next instruction after the loop
 
R(A)   = index
R(A+1) = limit
R(A+2) = step
R(A+3) = user loop variable
 

R(A), R(A+1) and R(A+2) might contain user objects instead of Lua numbers.
Operator ">?=" implies comparison of R(A+2) with number 0 to be resolved:
to ">=" for increasing loop, to "<=" for decreasing loop.
 
A trick is used here:
when the index R(A) reaches the limit R(A+1), the step R(A+2) is set to nil to mark the current iteration as final.
No addition is made after the final iteration.
 
function FORPREP(A, sBx)
   if R(A) >?= R(A+1) then
      if R(A) == R(A+1) then
         R(A+2) = nil   -- set step to nil (the next iteration will be final)
      else
         pc+=sBx  -- jump to [4]
         return
      end
   end
   R(A+3)=R(A)
end
 
function FORLOOP(A, sBx)
   if R(A+2) then  -- if step is not nil (if not after the final iteration) 
      R(A)+=R(A+2)
      if R(A) >?= R(A+1) then
         if R(A) == R(A+1) then
            R(A+2) = nil  -- set step to nil (the next iteration will be final)
         else
            return
         end
      end
      R(A+3)=R(A)
      pc+=sBx  -- jump to [2]
   end
end
 
This would involve unnoticeable decrease of performance of usual numeric "for"-loops.

Reply | Threaded
Open this post in threaded view
|

Re: [NoW] About numeric for-loop

Dirk Laurie-2
Op Wo. 16 Jan. 2019 om 23:45 het Egor Skriptunoff
<[hidden email]> geskryf:
>
> "NoW" means "Nitpicking on Wednesdays"
> (unimportant questions about Lua design and implementation)
>
> Let's start with two simple examples:
>    for x = -2^53, -2^53 do print(x) end
>    for x = 1e100, 1e100 do print(x) end
> Did you expect such results?

This is just disguised version of hardy perennial on this list:
(a) relying on equality testing involving floating-point arithmetic
(b) blaming Lua when it does not work as expected.

But I decided this time to read the whole post before replying, so
here is a simple example that illustrates your point without treading
into the floating-point quagmire:

for x=math.maxinteger,math.maxinteger do print(x) end

> There is a problem in numeric "for"-loop: Lua internally exceeds the range of values specified by user.
>  > The loop
>    for x = a, b, c do ... end
> is currently executed as follows:
>    y = a - c
>    while true do
>       y = y + c
>       if y <?= b then
>          set x = y and execute the loop body
>       else
>          break
>       end
>    end

What the 5.3.5 manual actually says is more complicated:

<quote>
...a for statement like

     for v = e1, e2, e3 do block end

is equivalent to the code:

     do
       local var, limit, step = tonumber(e1), tonumber(e2), tonumber(e3)
       if not (var and limit and step) then error() end
       var = var - step
       while true do
         var = var + step
         if (step >= 0 and var > limit) or (step < 0 and var < limit) then
           break
         end
         local v = var
         block
       end
     end
</quote>

> The range specified by user is: a <= x <= b
> Lua exceeds it in the beginning (first value of y = a-c)
> and in the end (the last value of y might be b+c).
> It might happen that a-c+c ~= a
> It might also happen that b+c == b
> User intuitively implies the correctness of addition and comparison operators for values inside the range a <= x <= b
> He might not expect that Lua performs calculations beyond this range.

He should expect that Lua does, unless he is the kind of user that
does not read manuals.

But it acrually makes matters worse that the objectionable behaviour
is not an implementation detail but part of the specification.

> Another not-a-good-thing is that Lua uses subtraction in numeric "for"-loop (the loop is supposed to always add and never subtract).
> This would prevent generalization of numeric "for"-loop (Sony L. some time ago asked for this useful feature).
> Addition and comparison metamethods should be enough to perform generalized numeric "for"-loop with arbitrary user objects.
> Such objects must implement operations "obj+obj", "obj==obj", "obj<obj" and "obj<0".
> The last one is needed to determine whether the loop is "increasing" (step>0) or "decreasing" (step<0).
>
>
> My suggestion is to implement numeric "for"-loop in more accurate way:
> - don't use subtraction;
> - don't make addition when upper limit is already reached.
>
>
> The loop
>    for x = a, b, c do ... end
> should be executed as follows:
>    y = a
>    while y <? b do
>       set x = y and execute the loop body
>       y = y + c
>    end
>    if y == b then
>       set x = y and execute the loop body
>    end

It may happen that y+c is undefined even though upper limit is not
reached. For this code to work, user's objects should therefore
include concept analogous to NaN.

> Lua VM instructions would be the following:
>
> [1] FORPREP
> [2] loop body
> [3] FORLOOP
> [4] next instruction after the loop
>
> R(A)   = index
> R(A+1) = limit
> R(A+2) = step
> R(A+3) = user loop variable
>
> R(A), R(A+1) and R(A+2) might contain user objects instead of Lua numbers.
> Operator ">?=" implies comparison of R(A+2) with number 0 to be resolved:
> to ">=" for increasing loop, to "<=" for decreasing loop.

> A trick is used here:
> when the index R(A) reaches the limit R(A+1), the step R(A+2) is set to nil to mark the current iteration as final.
> No addition is made after the final iteration.

A better trick would be to set the index to nil. Then the user can
simply return nil or nothing when R(A)+R(A+2) is not a valid object.

But all this will still not solve the problem that the following loop
does not work as expected:

> for k=1,2,1/6 do print(k) end
1.0
1.1666666666667
1.3333333333333
1.5
1.6666666666667
1.8333333333333
>

So I have an alternative suggestion.

    Simply avoid using the numerical 'for' when it might get dubious.

Put all the clever tricks in a function 'loop' and use the generic for:

   for v in loop(e1,e2,e3) do

Reply | Threaded
Open this post in threaded view
|

Re: [NoW] About numeric for-loop

Albert Chan

> On Jan 17, 2019, at 12:44 AM, Dirk Laurie <[hidden email]> wrote:
>
> Put all the clever tricks in a function 'loop' and use the generic for:
>
>   for v in loop(e1,e2,e3) do

Like this ?

> function loop(e1,e2,e3)
>>     local i, n = -1, math.floor((e2-e1)/e3)
>>     if e1 + n * e3 == e2 then n = n+1 end
>>     return function()
>>         i = i + 1
>>         if i < n then return e1 + i*e3 end
>>     end
>> end
>
> for k in loop(1,2,1/6) do print(k) end
1.0
1.1666666666667
1.3333333333333
1.5
1.6666666666667
1.8333333333333
2.0

Avoiding accumulated steps rounding error also work:

> for k = 6,12 do print(k/6) end
1.0
1.1666666666667
1.3333333333333
1.5
1.6666666666667
1.8333333333333
2.0
>

Reply | Threaded
Open this post in threaded view
|

Re: [NoW] About numeric for-loop

Albert Chan

>> function loop(e1,e2,e3)
>>>    local i, n = -1, math.floor((e2-e1)/e3)
>>>    if e1 + n * e3 == e2 then n = n+1 end
>>>    return function()
>>>        i = i + 1
>>>        if i < n then return e1 + i*e3 end
>>>    end
>>> end

Uh ... above can be simplified:

function loop(e1, e2, e3)
    local i, n = -1, (e2-e1)/e3
    return function()
        i = i + 1
        if i <= n then return e1 + i*e3 end
    end
end

Reply | Threaded
Open this post in threaded view
|

Re: [NoW] About numeric for-loop

Soni "They/Them" L.


On 2019-01-17 11:52 a.m., Albert Chan wrote:

>>> function loop(e1,e2,e3)
>>>>     local i, n = -1, math.floor((e2-e1)/e3)
>>>>     if e1 + n * e3 == e2 then n = n+1 end
>>>>     return function()
>>>>         i = i + 1
>>>>         if i < n then return e1 + i*e3 end
>>>>     end
>>>> end
> Uh ... above can be simplified:
>
> function loop(e1, e2, e3)
>      local i, n = -1, (e2-e1)/e3
>      return function()
>          i = i + 1
>          if i <= n then return e1 + i*e3 end
>      end
> end
>

See also the implementation details of
https://doc.rust-lang.org/std/ops/struct.RangeInclusive.html

Reply | Threaded
Open this post in threaded view
|

Re: [NoW] About numeric for-loop

Egor Skriptunoff-2
In reply to this post by Dirk Laurie-2
On Thu, Jan 17, 2019 at 8:45 AM Dirk Laurie wrote:
This is just disguised version of hardy perennial on this list:
(a) relying on equality testing involving floating-point arithmetic
(b) blaming Lua when it does not work as expected.
 
But all this will still not solve the problem that the following loop
does not work as expected:
> for k=1,2,1/6 do print(k) end
1.0
1.1666666666667
1.3333333333333
1.5
1.6666666666667
1.8333333333333
>

IMO, this loop works "as expected".
6*(1/6) ~= 1, and everybody reading this list is aware of it  ;-)
Float-comparison is a red herring which prevents you from seeing the main idea of the post.
 
I assume that user knows EVERYTHING about Lua numeric datatypes (floats, integers).
But anyway, Lua could make a surprise due to weird internal logic of numeric "for"-loop.
 


But it actually makes matters worse that the objectionable behaviour
is not an implementation detail but part of the specification.

Exactly!
This strange behavior should not be a part of the language specification!
My suggestion is to add some more LOC in Lua source and make numeric "for"-loop more correct.
 
"More correct" means "to satisfy user's expectations more closely".
For example, the loop "for x = N, N do" should work correctly whatever N is, including the case N==math.huge


 
Put all the clever tricks in a function 'loop' and use the generic for:
   for v in loop(e1,e2,e3) do

It's too slow (to call a Lua function on every iteration).

Reply | Threaded
Open this post in threaded view
|

Re: [NoW] About numeric for-loop

Dirk Laurie-2
Op Do. 17 Jan. 2019 om 21:49 het Egor Skriptunoff
<[hidden email]> geskryf:

> "More correct" means "to satisfy user's expectations more closely".

This is a political statement.

There are no shades of correctness. "Correct" means "conforming to
specification", even if the specification is bad.

Reply | Threaded
Open this post in threaded view
|

Re: [NoW] About numeric for-loop

Roberto Ierusalimschy
In reply to this post by Egor Skriptunoff-2
> "NoW" means "Nitpicking on Wednesdays"
> (unimportant questions about Lua design and implementation)
>
> Let's start with two simple examples:
>    for x = -2^53, -2^53 do print(x) end
>    for x = 1e100, 1e100 do print(x) end
> Did you expect such results?
>
> There is a problem in numeric "for"-loop: Lua internally exceeds the range
> of values specified by user.
>
> [...]

Maybe there is a simpler way for integer loops. I guess we could use
simple arithmetic to precompute, when entering the loop, how many times
it will iterate. Then, during the loop, we simply decrement the counter
until it reaches zero, without worries about overflows.

For loops with floating numbers, I guess the best is to do the "obvious"
computations (without the subtraction), due to all these problems with
precision.

-- Roberto