Changes between Version 13 and Version 14 of Commentary/Libraries/Integer
 Timestamp:
 Jan 31, 2014 6:41:14 PM (18 months ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Commentary/Libraries/Integer
v13 v14 17 17 All Integer implementations should export the same set of types and functions from `GHC.Integer` (within whatever `integer` package you are using). These exports are used by the `base` package However, all of these types and functions must actually be defined in `GHC.Integer.Type`, so that GHC knows where to find them. 18 18 Specifically, the interface is this: 19 {{{20 data Integer21 19 22 mkInteger :: Bool  True <=> nonnegative 20 {{{#!hs 21 data Integer 22 23 mkInteger :: Bool  True <=> nonnegative 23 24 > [Int]  Absolute value in 31 bit chunks, least significant first 24 25  ideally these would be Words rather than Ints, but 25  we don't have Word available at the moment. 26  we don't have Word available at the moment. (why?) 26 27 > Integer 27 28 28 29 29 smallInteger :: Int# > Integer 30 integerToInt :: Integer > Int# 30 31 31 32 32 wordToInteger :: Word# > Integer 33 integerToWord :: Integer > Word# 33 34 34 35  And similarly for Int64#, Word64# on 64bit 35 36 36 37 38 37 floatFromInteger :: Integer > Float# 38 decodeFloatInteger :: Float# > (# Integer, Int# #) 39 encodeFloatInteger :: Integer > Int# > Float# 39 40 40 41  And similarly Double 41 42 42 43 44 45 46 47 48 49 43 plusInteger :: Integer > Integer > Integer 44  And similarly: minusInteger, timesInteger, negateInteger, 45  eqInteger, neqInteger, absInteger, signumInteger, 46  leInteger, gtInteger, ltInteger, geInteger, compareInteger, 47  divModInteger, quotRemInteger, quotInteger, remInteger, 48  andInteger, orInteger, xorInteger, complementInteger, 49  shiftLInteger, shiftRInteger, 50  hashInteger, 50 51 }}} 51 52 … … 55 56 56 57 * '''Core'''. In `Core` representation, an integer literal is represented by the `LitInteger` constructor of the `Literal` type. 57 {{{ 58 {{{#!hs 58 59 data Literal = ...  LitInteger Integer Type 59 60 }}} … … 61 62 62 63 * '''Constant folding'''. There are many constantfolding optimisations for `Integer` expressed as builtin rules in [[GhcFile(compiler/prelude/PrelRules.lhs)]]; look at `builtinIntegerRules`. All of the types and functions in the `Integer` interface have builtin names, e.g. `plusIntegerName`, defined in [[GhcFile(compiler/prelude/PrelNames.lhs)]] and included in `basicKnownKeyNames`. This allows us to match on all of the functions in `builtinIntegerRules` in [[GhcFile(compiler/prelude/PrelRules.lhs)]], so we can constantfold Integer expressions. An important thing about constant folding of Integer divisions is that they depend on inlining. Here's a fragment of `Integral Integer` instance definition from `libraries/base/GHC/Real.lhs`: 63 {{{ 64 instance 64 {{{#!hs 65 instance Integral Integer where 65 66 toInteger n = n 66 67 … … 73 74 74 75 * '''Converting between Int and Integer'''. It's quite commonly the case that, after some inlining, we get something like `integerToInt (intToInteger i)`, which converts an `Int` to an `Integer` and back. This ''must'' optimise away (see #5767). We do this by requiring that the `integer` package exposes 75 {{{ 76 smallInteger :: Int# > Int 76 {{{#!hs 77 smallInteger :: Int# > Integer 77 78 }}} 78 79 Now we can define `intToInteger` (or, more precisely, the `toInteger` method of the `Integral Int` instance in `GHC.Real` ) thus 79 {{{ 80 80 {{{#!hs 81 toInteger (I# i) = smallInteger i 81 82 }}} 82 83 And we have a RULE for `integerToInt (smallInteger i)`. … … 89 90 90 91 * '''Don't inline integer functions'''. Most of the functions in the Integer implementation in the `integer` package are marked `NOINLINE`. For example in `integergmp` we have 91 {{{ 92 {{{#!hs 92 93 plusInteger :: Integer > Integer > Integer 93 94 plusInteger (S# i1) (S# i2) = ... 94 95 plusInteger (S# i1) (J# j1 j2) = ... 95 ...two more cases...96  ...two more cases... 96 97 }}} 97 98 Not only is this a big function to inline, but inlining it typically does no good because the representation of literals is abstact, so no patternmatching cancellation happens. And even if you have `(a+b+c)`, the conditionals mean that no cancellation happens, or you get an exponential code explosion!