Changes between Version 8 and Version 9 of PrimBool


Ignore:
Timestamp:
Feb 8, 2013 1:09:39 PM (2 years ago)
Author:
jstolarek
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • PrimBool

    v8 v9  
    9898}}} 
    9999 
    100 Having the possibility of converting `Bool` to an unboxed `Int#` allows us to compute results of logical expression by means of logical bitwise operations. The result can be converted back to a `Bool` so this is transparent on the Haskell source level, except for the fact that defined logical binary operators will be strict in both their arguments. 
     100Having the possibility of converting `Bool` to an unboxed `Int#` allows us to compute results of logical expression by means of logical bitwise operations. The result can be converted back to a `Bool` so this is transparent on the Haskell source level, except for the fact that defined logical binary operators will be strict in both their arguments.  
    101101 
    102102'''NOTE: Validity of this solution is based on assumption that `True` will always have a tag of `1#`, while `False` will have a tag of `0#`. Changing this invariant in the future would make these primitive logical operators invalid.''' 
     
    169169Primitive logical operators `&&#` and `not#` can be defined in a similar matter. 
    170170 
     171'''NOTE: Neither of this two workarounds produces good object code. The reason is that comparison operators return a `Bool` as a thunk that needs to be evaluated. The real solution requires that no thunk is created.''' 
     172 
    171173== Solutions == 
    172174 
    173 It seems that the best solution to the problem would be implementing second of the above workarounds as a separate primop. Alternatively we can implement primitive bitwise `or`, `and` and `xor` that work on `Int`s instead of `Word`s and define new logical operators using bitwise operators in one of the libraries. 
     175A good beginning would be to implementing second of the above workarounds as a primop. Then we need to create primops that return unboxed values instead of a thunk. The big question is should an unboxed version of Bool be introduced into the language? 
     176=== First approach === 
     177 
     178Treat `Bool` as a boxed version of primitive `Bool#`. `True` would be equivalent of `B# True#`, `False` of `B# False#`: 
     179  {{{ 
     180data Bool = B# True# | B# False# 
     181 
     182-- B# :: Bool# -> Bool 
     183}}} 
     184 
     185Not sure if this can be considered equivalent to what the Haskell Report says about Bool. We need to ensure that `Bool#` is populated only by `True#` and `False#` and that these two are translated to `1#` and `0#` in the Core. It should be **impossible** to write such a function at Haskell level: 
     186 
     187{{{ 
     188g :: Bool -> Int -> Int 
     189g (B# b) (I# i) = I# (b + i) 
     190}}} 
     191 
     192This approach might require one additional case expression to inspect the value of `Bool` at the Core level. For example: 
     193 
     194{{{ 
     195f :: Int -> Int -> Int 
     196f x y = if x > y 
     197        then x 
     198        else y 
     199}}} 
     200 
     201would compile to: 
     202 
     203{{{ 
     204case x of _ { I# xP -> 
     205 case y of _ { I# yP -> 
     206   case ># xP yP of _ { 
     207     B# bP -> case bP of _ { 1# -> e1; 0# -> e2 } 
     208   } 
     209 } 
     210} 
     211}}} 
     212 
     213This would complicate Core a bit but it should be possible to compile such Core to exactly the same result as with normal `Bool`. This code assumes that `>#` has type `Int# -> Int# -> Bool`, but to truly avoid branching in the Core we need `.># :: Int# -> Int# -> Bool#` so that we get a primitive value that doesn't need to be inspected using case expression but can be directly used by primitive logical operators. 
     214 
     215=== Second approach === 
     216 
     217Second approach assumes creating type `Bool#` that is independent of type `Bool`. Boxing and unboxing would have to be done explicitly via additional functions: 
     218 
     219{{{ 
     220data Bool = True | False -- no changes here 
     221 
     222bBox :: Bool# -> Bool 
     223bBox 1# = True 
     224bBox 0# = False 
     225 
     226bUnbox :: Bool -> Bool# 
     227bUnbox True  = 1# 
     228bUnbox False = 0# 
     229}}} 
     230 
     231`Bool#` could not be implemented as an ADT because it is unlifted and unboxed, while ADT value constructors need to be boxed and lifted (see comments in [[GhcFile(compiler/types/TyCon.lhs)]]). There would need to be some magical way of ensuring that `Bool#` is populated only by `#0` and `1#` and that these values cannot be mixed with unboxed integers. Perhaps this could be done by preventing programmer from explicitly creating values of that type (can this be done?) and allow her only to use values returned from functions. 
     232 
     233Another problem with this approach is that it would introduce primitive logical operations `||#` and `&&#` with type `Int# -> Int# -> Int#` - it is questionable whether anyone would want such operations available to the programmer. I think it is desirable to have primitive logical operators of type `Bool# -> Bool# -> Bool#`. 
    174234 
    175235== Places of interest in the source code ==