Changes between Version 13 and Version 14 of Commentary/Libraries/Integer


Ignore:
Timestamp:
Jan 31, 2014 6:41:14 PM (18 months ago)
Author:
hvr
Comment:

tweaks to markup

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Libraries/Integer

    v13 v14  
    1717All 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.
    1818Specifically, the interface is this:
    19 {{{
    20   data Integer
    2119
    22   mkInteger :: Bool -- True <=> non-negative
     20{{{#!hs
     21data Integer
     22
     23mkInteger :: Bool   -- True <=> non-negative
    2324          -> [Int]  -- Absolute value in 31 bit chunks, least significant first
    2425                    -- 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?)
    2627          -> Integer
    2728   
    28   smallInteger  :: Int# -> Integer
    29   integerToInt  :: Integer -> Int#
     29smallInteger  :: Int# -> Integer
     30integerToInt  :: Integer -> Int#
    3031 
    31   wordToInteger :: Word# -> Integer
    32   integerToWord :: Integer -> Word#
     32wordToInteger :: Word# -> Integer
     33integerToWord :: Integer -> Word#
    3334
    34   -- And similarly for Int64#, Word64# on 64-bit
     35-- And similarly for Int64#, Word64# on 64-bit
    3536
    36   floatFromInteger  :: Integer -> Float#
    37   decodeFloatInteger :: Float# -> (# Integer, Int# #)
    38   encodeFloatInteger :: Integer -> Int# -> Float#
     37floatFromInteger  :: Integer -> Float#
     38decodeFloatInteger :: Float# -> (# Integer, Int# #)
     39encodeFloatInteger :: Integer -> Int# -> Float#
    3940
    40   -- And similarly Double
     41-- And similarly Double
    4142
    42   plusInteger :: Integer -> Integer -> Integer
    43   -- And similarly: minusInteger, timesInteger, negateInteger,
    44   -- eqInteger, neqInteger, absInteger, signumInteger,
    45   --  leInteger, gtInteger, ltInteger, geInteger, compareInteger,
    46   --  divModInteger, quotRemInteger, quotInteger, remInteger,
    47   --  andInteger, orInteger, xorInteger, complementInteger,
    48   --  shiftLInteger, shiftRInteger,
    49   --  hashInteger,
     43plusInteger :: 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,
    5051}}}
    5152
     
    5556
    5657 * '''Core'''.  In `Core` representation, an integer literal is represented by the `LitInteger` constructor of the `Literal` type.
    57 {{{
     58{{{#!hs
    5859data Literal = ... | LitInteger Integer Type
    5960}}}
     
    6162
    6263 * '''Constant folding'''.  There are many constant-folding optimisations for `Integer` expressed as built-in rules in [[GhcFile(compiler/prelude/PrelRules.lhs)]]; look at `builtinIntegerRules`.  All of the types and functions in the `Integer` interface have built-in 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 constant-fold 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  Integral Integer where
     64{{{#!hs
     65instance Integral Integer where
    6566    toInteger n      = n
    6667
     
    7374
    7475 * '''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
     77smallInteger :: Int# -> Integer
    7778}}}
    7879 Now we can define `intToInteger` (or, more precisely, the `toInteger` method of the `Integral Int` instance in `GHC.Real` ) thus
    79 {{{
    80   toInteger (I# i) = smallInteger i
     80{{{#!hs
     81toInteger (I# i) = smallInteger i
    8182}}}
    8283 And we have a RULE for `integerToInt (smallInteger i)`.
     
    8990
    9091 * '''Don't inline integer functions'''.  Most of the functions in the Integer implementation in the `integer` package are marked `NOINLINE`. For example in `integer-gmp` we have
    91 {{{
     92{{{#!hs
    9293plusInteger :: Integer -> Integer -> Integer
    9394plusInteger (S# i1) (S# i2) = ...
    9495plusInteger (S# i1) (J# j1 j2) = ...
    95 ...two more cases...
     96-- ...two more cases...
    9697}}}
    9798 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 pattern-matching cancellation happens.  And even if you have `(a+b+c)`, the conditionals mean that no cancellation happens, or you get an exponential code explosion!