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 p1 ... pn', where `MkPArr' 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.]