2s-Complement Wrap-Around Integers

Poll standings

Systems

[ ] conforms to ANS Forth.
  Gforth (Anton Ertl)
  iForth (Marcel Hendrix)
  CForth (Mitch Bradley)
  Open Firmware (Mitch Bradley)
  bigForth (Bernd Paysan)
  SwiftForth (Leon Wagner)
  SwiftX (Leon Wagner)
  JavaForth (Peter Knaggs)
  IronForth (Peter Knaggs)
[ ] already implements the proposal in full since release [ ].
  Gforth 0.1alpha (Anton Ertl)
  iForth 0 (Marcel Hendrix)
  amForth 0.1 (Matthias Trute)
  CForth (Mitch Bradley)
  Open Firmware (Mitch Bradley)
  bigForth 1.0 (Bernd Paysan)
  SwiftForth all (Leon Wagner)
  SwiftX all (Leon Wagner)
  TurboForth (Mark Wills, for TI-99/4A)
[ ] implements the proposal in full in a development version.
[ ] will implement the proposal in full in release [ ].
[ ] will implement the proposal in full in some future release.
[ ] There are no plans to implement the proposal in full in [ ].
[ ] will never implement the proposal in full.
  JavaForth (Peter Knaggs)
  IronForth (Peter Knaggs)

Programmers

[ ] I have used (parts of) this proposal in my programs.
 Leon Wagner
 Bernd Paysan
 Mitch Bradley
 Anton Ertl
 Marcel Hendrix
 Matthias Trute
 Mark Wills
[ ] I would use (parts of) this proposal in my programs if the systems
     I am interested in implemented it.
 Anton Ertl
 Marcel Hendrix
 Matthias Trute
 Mark Wills
[ ] I would use (parts of) this proposal in my programs if this
     proposal was in the Forth standard.
 Mark Wills
[ ] I would not use (parts of) this proposal in my programs.
 Tim Partridge

Informal results

You forget 4.1.2:

producing a result out of range, e.g., multiplication (using *) results in  
a value too big to be represented by a single-cell integer (6.1.0090 *,  
6.1.0100 */, 6.1.0110 */MOD, 6.1.0570 >NUMBER,
6.1.1561 FM/MOD, 6.1.2214 SM/REM, 6.1.2370 UM/MOD, 8.6.1.1820 M*/);

Hans Bezemer writes:

4tH is implemented in C and consequently takes on the identity of the
compilant. And that is how it should be IMHO. Enforcing 2s-complement would
mean implementing my own arithmatic routines - and that I won't do.

On the other hand, lots of double, unsigned and floating point library
routines of 4tH are based on 2s complement. However, if a user on a signed
magnitude or 1s complement machine would adapt them and offer them for
inclusion, I'd include 'em.

I think a standard should unify stuff by abstraction - not exclude
technologies by being specific. So, this vote is a whole-hearted NO. If this
means 4tH is diverging from Forth-200x then it is what it is.

Proposal etc.

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; examples are hash functions and cryptography.  In
the current standard these programs 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).

Author

Voting instructions

Note that you can be both a system implementor and a programmer, so you can submit both kinds of ballots.

Ballot for systems

[ ] conforms to ANS Forth.
[ ] already implements the proposal in full since release [ ].
[ ] implements the proposal in full in a development version.
[ ] will implement the proposal in full in release [ ].
[ ] will implement the proposal in full in some future release.
[ ] There are no plans to implement the proposal in full in [ ].
[ ] will never implement the proposal in full.

Ballot for programmers

[ ] I have used (parts of) this proposal in my programs.
[ ] I would use (parts of) this proposal in my programs if the systems
     I am interested in implemented it.
[ ] I would use (parts of) this proposal in my programs if this
     proposal was in the Forth standard.
[ ] I would not use (parts of) this proposal in my programs.