PR

並列論理和

 もう一つ,単純な並列化ではうまくいかない場合について見てみましょう。単純な並列化だけでは実装できないプログラムとしては,2007年5月頃に話題になった並列論理和があります(参考リンク1参考リンク2)。他の言語と同様に,Haskellでも論理和演算子(||)は「第1引数が真であれば第2引数にかかわらず真を返す」演算子として実装されています。

(||)             :: Bool -> Bool -> Bool
True  || _       =  True
False || x       =  x

 このため,第2引数が無限ループであったとしても何も問題はありません。

Prelude> let f = True
Prelude> let g = g
Prelude> f || g
True

 しかし,「第1引数と第2引数のどちらか一方が真になったら,もう一方の引数にかかわらず真を返す」ような並列論理和を定義しようとすると,一つの問題に直面します。

 ||演算子では,遅延評価により,第1引数がFalseになるまで第2引数の評価を防ぐことができます。このため,上のような単純な定義でも,第2引数に無限ループする値(⊥)を渡しても何の問題もありません。

 しかし,並列論理和の場合には,以下のようにたとえ引数のどちら側に無限ループを渡したとしても正常に評価されることを保障しなければなりません。

*Por> f |||| g
True
*Por> g |||| f
True

 残念ながら現在の並列Haskellでは,いくつかの理由でそのような関数を表現できません。

(||||) :: Bool -> Bool -> Bool
a |||| b = a `par` b `par` a ||||- b

(||||-) :: Bool -> Bool -> Bool
(||||-) _ True = True
(||||-) True _ = True
(||||-) _ _ = False

 例えば,上のような単純な定義を使った場合,無限ループによって評価が終了しないか.あるいは無限ループやスタック溢れ(stack overflow)を示す例外が発生することになります(GHCでは最適化オプション(-O<n>)を有効にしたときのみ,無限ループを示す例外が発生します)。

*Por> f |||| g
Interrupted.
*Por> :q
Leaving GHCi.

$ ghc -O --make -main-is Por Por.hs
[1 of 1] Compiling Main             ( Por.hs, Por.o )
Linking Por.exe ...

$ ./Por
Por.exe: <<loop>>

 この問題を解決するには,評価を打ち切るための操作と,例外処理のための仕組みが必要です。しかし,今回の冒頭や第10回で述べたように,GHCではそのような操作は並列Haskellではなく,並行Haskellの領分としています。このため,並列Haskellでは評価方法を完全に処理系任せにしていて,遅延評価や例外の発生以外に評価を打ち切るための仕組みは特に用意していません。

 また,現在のGHCでの並列Haskellの実装では,例外処理も並行Haskellを使ってI/Oの中で行うほどにはうまくはいかないようです。よって,並列論理和を実現するためには,並行Haskellを使う必要があります。

module Por where
import Prelude hiding (catch)
import Control.Concurrent
import Control.Concurrent.STM
import Control.Exception
import System.IO.Unsafe

a |||| b = unsafePerformIO $ parSTM (return a) (return b)

parIO :: IO a -> IO a -> IO a
parIO a1 a2
 = do m <- newEmptyTMVarIO
      c1 <- forkIO (child m a1)
      c2 <- forkIO (child m a2)
      r <- atomically $ takeTMVar m
      killThread c1
      killThread c2
      return r
 where
     child m a = catch (do
         b <- a
         atomically $ putTMVar m b)
       (\e -> return ())

 ||||演算子の内部で使われているunsafePerformIOは,第7回で出てきたunsafeInterleaveIOの親戚で,値を評価するときにmain変数から駆動したI/Oとは非同期にI/Oを実行するものです。unsafePerformIOはunsafeInterleaveIOと同様に,System.IO.Unsafeモジュールで提供されています。

Prelude System.IO.Unsafe> :i unsafePerformIO
unsafePerformIO :: IO a -> a    -- Defined in GHC.IOBase

 unsafePerformIOはIO型を取り外せるため,unsafeInterleaveIO以上に危険なので気をつけてください(参考リンク)。ここでは並列論理和が関数全体としては副作用を持たないことから,大丈夫だと判断してunsafePerformIOを使っています。

 parIOは,スレッドを使って二つのI/Oアクションを並行実行し,そのうち速く求められた値を取得して残りのスレッドを殺すというものです。後で詳しく説明するので,ここではそういうものだと理解してください。

 evaluateはControl.Exceptionモジュールにある例外処理のための関数の一つです。

Prelude Control.Exception> :i evaluate
evaluate :: a -> IO a   -- Defined in GHC.Exception

 evaluateは見ての通り,値が評価されたときにI/Oに包んで返す関数です。といっても,returnとの違いがわからないと思うので,少し説明しましょう。evaluateを導入する動機は例外処理にあります。

 例外とはエラーを構造化したものです。これまでerror関数やundefinedなどを使って発生させてきたエラーは,例外のうちErrorCallというものにあたります。そのため,Control.Exceptionモジュールのcatch関数を使って取得できます。

Prelude Control.Exception> :i Control.Exception.catch
catch :: IO a -> (Exception -> IO a) -> IO a
        -- Defined in Control.Exception
Prelude Control.Exception> :i Exception
data Exception
  = ArithException ArithException
  | ArrayException ArrayException
  | AssertionFailed String
  | AsyncException AsyncException
  | BlockedOnDeadMVar
  | BlockedIndefinitely
  | NestedAtomically
  | Deadlock
  | DynException Data.Dynamic.Dynamic
  | ErrorCall String
  | ExitException GHC.IOBase.ExitCode
  | IOException IOException
  | NoMethodError String
  | NonTermination
  | PatternMatchFail String
  | RecConError String
  | RecSelError String
  | RecUpdError String
        -- Defined in GHC.IOBase
instance Eq Exception -- Defined in GHC.IOBase
instance Show Exception -- Defined in GHC.IOBase
Prelude Control.Exception> Control.Exception.catch (error "error ocuur") (\e -> case e of ErrorCall str -> print str; _ -> return ())
"error ocuur"
Prelude Control.Exception> Control.Exception.catch (undefined) (\e -> case e of ErrorCall str -> print str; _ -> return ())
"Prelude.undefined"

 Control.Exception.catchというようにモジュール名で修飾されている名前を使っているのは,Preludeに存在する標準Haskellのcatch関数と名前が衝突してしまうためです(参考リンク)。

Prelude Control.Exception> catch (error "error ocuur") (\e -> case e of ErrorCall str -> print str;_ -> return ())

<interactive>:1:0:
    Ambiguous occurrence `catch'
    It could refer to either `catch', imported from Prelude
                          or `catch', imported from Control.Exception

 上の||||演算子の定義では,インポート宣言の部分でPreludeを明示的にインポートすると同時に,catch関数をインポートするものの「構成要素(entity,エンティティ)」からhidingを使って取り除くことで,このようなあいまい性を回避していました(参考リンク)。Haskell'ではControl.Exceptionモジュールの例外仕様が取り込まれる可能性が高いとされています。そうなれば,こうした不便さを解消できるでしょう(参考リンク

 また,同じくControl.Exceotionのthrow関数を使うことで,例外を起こすことができます。

Prelude Control.Exception> :i throw
throw :: Exception -> a         -- Defined in GHC.IOBase
Prelude Control.Exception> throw $ ErrorCall "error occur"
*** Exception: error occur
Prelude Control.Exception> throw $ NonTermination
*** Exception: <<loop>>

 例外について理解したところで,evaluateに戻りましょう。以下のように,関数の引数のうち一つだけが例外を起こす可能性がある場合には,どの例外が生じるか考えるのはそう難しくないと思います。

Prelude Control.Exception> id undefined
*** Exception: Prelude.undefined
Prelude Control.Exception> id $ throw NonTermination
*** Exception: <<loop>>
Prelude Control.Exception> 12 `div` 0 - 12
*** Exception: divide by zero

 しかし実際には複数の値が例外を起こす可能性があり,その場合,式全体から生じる例外は先に起こったものだけです。

Prelude Control.Exception> throw Deadlock + error "error occur"
*** Exception: <<deadlock>>

 よって,このときに生じる例外は,完全にプログラム実行時の評価順序に依存します。どの例外が先に生じることになるかは,この式からは推測できません。つまり,この式での例外の発生は非決定性を持ちます。このような非決定的に生じる例外を純粋関数として扱うのは,あまり好ましくありません。このため,複数の例外を受け取るための受け皿として,evaluate関数が用意されているのです(起こりうるすべての例外の集合を取得し,それに対する処理を行うという形で例外処理を規定することもできます。しかし,利便性や効率の面から考えてあまり現実的な方法ではないでしょう)。

Prelude Control.Exception> evaluate $ throw Deadlock + error "error occur"
*** Exception: <<deadlock>>

 なお,evaluateの内部できちんとエラーが発生するようにするため,evaluateは他のI/Oアクションと同様に,次のアクションに移る前に評価を行ってくれます。ここがevaluateはreturnとは異なります。

Prelude Control.Exception> return (12 `div` 0) >> print "good"
"good"
Prelude Control.Exception> evaluate (12 `div` 0) >> print "good"
*** Exception: divide by zero

 では,return $!と比べた場合には何か違いはあるでしょうか? それとも,ただのreturn $!の糖衣構文に過ぎないのでしょうか?

 ドキュメントによると,evaluateは以下のような意味を持つものとして定義されています(参考リンク)。

evaluate x `seq` y    ==>  y
evaluate x `catch` f  ==>  (return $! x) `catch` f
evaluate x >>= f      ==>  (return $! x) >>= f

 2番目,3番目の式では,evaluateがreturn $!と等価な意味を持つ場合について書いてありますが,一番上の式にはreturn $!と異なった意味を持つ場合について書いてあります。

 では実際に試してみましょう。seqの第1引数として例外の発生する可能性のある値を与えた場合,evaluate xではyが返りますが,return $! xではそこから生じる例外が返ってくることになります。

Prelude Control.Exception> (evaluate (12 `div` 0)) `seq` print "good"
"good"
Prelude Control.Exception> ((return $! 12 `div` 0):: IO Int) `seq` print "good"
*** Exception: divide by zero

 このように,evaluateとreturn $!の間にも,細かいながらも微妙な違いが存在します。

 ここまで見てきたように,例外にはいろいろと複雑な規則があります。ただ,遅延評価を利用する場合と同じく,使う前からそれらの規則についてごちゃごちゃと考えるのはあまり好ましくありません。例外処理について考えるのは,実際にプログラミングを行ううえで重要なことです。しかし,Haskellには強固な静的型があります。第5回で述べたように,潜在的な例外への対策は,本来は型を使って行うべきものなのです。

 例外安全性(exception safety)という名前で知られる,例外処理に対する基本原則の一つに,「例外を送出しない(nothrow)保証」があります。これは,例外処理がその中で例外を発生させることで例外処理が破綻してしまう,という現象を防ぐために重要な規則です(参考リンク1参考リンク2)。例外処理の破綻を防ぐためにも,型検査などを使って例外の発生を回避できるならそうすべきでしょう。例外処理は,あくまでそこから漏れ出てくるものへの対処として行うべきです。

 例外機能は「プログラム中で例外が発生する場合があることに気づいたとき,初めてそこをevaluateで包んで例外処理をする」ぐらいの割り切りで利用するとよいでしょう。そうすれば,おのずと気にしなければならない規則は限定されたものになるはずです。