2 | | == Regular, Multi-dimensional Arrays == |
| 2 | = Regular, Multi-dimensional parallel Arrays = |
| 3 | The nested parallel arrays of DPH could be used to model regular arrays, as we could simply either create segment information using replicate, or define regular arrays in terms of flat parallel arrays and separately stored dimensionality information, and define operations on these arrays in a library in terms of the nested operations. However, there are two main reasons why this is unsatisfactory: convenience and efficiency. |
| 4 | |
| 5 | === Convenience === |
| 6 | |
| 7 | Languages like SAC, which provide high-level support for operations on multi-dimensional arrays, offer shape invariant operations. If we want to model this on a library level, we either have to give up type safety to a |
| 8 | large extend (for example, by encoding the shape as a list of integer values whose length is proportionate to its dimensionality) or use sophisticated language features like GADTs, which may impede the usability of the library for inexperienced users. |
| 9 | |
| 10 | |
| 11 | |
| 12 | |
| 13 | == The regular array type == |
| 14 | |
| 15 | Regular parallel arrays are similar to arrays in SAC, with one major |
| 16 | difference: array operations in DPH are fully typed, and consequently, what |
| 17 | is called 'shape invariant programming' in SAC works differently in DPH. |
| 18 | |
| 19 | An multidimensional array is parametrised with its dimensionality and its |
| 20 | element type: |
| 21 | |
| 22 | {{{ |
| 23 | (Ix (Shape dim), Elt a) => Array dim a |
| 24 | |
| 25 | }}} |
| 26 | where Shape is a type family defined on tuples of integers, including nullary |
| 27 | tuples - arrays of which correspond to scalar values. So, for example |
| 28 | {{{ |
| 29 | Array () Double -- scalar double precision floating point value |
| 30 | Array (3,2) Double -- two dimensional array (matrix) of three rows, two columns |
| 31 | }}} |
| 32 | |
| 33 | Internally, shapes are represented as nested pairs |
| 34 | {{{ |
| 35 | type family Shape dim |
| 36 | type instance Shape () = () |
| 37 | type instance Shape (Int) = ((),Int) |
| 38 | type instance Shape (Int, Int) = (((),Int), Int) |
| 39 | }}} |
| 40 | |
| 41 | Elements types are restricted to the element type of flat parallel |
| 42 | arrays, that it, primitive types like integers, boolean and floating |
| 43 | point numbers, and tuples. |
| 44 | |
| 45 | == Operations == |
| 46 | |
| 47 | === Creating Arrays === |
| 48 | |
| 49 | A new arrays can be created from flat parallel arrays |
| 50 | {{{ |
| 51 | fromNArray:: U.Elt r => U.Array r -> Array DIM1 r |
| 52 | }}} |
| 53 | and from scalar values: |
| 54 | {{{ |
| 55 | fromScalar:: U.Elt r => r -> Array DIM0 r |
| 56 | }}} |
| 57 | |
| 58 | === Manipulating array values === |
| 59 | |
| 60 | All the shape invariant operations available on parallel arrays are also defined on regular arrays: |
| 61 | {{{ |
| 62 | map :: (Elt a, Elt b) => (a -> b) -> Array dim a -> Array dim b |
| 63 | zipWith :: (Elt a, Elt b, Elt c) => (a -> b -> c) -> Array dim a -> Array dim b -> Array dim c |
| 64 | }}} |
| 65 | Parallel array operations which can change the shape are restricted to one dimensional arrays, to make sure that the |
| 66 | result is still a regular array. |
| 67 | {{{ |
| 68 | filter :: Elt a => (a -> Bool) -> Array DIM1 a -> Array DIM1 a |
| 69 | scan :: Elt a => ((a, a) -> a) -- combination function |
| 70 | -> a -- default value |
| 71 | -> Array (dim, Int) a -- linear array |
| 72 | -> (Array dim a, Array (dim, Int) a) |
| 73 | }}} |
| 74 | Manipulating the shape of arrays: |
| 75 | {{{ |
| 76 | reshape ::(Ix (Shape dim), Ix (Shape dim')) => |
| 77 | (Shape dim) -- new shape |
| 78 | -> Array dim' a -- array to be reshaped |
| 79 | -> Array dim a |
| 80 | }}} |
| 81 | |
| 82 | === Changing the dimensionality of an array === |
| 83 | |
| 84 | |
| 85 | |
| 86 | |
| 87 | ==== The index type ==== |
| 88 | |
| 89 | Two operations we provide change the dimensionality of an argument |
| 90 | array, namely the generalised indexing function, which extracts |
| 91 | subarrays from an multidimensional array, and generalised replicate, |
| 92 | which expands the array along specified axes. To encode the |
| 93 | relationship between the argument's dimensionality and the result's dimensionality, |
| 94 | we use the Index type. |
| 95 | {{{ |
| 96 | (!) :: Elt e => Arr dim e -> Index dim dim' -> Arr dim' e |
| 97 | |
| 98 | replicate :: Index dim' dim -- ^specifies new dimensions |
| 99 | -> Array dim a -- ^data to be replicated |
| 100 | -> Array dim' a |
| 101 | |
| 102 | }}} |
| 103 | where Index is defined as |
| 104 | {{{ |
| 105 | data Index initialDim projectedDim where |
| 106 | IndexNil :: Index () () |
| 107 | IndexAll :: Index init proj -> Index (init, Int) (proj, Int) |
| 108 | IndexFixed :: Int -> Index init proj -> Index (init, Int) proj |
| 109 | }}} |
| 110 | |
| 111 | ==== Examples ==== |
| 112 | |
| 113 | To demonstrate the use of the Index type, consider the following replicates expressed in terms of generalised replicate: |
| 114 | {{{ |
| 115 | -- 'chunk replicate' - create a two dimensional array by replicating the one dimensional |
| 116 | -- argument array n times |
| 117 | replicateC:: Int -> Array DIM1 a -> Array DIM2 a |
| 118 | replicateC n arr = RArray.replicate (IndexFixed n (IndexAll IndexNil)) arr |
| 119 | |
| 120 | -- create a two dimensional array by replicating each element n times |
| 121 | replicateL:: Int -> Array DIM1 a -> Array DIM2 a |
| 122 | replicateL n arr = RArray.replicate (IndexAll (IndexFixed n IndexNil)) arr |
| 123 | |
| 124 | |
| 125 | replicateC2:: Int -> Array DIM2 a -> Array DIM3 a |
| 126 | replicateC2 n arr = RArray.replicate (IndexFixed n (IndexAll (IndexAll IndexNil))) arr |
| 127 | |
| 128 | |
| 129 | replicateLL:: Int -> Array DIM2 a -> Array DIM3 a |
| 130 | replicateLL n arr = RArray.replicate (IndexAll (IndexAll (IndexFixed n IndexNil))) arr |
| 131 | }}} |
| 132 | |
| 133 | The use of the index type is not very intuitive, and it should be |
| 134 | hidden from the user, preferably by offering syntactic support similar to SACs dot-notation. |
| 135 | |
| 136 | |