--- /dev/null
+ TODO List for Flattening Support in GHC -*-text-*-
+ =======================================
+
+Middle-End Related
+~~~~~~~~~~~~~~~~~~
+
+Flattening Transformation
+~~~~~~~~~~~~~~~~~~~~~~~~~
+
+* Complete and test
+
+* Complete the analysis
+
+* Type transformation: The idea solution would probably be if we can add some
+ generic machinery, so that we can define all the rules for handling the type
+ and value transformations in a library. (The PrelPArr for WayNDP.)
+
+
+Library Related
+~~~~~~~~~~~~~~~
+
+* Problem with re-exporting PrelPArr from Prelude is that it would also be
+ visible when -pparr is not given. There should be a mechanism to implicitly
+ import more than one module (like PERVASIVE modules in M3)
+
+* We need a PrelPArr-like library for when flattening is used, too. In fact,
+ we need some library routines that are on the level of merely vectorised
+ code (eg, for the dummy default vectors), and then, all the `PArrays' stuff
+ implementing fast unboxed arrays and fusion.
+
+* Enum is a problem. Ideally, we would like `enumFromToP' and
+ `enumFromThenToP' to be members of `Enum'. On the other hand, we really do
+ not want to change `Enum'. The solution for the moment is to define
+
+ enumFromTo x y = mapP toEnum [:fromEnum x .. fromEnum y:]
+ enumFromThenTo x y z = mapP toEnum [:fromEnum x, fromEnum y .. fromEnum z:]
+
+ like the Haskell Report does for the list versions. This is hopefully
+ efficient enough as array fusion should fold the two traversals into one.
+ [DONE]
+
+
+DOCU that should go into the Commentary
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+The type constructor [::]
+-------------------------
+
+The array type constructor [::] is quite similar to [] (list constructor) in
+that GHC has to know about it (in TysWiredIn); however, there are some
+differences:
+
+* [::] is an abstract type, whereas [] is not
+
+* if flattening is switched on, all occurences of the type are actually
+ removed by appropriate program transformations.
+
+The module PrelPArr that actually implements nested parallel arrays. [::] is
+eliminated only if in addition to array support, flattening is activated. It
+is just an option rather than the only method to implement those arrays.
+
+ Flags: -fparr -- syntactic support for parallel arrays (via `PrelPArr')
+ * Dynamic hsc option; can be reversed with -fno-parr
+ -fflatten -- flattening transformation
+ * Static hsc option
+ -ndp -- this a way option, which implies -fparr and -fflatten
+ (way options are handled by the driver and are not
+ directly seen by hsc)
+ -ddump-vect -- dump Core after vectorisation
+ * Dynamic hsc option
+
+* PrelPArr implements array variants of the Prelude list functions plus some
+ extra functions (also, some list functions (eg, those generating infinite
+ lists) have been left out.
+
+* prelude/PrelNames has been extended with all the names from PrelPArr that
+ need to be known inside the compiler
+
+* The variable GhcSupportsPArr, which can be set in build.mk decides whether
+ `PrelPArr' is to be compiled or not. (We probably need to supress compiling
+ PrelPArr in WayNDP, or rather replace it with a different PrelPArr.)
+
+* Say something about `TysWiredIn.parrTyCon' as soon as we know how it
+ actually works...
+
+Parser and AST Notes:
+- Parser and AST is quite straight forward. Essentially, the list cases
+ duplicated with a name containing `PArr' or `parr' and modified to fit the
+ slightly different semantics (ie, finite length, strict).
+- The value and pattern `[::]' is an empty explicit parallel array (ie,
+ something of the form `ExplicitPArr ty []' in the AST). This is in contrast
+ to lists, which use the nil-constructor instead. In the case of parallel
+ arrays, using a constructor would be rather awkward, as it is not a
+ constructor-based type.
+- Thus, array patterns have the general form `[:p1, p2, ..., pn:]', where n >=
+ 0. Thus, two array patterns overlap iff they have the same length.
+- The type constructor for parallel is internally represented as a
+ `TyCon.AlgTyCon' with a wired in definition in `TysWiredIn'.
+
+Desugarer Notes:
+- Desugaring of patterns involving parallel arrays:
+ * In Match.tidy1, we use fake array constructors; ie, any pattern `[:p1, ...,
+ pn:]' is replaces by the expression `MkPArr<n> p1 ... pn', where
+ `MkPArr<n>' is the n-ary array constructor. These constructors are fake,
+ because they are never used to actually represent array values; in fact,
+ they are removed again before pattern compilation is finished. However,
+ the use of these fake constructors implies that we need not modify large
+ parts of the machinery of the pattern matching compiler, as array patterns
+ are handled like any other constructor pattern.
+ * Check.simplify_pat introduces the same fake constructors as Match.tidy1
+ and removed again by Check.make_con.
+ * In DsUtils.mkCoAlgCaseMatchResult, we catch the case of array patterns and
+ generate code as the following example illustrates, where the LHS is the
+ code that would be produced if array construtors would really exist:
+
+ case v of pa {
+ MkPArr1 x1 -> e1
+ MkPArr2 x2 x3 x4 -> e2
+ DFT -> e3
+ }
+
+ =>
+
+ case lengthP v of
+ Int# i# ->
+ case i# of l {
+ 1 -> let x1 = v!:0 in e1
+ 3 -> let x2 = v!:0; x2 = v!:1; x3 = v!:2 in e2
+ DFT -> e3
+ }
+ * The desugaring of array comprehensions is in `DsListComp', but follows
+ rules that are different from that for translating list comprehensions.
+ Denotationally, it boils down to the same, but the operational
+ requirements for an efficient implementation of array comprehensions are
+ rather different.
+
+ [:e | qss:] = <<[:e | qss:]>> () [:():]
+
+ <<[:e' | :]>> pa ea = mapP (\pa -> e') ea
+ <<[:e' | b , qs:]>> pa ea = <<[:e' | qs:]>> pa (filterP (\pa -> b) ea)
+ <<[:e' | p <- e, qs:]>> pa ea =
+ let ef = filterP (\x -> case x of {p -> True; _ -> False}) e
+ in
+ <<[:e' | qs:]>> (pa, p) (crossP ea ef)
+ <<[:e' | let ds, qs:]>> pa ea =
+ <<[:e' | qs:]>> (pa, (x_1, ..., x_n))
+ (mapP (\v@pa -> (v, let ds in (x_1, ..., x_n))) ea)
+ where
+ {x_1, ..., x_n} = DV (ds) -- Defined Variables
+ <<[:e' | qs | qss:]>> pa ea =
+ <<[:e' | qss:]>> (pa, (x_1, ..., x_n))
+ (zipP ea <<[:(x_1, ..., x_n) | qs:]>>)
+ where
+ {x_1, ..., x_n} = DV (qs)
+
+ Moreover, we have
+
+ crossP :: [:a:] -> [:b:] -> [:(a, b):]
+ crossP a1 a2 = let
+ len1 = lengthP a1
+ len2 = lengthP a2
+ x1 = concatP $ mapP (replicateP len2) a1
+ x2 = concatP $ replicateP len1 a2
+ in
+ zipP x1 x2
+
+ For a more efficient implementation of `crossP', see `PrelPArr'.
+
+ Optimisations:
+ - In the `p <- e' rule, if `pa = ()', drop it and simplify the `crossP ea
+ e' to `e'.
+ - We assume that fusion will optimise sequences of array processing
+ combinators.
+ - Do we want to have the following function?
+
+ mapFilterP :: (a -> Maybe b) -> [:a:] -> [:b:]
+
+ Even with fusion `(mapP (\p -> e) . filterP (\p -> b))' may still result
+ in redundant pattern matching operations. (Let's wait with this until
+ we have seen what the Simplifier does to the generated code.)
+
+Flattening Notes:
+* The story about getting access to all the names like "fst" etc that we need
+ to generate during flattening is quite involved. To have a reasonable
+ chance to get at the stuff, we need to put flattening inbetween the
+ desugarer and the simplifier as an extra pass in HscMain.hscMain. After
+ that point, the persistent compiler state is zapped (for heap space
+ reduction reasons, I guess) and nothing remains of the imported interfaces
+ in one shot mode.
+
+ Moreover, to get the Ids that we need into the type environment, we need to
+ force the renamer to include them. This is done in
+ RnEnv.getImplicitModuleFVs, which computes all implicitly imported names.
+ We let it add the names from FlattenInfo.namesNeededForFlattening.
+
+ Given all these arrangements, FlattenMonad can obtain the needed Ids from
+ the persistent compiler state without much further hassle.
+
+ [It might be worthwhile to document in the non-Flattening part of the
+ Commentary that the persistent compiler state is zapped after desugaring and
+ how the free variables determined by the renamer imply which names are
+ imported.]
projects / ghc-hetmet.git / blobdiff