Re: [Caml-list] overflow checks on `int` operations

[Stefan Monnier <monnier@iro.umontreal.ca>]

Thanks Gabriel and Glen,

Not sure how I missed the version that's in Batteries,


        Stefan


Gabriel Scherer [2019-07-11 08:44:11] wrote:

> The compiler has defined predicates (in utils/misc.ml) that test whether
> the operation would overflow on the given inputs.
>
> let no_overflow_add a b = (a lxor b) lor (a lxor (lnot (a+b))) < 0
>
> let no_overflow_sub a b = (a lxor (lnot b)) lor (b lxor (a-b)) < 0
>
> (* Taken from Hacker's Delight, chapter "Overflow Detection" *)
> let no_overflow_mul a b =
>   not ((a = min_int && b < 0) || (b <> 0 && (a * b) / b <> a))
>
> let no_overflow_lsl a k =
>   0 <= k && k < Sys.word_size && min_int asr k <= a && a <= max_int asr k
>
> Batteries exposes functions similar in spirit to Glen's Arith module (they
> raise an exception on overflow) as part of the Int.SafeInt module:
>
>
> https://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatInt.Safe_int.html
>
> On Thu, Jul 11, 2019 at 1:06 AM Glen Mével <glen.mevel@crans.org> wrote:
>
>> Stefan Monnier wrote (2019-07-10 22:36):
>> > What's the "standard" way to perform arithmetic operations on `int`
>> > with overflow checking (e.g. returning an `Option` or signaling an
>> > exception on overflow)?
>> I don’t know whether there is a “standard” for integers specifically,
>> but the rationale for option vs. exception is the following: exceptions
>> are used for behaviours that are not meant to happen, (ie. program
>> errors), whereas options are used for the normal course of a program.
>> For instance, depending on your application, the fact that an element is
>> unbound in a hash table may be an expected fact that should be dealt with.
>>
>> In this case, I would advocate for exceptions, because an overflow is
>> clearly a failure of the program: the bounds on native integers are only
>> related to the internals of the OCaml runtime, thus it is very unlikely
>> to have any meaning in your application. It is also likely that you may
>> not work around an overflow, except by running the same computation with
>> zarith. If you expect overflows with int, maybe you should use zarith.
>>
>> Throwing an exception allows you to interrupt your program and track
>> precisely where the overflow occurred (with the stack trace), either by
>> wrapping your whole computation in a single exception handler, or by
>> letting the runtime handle the exception.
>>
>> With options, by contrast, either you would write an option handler
>> around each problematic operation, or you would propagate the option,
>> which implies (1) rewriting your whole computation in a monadic style
>> and (2) losing the provenance of a None. And you would pay a penalty for
>> boxing your integers.
>>
>> > Currently I do the checks by hand but it occurred to me that maybe I'm
>> > not the first one to want that.
>>
>> You’re not indeed. For my own needs, I wrote carefully overflowing
>> versions of some usual arithmetic functions[1]. But more serious
>> projects may be available, I guess.
>>
>> [1]:
>> https://gitlab.crans.org/mevel/project-euler-lib/blob/master/Arith.mli
>>
>> --
>> Glen Mével
>>
>>