compiler/ndpFlatten/TODO

   1                    TODO List for Flattening Support in GHC           -*-text-*-
   2                    =======================================
   3
   4 Middle-End Related
   5 ~~~~~~~~~~~~~~~~~~
   6
   7 Flattening Transformation
   8 ~~~~~~~~~~~~~~~~~~~~~~~~~
   9
  10 * Complete and test
  11
  12 * Complete the analysis
  13
  14 * Type transformation: The idea solution would probably be if we can add some
  15   generic machinery, so that we can define all the rules for handling the type
  16   and value transformations in a library.  (The PrelPArr for WayNDP.)
  17
  18
  19 Library Related
  20 ~~~~~~~~~~~~~~~
  21
  22 * Problem with re-exporting PrelPArr from Prelude is that it would also be
  23   visible when -pparr is not given.  There should be a mechanism to implicitly
  24   import more than one module (like PERVASIVE modules in M3)
  25
  26 * We need a PrelPArr-like library for when flattening is used, too.  In fact,
  27   we need some library routines that are on the level of merely vectorised
  28   code (eg, for the dummy default vectors), and then, all the `PArrays' stuff
  29   implementing fast unboxed arrays and fusion.
  30
  31 * Enum is a problem.  Ideally, we would like `enumFromToP' and
  32   `enumFromThenToP' to be members of `Enum'.  On the other hand, we really do
  33   not want to change `Enum'.  The solution for the moment is to define
  34
  35     enumFromTo x y       = mapP toEnum [:fromEnum x .. fromEnum y:]
  36     enumFromThenTo x y z = mapP toEnum [:fromEnum x, fromEnum y .. fromEnum z:]
  37
  38   like the Haskell Report does for the list versions.  This is hopefully
  39   efficient enough as array fusion should fold the two traversals into one.
  40   [DONE]
  41
  42
  43 DOCU that should go into the Commentary
  44 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  45
  46 The type constructor [::]
  47 -------------------------
  48
  49 The array type constructor [::] is quite similar to [] (list constructor) in
  50 that GHC has to know about it (in TysWiredIn); however, there are some
  51 differences:
  52
  53 * [::] is an abstract type, whereas [] is not
  54
  55 * if flattening is switched on, all occurences of the type are actually
  56   removed by appropriate program transformations.
  57
  58 The module PrelPArr that actually implements nested parallel arrays.  [::] is
  59 eliminated only if in addition to array support, flattening is activated.  It
  60 is just an option rather than the only method to implement those arrays.
  61
  62   Flags: -fparr       -- syntactic support for parallel arrays (via `PrelPArr')
  63                          * Dynamic hsc option; can be reversed with -fno-parr
  64          -fflatten    -- flattening transformation
  65                          * Static hsc option
  66          -ndp         -- this a way option, which implies -fparr and -fflatten
  67                          (way options are handled by the driver and are not
  68                          directly seen by hsc)
  69          -ddump-vect  -- dump Core after vectorisation
  70                          * Dynamic hsc option
  71
  72 * PrelPArr implements array variants of the Prelude list functions plus some
  73   extra functions (also, some list functions (eg, those generating infinite
  74   lists) have been left out.
  75
  76 * prelude/PrelNames has been extended with all the names from PrelPArr that
  77   need to be known inside the compiler
  78
  79 * The variable GhcSupportsPArr, which can be set in build.mk decides whether
  80   `PrelPArr' is to be compiled or not.  (We probably need to supress compiling
  81   PrelPArr in WayNDP, or rather replace it with a different PrelPArr.)
  82
  83 * Say something about `TysWiredIn.parrTyCon' as soon as we know how it
  84   actually works...
  85
  86 Parser and AST Notes:
  87 - Parser and AST is quite straight forward.  Essentially, the list cases
  88   duplicated with a name containing `PArr' or `parr' and modified to fit the
  89   slightly different semantics (ie, finite length, strict).
  90 - The value and pattern `[::]' is an empty explicit parallel array (ie,
  91   something of the form `ExplicitPArr ty []' in the AST).  This is in contrast
  92   to lists, which use the nil-constructor instead.  In the case of parallel
  93   arrays, using a constructor would be rather awkward, as it is not a
  94   constructor-based type.
  95 - Thus, array patterns have the general form `[:p1, p2, ..., pn:]', where n >=
  96   0.  Thus, two array patterns overlap iff they have the same length.
  97 - The type constructor for parallel is internally represented as a
  98   `TyCon.AlgTyCon' with a wired in definition in `TysWiredIn'.
  99
 100 Desugarer Notes:
 101 - Desugaring of patterns involving parallel arrays:
 102   * In Match.tidy1, we use fake array constructors; ie, any pattern `[:p1, ...,
 103     pn:]' is replaces by the expression `MkPArr<n> p1 ... pn', where
 104     `MkPArr<n>' is the n-ary array constructor.  These constructors are fake,
 105     because they are never used to actually represent array values; in fact,
 106     they are removed again before pattern compilation is finished.  However,
 107     the use of these fake constructors implies that we need not modify large
 108     parts of the machinery of the pattern matching compiler, as array patterns
 109     are handled like any other constructor pattern.
 110   * Check.simplify_pat introduces the same fake constructors as Match.tidy1
 111     and removed again by Check.make_con.
 112   * In DsUtils.mkCoAlgCaseMatchResult, we catch the case of array patterns and
 113     generate code as the following example illustrates, where the LHS is the
 114     code that would be produced if array construtors would really exist:
 115
 116       case v of pa {
 117         MkPArr1 x1       -> e1
 118         MkPArr2 x2 x3 x4 -> e2
 119         DFT              -> e3
 120       }
 121
 122     =>
 123
 124       case lengthP v of
 125         Int# i# ->
 126           case i# of l {
 127             1   -> let x1 = v!:0                       in e1
 128             3   -> let x2 = v!:0; x2 = v!:1; x3 = v!:2 in e2
 129             DFT ->                                            e3
 130           }
 131   * The desugaring of array comprehensions is in `DsListComp', but follows
 132     rules that are different from that for translating list comprehensions.
 133     Denotationally, it boils down to the same, but the operational
 134     requirements for an efficient implementation of array comprehensions are
 135     rather different.
 136
 137     [:e | qss:] = <<[:e | qss:]>> () [:():]
 138
 139     <<[:e' |           :]>> pa ea = mapP (\pa -> e') ea
 140     <<[:e' | b     , qs:]>> pa ea = <<[:e' | qs:]>> pa (filterP (\pa -> b) ea)
 141     <<[:e' | p <- e, qs:]>> pa ea =
 142       let ef = filterP (\x -> case x of {p -> True; _ -> False}) e
 143       in
 144       <<[:e' | qs:]>> (pa, p) (crossP ea ef)
 145     <<[:e' | let ds, qs:]>> pa ea =
 146       <<[:e' | qs:]>> (pa, (x_1, ..., x_n))
 147                       (mapP (\v@pa -> (v, let ds in (x_1, ..., x_n))) ea)
 148     where
 149       {x_1, ..., x_n} = DV (ds)         -- Defined Variables
 150     <<[:e' | qs | qss:]>>   pa ea =
 151       <<[:e' | qss:]>> (pa, (x_1, ..., x_n))
 152                        (zipP ea <<[:(x_1, ..., x_n) | qs:]>>)
 153     where
 154       {x_1, ..., x_n} = DV (qs)
 155
 156     Moreover, we have
 157
 158       crossP       :: [:a:] -> [:b:] -> [:(a, b):]
 159       crossP a1 a2  = let
 160                         len1 = lengthP a1
 161                         len2 = lengthP a2
 162                         x1   = concatP $ mapP (replicateP len2) a1
 163                         x2   = concatP $ replicateP len1 a2
 164                       in
 165                       zipP x1 x2
 166
 167     For a more efficient implementation of `crossP', see `PrelPArr'.
 168
 169     Optimisations:
 170     - In the `p <- e' rule, if `pa = ()', drop it and simplify the `crossP ea
 171       e' to `e'.
 172     - We assume that fusion will optimise sequences of array processing
 173       combinators.
 174     - Do we want to have the following function?
 175
 176         mapFilterP :: (a -> Maybe b) -> [:a:] -> [:b:]
 177
 178       Even with fusion `(mapP (\p -> e) . filterP (\p -> b))' may still result
 179       in redundant pattern matching operations.  (Let's wait with this until
 180       we have seen what the Simplifier does to the generated code.)
 181
 182 Flattening Notes:
 183 * The story about getting access to all the names like "fst" etc that we need
 184   to generate during flattening is quite involved.  To have a reasonable
 185   chance to get at the stuff, we need to put flattening inbetween the
 186   desugarer and the simplifier as an extra pass in HscMain.hscMain.  After
 187   that point, the persistent compiler state is zapped (for heap space
 188   reduction reasons, I guess) and nothing remains of the imported interfaces
 189   in one shot mode.
 190
 191   Moreover, to get the Ids that we need into the type environment, we need to
 192   force the renamer to include them.  This is done in
 193   RnEnv.getImplicitModuleFVs, which computes all implicitly imported names.
 194   We let it add the names from FlattenInfo.namesNeededForFlattening.
 195
 196   Given all these arrangements, FlattenMonad can obtain the needed Ids from
 197   the persistent compiler state without much further hassle.
 198
 199   [It might be worthwhile to document in the non-Flattening part of the
 200   Commentary that the persistent compiler state is zapped after desugaring and
 201   how the free variables determined by the renamer imply which names are
 202   imported.]