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

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

[Stefan Monnier]

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

Currently I do the checks by hand but it occurred to me that maybe I'm
not the first one to want that.


        Stefan


PS: I'm not looking to have all arithmetic on `int` with overflow
checks: only some specific uses of them.

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

[Glen Mével]

[-- Attachment #1.1: Type: text/plain, Size: 2043 bytes --]

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: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

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

[Gabriel Scherer]

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

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

[Stefan Monnier]

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