<div dir="ltr">> Question is: do we need/want to keep this behavior?<br><div><br></div><div>I think we really do want to keep this behavior. </div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.)<br></div><div><br></div><div>-Edward</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Nov 15, 2019 at 9:34 PM Sylvain Henry <<a href="mailto:sylvain@haskus.fr">sylvain@haskus.fr</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi GHC devs,<br>
<br>
As some of you may know, I am working on fixing several longstanding <br>
issues with GHC's big numbers implementation (Integer, Natural). You can <br>
read more about it here: <br>
<a href="https://gitlab.haskell.org/hsyl20/ghc/raw/hsyl20-integer/libraries/ghc-bignum/docs/ghc-bignum.rst" rel="noreferrer" target="_blank">https://gitlab.haskell.org/hsyl20/ghc/raw/hsyl20-integer/libraries/ghc-bignum/docs/ghc-bignum.rst</a><br>
<br>
To summarize, we would have a single `ghc-bignum` package with different <br>
backends (GMP, pure Haskell, etc.). The backend is chosen with a Cabal <br>
flag and new backends are way easier to add. All the backends use the <br>
same representation which allows Integer and Natural types and datacons <br>
to be wired-in which has a lot of nice consequences (remove some <br>
dependency hacks in base package, make GHC agnostic of the backend used, <br>
etc.).<br>
<br>
A major roadblock in previous attempts was that integer-simple doesn't <br>
use the same representations for numbers as integer-gmp. But I have <br>
written a new pure Haskell implementation which happens to be faster <br>
than integer-simple (see perf results in the document linked above) and <br>
that uses the common representation (similar to what was used in <br>
integer-gmp).<br>
<br>
I am very close to submit a merge request but there is a remaining <br>
question about the Bits instance for negative Integer numbers:<br>
<br>
We don't store big negative Integer using two's complement encoding, <br>
instead we use signed magnitude representation (i.e. we use constructors <br>
to distinguish between (big) positive or negative numbers). It's already <br>
true today in integer-simple and integer-gmp. However integer-gmp and <br>
integer-simple fake two's complement encoding for Bits operations. As a <br>
consequence, every Bits operation on negative Integers does *a lot* of <br>
stuff. E.g. testing a single bit with `testBit` is linear in the size of <br>
the number, a logical `and` between two numbers involves additions and <br>
subtractions, etc.<br>
<br>
Question is: do we need/want to keep this behavior? There is nothing in <br>
the report that says that Integer's Bits instance has to mimic two's <br>
complement encoding. What's the point of slowly accessing a fake <br>
representation instead of the actual one? Could we deprecate this? The <br>
instance isn't even coherent: popCount returns the negated numbers of 1s <br>
in the absolute value as it can't return an infinite value.<br>
<br>
Thanks,<br>
Sylvain<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div>