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

[Gabriel Scherer <gabriel.scherer@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2964 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 3846 bytes --]