MOD issue about voc HOT 21 OPEN

hello, @Oleg-N-Cher!
thank you for the links, interesting discussions.
I agree with Comdiv. (:

also, this is from the report:

My understanding, based on communication with ETH team is that Wirth himself and ETH compilers always assume that the remainder cannot be negative, just like we learnt in school.
When I was doing x86 code generator for Oberon-07, one of the Wirth's tests was failing just because I did not handle the issue correctly.

Back then I tested many compilers and I believe only ooc wasn't following the report on it. All ETH compilers have checks for this, and all Wirth's compilers handle this issue.

@dcwbrown would you run builds or take a look at the pull request #92 to confirm it's ok to merge?

from voc.

Oberon has not negative literals. I.e. -5 MOD 3 = -(5 MOD 3), and you need (-5) MOD 3
So this is not a bug, it's feature. Just write (-5) MOD 3

from voc.

Unary minus has lower priority, than MOD.

from voc.

The corresponding topic on the forums:

Приоритет унарного минуса
• https://forum.oberoncore.ru/viewtopic.php?f=29&t=5870

Повысить приоритет унарного минуса (и плюса) легко! Но стОит ли...
• https://zx.oberon.org/forum/viewtopic.php?f=32&t=290

from voc.

Well, this is quite interesting.

The specs from the original Oberon, Oberon 2 and Oberon 07+ all define DIV and MOD behaviour only for positive divisors.

Here they are:

From Oberon (Wirth October 1990)

  The operators DIV and MOD apply to integer operands only.
  They are related by the following formulas defined for any dividend
  x and positive divisors y:

    x = (x DIV y) * y  +  (x MOD y)
    0 ≤ (x MOD y) < y

From Oberon2 (H. Mössenböck, N. Wirth)

  The operators DIV and MOD apply to integer operands only.
  They are related by the following formulas defined for any
  x and positive divisors y:

    x = (x DIV y) * y + (x MOD y)
    0 ≤ (x MOD y) < y

From Oberon 2007+ (Wirth May 2016)

  The operators DIV and MOD apply to integer operands only. 
  Let q = x DIV y, and r = x MOD y. 
  Then quotient q and remainder r are defined by the equation 
    
    x = q*y + r     0 <= r < y 

Note that Wirth has moved his description from prose to formula in his latest spec, but that he still limits the spec to describing cases where 0 <= r < y.

Now consider the cases where x is negative and y is positive (i.e. where the spec tells us what the correct result must be).

The Oberon2 spec actually includes examples:

  Examples:
    x  y  x DIV y  x MOD y
    5  3     1        2
   -5  3    -2         1

Happily, voc gets these right. (Norayr, you didn't say explicitly whether you acknowledged Olegs point about unary operators, so with apologies for being tedious, to avoid ambiguity: providing you test with (-5) MOD 3 as is required by the Oberon priority rules, you will get the correct (i.e. positive) answer.

And so we come to what should happen if the divisor is negative.

To be clear, Wirth has chosen explicitly to omit this case from the specification of Oberon.

However Component Pascal does define it:

  The operators DIV and MOD apply to integer operands only. 
  They are related by the following formulas:

    x  = (x DIV y) * y + (x MOD y)
    0 <= (x MOD y) < y   or   0 >= (x MOD y) > y

  Note: x DIV y = ENTIER(x/y)

  Examples:
    
    x  y   x DIV y   x MOD y
    5  3      1         2
   -5  3     -2         1
    5 -3     -2        -1
   -5 -3      1        -2

They have specified that when the divisor is negative, so is the result of MOD.

One can look at it like this:

x MOD 5 means: give me an offset in the range 0 .. 4 inclusive.

while

x MOD (-5) means: give me an offset in the range 0..-4 inclusive.

And indeed VOC already conforms to this specification.

Therefore VOC conforms accurately to both Wirth's specification, and to the Component Pascal specification.

Should we change the existing code? I see these two arguments against making this change.

1. The existing code is not broken - it conforms to the specs.
2. Any existing programs being compiled with voc that pass negative divisors to MOD will be broken by this change.

So, I'm sorry to be in conflict Noray, but I would recommend against making this change.

All the best -- Dave.

from voc.

I think I was not clear, so:
Thank you, @Oleg-N-Cher - the discussions were interesting, and my

I agree with Comdiv. (:

means that I agree with the current situation with operator precedence, and I did not realize in the beginning that my test wasn't revealing anything wrong, and everything regarding that is ok.

Thank you, @dcwbrown for explanations. I saw the code handles several cases, but did not understand the reasoning. Now that I know this, and CP solution, it looks reasonable.

However it is still unclear to me if that is the best solution of case with negative divisors.
I am trying to understand how other compilers were implemented, so far I found this:

RISC Oberon V5 (disk image from 2019-01-21, pdewacht's emulator) traps when divisor is negative in both DIV and MOD operations.

Otherwise, MOD result is positive.

x86 OP2 compiler from Linux ETH Oberon output is interesting. It gives us positive result in case of negative divisor 5 MOD -3, just like voc with my changes, but when both dividend and divisor are negative, something strange happens:

I think there is a bug in x86 implementation, and -5 should not happen, but 1 shoud've happened instead.

ETH Oberon compiler for ARM. This is compiler from OLR, descendent from the Ceres version.
this is a screenshot of Qemu with Raspbian and Arm Oberon:

Interesting, that the changelog states:

ARM: made DIV/MOD OBERON compatible; x86 version still gives wrong result for a DIV/MOD b if a and b are negative

So may be Peter Matthias knows something which is not clear to us?

btw, DIV results are also different in three cases:

                                     voc     x86 OP2   ARM OLR
i := 5; j := 3; i DIV j               1         1          1
i := -5; j := 3; i DIV j             -2        -2         -2
i := 5; j := -3; i DIV j             -2        -1         -1
i := -5; j := -3; I DIV j             1         0          2

It seems that when 5 DIV -3, it is a rounding issue, and -5 DIV -3 - again, the x86 OP2 bug?

But let us come to that later. For now, I am getting back to MOD cases.
I think that having a positive MOD result is a right way.
the remainder is something that left out. and the number left out is positive.
Mathematically it is correct: the division theorem page confirms that

for any integers a and b there is a remainder that is 0¶r<|b|

I hope all the screenshots are correctly loaded.
the main question i want us to agree on, is the CP behaviour when MOD result is negative for negative divisors is applicable to Oberon-2 compiler, or Oberon-2 remainder, as in math and ETH tradition(?) should have always positive result of MOD operation?

from voc.

and I am unable to run new OLR for ARM, which is PO version ported to ARM by Peter, because it crashes parsing one of the home directory files, and I cannot debug and fix it because I have no working PO for ARM. But I understand most likely Peter made it the same way he made S3 OLR for ARM, just like I did in this commit.

from voc.

regarding the point of backward compatibility and breaking the existing code:
voc has (and may have in the future) code from ETH Oberon system.
If that code assumes positive result of MOD operation, then the current behaviour may break that code, not my fix.
regarding current voc users - I think there are not many, and we are an open source project, it is okay to change, and notify the users, so they can change with us. what we should adopt is the habit of making minor releases, here on github, and release notes about the changes.

from voc.

it is good to test how V4 handles this. for now I cannot run any V4, linux versions require very old systems, and I have no windows.

from voc.

it is interesting that Oberon reports state
0 ≤ (x MOD y) < y but not 0 ≤ (x MOD y) < |y|

from voc.

ah, because if r is >= 0, then it cannot be at the same time < y which is negative.
so no news, the definition does not define behaviour for negative divisors.

from voc.

for now one more screenshot as a part of on going research.

ofront on 32bit ARM Linux.

from voc.

more discussions

https://groups.google.com/g/comp.lang.oberon/c/QWlSVvuTB3M/m/Z3uW8utpkdAJ?pli=1
https://groups.google.com/g/comp.lang.oberon/c/1UL8zwiswTk/m/MspRbdJWgJ4J

from voc.

this can be found on ulm's compiler site, on a page about differences: http://www.mathematik.uni-ulm.de/oberon/reports/ulmdiff-1994.html

-> 8.2.2. DIV and MOD are defined even for negative operands on the right side. Following rules hold in conformance to [Wirth88] and [Wirth89b]:

	x = (x DIV y) * y + (x MOD y)
0 <= (x MOD y) < y    or   y < (x MOD y) <= 0

apparently first two Oberon reports were defining DIV and MOD for negative operands on the right side, and the result had to be negative.

from voc.

May I suggest to have a look at:
https://github.com/linkrope/oberon2d/blob/master/include/runtime.d

from voc.

today i was reading Josef Templ's Dr. Dobb's Journal Oberon article, published in 1994.

In the section 'type constructors' he writes:

The MOD-operator (positive remainder) yields results including 0. Lower bounds at 0 fit perfectly, for example, for an implementation of a cyclic buffer.

from voc.

I was reading this paper today and stumbled upon these lines:

Because the definition of div/mod in Oberon is more mathematical than it is in C, some ‘glue’ is needed to obtain correct results with negative denominators.

One can only guess what this more mathematical means.

from voc.

"more mathematical" means: if b > 0, then 0 <= a MOD b < b
Example: MOD 10 is always between 0 and 9
C, however, fails this condition: -12 MOD 10 is -2 (instead of 8)

from voc.

If we look at a common sitution where we Inc modulo and sometimes Dec modulo:

FigNr := (FigNr + 1) MOD N;
possible := CheckDisplay(FigNr);
IF possible THEN DrawFigure(FigNr)
ELSE FigNr := (FigNr - 1) MOD N
END

We want
FigNr (before) = FigNr (after Dec) [Modulo N], i.e.
FigNr (before) MOD N = FigNr (after Dec) MOD N.

from voc.

from voc.

Dear Stefan

Thanks a lot for your contribution. This is a very good trick if one wants to program in a manner to reuse the statements in different contexts e.g. in Pascal, Modula-2 and Oberon.

In our case however we are aiming at a clean solution for implementing the language by means of a compiler. By clearly stating the behaviour of the implementation or even better by generally coming to a conclusion what the correct interpretation for the language Oberon is we offer the programmer the possibility to write the most efficient statements.

Eduard

from voc.