[MLton] IntInf implementation questions

[Matthew Fluet]

>> I think this is an artefact of the long-gone days before MLton
>> supported overflow.  It seems fine to replace as you suggest.
>
> In fact, since the IntInf implementation has not been substantially
> revised since those days, it probably has a number of similar
> artefacts that would benefit from rewriting to take advantage of
> overflow.

I don't see any others.  Given two IntInf integers represented as small 
integers (say, 32 bits == 31 bits data + 1 bit tag), then the small 
integer + and - (say, Int32.+ and Int32.-) can't overflow, although the 
resulting value may not be expressible as a small integer with a tag bit.

Of course, we could use overflow checking if we don't completely convert 
the small integer into it's 32 bit representation.  That is, consider 
bigPlus:

       (* Coercion to/from 32-bit representation. *)
       fun stripTag (arg: bigInt): Word.word =
          Word.~>> (Prim.toWord arg, 0w1)
       fun addTag (argw: Word.word): Word.word =
          Word.orb (Word.<< (argw, 0w1), 0w1)

       fun zeroTag (arg: bigInt): Word.word =
          Word.andb (Prim.toWord arg, 0wxFFFFFFFE)
       fun incTag (argw: Word.word): Word.word =
          Word.orb (argw, 0w1)

       (* Check if two words have the same sign bit. *)
       fun sameSign (lhs: Word.word, rhs: Word.word): bool =
          Word.toIntX (Word.xorb (lhs, rhs)) >= 0

       fun bigPlus (lhs: bigInt, rhs: bigInt): bigInt =
          let
             val res =
                if areSmall (lhs, rhs)
                   then let val ansv = Word.+ (stripTag lhs, stripTag rhs)
                            val ans = addTag ansv
                        in if sameSign (ans, ansv)
                              then SOME (Prim.fromWord ans)
                           else NONE
                        end
                else NONE
          in
             case res of
                NONE =>
                   dontInline
                   (fn () =>
                    Prim.+ (lhs, rhs, reserve (Int.max (size lhs, size rhs), 1)))
              | SOME i => i
          end

On the small fast path, I count 6 bitops and one comparison test.  (Note 
that Word.{fromInt,toIntX} are the identity functions.)  I think the 
following is equivalent:

       fun bigPlus (lhs: bigInt, rhs: bigInt): bigInt =
          let
             val res =
                if areSmall (lhs, rhs)
                   then let val ansv = Int.+ (Word.toIntX (Prim.toWord lhs),
                                              Word.toIntX (zeroTag rhs))
                        in SOME (Prim.fromWord (Word.fromInt ansv))
                        end handle Overflow => NONE
                else NONE
          in
             case res of
                NONE =>
                   dontInline
                   (fn () =>
                    Prim.+ (lhs, rhs, reserve (Int.max (size lhs, size rhs), 1)))
              | SOME i => i
          end

On the small fast path, I count 2 bitops and one overflow test.  I think 
you can do the same thing for bigMinus.