caml-list - the Caml user's mailing list
 help / Atom feed
From: Gabriel Scherer <gabriel.scherer@gmail.com>
To: Glen Mével <glen.mevel@crans.org>
Cc: caml users <caml-list@inria.fr>, Stefan Monnier <monnier@iro.umontreal.ca>
Subject: Re: [Caml-list] overflow checks on `int` operations
Date: Thu, 11 Jul 2019 08:44:11 +0200
Message-ID: <CAPFanBH73Fuf-AqAxnp-L8fnQLxdRTaV6YnC+R+PzENTzUnxZw@mail.gmail.com> (raw)
In-Reply-To: <10c67553-1e80-6dea-9ef8-13486746672d@crans.org>

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

  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 [this message]
2019-07-12 18:58     ` Stefan Monnier

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=CAPFanBH73Fuf-AqAxnp-L8fnQLxdRTaV6YnC+R+PzENTzUnxZw@mail.gmail.com \
    --to=gabriel.scherer@gmail.com \
    --cc=caml-list@inria.fr \
    --cc=glen.mevel@crans.org \
    --cc=monnier@iro.umontreal.ca \
    /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