Builder Monad

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)