SetはFunctorである

Haskell Advent Calendar 2013 9日目です。

概要


SetはFunctor。

なぜSetはFunctorになっていないのか


Setを要素が重複しないデータ構造とします。Setはその性質のため、要素には比較出来ることが要求されます。Haskellで言うとEq制約です。まあ本来重複しないことだけを要求するならEq制約だけでいいはずですが、SetがOrd制約を要求しているのは効率の良い実装にするためでしょう。containersパッケージのData.Setはバランス二分木で実装されています。


本来SetはFunctorにすることが出来るはずです。しかし現状(GHC7.6.3)、SetはFunctorのinstanceとはなっていません。それはSetがその要素にOrd制約を要求することが原因となっています。一般にHaskellでよく用いられるFunctorは、その定義より、コンテナの要素について何も言及することが出来ません。

class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b


試しにSetをFunctorにしようとしてみます。


containersパッケージはSetのmapを提供しており、以下の型を持っています。

Data.Set.map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

このmapは、Setの性質である「要素は重複しない」という性質を保ちます。

import qualified Data.Set as S
main = print $ S.map abs (S.fromList [-3,-2,-1,0,1,2,3]) -- fromList [0,1,2,3]

これをfmapにする形でSetをFunctorのinstanceにします。

import qualified Data.Set as S

instance Functor S.Set where
    fmap = S.map

すると以下の様に怒られます。

/Users/ruicc/works/sketch/set.hs:4:12:
    No instance for (Ord b) arising from a use of `S.map'
    Possible fix:
      add (Ord b) to the context of
        the type signature for fmap :: (a -> b) -> S.Set a -> S.Set b
    In the expression: S.map
    In an equation for `fmap': fmap = S.map
    In the instance declaration for `Functor S.Set'

fmapに(Ord b)を加えてはどうか？などと言ってきますが、それを加えたらFunctorがFunctorでなくなってしまいます。
FunctorやMonadは現在、型制約をうまく扱えるような定義になっていないのです。

Restricted Monad Problem


このSetをFunctorやMonadに出来ない問題は、Restricted Monad Problemとかなんとかと呼ばれ、以前から様々な解決法が提案されています。
コンテナの中身を型クラスに含めるものやTHでなんとかするもの、そしてConstraint Kindsを用いるものなどです。

Constraint Kinds


ConstraintKinds下では、Constraint周辺は以下の様に扱われます。

Ord :: * -> Constraint -- 型クラスの型コンストラクタのkind
() :: Constraint -- 空のConstraint
(,) :: Constraint -> Constraint -> Constraint -- Constraintの結合

ConstraintKindsプラグマはConstraintをモノイドのように扱えるようにしてくれるようです。具体的には以下の用な記述を可能にします。

f :: () => a -- これはプラグマ無くても書ける
g :: ((), ()) => a
h :: ((Ord a, Eq a), a ~ b) => a -> b

type familyと組み合わせると、Constraintに関する関数のようなものも記述出来ます。

type family Conj (a :: Constraint) (b :: Constraint) (c :: Constraint) :: Constraint
type instance Conj a b c = (a, b, c)

楽しげですね。
まあこのあたりは今は置いておきましょう。

Set Functor


Restricted Functor(RFunctor)を次の様に定義します。

{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE TypeFamilies #-}

import           GHC.Prim (Constraint)
import qualified Data.Set as S

class RFunctor f where
    type RSubCats f a :: Constraint
    type RSubCats f a = ()
    rfmap :: (RSubCats f a, RSubCats f b) => (a -> b) -> f a -> f b

するとそのインスタンスは次の様に定義出来ます。
例として[]とSetをインスタンスにします。

instance RFunctor [] where
    rfmap = map

instance RFunctor S.Set where
    type RSubCats S.Set a = (Ord a)
    rfmap = S.map

嬉しいことに[]の定義は既存のFunctorと全く変わりません。RFunctorのRSubCatsのデフォルトの定義を()としているためです。そのため、Setの様に要素に制限を付けたいときだけRSubCatsを定義すればいいことになります。

main = print $ rfmap abs (S.fromList [-2, -1, 0, 1, 2]) -- fromList [0,1,2]

SetがFunctorのインスタンスになったことにより、(r)fmapが使えるようになりました。
まあしかしこのままではS.mapをそのまま使っても全く変わりません。やはりモナドが欲しくなりますね。

Set Monad


Set Monadを定義します。
まずはRMonadです。RFunctorにを親クラスにします。RApplicativeを挟まなかったのは面倒だっただけです。

class RFunctor m => RMonad m where
    rreturn :: (RSubCats m a) => a -> m a
    rbind :: (RSubCats m a, RSubCats m b) => m a -> (a -> m b) -> m b

instance RMonad S.Set where
    rreturn = S.singleton
    m `rbind` f = S.unions $ map f (S.toList m)

Set Monadが定義出来ました。
重複した値が潰されるモナドの完成です。

main = do
    print $ (S.fromList [-2 .. 2 :: Int]) `rbind` \x ->
            (S.fromList [-3 .. 3 :: Int]) `rbind` \y ->
            rreturn $ x * y

do構文が使いたいですね。しかしdo構文はGHC.Base.Monadのインスタンスでないと発動されません。残念。

Restricted Functor, Restricted Monad


この定義はすっきりしており自然な拡張ぽいので悪くないと思うのですが、そもそもGHCプラグマ依存ですし、GHC.Base.Monadがこんな感じに拡張されることは無いような気がします。
do構文の使用が緩和される方があり得そうですかね。

元論文について


上記コードはoriginal paperの定義とは少し異なりますしはそちらはあまり読めてませんごめんなさい。
他にもpaperにはUArrayをRFunctorのインスタンスにするといったことやComonadについても書かれています。圏論に関する部分は途中まで読んですっ飛ばしました。
型クラスの型制約に関しては圏論的に解釈するとHask圏のSubCategoryに相当するという記述や、止まらないプログラムとか意図的なものじゃないからと言って⊥が自然に無視されたことが印象的でした。あ、はい残りも読みます。

コード片

モナドが比喩で表せないことをわかりやすく説明したいモナドチュートリアル補足


厄介なのはjoinだ。joinは以下のような型を持つ。

join :: Monad m => m (m a) -> m a

読み下してみよう。「joinは、二重にネストしたモナド(m (m a))をとり、一つに潰して返す(m a)」。
モナドとは、このjoinによって決まる。
モナドの定義でreturn, (>>=)の対がよく出てくるが、(>>=)の代わりにjoinを使ってもいい。
(>>=)のjoinを用いた定義は以下だ。

(>>=)     :: Monad m => m a -> (a -> m b) -> m b
m >>= f   = join $ fmap f m

これも読んでみよう。「bind(>>=)は、(fmap f m)で生成されたネストされたモナド(m (m b))を、joinで潰した結果を返す」


つまりモナドの性質とは、このjoinの、モナドの潰し方によって決まる。
つまりモナドとは、このjoinの具体的な実装によってベルトコンベアにもシュークリームにも象にも接ぎ木にもベドウィンにもなるということだ。


問題はこのjoin、「ネストを潰して一つにする」という部分をリアルワールドで上手く例えられる概念が存在しないのだ。
だからモナドの比喩は失敗する。
何か見つかった方は、それを使ってうまくモナドを例えて欲しい。僕は思いつかなかった。


プログラムの結果


関数は次のような形をしている。

a -> b

入力aに対し、bが返る。
対してプログラムとは次の様な形をしている。

a -> m b

入力aに対し、単なるbではなく、(m b)が出力として返る。
m bとは何か。プログラムの結果だ。ということをMoggiさんが考えた。らしい。

ということをwikipediaのモナドのページをみてへーって思った。

僕らはこのプログラムを組み合わせたい。ということは他のエントリで何度も書かれているのでここでは置いておこう。

さて問題は(m a)といった形式だと思う。Haskellで頻出する(m a)はとても抽象的な表現だ。
Haskell入門者はこの(m a)から具体的な値が想像出来ない。mもaも型パラメータである。なんだこれは。抽象的すぎて意味が分からない、となるわけだ。僕はなった。


この(m a)を、「型aを所持したmというコンテナ」と解釈してしまうと、理解の壁にぶつかるかもしれない。
例えば(m a)は次のような形をしている。

data Maybe a = Nothing | Just a

例えば(m a)は次のような形をしている。

data List a = Nil | Cons a (List a)

例えば(m a)は次のような形をしている。(State s)の部分がmだ。

newtype State s a = State { runState :: s -> (a, s) }

例えば(m a)は次のような形をしている。

newtype Writer w a = Writer { runWriter :: (a, w) }

例えば(m a)は次のような形をしている。

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

例えば(m a)は次のような形をしている。

data Free f a = Pure a | Free (f (Free f a))

例えば(m a)は次のような形をしている。

data Pipe l i o u m a =
    HaveOutput (Pipe l i o u m a) (m ()) o
  | NeedInput (i -> Pipe l i o u m a) (u -> Pipe l i o u m a)
  | Done a
  | PipeM (m (Pipe l i o u m a))
  | Leftover (Pipe l i o u m a) l

aを含んだコンテナというより、aは単なるパラメータと考えた方がいいかもしれない。
少しややこしい事に、型族による型関数のために同じような見た目になっていることがある。よく見れば気づくだろうけど、気をつけて。


具体的なモナドを見かけたら、その型とjoinを確認するといいかもしれない。

静的型付言語/動的型付言語のメリット/デメリットについて考えてみる

http://d.hatena.ne.jp/perlcodesample/20130227/1361928810
Haskellが好きな人です。
普段0.4M行くらいのPHPコードなんとかしてます。

Haskellerへ

変な事言ってないかチェックお願いします。

動的型付言語のトレードオフ

変数に型が無い事のトレードオフが理解出来ていないと思われる。

件のエントリを見ると、変数に型が付いていない方が圧倒的に有利に見える。そうだったら世の中のソフトウェアは全て動的型付言語を用いるはずだ、そうなっていないのは静的型付言語にもメリットがあるからだ、という論を僕はここではしたくはない。


彼が書いている部分でそのような論を用いている箇所が有る。大規模サイトで実際に動的型付言語を用いている、だから十分に使える（はずだ）という。ここは彼の自分の論(型が付いていない方が有利)から発生していない、少しずるい論調だ。


大規模サイトにおいて動的型付言語を用いている理由は、型がどうのこうの以前のビジネス的な理由の方が大きいと僕は思っている。だから、大規模サイトで採用されているから動的型付言語も大規模で十分使えるしミッションクリティカルな領域でも問題ないと言うのは、僕にはナンセンスに見えるわけだ。


僕の立場を書くと、動的型付言語にメリットはあると思う、しかし構築するシステムの規模やチーム規模が大きくなるにつれてそのメリットよりデメリットが大きくなる。そしてそのメリットとデメリットのが反転する規模の分岐点は(常人が思っているより恐らくは)小さい、というものだ。
具体的には10K行程度。もう少し言うなら、一人で実装する場合は実装内容が人一人の頭の中に全て入る程度の規模。複数人で作業するなら、それら一人一人の頭に入る規模の最小値より、更に小さい。動的型付言語は実装を小さくまとめられる限り、そのメリットを十分に享受出来ると思っている。動的型付言語はコンパクトにまとめるための機能を沢山持っている事が多いので、それらをふんだんに活用して、人のメモリを超えない様にすることが望ましいと思う。しかし解くべき問題がそもそも複雑である場合、本質的にコードも複雑にならざるを得ない場合も多い。そのような大規模/複雑な問題に動的型付言語は向いていないし、使うべきではない。そういう立場をとる。


そして静的型システムは、動的型システムよりもテストの記述を少なくしてくれる。以下ではそれを示そう。

関数の引数と返り値が何か分からない動的型付言語

関数fを考えよう。引数Xに対して返り値Yが返る関数だ。

f :: X -> Y

このとき、関数fに対して網羅的にテストをする場合、そのパターン数は型Xの要素数となる。
XがBoolなら2通り、XがCharなら文字の個数通り。


関数gを考えよう。引数S, Tに対して返り値Uが返る。

g :: S -> T -> U

このとき、関数gに対して網羅的にテストをする場合、そのパターン数は(型Sの要素数)*(型Tの要素数)となる。つまりS, Tが共Boolなら4通り。Sの要素数が3, Tの要素数が4なら12通り。

そのはずだ。静的型付言語ならば。


動的型付言語は言語にもよるかもしれないが、関数の引数には任意の値を渡す事が出来る。よって言語でとれる値の要素数をN_langで表すと、1引数関数ならばN_lang通り、2引数関数ならN_lang^2通り、n引数関数ならN_lang^n通りのパターンが発生する。


N_langという要素数は、IntとDoubleが含まれることから、1引数関数であっても1京通りは下らない。それどころか直積構造であるオブジェクトとかも含まれるので一引数だけでも無量大数(10^68)は突破しているだろう。2引数関数、3引数関数あたりでは膨大すぎて見たくもなくなる数だ。


もしかしたら馬鹿にしていると感じるかもしれない。そんなことはそもそも問題ではない、関数毎に受け入れる値はそれよりもずっと小さいのだからと。「テストを書いて保証すればよい」と。


そう感じるならば、恐らくあなたは既に「型チェック相当のテストを自分で書く」という、静的型付言語だったなら自動化出来る事をわざわざ自分の手を使って実行しまっていることになる。しかも型チェックに比べ物にならない程にお粗末な形で。型システムはそのコストを0にし、尚かつシステム全てで一貫性を保ってくれる。


以上、静的型付言語はテストの一部を担保してくれる。


捕捉するなら、動的型付言語ほどでもないが、静的型付言語でも同様の問題は発生し得る。そうであっても、例えば要素が3つしか無い型をIntで代用するなんて阿呆なことはしないし、Intを用いざるを得ない、もしくはIntをラップした型を用いるしか無いなら、それは言語機能が貧弱なだけで型システムとは無関係だ。また、その問題も型で解決しようという試みがあるため、今後に期待したい。

動的型付言語と大規模開発

前述した「関数の引数と返り値で何が渡されるか分からない、何が返るかわからないために発生するエラーのリスク」は、関数の定義数に比例して増大するリスクであるため、動的型付き言語は大規模開発に向かない。


Nullのような欠損値を持つ言語にも同様の議論が当てはまる。「Nullの存在によって関数からNullが返るかどうかわからないために発生するエラーのリスク」は、関数の定義数に比例して増大するリスクであるため、Nullのある言語は大規模開発に向かない。


前述したけども、大規模Webサイトで動的型付言語が採用されているのは型以前の他の要因が大きいと思っており、彼らはそのコストを支払えるし実際に支払っているのだと思う。大規模開発に向かないという僕の主張は変わらない。

他のプログラマが変に使わない保証、制限の共有

ソフトウェア開発上難しい問題のうち、他の開発者に変なコードを書かせない、というものがある。これは能力が低いからと一概には言えない。静的型付言語では型を見れば何を引数に渡せば分かるが、動的型付言語ではその使い方がはドキュメント(人間が書いた不完全な何か)を頼るか実装(人間が書いた、意図が分かる様に分かり易く書いてないかもしれない何か)を見るか、テスト(人間が書いた、もしかしたら見ても使い方が分からないかもしれない何か)を見なければならない。どれにせよ型を見るよりずっとコストが高い。当然規模が大きくなればなるほどそのコストは増える。


静的型付言語でドキュメントが要らないとかテストが要らないとかいう話をしている訳ではない。
そのどれをとっても、動的型付言語は構造的に静的型付き言語よりもコストが高くなるという話をしている。


型とは本質的に制限であるが、ソフトウェア開発に関しては制限を明確にすること、その制限をチームの開発者とコストゼロで共有出来る事は大きなメリットとなる。理想を言うならば、チーム開発で共有される様々なポリシー/制約は、コンパイルエラー/警告あたりまで持ち上げられる事が出来る(つまりコストゼロで共有出来る)と僕は嬉しい。それは言語の役割かどうかと聞かれると微妙だけども。

型とテスト

純粋な関数に関しては、関数の性質をテスト出来る性質テストが有効だ。
現在QuickCheck, SmallCheck等がある。QuickCheckは他言語にも移植されており、Perlにも有るようだ。
Haskellでは型からテストデータを自動で生成する。

型とは設計である

型とは設計だと思っている*1。しかもコードから乖離することのない、生きた設計だ。
型を見れば問題の切り分けが出来ているかどうか分かる。
型を見れば開発者の意図が分かる。
型を見れば静的な性質の多くが分かる。
型を見てそれらが分からないようなら、それは設計(型)が悪いのだろう、と僕は思っている。
さらに型チェックが通れば設計の一貫性も担保される。
設計の変更時にはコンパイラが何処を直せば良いか全て洗い出してくれる。


静的型付言語では型が煩わしくなるという旨の発言を聞くたびに、僕には「私は設計が出来ません/設計を考えた事がありません」と言っている様にしか聞こえない。

型の煩わしさを低減させる試み

型が一部でとても便利である一方、煩わしいと感じることも実用上は存在する。
その煩わしさを低減させる機能の一部を紹介する。

型推論(Type Inference)

型を書かずとも推論する機能。健全性と完全性があり、健全な型推論を持つコンパイラは、型が付けば正しいプログラムであると保証される。完全な型推論をもつコンパイラでは、正しいプログラムであるならば、型が推定出来ると保証される。ここで「正しいプログラム」とはバグが無いという意味ではなく、stuck状態にならない(progress)かつ、well-typedな項は簡約してもwell-typedである(preservation)という意味。のはず。
詳しくは近日邦訳版が発売されるTAPLを買おう。
型システム入門 −プログラミング言語と型の理論−

Deferring Type Errors

型エラーを実行時まで遅延させる。
つまり型エラーが存在する(型の一貫性がない)としても、取りあえず実行させられる機能。
これで動的型付言語の様にプロトタイピングが出来る様になるはず。すごい。
GHC7.6.1 or later.

Type-Holes

Haskellで以前はundefinedを実装を書かずに型チェックを通すために用いていたりしたが、それをコンパイラが強化してサポートしたもの。というかAgdaでまず実装されたものらしい。
型が分からない箇所にholeと呼ばれるプレイスホルダ'_'を書いておくと、そこに書くべき値の型をコンパイラが教えてくれるとい
う機能。のはず。
GHC7.8(?)

あ、

すみませんHaskell以外のことはよくわかりませんし知っていたら教えて下さい。

*1:少なくともHaskellでは

dataToExpQ

Haskell Advent Calendar 2012二日目です。
一日目から飛ばしてきましたね。負けずに頑張らなければなりませんね。


QuasiQuotes書くときにdataToExpQ便利ですよね。
便利だけどこんさんが何言っているかわかんねえ！という人向けの記事です。
間違ってたらツッコミください。


(以下ではGHC7.4.1を用いています)

何故QuasiQuotesなのか

僕らエンジニアが扱うものは基本何らかのシンタックスに則って書かれています。
つまりHaskellerはConfigファイルやSQL文字列、もしくはある言語ファイルなどを目の前にして、
「このファイルパーズして"Haskellのデータ構造"として欲しいなあ」とつぶやく訳です。
文字列から値生成ならまだランタイムに出来ますが、型の生成や型クラスの生成などとなるとコンパイルタイムにやるしかありません。
というわけでまあQuasiQuotesを使うわけです。

QuasiQuotes作成

このQuasiQuotes、定義は以下の様になっているわけですが、

data QuasiQuoter = QuasiQuoter { quoteExp  :: String -> Q Exp,
                                 quotePat  :: String -> Q Pat,
                                 quoteType :: String -> Q Type,
                                 quoteDec  :: String -> Q [Dec] }

つまりはString -> Q Expといった関数作れば良い訳ですね。
で、パーザが必要になるのまではまあいいんですが、ExpQ(Q Expのalias)を自分で構築するの面倒ですよね。
GHCでは、「あるデータ型の生成」に対象を絞ることで簡単にQuasiQuotesを構築する方法が提供されています。
それがdataToExpQ系列の関数です。ここではdataToExpQをとりあげます。

dataToExpQとは

dataToExpQはLanguage.Haskell.TH.Quotesで提供されています。
QuasiQuoterを作る際のイメージを簡略化して図で表すと、

+--------+ parser +---------------+ dataToExpQ +--------+
| String |------->| (Data a) => a |----------->|  ExpQ  |
+--------+        +---------------+            +--------+

こんな感じです。parserでStringからあるデータ(Dataのインスタンス)を生成します。
そのデータからExpQを生成するのがdataToExpQです。結果(String -> ExpQ)の関数が出来るため、
それをQuasiQuoterにぶちこみます。


具体的に型を見てみます。

Prelude> import Language.Haskell.TH.Quote as Quote
Prelude Quote> :type Quote.dataToExpQ
dataToExpQ
  :: Data a =>
     (forall b.
      Data b =>
      b
      -> Maybe
           (Language.Haskell.TH.Syntax.Q Language.Haskell.TH.Syntax.Exp))
     -> a -> Language.Haskell.TH.Syntax.Q Language.Haskell.TH.Syntax.Exp

ややこしそうに見えますが、1引数適当に渡して、fullQualifiedな部分を落とすと分かり易くなります
(手で簡略化してます)。

Prelude Quote> :type Quote.dataToExpQ $ \_ -> Nothing
dataToExpQ $ \_ -> Nothing
  :: Data a => a -> ExpQ

つまり、Data a => a を ExpQ に変換するからdataToExpQという名前がついていると。そのままですね。
この変換過程にユーザが口を挟むためのものがさっき渡した引数という訳です。
\_ -> Nothing (const Nothingでもいいですが)を渡した場合は特別なことは何もしません。
ではDataとは何でしょう。

Scrap Your Boilerplate

Generic Programmingという概念があって、それのHaskell版です。ひどい説明ですね。
Scrap Your Boilerplate(syb)という論文とライブラリを以てHaskell(GHC)に取り込まれ
ました。

GHCの拡張、DeriveDataTypeableを有効にすると、deriving節でTyepable, Dataが指定出来る様になります。
Typeableは自身の型表現を返せる型のクラスであり、型安全なcastを提供します。
Dataは一般化されたfold(gfold)を持つ型のクラスであり、Generic Programmingを提供します。

// TODO: syb例を書こうと思ったけど面倒になってきた

dataToExpQを適当に使ってみる

dataToExpQを使ってみましょう。
XXXという文字列からYYYというデータ型ほしいなあ、という欲求部分ですが、
例題としてXXXを数値リテラルと和と積のみの数式、YYYをExprとします。
あ、文字列のパーズ部分は省略します。

{-# LANGUAGE TemplateHaskell #-}
module Main where
import Language.Haskell.TH
import Language.Haskell.TH.Quote
import Data.Generics.Aliases
import Expr -- GHC stage restrictionのためモジュール分けた。後述。

-- 以下ではexpressionをExpQに変換した後、その場に直ぐspliceしている
main = do
    putStrLn "---- do nothing"
    print $((dataToExpQ $ const Nothing) expression)
    putStrLn "---- 3 to 8"
    print $((dataToExpQ $ Nothing `mkQ` lit3tolit8) expression)
    putStrLn "---- Add to Mul"
    print $((dataToExpQ $ Nothing `mkQ` addToMul) expression)
    putStrLn "---- succ and addToMul"
    print $((dataToExpQ convertExpr) expression)


以下がExprです。

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE TemplateHaskell #-}
module Expr where
import Language.Haskell.TH
import Language.Haskell.TH.Quote
import Data.Generics

-- 数式パーズして得られるデータ型(derivingでDataのインスタンスにしてある)
data Expr =
    Lit MyInt
  | Add Expr Expr
  | Mul Expr Expr
  deriving (Typeable, Data, Show)

-- データ型ひとつではつまらないのでもう一つ定義
newtype MyInt = MyInt Int
  deriving (
      Typeable
    , Data
    , Show -- 表示用
    , Num  -- 数値リテラルとして使用する(Cf.GeneralizedNewtypeDeriving)
    , Enum -- succの使用
  )

-- パーズ後得た値の例
expression :: Expr
expression = Add (Lit 3) (Add (Lit 4) (Mul (Lit 5) (Add (Lit 6) (Lit 7))))
-- ... snip ...


dataToExpQに渡す部分を見てみます。まず木構造の葉の変換。

-- 3 を 8 に変換(葉の変換)
lit3tolit8 :: MyInt -> Maybe ExpQ
lit3tolit8 (MyInt 3) = Just [| MyInt 8 |]
lit3tolit8 _ = Nothing

葉の所で現れるMyIntだけを考慮して変換ルールを書いてしまいます。
これをmkQを使ってクエリ化(mkQのQはQモナドではなく、Queryを意味しています)し、dataToExpQに食わせます。

main = do
	-- ... snip ...
    print $((dataToExpQ $ Nothing `mkQ` lit3tolit8) expression)
	-- ... snip ...

mkQは定義見ると分かりますが、動作は要するにmaybeです。第2引数試して駄目なら第一引数返します。
つまりlit3tolit8が使えない(MyIntでない)ならNothingを返します。
ここで僕らはGeneric Programmingをしていることを思い出して下さい。
dataToExpQは変換対象の値(expression)にDataのインスタンスを要求しているため、
Dataの親クラスであるTypeableも要求しており、対象の値の型表現をチェック出来るわけです。


次に内部ノードの変換です。

-- AddをMulに変換(枝の変換)
addToMul :: Expr -> Maybe ExpQ
addToMul (Add x y) = Just [| Mul
    $((dataToExpQ $ Nothing `mkQ` addToMul) x)
    $((dataToExpQ $ Nothing `mkQ` addToMul) y)
    |]
addToMul _ = Nothing

ここでもやはりExprのみを考慮して書きます。
自身を再帰しています。Generic Programmingとはいえ、
dataToExpQがMaybe ExpQを要求してしまっているので、
自分で末端まで変換して上げないといけない気がします..
ということで再帰しています。


最後にクエリの合成です。mkQの後にextQでクエリを連結させていきます。

-- succMyIntとaddToMulの合成、と言いたいが..
convertExpr :: Data a => a -> Maybe ExpQ
convertExpr = Nothing `mkQ` succMyInt' `extQ` addToMul'
  where
    -- AddをMulに変換(convertExprを呼び出してしまっている)
    addToMul' :: Expr -> Maybe ExpQ
    addToMul' (Add x y) = Just [| Mul $((dataToExpQ convertExpr) x) $((dataToExpQ convertExpr) y) |]
    addToMul' _ = Nothing

    -- MyIntの部分をインクリメント
    succMyInt' :: MyInt -> Maybe ExpQ
    succMyInt' (MyInt i) = Just $ appE (conE 'MyInt) (litE (integerL $ fromIntegral (succ i)))

succMyInt'とaddToMul'の単純な合成が出来ればいいのですが、
やはりdataToExpQがMyabe ExpQを要求しているので単純に合成とは行かなそうです。
しようがないのでaddToMul'の内部でconvertExprを呼び出しています。


さて以上の様に、パーズした結果を自由に変更しつつExpQに持ち上げることが出来るとわかりました。
本来ならばこれを応用してAntiQuote(反クオート)を行います。
まあそのへん適当にやってください。
反クオート以外にも色々出来るかもしれません。


sybは実行時に型表現をチェックしているために動作が遅いのですが、
やっていることはQモナドの生成であるため、コンパイル時間が遅くなる程度ですみます。
Generic ProgrammingとTemplate Haskellは相性いいですね。


あ、今思いついたけど、データ色々変更したいならdataToExpQに渡す前に自分でGeneric Programmingすればいいですねあほでしたね僕。
色々台無しになりましたが終わります。

GHC stage restriction

Template Haskellを書いていると以下のようなエラーに度々出会います。

/some/path/to/haskell/file.hs:xx:yy:
    GHC stage restriction: hoi'
      is used in a top-level splice or annotation,
      and must be imported, not defined locally
    In the first argument of `foo', namely hoi'
    In the expression: foo hoi'
    In the first argument of `print', namely `$(foo hoi')'

無限ループ処理が面倒なことによる制限らしいのですが、対処法は単純です。
エラーメッセージで書いてある様にモジュールローカルで定義をせずに、外部モジュールで定義するか、
怒られている対象の関数を関数化せずに手動でインライン化するかすればいいです。


ここからはTemplate Haskell内部知らないので予想でしかないのですが、GHCはTemplate Haskellを扱う際(恐らく-XTemplateHaskellあたりをフラグとして)、
ExpQなどTemplate Haskell用のQモナドを扱う関数とその他の関数を区別して取り扱うようなので(考えてみればそりゃそうだ、という感じですが)
開発者側でもマクロに関わる関数と普通の関数に気をつけて記述する必要があるのだと思います。


ちなみにHaskellと同じような型付きマクロを持っているHaxe(2.10)でも同様の制限がありました。
コンパイルが止まらなくなるよりはマシだろ、ということですかね。




// TODO: リンクとかはる

HaskellでGPUプログラミングしてみた

Haskell

repa触ってみたらGPUも触ってみたくなったので触りました。
ライフゲームを略。


次の時刻の盤面を計算する部分です。ドキュメントやサンプルを見ると、どうやらstencilを使うと良いようです。

step :: Board -> Acc Board
step arr = Acc.stencil stencil2D (Constant 0) . Acc.use $ arr

cellとその周囲cellから次の時刻の値を計算出来るという、流体シミュレーションのために有るような関数ですね。
その際、境界条件をどうするかが第二引数です。

data Boundary a = Clamp | Mirror | Wrap | Constant a

最外値がその外もそのまま続いているかのように扱うのがClamp、範囲外の値が反転しているものがMirror、境界外が反対側と繋がっているものがWrap、定数値が広がっているように扱うのがConstant aです。
ライフゲームでは範囲外の値は死んでいると判断されれば十分なのでConstant 0にしています。


そしてlifecheck部分。

stencil2D :: Stencil3x3 Int -> Exp Int
stencil2D ((a,b,c), (d,e,f), (g,h,i)) = (cnt ==* 2) ? (e, (cnt ==* 3) ? (1, 0))
    where
        cnt = a+b+c+d+f+g+h+i

初め普通にガードで書いたのですが、Eq.==は使えません的な実行時エラー出ました。どうやらGPU上の表現であるらしいAcc, Expなどといった値はいつもの関数をそのまま使う事は出来ないようです。

ここでは(?)演算子を使って分岐を行っています。

(?) :: Elt t => Exp Bool -> (Exp t, Exp t) -> Exp t

丁度三項演算子の様なものですね。結果はtupleでまとまっているので2項演算子ですが。

比較演算子も==, <, >といったものではなくて、==*, /=*, <*, >*, <=*, >=*といった*付きの演算子が用意されています。


GPU上でのAccな値を計算する関数がrunです。

repeatStep :: BoardSize -> Board -> IO ()
repeatStep siz board = do
    let board' = CUDA.run $ step board
    threadDelay 120000
    clearDisp
    printRect siz board'
    repeatStep siz board'

一ステップ毎にGPU上で計算しているとあまり効果がないような...
だけど多分Accな値は触りようが無い気がするので今回は仕方ないような。高fpsが要求される場面ではGPUとの連携はどうするのが良いのでしょうね。


ソースコードです。

そういえばcabal install accelerate-cudaで少しつまづいたのでした。

$ export DYLD_LIBRARY_PATH=/usr/local/cuda/lib

などとしたら通る様になりましたが。

高速並列演算多次元多相配列repaを使ってみる。

Haskell

Haskellのライブラリで前から気になっていたrepaを触ってみます。高速並列演算多次元多相配列ですからね。それは気になります。regular pallalelの「regular」の意味がいまいち分かりませんが。
丁度@shelarcyさん記事が書かれたことをきっかけとしています。

ここではrepaでライフゲーム作ってみます。
ライフゲームは周囲8マスの影響で次の時刻の生死がわかるという仕組みを持っています。要するに流体のシミュレーションと同じ仕組みを持っているんですね。ライフゲーム書ければ流体のシミュレーションが書けるわけですよ多分。


ソースは一番下においておきますのでポイントだけ。
Arrayからライフゲーム的に次の時刻のArrayを得るためにはtraverseを使えばいいらしい、という情報を得たのでそれを使います。
残念ながら上記@shelarcyさんの記事ではtraverseはまだ説明されていませんでした。今後解説されるのでしょうか。
ということである時刻の配列(ここではBoard U)から次の時刻の配列(ここではBoard D)を得るには以下の様に書けます。

step :: BoardSize -> Board U -> Board D
step siz board = R.traverse board id nextStatus

これだけです。まあnextStatusが多少複雑ですが。素敵ですね。
そしてそのstepでの返り値、Delayed Array(Board D)をcomputePで処理して次の時刻の値を取得します。
repeatStepはそれを適当に（本当に適当に...）表示しているだけです。

repeatStep :: BoardSize -> Board U -> IO ()
repeatStep siz board = do
    board' <- R.computeP $ step siz board  
    usleep 120000
    putStr "\x1b[2J"
    putStr "\x1b[1;1H"
    printListToRect siz $ R.toList board'
    repeatStep siz board'

このcomputePだけで並列処理が出来ます。素敵ですね。
Delayed arrayが返ってくるのに逐次computePするのは少々もったいない気分ですね。まあ今回は仕方ない。

コンパイルして実行します。色々付けるらしいです。

$ ghc -Odph -fllvm -optlo-O3 -rtsopts -threaded lifegame.hs
$ ./lifegame +RTS -N2

GPUもちょっと触ってみたくなりますね。


ということでソースです。