"default word size" in the documentation for Util/Random

[YawarRaza7349]

Version

110.99.8 (Latest)

Operating System

• Any
• Linux
• macOS
• Windows
• Other Unix

OS Version

No response

Processor

• Any
• Arm (using Rosetta)
• PowerPC
• Sparc
• x86 (32-bit)
• x86-64 (64-bit)
• Other

System Component

SML/NJ Library

Severity

Cosmetic

Description

The documentation of the Random module of the SML/NJ library uses the terms "native word size" and "default word size". What does "default word size" mean here? If it just means "native word size minus 1" then it would be clearer to just say that.

If it's supposed to mean "the size of the type assigned to the global unqualified word type" — as it does in the docs for MONO_HASH_TABLE —, then the implementation does not account for this. For example, on MLton, where the unqualified word defaults to 32-bits, if the native word size is 64-bits, then randInt generates a random 63-bit word and calls toIntX on it (which is actually based on the default int size, not word size, though MLton's default int happens to also be 32-bits), thus Overflowing if the result doesn't fit in the 32-bit int. Based on the docs, one would expect it to instead always generate a number between -2^30 and 2^30 - 1 and thus never overflow.

It would probably be easier to just change the docs to change "default word size" to "native word size minus 1" because you'd technically also need to account for the case where the default word size is larger than the native word size, where you'd need to generate multiple random words and yadda yadda yadda (or you could ignore this niche case, I guess). I don't know if the SML spec guarantees properties about relative sizes of some types, which could make some (not all) concerns here moot.

Transcript

No response

Expected Behavior

No response

Steps to Reproduce

See MLton/mlton#617

Additional Information

No response

Email address

ysr7349@rit.edu

[JohnReppy]

Native word size means the natural size of a machine word (i.e., the size of a pointer). The default word size is the size of the default word/int type. For SML/NJ, the native word size is 32/64, with corresponding default sizes of 31/63. It is true that one could have a default integer type that is larger than the native word size (i.e., IntInf.int), but I don't think that is likely for words. BTW, the SML/NJ library defines structure aliases for NativeInt and NativeWord.

I have reclassified this as a documentation issue, since the code behaves correctly for SML/NJ (after all, it is the SML/NJ Library).

Since MLton patches the library in their release, the overflow issue could be fixed in the patching.

[JohnReppy]

After thinking about it a bit more, if we use the following conversions in the randInt and randWord functions, then the code should work for MLton even when the default word size is 32 bits:

fun w64ToWord w = Word.fromLarge(Word64.toLarge w)
fun w64ToInt w = Word.toIntX(w64ToWord w)

Basically, we are discarding bits from the top of the word instead of the bottom. I don't know what, if any, impact that change has on the distribution of random values. If one assumes that all 64-bit patterns are equally likely, then I think that the distribute will still be uniform.

Also, I think that this code should work for systems that use IntInf.int as the default integer type, but if the default word size is larger than 64 bits, then randInt will only return positive values.

[YawarRaza7349]

Yeah, looking back at this, I don't know why I opened this issue, since the "default word size" was just matching with the function signature's return type, so if SML/NJ aligns the default types with the native types, the current code works fine for it. (I personally have a pet peeve of unneeded non-zero-cost code, so I think this should go in the MLton patch.)

[JohnReppy]

I'm not sure what the "unneeded non-zero-cost code" is in this case. The conversion is required because there is a difference in representation. Anyway, I'm going to reopen the issue because I am making some changes to both the code and documentation to address it.