RfD: 2s-Complement Wrap-Around Integers

[Anton Ertl]

Problem

Many programs depend on 2s-complement representation of negative
integers (e.g., assuming that TRUE is -1), and on wraparound behaviour
on integer overflow, and should declare an environmental dependency on
these features. These programs should become unconditionally standard
programs.

To my knowledge, all Forth systems provide these features and all
architectures developed since about 1970 support 2s-complement (this
includes Chuck Moore's chips), so other signed number representations
are now even less relevant than in the past (when they did not lead to
non-2s-complement Forth systems, either).


Solution

Negative integers are represented as 2s-complement numbers.

On integer overflow of single-cell addition (+ 1+ +! cell+ char+ etc.),
subtraction (- 1- negate abs), multiplication (* chars cells floats
etc.) 2* and d>s the result is the exact result modulo 2^n (for n-bit
cells) leading to wraparound behaviour for + and -; for overflow of d+
d- dnegate dabs m+, the result is the exact result modulo 2^(2*n).

Division by 0 and when the division result does not fit into the
result are still ambiguous conditions (some architectures produce
exceptions in these cases, others don't).

Not sure about F>S F>D.


Typical use

: within ( n a b -- f )
over - >r - r> u< ;

Implementing this without relying on wrap-around arithmetics
is <a href="http://al.howardknight.net/msgid.cgi?ID=143257091900">complicated</a>.


Proposal

Remove permission for one's complement and sign-magnitude from 3.2.1.1.

Replace 3.2.2.2 with: In all integer arithmetic operations except
divisions, both overflow and underflow shall be ignored. Replace the
second sentence with: The value returned when either overflow or
underflow occurs is:

for unsigned results, the exact result modulo 2^n

for signed results, and the exact result r, the number x in the range
2^(n-1)<=x<2^(n-1) that satisfies x congruent r (mod 2^n).

where n is the number of bits in the result.

(can we make this any more understandable without losing precision?).

Replace -32767 with -32768 in 3.1.3.2

(Any other places we have to look after?)


Reference implementation

Any current Forth system.


Test cases

T{ 0 invert -> -1 }T
T{ MAX-INT 1+ -> MIN-INT }T

More TBD.


Experience

Universally implemented and widely used.


- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.mpeforth.com/euroforth2015/euroforth2015.htm

[Alex McDonald]

on 25/05/2015 09:58:19, anton ertl wrote:
> Problem
>
> Many programs depend on 2s-complement representation of negative
> integers (e.g., assuming that TRUE is -1), and on wraparound behaviour
> on integer overflow, and should declare an environmental dependency on
> these features. These programs should become unconditionally standard
> programs.
>

TRUE NEGATE

http://www.urbandictionary.com/define.php?term=%2B1

[Bernd Paysan]

Alex McDonald wrote:

> on 25/05/2015 09:58:19, anton ertl wrote:
>> Problem
>>
>> Many programs depend on 2s-complement representation of negative
>> integers (e.g., assuming that TRUE is -1), and on wraparound behaviour
>> on integer overflow, and should declare an environmental dependency on
>> these features. These programs should become unconditionally standard
>> programs.
>>
>
> TRUE NEGATE

I suggest:

TRUE ABS

short form of Forth syntax for "absolutely true", and also incidently +1
;-).

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

[Anton Ertl]

Changes since the first RfD:

Decided what to do about F>S F>D (overflow stays an ambiguous
condition).

Added a number of additional changes to the Proposal part.

Summarized feedback up to now in the Comments section, plus an answer.

Problem

Many programs depend on 2s-complement representation of negative
integers (e.g., assuming that TRUE is -1), and on wraparound behaviour

on integer overflow, and in the current standard need to declare an

environmental dependency on these features. These programs should
become unconditionally standard programs.

To my knowledge, all Forth systems provide these features and all
architectures developed since about 1970 support 2s-complement (this
includes Chuck Moore's chips), so other signed number representations
are now even less relevant than in the past (when they did not lead to
non-2s-complement Forth systems, either).


Solution

Negative integers are represented as 2s-complement numbers.

On integer overflow of single-cell addition (+ 1+ +! cell+ char+ etc.),
subtraction (- 1- negate abs), multiplication (* chars cells floats

etc.), 2* and d>s the result is the exact result modulo 2^n (for n-bit

cells) leading to wraparound behaviour for + and -; for overflow of d+
d- dnegate dabs m+, the result is the exact result modulo 2^(2*n).

Division by 0 is still an ambiguous condition, as well as when the
division result does not fit into the result type (some architectures

produce exceptions in these cases, others don't).

For F>D and F>S it is still an ambiguous condition if the result does
not fit into the result type (e.g., Gforth produces 0 for F>D with
many too-big inputs).

Typical use

: within ( n a b -- f )
over - >r - r> u< ;

Implementing this without relying on wrap-around arithmetics

is complicated.


Proposal

Remove "Programs that use flags as arithmetic operands have an
environmental dependency." from 3.1.3.1.

Remove permission for one's complement and sign-magnitude from 3.2.1.1.

Replace 3.2.2.2 with:

|In all integer arithmetic operations except divisions, both overflow

|and underflow shall be ignored. The value returned when either
|overflow or underflow occurs in these cases is:

|
|for unsigned results, the exact result modulo 2^n
|

|for signed results, with the exact result being r, the number x in the

|range 2^(n-1)<=x<2^(n-1) that satisfies x congruent r (mod 2^n).
|
|where n is the number of bits in the result.

(can we make this any more understandable without losing precision?).

Replace -32767 with -32768 in 3.1.3.2

4.1.1: Delete "values returned after arithmetic overflow (3.2.2.2
Other integer operations);"

6.1.0570: "An ambiguous condition exists if ud2 overflows during the
conversion." I guess we want to keep that.

A.3.1.2: Delete a) 3)

Delete references to ones-complement and sign-magnitude from A.3.2.1

A.3.2.2.2: Replace "For example, the phrase 1 2 - underflows if the
result is unsigned and produces the valid signed result -1." with "For
example, the phrase 1 2 - underflows and produces the largest unsigned
number if the result is unsigned and produces the valid signed result
-1."

Change example in A.5.2.2 from a dependence on twos-complement to
something else, e.g., byte order.

A.6.2.2440: Delete "For two's-complement machines that ignore
arithmetic overflow (most machines),".

A.8.6.1.1140: Replace the section with: "An alias for DROP that
conveys the intent to convert a double-cell to a single-cell integer.
The original intention of this word was to support signed-number
representations other than twos-complement.".

Delete D.3.2

(Any other places we have to look after?)


Reference implementation

Any current Forth system.


Test cases

T{ 0 invert -> -1 }T
T{ MAX-INT 1+ -> MIN-INT }T

More TBD.


Experience

Universally implemented and widely used.

Comments

Several reactions support the proposal.

Some reactions oppose the proposal, but they give philosophical
reasons (it seems that the idea of these reactions is that the Forth
standard should be machine-independent beyond actually existing
machines) rather than pointing out any real problems that are foreseen
from adopting this proposal.

Note that the Forth standard already contains a number of assumptions
about the machine and environment. E.g., an ASCII-compatible
character set (although there are machines that mostly work with other
character sets), or that cells have at least 16 bits (although there
are machines with smaller word size), or that cells consist of bits
(binary base) rather than, say, decimal digits (decimal computers also
used to exist and have died out, like 1s-complement).