並列処理の手順を組み立てるEvalモナド

 この問題を解決するために,現行のparallel 3.x.x.xでは,並列処理の評価のためのEvalモナドが新たに導入されています(参考リンク)。

 Control.Parallel.Strategiesモジュールでは,Evalモナドの上で並列処理を組み立てるための関数として,par関数やpseq関数の代わりになる関数が提供されています。並列計算のタスクであるsparkを作成するためのrpar関数と,式をWHNFまで評価するためのrseq関数です。

-- | 'rpar' sparks its argument (for evaluation in parallel).
rpar :: a -> Eval a
rpar  x = Eval $ \s -> spark# x s
{-# INLINE rpar  #-}

-- | 'rseq' evaluates its argument to weak head normal form.
--
-- > rseq == evalSeq Control.Seq.rseq
--
rseq :: Strategy a
rseq x = Eval $ \s -> seq# x s

 rpar関数やrseq関数は,Control.Parallelモジュールで提供されるpar関数やpseq関数ではなく,GHC.Extsモジュールが提供するspark#関数やseq#関数といった組み込み関数を使って実装されています。

Prelude GHC.Exts> :t spark#
spark# :: a -> State# d -> (# State# d, a #)
Prelude GHC.Exts> :t seq#
seq# :: a -> State# d -> (# State# d, a #)

 spark#関数やseq#関数は,評価の対象である式aのほかに「State# d」を取り,「State# d」と式aの評価結果の組を返します。IOモナドやStateモナドなどでは,状態の受け渡しを行うことで逐次処理の実行順序を制御していました。同様にEvalモナドでも,「State# d」という状態の受け渡しを行うことで並列プログラムの評価方法を制御しているのです(参考リンク)。

newtype Eval a = Eval (State# RealWorld -> (# State# RealWorld, a #))
  -- GHC 7.2.1 added the seq# and spark# primitives, that we use in
  -- the Eval monad implementation in order to get the correct
  -- strictness behaviour.

-- | Pull the result out of the monad.
runEval :: Eval a -> a
runEval (Eval x) = case x realWorld# of (# _, a #) -> a

instance Monad Eval where
  return x = Eval $ \s -> (# s, x #)
  Eval x >>= k = Eval $ \s -> case x s of
                                (# s', a #) -> case k a of
                                                      Eval f -> f s'

 Evalモナドで組み立てた並列プログラムの評価結果は,runEval関数を使うことで取り出せます。また,parallel 3.x.x.xのStrategy型は「a型の値を取って『Eval a型』の値を返す型」の別名として定義されています。このため,Evalモナドを使って組み立てた計算手順は,using関数やwithStrategy関数に渡す評価戦略としても利用できます。

type Strategy a = a -> Eval a

-- | Evaluate a value using the given 'Strategy'.
--
-- > x `using` s = runEval (s x)
--
using :: a -> Strategy a -> a
x `using` strat = runEval (strat x)

-- | evaluate a value using the given 'Strategy'.  This is simply
-- 'using' with the arguments reversed.
-- 
withStrategy :: Strategy a -> a -> a
withStrategy = flip using

 実は,rdeepseq関数もEvalモナドを使って実装されています。

-- | 'rdeepseq' fully evaluates its argument.
--
-- > rdeepseq == evalSeq Control.Seq.rdeepseq
--
rdeepseq :: NFData a => Strategy a
rdeepseq x = do rseq (rnf x); return x

 rdeepseq関数では,まずrseq関数で「NFDataクラスのrnfメソッドを使い,値xをデータ構造の中身まで評価する式」を呼び出します。ただし,「rseq (rnf x)」だけでは期待した結果にはなりません。第43回のコラムで説明したように,rnfメソッドは評価した値xではなく()を返すからです。そこでreturnメソッドを使って値xを返すようにしています。Evalモナドにより,rseq関数とreturnメソッドはdo式で記述した通りの順番で処理されることが保証されます。この結果,rdeepseqは「値xをデータ構造の中身まで評価し,値xを返す」という期待通りの定義になるのです。

 Control.Parallel.Strategiesモジュールでは,定義済みの評価戦略を使って値を並列に評価するrparWith関数も提供されています。

-- | instead of saying @rpar `dot` strat@, you can say
-- @rparWith strat@.  Compared to 'rpar', 'rparWith'
--
--  * does not exit the `Eval` monad
--
--  * does not have a built-in `rseq`, so for example `rparWith r0`
--    behaves as you might expect (it is a strategy that creates a
--    spark that does no evaluation).
--
--
rparWith :: Strategy a -> Strategy a
rparWith s a = do l <- rpar r; return (case l of Lift x -> x)
  where r = case s a of
              Eval f -> case f realWorld# of
                          (# _, a' #) -> Lift a'

data Lift a = Lift a

 rparWith関数を利用することで,前述したクイックソート関数を以下のように書き換えられます。

    ~ 略 ~
    | otherwise             = losort ++ hisort `using` strategy
  where
      ~ 略 ~
      strategy result = do
         rparWith rdeepseq losort
         rdeepseq hisort
         rdeepseq result

あるいは

    ~ 略 ~
    | otherwise             = parLoHi losort hisort
  where
      ~ 略 ~
      parLoHi losort hisort = runEval $ do
         lo <- rparWith rdeepseq losort
         hi <- rdeepseq hisort
         rdeepseq $ lo ++ hi

 par関数やpseq関数を使って「rdeepseq losort `par` rdeepseq hisort `pseq` rdeepseq result」とベタに書いた場合に比べて,処理の流れが明確になっているのがわかります。具体的には,rparWith関数で「rdeepseq関数を使ったlosortに対する評価」を並列計算のタスクとし,rdeepseq関数を使ってhisortを評価し,losortとhisortそれぞれの結果を連結しています。

 Evalモナドではこのように処理の流れが明確になるため,並列処理のタスク作成とそれ以外の処理を混同する可能性は少なくなります。par関数やpseq関数を使ってベタに書いた場合とは異なり,並列処理のタスクにしなくて良いものまでを並列処理のタスクにしてしまうという問題を防げます。また,誤りが混入した場合でも,その個所をソースコードからすぐに発見できます。特に,この例のようにrdeepseq関数を使う場合であれば,rparWith関数が出てくるかどうかで並列処理のタスクになっているかどうかを判別できます。

 またEvalモナドでは,型の異なるseq関数やpseq関数は使わずに,rseq関数とrdeepseq関数,rpar*関数からなる処理をEvalモナドを使って順序付けています。Evalモナドによって処理を順序付けられるので,seq関数やpseq関数は不要です。seq関数とpseq関数との違いに相当する問題もEvalモナドにはありません。