星の贈り物

StdHtml はどこ？

[topic:Clean、Generic Programming、Functional Reactive Programming]

lethevert さんが Clean の HTML ライブラリを作っているのを見て 、そんなことしなくても StdHtml を使えば良いとつっこもうとしていたのですが……いざ探してみるとどこにも見つからない。

どこにあるんだろうと思いつつ ググっていった結果分かったのは、htmlGEC に入っているということでした （ちなみに検索結果に挙がっている CVS には現在アクセスできないようです）。あー、よく考えればそうですね。 CEFP 2005 の講義資料の htmlGEC を使っている部分では、StdHtml しかインポートしていませんでした。 FLOPS での発表 から分かる通り、htmlGEC はまだまだ開発中です。そんなわけで、少なくとも次のバージョンまでは使えませんね。

あと、この件について調べているうちに Central European Functional Programming School（CEFP 2005）の本 ( Amazon ) が出ていたことに気がつきました。これは買うべきかしら。

Haskell で並列処理

[topic:Haskell、並列プログラミング]

そのうち誰か話題にすると思っていたのですが、見て回った範囲ではまだ誰も書いていないようなので GHC 6.6 での並列処理のサポートについて書くことにします。 GHC の並列処理をサポートする機能のうち、計算の並列性を記述する形でプログラミングを行っていく機能を Parallel Haskell と呼びます。今回説明するのは主にこの Parallel Haskell とその周辺の話ですが、最後にちょっとだけ別の並列化手段についても紹介します。

まず最初に注意事項を書いておきます。 6.6 の SMP サポートを使って並列処理をやる場合には、-threaded オプションをつけてコンパイルするのと、+RTS -Nx（x はCPUやコアの数に応じた数）オプションをつけてプログラムを実行する を忘れないようにしてください。（ Parallel GC はまだ実装されていないようです ので、GC が並列に行われなくても驚かないように。）

次に、-O オプションなどをつけて最適化するとしないとでボトルネックが変化した結果、最適化前に並列性や正格性をつけて改善したパフォーマンスが最適化後にうまく表れない可能性があります。特に GUI などのリアルタイム処理を行っている場合には、最適化の結果ボトルネックへの負荷が増加する可能性があります。最適化オプションをつけると並列性の部分で警告メッセージがでますが、これが原因でうまく処理されていないわけではないので間違えないようにしてください。（というか、リンクは張りませんが私が間違えました。すみません。）

あと、 Algorithm + Strategy = Parallelism などをつまみ読みしただけで、きちんと読み込んでいないので、色々と間違いがあるかもしれません。この記事に間違いを発見したら、つっこみなどを入れてもらえるようお願いします。

さて、本題に入りましょう。Control.Parallel モジュールには、seq と同じ a -> b -> b という型の par という関数があります。seq との違いは、seq が引数を正格に評価するよう指示するのに対し、par は引数を並列に評価するように指示します。（ par はライブデータ構造体（Live Data Structure）を作成するという方法で並列化を実現します。 ）par を使用することで、フィボナッチ数を求めるアルゴリズムの並列化版を以下のように記述できます。

> import Control.Parallel
> 
> pfib :: Int -> Int
> pfib n 
>   | n <= 1    = 1
>   | otherwise = n1 `par` n2 `seq` n1+n2+1
>     where 
>       n1 = pfib (n-1) 
>       n2 = pfib (n-2)

……となれば良いのですが、実は（GHC.Conc のものと違い）par の結合順序が正しく定義されていないそうです。なので、使用する際には括弧で括るか、GHC.Conc モジュールのものを使うか、以下のように定義しておくことにしましょう。

> infixr 0 `par`
> par = Control.Parallel.par

また、seq は両辺の引数を正格評価することを指示するだけで、（名前から良く誤解されるように）aを評価して次にbを評価するという動作を行うわけではありません。右左どちらの側も先に評価され得ます。 評価順序を気にする場合には、第一引数だけ正格評価する GHC.Conc モジュールの pseq を使ってください。 （それだと不便ですよね。darcs HEAD の方では修正が入っているので、GHC 6.8 以降では pseq を Control.Parallel モジュールから利用できるようになります。）

以上のことを踏まえると、上の pfib の定義は以下のように書き直す必要があります。

> import GHC.Conc (par, pseq)
> 
> pfib :: Int -> Int
> pfib n 
>   | n <= 1    = 1
>   | otherwise = n1 `par` n2 `pseq` n1+n2+1
>     where 
>       n1 = pfib (n-1) 
>       n2 = pfib (n-2)

さて、実は par は、式が WHNF になるとその時点で並列に評価するのをやめてしまいます。そのため、クイックソートなどの途中でデータ型が出てくるようなアルゴリズムを素直に記述することはできません。そのため、アルゴリズムがきちんと並列化されるように制御するためのコードを埋め込んでやる必要があります。このようにプログラムの動きを細かくコントロールする形でプログラミングを行うと、当然ながらアルゴリズムとコントロールが絡み合うにつれてプログラムが分かりにくくなっていってしまいます。

この問題を解決するために、Control.Parallel.Strategies モジュールには Strategy という型やネストした型に Strategy を適用するための NFData という型クラスが用意されています。

> type Done = ()
> type Strategy a = a -> Done
> 
> rwhnf :: Strategy a
> rwhnf x = x `seq` ()
> 
> class NFData a where
>   rnf :: Strategy a
>   rnf = rwhnf
> 
> instance (NFData a, NFData b) => NFData (a,b) where
>   rnf (x,y) = rnf x `seq` rnf y

あとは Strategy を適用した値にそれぞれに par を適用する関数を用意してやれば、以下の補助関数の右側で Strategy を適用した値が左側で並列化されます。

> using :: a -> Strategy a -> a
> using x s = s x `seq` x
> 
> demanding, sparking :: a -> Done -> a
> demanding = flip seq
> sparking  = flip par

ここまでの関数定義ですが、例によって pseq ではなく seq を使っているためうまく動かない可能性があることに気をつけましょう。（HEAD では修正済み。）

> pfib n
>   | n <= 1    = 1
>   | otherwise = (n1+n2+1) `demanding` strategy
>     where
>       n1 = pfib (n-1)
>       n2 = pfib (n-2)
>       strategy = rnf n1 `par` rnf n2
> 
> quicksortS (x:xs) = losort ++ (x:hisort) `using` strategy
>                     where
>                       losort = quicksortS [y|y <- xs, y < x]
>                       hisort = quicksortS [y|y <- xs, y >= x]
>                       strategy result = rnf losort `par`
>                                         rnf hisort `par`
>                                         rnf result

ここまで述べてきたのは全て分割統治法を使ったコントロール中心の方法（Control-Oriented Parallelism）でしたが、データ構造の要素を並列に評価するという別の方法（Data-Oriented parallelism）もあります。例えば parMap がこの方法を使っています。

> parList :: Strategy a -> Strategy [a]
> parList strat []     = ()
> parList strat (x:xs) = strat x `par` (parList strat xs)
> 
> parMap :: Strategy b -> (a -> b) -> [a] -> [b]
> parMap strat f xs 	= map f xs `using` parList strat

さて、Parallel Haskell ではこのようにマシン構成に依存しない形でプログラムを書くことができますが、普通はもっとマシン構成を意識してカリカリにチューニングしたいでしょう。例えば、 Concurrent Clean の並列性注釈では計算を行う場所を指示できるようになっています 。（この日記にしては珍しくわざわざ Concurrent をつけて呼んでいることからも分かる通り、 現在この機能を使用することはできません 。）

ただそうやってマシンに最適化されたプログラムを書いていくのは大変なので、並列処理で良く使わる処理に焦点を当てて、それらを最適化した実装をスケルトンとして用意し合成して使用することにします。 これが MapReduce などで有名なスケルトン並列プログラミングです 。（ D-Clean もこっちのアプローチのはず 。）Parallel Haskell における Strategy を使ってのスケルトンの実装は、parMap のように簡単に実現できるものもあるし、そうでないものもあるようです。

よりチューニングを意識した形で並列性をサポートする Haskell （というよりは GHC や GPH）の派生形（variation）に、 Eden という言語があります。この言語では process と # を使い、明示的にプロセスを使用する形で処理の並列化を行います。

> class NFData a => Trans a where (...)
> data (Trans a, Trans b) =>
>     Process a b = Proc (ChanName b -> ChanName (ChanName a) -> ())
> 
> process :: (Trans a, Trans b) => (a -> b) -> Process a b
> ( # ) :: (Trans a, Trans b) => Process a b -> a -> b
> 
> mergesort :: (Ord a, Trans a) => [a] -> [a]
> mergesort [] = []
> mergesort [x] = [x]
> mergesort xs = sortmerge (process mergesort # xs1)
>                          (process mergesort # xs2)
>          where (xs1,xs2) = unshuffle xs

その性質上、Eden ではスケルトンを使ってのプログラミングがより重要なものとなってきます。そのため、スケルトンライブラリやスケルトンの構築を補助するためのライブラリの開発が試みられているようです。その中には、 Template Haskell を使ったスケルトンの自動生成 を行うものもあるようです。

Eden の機能が GHC に取り込まれるのはまだまだ先の話だと思うので、詳しくは調べていません。興味のある方は自分で調べてみてください。

あと他に GHC 6.6 では、High-Performance Fortran (HPF) などに採用されている Parallel Array（GHC.PArr）を使ったデータ並列 も使用できます。データ並列をサポートするメリットは、これまで説明してきたような形で明示的に並列化を指示せずとも暗黙的に処理が並列化されるようになるということです。

ただ、ベクトル化機能の実装がまだできていません。よって現在は効率性を捨ててリストのように扱うことのできる Parallel Array を使うか、（使いやすさを犠牲にして）自動ベクトル化の代替物として提供されている ndp パッケージのセグメント化された配列を使うか、どちらか一方を選ぶ必要があるようです。あと当然ながら、この配列は遅延評価ではなく正格評価になっています。

ここまで GHC の Parallel Array について紹介してきましたが、6.6 にドキュメントが存在しないことから分かるようにこの機能はまだまだ開発中です。一見実装されているように見えても、きちんと使えない関数などもあるようです。よって、使い方については特に説明はしません。興味のある方は上のリンク先を見てください。

サピア・ウォーフの仮説解釈におけるサピア・ウォーフの仮説的現象の発現について

[topic:言語学]

というか、相変わらずなまつもとさんの「サピア・ウォーフの仮説の素朴な理解」が非常に気になる。サピア・ウォーフの仮説をどう理解するか自体が既に一大テーマなんですよ。いや、言語学の研究者ではないので内部でどう扱われているかきちんと知っているわけではないのですが、言語学者の間では、どうやら「使用する言葉自体がものの見方を支配する」という共通解釈の周辺に論者にとって都合の良い「サピア・ウォーフの仮説像」が付け加えられて議論がおこなわれている雰囲気。Haskell 連載の初回でさりげなく誤解されているということに言及するつもりだったのですが、そのあたりつっこむとかなりの長文になりそうだったので止めてああいう形になりました。

とりあえず今後サピア・ウォーフの仮説について言及する気のある方は、以下のリンク先の記事でも読んでおいてください。

• [ことばをめぐる] (020527)サピア=ウォーフ仮説,アリーmyラブ,本貫,脳死,カステラ

• EP : end-point 科学に佇む心と体 Pt.1: サピア＝ウォーフ仮説再考

• kinjoblog:サピア・ウォーフの仮説

ある意味、このようなサピア・ウォーフの仮説や言語過定説という言葉に対する自分の知識を背景とした様々な解釈そのものが、まさにその仮説の実例であるとも言えますね。