Unsigned integer types

[eduardoleon]

Many functions only make sense when applied to nonnegative integers (e.g., List.nth). However, because Standard ML doesn't have an unsigned integer type, one has to use signed integers, and then hopefully not forget to implement a nonnegativity check. I'd like a proper unsigned integer type, so that the check is performed automatically and at compile-time, rather than manually and at runtime.

I can anticipate an argument that I should use the existing word type. However, as useful as the word type may be for certain use cases (e.g., processing files with non-textual contents), it isn't a good general-purpose unsigned integer type for the following reasons:

• It wraps around on over or underflow, rather throwing an exception. This is acceptable, perhaps even desirable, for low-level bit twiddling, but not for doing arithmetic in most applications.
• word constants are represented textually as hexadecimals preceded by 0w. To get the more familiar decimal representations of numeric values, one would have to translate back and forth between word and int all over the place.

Unsigned integers should be provided in modules with the usual INTEGER signature, subject to the following constraints:

• minInt is always SOME 0
• abs is the identity function
• sign never returns ~1
• ~ raises Overflow if its argument isn't 0
• - raises Overflow if its first argument is less than the second
• div and quot are the same function
• mod and rem are the same function

[RobertHarper]

this suggestion, at least, does not sound hard to implement!

On Jul 3, 2016, at 00:18, eduardoleon [email protected] wrote:

Many functions only make sense when applied to nonnegative integers (e.g., List.nth). However, because Standard ML doesn't have an unsigned integer type, one has to use signed integers, and then hopefully not forget to implement a nonnegativity check. I'd like a proper unsigned integer type, so that the check is performed automatically and at compile-time, rather than manually and at runtime.

I can anticipate an argument that I should use the existing word type. However, as useful as the word type may be for certain use cases (e.g., processing files with non-textual contents), it isn't a good general-purpose unsigned integer type for the following reasons:

It wraps around on over or underflow, rather throwing an exception. This is acceptable, perhaps even desirable, for low-level bit twiddling, but not for doing arithmetic in most applications.

word constants are represented textually as hexadecimals preceded by 0w. To get the more familiar decimal representations of numeric values, one would have to translate back and forth between word and int all over the place.

Unsigned integers should be provided in modules with the usual INTEGER signature, subject to the following constraints:

minInt is always SOME 0
abs is the identity function
sign never returns ~1
~ raises Overflow if its argument isn't 0

• raises Overflow if its first argument is less than the second
  div and quot are the same function
  mod and rem are the same function
  —
  You are receiving this because you are subscribed to this thread.
  Reply to this email directly, view it on GitHub Unsigned integer types #17, or mute the thread https://github.com/notifications/unsubscribe/ABdsdUHxCmVpdL01F3QoTc0qTgeQO1idks5qRzgNgaJpZM4JDzLM.

[JohnReppy]

First, decimal word literals are supported (e.g., 0w10). The reason for the "0w" prefix is similar to the reason the SML requires real literals to have a decimal point.

The problem with this suggestion is that there is no hardware support for underflow checking, so you would take a performance hit on subtraction and negation. Since subscripting already checks for negative indices, I don't think that we gain much from such a type.

BTW, exceptions on integer overflow are a real pain for deterministic parallel computation, because so much code can potentially raise an exception, but is very unlikely to do so. I'm not sure if the right choice is to relax the requirement for sequential semantics where exceptions are concerned, or switch to C-style integer arithmetic.