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
returns. 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)