[MLton] user-level elimination of array bounds checks

[Stephen Weeks]

> Don't you also need to check if the arrays are equal?

Agreed.

> > 	    fun get (T (a, i)) = Array.sub (a, i)
> >
> > 	    fun set (T (a, i), x) = Array.update (a, i, x)
> 
> Presumably these are the Unsafe sub and updates.

Yes.

> > 	    fun next (T (a, i)) = elt (a, i + 1)
> >
> > 	    fun prev (T (a, i)) = elt (a, i - 1)
> 
> I would think that the following is just a little more efficient:
> 
>             fun next (T (a, i)) = let val j = i + 1
>                                   in if j < Array.length a
>                                         then SOME (T (a, j))
>                                      else NONE
>                                   end
>             fun prev (T (a, i)) = let val j = i - 1
>                                   in if 0 <= j
>                                         then SOME (T (a, j))
>                                      else NONE
>                                   end
> 
> The point is that a value T (a, i) of type 'a Elt.t is definitely within
> bounds, so we know that 0 <= i andalso i < Array.length a.  Hence, it
> certainly follows that 0 <= i + 1 andalso i - 1 < Array.length a.
> Actually, the real point is that if the value was created too far away,
> then the optimizer won't be able to see the bounds check used to create
> the value.

Agreed, bu it doesn't matter.  It will all be a single test in the end
because I would implement the bounds check as an unsigned comparison.

fun elt (a, i) =
   if Word.fromInt i < Word.fromInt (Array.length a)
      then SOME (Elt.T (a, i))
   else NONE