The data-flow graph of OM takes three type parameters

`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) Edge

Paraiso 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 return

Like this:

x <- bind $ loadIndex (Axis 0)
y <- bind $ loadIndex (Axis 1)
z <- bind $ x*y
w <- bind $ x+y

The above program originally looked like this:

x <- loadIndex (Axis 0)
y <- loadIndex (Axis 1)
z <- return x * return y
w <- return x + return y

The 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.Operator

and 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.

We will gradually see the detail via examples.

##
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)