caml-list - the Caml user's mailing list
 help / Atom feed
From: Stefan Monnier <monnier@iro.umontreal.ca>
To: Gabriel Scherer <gabriel.scherer@gmail.com>
Cc: Glen Mével <glen.mevel@crans.org>,  caml users <caml-list@inria.fr>
Subject: Re: [Caml-list] overflow checks on `int` operations
Date: Fri, 12 Jul 2019 13:44:22 -0400
Message-ID: <jwvims7up1g.fsf-monnier+diro@gnu.org> (raw)
In-Reply-To: <CAPFanBH73Fuf-AqAxnp-L8fnQLxdRTaV6YnC+R+PzENTzUnxZw@mail.gmail.com>

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


      reply index

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-07-10 21:26 Stefan Monnier
2019-07-10 23:05 ` Glen Mével
2019-07-11  6:43   ` Gabriel Scherer
2019-07-12 18:58     ` Stefan Monnier [this message]

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=jwvims7up1g.fsf-monnier+diro@gnu.org \
    --to=monnier@iro.umontreal.ca \
    --cc=caml-list@inria.fr \
    --cc=gabriel.scherer@gmail.com \
    --cc=glen.mevel@crans.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

caml-list - the Caml user's mailing list

Archives are clonable: git clone --mirror https://inbox.ocaml.org/caml-list

AGPL code for this site: git clone https://public-inbox.org/ public-inbox