Builderモナド - nushio's diary

Paraisoのプログラムは、Builderモナドを組み合わせることで記述します。Builderモナドは、実のところ作りかけのデータフローグラフを状態にもつStateモナドです。それぞれのBuilderモナドは、データフローグラフの頂点をいくつか引数に取って、新たな頂点を返します。

type Graph vector gauge anot = Gr (Node vector gauge anot) Edge

できあがるグラフの型は、vector、gauge、anotという3つの型引数を取るもので、これがBuilderにも常についてまわります。vectorは配列の次元(例:3次元)、gaugeは添字の型(例:Int)、anotは解析や最適化に使う注釈の型でして、vector gaugeという組み合わせは配列にアクセスするための添字のベクトル(Intの3次元ベクトル)になります。

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

この頂点はValue型であり、各頂点にたいして領域情報reaと、中身の型の情報conを運んでいます。reaの位置に入るのはLanguage.Paraiso.OM.RealmにあるTArrayかTScalarのいづれかであり、それぞれ配列変数およびスカラー変数を表します。conの位置に入るのはIntとかDoubleとかいった要素型ですが、多くの場合は型情報のみがグラフの構築に使われ値は単に無視されます。この多相な[Value型]を接点にグラフを組み立てることで、できあがったグラフの型安全性が(かなり)保証されます。

Paraisoプログラムを組み立てる材料はLanguage.Paraiso.OM.Builderモジュールに揃っています。モジュールのページに行って、"Synopsis"タブを押してください。

bindが便利なわけ

これまでもいくつかParaisoのプログラムはでてきましたが、やたらと各行ごとにbindがあるなあと思われたかもしれません。

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

こんなふうに。

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

このプログラムは素直に書くと、以下のようになります。

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

右辺の式loadIndex (Axis 0)などはBuilderモナドから成り立っている一方で、左辺のx,y,z,wなどはデータフローグラフの頂点ですから、Value型の値です。このため、いったん左辺でxなどの変数名を束縛したら、その後右辺で使うたびにモナドに変換する必要があります。(このとき使うのはむろん、最小の文脈を付与するreturnです！)ところがbind = fmap returnにより束縛時点で一度returnを施せば、以降、右辺ではそのまま使えます。こちらの方がずっと便利でしょう？

というわけで、Paraisoのサンプルプログラムに出てくるx,yといった何気ない変数名はすべてモナディックな値であることに注意して下さい。

直胞機械の命令

直胞機械の(実際コンパクトな)命令セットはLanguage.Paraiso.OM.GraphモジュールのInst型として定義されており、Language.Paraiso.OM.Builderモジュールには、これにほぼ一対一対応する形で材料が用意してあります。以下に、それぞれのコンビネータを表形式で整理しておきます。Bを一般のモナド記号mだと(実際の定義はtype B ret = forall v g a. Builder v g a ret)思うと感覚がつかめるのではないでしょうか。

これが命令セットで、

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

これが対応するモナド・コンビネータです。

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

各命令の機能をひとことで言うと、

loadは名前つき静的変数から読み込む。
storeは名前つき静的変数へ書き込む。
reduceは配列をスカラーに畳み込む。
broadcastはスカラーを配列にする。
loadIndexは配列の添字を取得。
loadSizeは配列のサイズを取得。
shiftはベクトルv gを使って配列をずらす。
immは即値を読み込む。
Arithはさまざまな算術演算を施す。

となります。各命令の詳細については、これから例で見ていきます。

演算子たち

そういえば、Arith命令に対応するコンビネータが見当たりませんが、どうなってるのでしょうか。Paraisoでは、numeric-preludeというライブラリを使い、Buiderモナドをさまざまな代数構造のインスタンスにすることで、普通の数式を書くのと同じ感覚でBuiderモナドの数式を組み立てられるようになっています。

(+) :: B (Value r c) -> B (Value r c) -> B (Value r c) 
sin :: B (Value r c) -> B (Value r c)

ただし、HaskellのBoolを扱う演算子に関しては、(==) :: Eq a => a -> a -> Boolなどの固定された型を持っているため、BoolのBuilderを返させることができません。そのため、モジュールLanguage.Paraiso.OM.Builder.BooleanやLanguage.Paraiso.Prelude.で定義されている関数で代用してください。またifも同じ理由でBuilderを組み立てる用途には使えませんので、代わりにselectを使ってください。

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)

最後に、型変換のための関数castがあります。具体的にどういう型変換コードが生成されるかは対象言語しだいです。ここでc2は変換先の型を指定するための変数で、値は使われません。

cast ::  c2 -> B (Value r c1) -> B (Value r c2)