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


Ignore:
Timestamp:
Jan 31, 2014 6:41:14 PM (15 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!