caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] overflow checks on `int` operations
@ 2019-07-10 20:36 Stefan Monnier
  2019-07-10 23:05 ` Glen Mével
  0 siblings, 1 reply; 4+ messages in thread
From: Stefan Monnier @ 2019-07-10 20:36 UTC (permalink / raw)
  To: caml-list

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.


^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [Caml-list] overflow checks on `int` operations
  2019-07-10 20:36 [Caml-list] overflow checks on `int` operations Stefan Monnier
@ 2019-07-10 23:05 ` Glen Mével
  2019-07-11  6:44   ` Gabriel Scherer
  0 siblings, 1 reply; 4+ messages in thread
From: Glen Mével @ 2019-07-10 23:05 UTC (permalink / raw)
  To: caml-list; +Cc: Stefan Monnier


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

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [Caml-list] overflow checks on `int` operations
  2019-07-10 23:05 ` Glen Mével
@ 2019-07-11  6:44   ` Gabriel Scherer
  2019-07-12 17:44     ` Stefan Monnier
  0 siblings, 1 reply; 4+ messages in thread
From: Gabriel Scherer @ 2019-07-11  6:44 UTC (permalink / raw)
  To: Glen Mével; +Cc: caml users, Stefan Monnier

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

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [Caml-list] overflow checks on `int` operations
  2019-07-11  6:44   ` Gabriel Scherer
@ 2019-07-12 17:44     ` Stefan Monnier
  0 siblings, 0 replies; 4+ messages in thread
From: Stefan Monnier @ 2019-07-12 17:44 UTC (permalink / raw)
  To: Gabriel Scherer; +Cc: Glen Mével, caml users

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


^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2019-07-12 18:58 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-07-10 20:36 [Caml-list] overflow checks on `int` operations Stefan Monnier
2019-07-10 23:05 ` Glen Mével
2019-07-11  6:44   ` Gabriel Scherer
2019-07-12 17:44     ` Stefan Monnier

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).