`vector`

,`gauge`

and `anot`

, so does the Builder Monads. `vector`

represents the dimension of the array (say, three-dimension,) `gauge`

the type of the index of the array (say, Int,) and `anot`

the annotations given to the graph for analysis and optimization purposes. The combination `vector gauge`

represents an index vector (in this case, three-dimensional vector of Int) for accessing the arrays.type Graph vector gauge anot = Gr (Node vector gauge anot) EdgeParaiso programs are described by combining

`Builder Monad`

s, which are actually `State`

monads each carrying a half-built data-flow graph. Builder Monads take a few vertices from the data-flow graph, and return (usually one) new vertex. The vertices are of type `Value`

, which carry their `Realm`

information --- whether they are `Array`

or `Scalar`

--- and their content type information.-- | value type, with its realm and content type discriminated in -- type level data Value rea con = -- | data obtained from the data-flow graph. -- 'realm' carries a type-level realm information, -- 'content' carries only type information and its ingredient is -- insignificant and can be 'undefined'. FromNode {realm :: rea, content :: con, node :: G.Node} | -- | data obtained as an immediate value. -- 'realm' carries a type-level realm information, -- 'content' is the immediate value to be stored. FromImm {realm :: rea, content :: con} deriving (Eq, Show)The monadic building blocks we use in Paraiso are defined in Language.Paraiso.OM.Builder module. Please go to the page, and tap the "Synopsis" tab.

## bind trick

We have already seen several Paraiso programs, and you may have noticed the too frequent use of the term`bind`

,bind :: (Monad m, Functor m) => m a -> m (m a) bind = fmap returnLike this:

x <- bind $ loadIndex (Axis 0) y <- bind $ loadIndex (Axis 1) z <- bind $ x*y w <- bind $ x+yThe above program originally looked like this:

x <- loadIndex (Axis 0) y <- loadIndex (Axis 1) z <- return x * return y w <- return x + return yThe right hand side expressions are built of

`Builder`

monads while the bound names at the left hand side like `x,y,z,w`

are of type `Value`

. So we need to convert pure values to monads using `return`

s. This cannot be helped, because we cannot have `x`

,`y`

and `z`

of the same type in such expressions like `z <- x*y`

. However, there's a solution. By using `bind = fmap return`

, we apply `return`

only once at the binding timing, instead of everywhere else later on.## OM instructions

The instruction set of the Orthotope Machine is defined as algebraic data type`Inst`

in `Language.Paraiso.OM.Graph`

module, and `Language.Paraiso.OM.Builder`

provides the (almost) corresponding Builder Monad combinators. Here is the table of them. Read `B`

as the general monad symbol `m`

. (The actual definition is `type B ret = forall v g a. Builder v g a ret`

.)Here is the instruction set:

data Inst vector gauge = Load StaticIdx | Store StaticIdx | Reduce R.Operator | Broadcast | LoadIndex (Axis vector) | LoadSize (Axis vector) | Shift (vector gauge) | Imm Dynamic | Arith A.Operatorand the corresponding monad combinators:

```
-- options input nodes output nodes
load :: Named (StaticValue r c) -> B (Value r c)
store :: Named (StaticValue r c) -> B (Value r c) -> B ()
reduce :: Reduce.Operator -> B (Value TArray c) -> B (Value TScalar c)
broadcast :: B (Value TScalar c) -> B (Value TArray c)
loadIndex :: Axis v -> B (Value TArray g)
loadSize :: Axis v -> B (Value TScalar g)
shift :: v g -> B (Value TArray c) -> B (Value TArray c)
imm :: c -> B (Value r c)
```

In short,`Load`

takes a static variable, and loads from it, starting the data-flow graph.`Store`

ends the data-flow graph by storing the result to the specified static variable.`Reduce`

turns an array into a scalar value by use of the specified reduction operator.`Broadcast`

does the opposite and turns a scalar value into an array of the same type.`LoadIndex`

is used to retrieve the array index in the specified direction. The result is always an array.`LoadSize`

is used to retrieve the array size in the specified direction. The result is a scalar, of course.`Shift`

is used to move an array by a certain vector`v g`

.`Imm`

is to introduce an immediate value.`Arith`

is for arithmetic operations.

## Arithmetic

Where are the combinators for the`Arith`

instructions? Well, thanks to algebraic type classes defiend in numeric-prelude, we can write Builder expression using the usual arithmetic operators, in the same manner as writing ordinary expressions.(+) :: B (Value r c) -> B (Value r c) -> B (Value r c) sin :: B (Value r c) -> B (Value r c)One important exception to this are Boolean operators. Since Haskell's Boolean operators are of type, say,

`(==) :: Eq a => a -> a -> Bool`

, we cannot construct a Builder of Bool out of them. Instead, use functions defined in modules Language.Paraiso.OM.Builder.Boolean and Language.Paraiso.Prelude. Also `if`

cannot be re-used, so `select`

instead.```
eq :: B (Value r c) -> B (Value r c) -> B (Value r Bool)
ne :: B (Value r c) -> B (Value r c) -> B (Value r Bool)
select :: B (Value r Bool) -> B (Value r c) -> B (Value r c) -> B (Value r c)
```

And here's a `cast`

operator for type conversion. Here, `c2`

provides only the type information but its value is never used.cast :: c2 -> B (Value r c1) -> B (Value r c2)

## No comments:

## Post a Comment