Question about negative Integers

[Edward Kmett]

> Question is: do we need/want to keep this behavior?

I think we really do want to keep this behavior.

And not just because I for one have a decent cross-section of code that
would just become horribly broken (and would have to find some way to
jerry-rig the existing behavior anyways) if we randomly changed it.

The current underlying representation if more directly exposed would be
quite surprising to users and doesn't at all fit the mental model of what
an Int-like thing is.

Other examples: Conor McBride's work on co-deBruijn syntax exploits the
current Bits instance heavily (and can be greatly streamlined by making
more use of it that he doesn't, quite yet.)

-Edward

On Fri, Nov 15, 2019 at 9:34 PM Sylvain Henry <sylvain at haskus.fr> wrote:

> Hi GHC devs,
>
> As some of you may know, I am working on fixing several longstanding
> issues with GHC's big numbers implementation (Integer, Natural). You can
> read more about it here:
>
> https://gitlab.haskell.org/hsyl20/ghc/raw/hsyl20-integer/libraries/ghc-bignum/docs/ghc-bignum.rst
>
> To summarize, we would have a single `ghc-bignum` package with different
> backends (GMP, pure Haskell, etc.). The backend is chosen with a Cabal
> flag and new backends are way easier to add. All the backends use the
> same representation which allows Integer and Natural types and datacons
> to be wired-in which has a lot of nice consequences (remove some
> dependency hacks in base package, make GHC agnostic of the backend used,
> etc.).
>
> A major roadblock in previous attempts was that integer-simple doesn't
> use the same representations for numbers as integer-gmp. But I have
> written a new pure Haskell implementation which happens to be faster
> than integer-simple (see perf results in the document linked above) and
> that uses the common representation (similar to what was used in
> integer-gmp).
>
> I am very close to submit a merge request but there is a remaining
> question about the Bits instance for negative Integer numbers:
>
> We don't store big negative Integer using two's complement encoding,
> instead we use signed magnitude representation (i.e. we use constructors
> to distinguish between (big) positive or negative numbers). It's already
> true today in integer-simple and integer-gmp. However integer-gmp and
> integer-simple fake two's complement encoding for Bits operations. As a
> consequence, every Bits operation on negative Integers does *a lot* of
> stuff. E.g. testing a single bit with `testBit` is linear in the size of
> the number, a logical `and` between two numbers involves additions and
> subtractions, etc.
>
> Question is: do we need/want to keep this behavior? There is nothing in
> the report that says that Integer's Bits instance has to mimic two's
> complement encoding. What's the point of slowly accessing a fake
> representation instead of the actual one? Could we deprecate this? The
> instance isn't even coherent: popCount returns the negated numbers of 1s
> in the absolute value as it can't return an infinite value.
>
> Thanks,
> Sylvain
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20191116/d1e94be3/attachment.html>