# [MLton] user-level elimination of array bounds checks

**Stephen Weeks
**
MLton@mlton.org

*Fri, 23 Jan 2004 07:32:53 -0800*

>* 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