Paraiso 0.1.0.0公開
あの日胸に抱いたのは、ささやかな希望と憧れ。訪れたのは、速すぎるコードと尽きせぬ課題。
http://hackage.haskell.org/package/Paraiso-0.1.0.0 うごごご・・・
以前はただ文字列の結合でコードを生成していたバックエンドまわりを大幅に強化し、データフローグラフ組立て→解析と最適化→計画立案→抽象文法→コードという段階を踏んでコードを作るようにしましたよ。その結果、CUDAをサポートするようになった。仕組みを悩みながら決めるまでに２ヶ月くらいかかったが、CUDAバックエンド作るのはすぐだったことに驚く。
うちらの分野で使われている既存のコード（CPU向け）と対決しても遜色ない性能が出ますし、(Paraisoとしての)ソースコードには指一本触れずにGPUに移行できる。なにより、ソースの変更は１、２行で、１万行以上にも及ぶC, CUDAコードを操り、性能をがらりと変えていく、そんな夢が現実のものとなりました。すでに2^1000通りのオーダーのコードを生成できる可能性を実現できたので、ぜひGAとかに掛けてみたい。
やんぬるかな、あまり大きな報告をまとめてる時間はないです。詳細は函数プログラミングの集い 2011で！
いづれにせよ、ほんとうの勝負はMPI化してからですよ・・・
ParaisoにDead Code Eliminationを実装
劇的ビフォー／アフター
ほんとはHoopl使いたいんだお・・・
でも今の俺じゃ歯が立たないお・・・
だからまずは基本的な最適化を自前で実装するお！！！
renumberのところがちょっとApplicative使って綺麗に書けたのはうれしかった
newNodes = catMaybes $ fmap (\(idx, lab) -> (,lab) <$> renumber idx) $ FGL.labNodes graph newEdges = catMaybes $ fmap (\(iFrom, iTo, lab) -> (,,lab) <$> renumber iFrom <*> renumber iTo) $ FGL.labEdges graph
だが、こんなので喜んでるレベルじゃまだまだだな…
上がbeforeで下がafterです
上から2番目の関数、同じものなのですが相当縮んでいるのがおわかりでしょうか
ていうか関数の宣言で一画面埋まるとか・・・
ICFPC2011 マルチスレッド版LTGモナド
未だにICFP programming contest 2011の余韻から抜け出せないでいます。打ち上げでもいろんなプログラマーやジャッジ側と交流ができて楽しかったです。
さて、その打ち上げ当時から「１ターンで殺してゾンビ化して次弾Getまで出来るよね」「それで浮いたターンで殴れば最強じゃね？」とかいうアイデアがよく出ていましたが、いざ作るとなると断片的な浮いたターンで呪文を組み立てるとかとても難しそうです。ところが週末にそれを可能にするフレームワークの発想が降ってきたので矢も盾もたまらず実装していました。
ありがたいことに、id:tanakhさんから「こういうきれいな抽象化を書かれると悔しい＞＜」「世界が嫉妬するコード」「これはやばいし、Haskellじゃないともはやこのレベルのコードはここまで綺麗にかけないだろう」「これコードシンプルすぎるし、他の言語だと多分これ実装するの死ぬのじゃないか？」との言葉を頂きましたので、Haskellの宣伝のために紹介してみようと思います。ちなみに僕はHaskellだけが特別な言語だとかあまり思いこまないようにしようとしているし例えばRubyだってThreadもQueueもあるんだから似たようなことはできるんじゃないかなと思います！
LTGモナドのマルチスレッド化
runLTG :: LTG a -> IO () runLTGs :: [(LTG Bool, LTG ())] -> IO ()
僕らのチームではLTGモナドというのを作ってAIの戦略を組み立てています。runLTGは１つのLTGモナドを実行に移す関数です。今回作ったrunLTGsは、[(ある戦略を実行すべきかどうかの判定,実行すべき戦略)のリスト]を受け取り、毎ターン、リストの中で最初にTrueになった戦略を一ステップだけ進行させます。このマルチスレッド機構の実装は主にMonad.hsの --coroutine-- とコメントされている部分です。それを使って書かれたAIの例もあります。
基本的な発想は、LTGモナドを並列に実行したいんだったら、その数だけHaskellのスレッドを立てて並列に走らせておいて、適切なところでタスク切り替えしてやれ、というものです。
type LTG = StateT (ThreadAttr, Simulator) IO data ThreadAttr = SingleThread | MultiThread (TVar Scheduler) Int{-tid-} data Scheduler = Scheduler { mailbox :: Vector(TMVar Simulator), condition :: Vector(LTG Bool) }
まず、LTGモナドはSimulatorの情報（現時点でのゲーム状態の全て）に加えてThreadAttrを持つように改造されています。ThreadAttrはMultiThread実行の場合、マルチスレッド実行全体を司るSchedulerへの参照と、自分のスレッドIDを含んでいます。Schedulerがスレッドの並列実行を管理しており、これには各スレッドのmailboxと実行判定が格納されています。TMVarは「空になることが出来るSTM変数」であり、空の状態のものを読もうとすると、中身が入るまでブロックします。mailboxでシミュレーションの状態をまるごとやりとりすることで、複数のスレッドが一貫して１つのゲームを進行できるようにします。Schedulerは後述するように、ゲーム中でconditionが変化するなど更新されることがあるので、その更新が全てのスレッドで共有されるよう、ThreadAttrはSchedulerをTVarにくるんで持つようにしています。
基本的に、runLTGsは渡された戦略LTGモナドの数だけのワーカースレッドと、タスク切り替えを制御する１つのマスタースレッドを起動します。シミュレーションは、マスタースレッドのメールボックスに初期状態のシミュレータが入り、他のスレッドのメールボックスは空である状態でスタートします。
mailbox0 <- newSimulator >>= newTMVarIO mailboxes <- replicateM n newEmptyTMVarIO . . . schdr = Scheduler { mailbox = Vector.fromList $ mailbox0 : mailboxes , condition = Vector.fromList $ return False : map fst ltgs } tvs <- newTVarIO schdr
各スレッドは実行されると、実行すべきタスクltgを実行する前に、いきなりwaitWakeで待ちに入ります。
runLTGThread tvs tid ltg = do flip evalStateT (MultiThread tvs tid , error "undefined state") $ do waitWake er <- E.try ltg waitWake = do . . . sim <- atomicalift $ takeTMVar (mailbox schdr ! tid) putSimulator sim
waitWakeでは、自分のメールボックスに状態が届くまで待ち、届いたら、それが最新のゲームの状態なので、自身のシミュレーターを上書きしてしまいます。waitWakeを抜けると実際の戦略ltgが実行され始めるわけですが、自分の手を打ち、相手の手を読み取ってシミュレーションを進めた直後に、yieldします。yieldでは自分のシミュレータをマスタースレッドのメールボックスに投函し、自分は待ちに入ります。
getHand = do h <- liftIO readHand s <- getSimulator (ns, msg) <- liftIO $ execStep h s putSimulator ns . . . yield yield = do . . . sim <- getSimulator atomicalift $ putTMVar (mailbox schdr ! masterTID) sim waitWake
マスタースレッドはというと、シミュレーション状態を受け取って上書きしたら、その文脈で各スレッドのconditionを評価して、最初にTrueを返したスレッドのメールボックスにシミュレーション状態を投函します。
masterThread = forever $ do . . . conds <- Vector.mapM id (condition schdr) let f = Vector.findIndex id conds case f of . . . Just tid -> do sim <- getSimulator atomicalift $ putTMVar (mailbox schdr ! tid) sim waitWake
マルチスレッド機構の概要は以上です。他にも、スレッド内の戦略が例外で抜けた場合は実行条件をreturn Falseにしてやるとか、conditionが全ての場合を尽くしていない(または、例外終了により尽くさなくなった)場合に備え優先順位最低の何もしないtailWorkerを挿入するなど、いくつかの工夫がしてあります。
最初はマルチスレッド化するのに継続とか必要なんじゃないか、じゃあモナド計算の継続ってどうやって取り出すの、というところで詰まっていました。関数型言語でマルチタスクな戦略を記述というと、どうしても各戦略の継続を取った上で並列実行の全てを管轄するような方向に発想が行きがちでした(できもしないのに^^;)。でもそんなことはなく、スレッド立てたいだけ立てて走らせ始めてしまい、後から必要な箇所で「情報を送って停止、情報が来たら上書きして再開」という、泥縄的なメカニズムで適切に動作したのには驚きました。この泥縄式で上手く行った背景には、Stateモナドを使って状態のある計算を明示的に記述しているために、状態をすり替えることの意味がはっきりしていること、さらにStateT IOになっているために中でIOが使えること、そこでSoftware Transactional Memoryを道具に使ってどんな物でも手軽にやりとりできることなどがあり、そのへんは書いていて有り難く感じました。
並列計算の実行を始めてしまったあとでも、その実行を自在に制御できると言う面で、Haskellの強みが出せたかと思います。
並列計算というと、とかくマルチコアを使い倒して速度を出すという方向性が強調されますが、今回のように「やりかけのタスクを沢山抱えたうえで適切な順序で実行していく」というアルゴリズムを書くにも、並列計算のビルディングブロックは有効なのだなということが体験できました。
戦略
このマルチスレッド版LTGモナドを使って実装した戦略がMamisanKawaii.hsです。名前が紛らわしいですが、書いているうちに何故かマミさんの魅力をコードで表現したようなものになっていったので、ほかに適切な名前が思いつきませんでしたご容赦ください。
コードはこんな感じです。
main :: IO () main = runLTGs [(isOpening , openingMove ), (mamitta , bikunbikun ), (isAlive False 0 , discipline ), (enemyWeak , madanNoButou), ((<55000) <$> getVital True 0, pumpUp ), (return True , shoot ) ]
本当に、実行条件とやりたいことの優先順位つきリストを与えるだけでマルチタスクな戦略が書けちゃうんです。美しい。
序盤の定跡がmamittaらbikunbikunするほかなく、無力化されますが、そこさえ通ればこっちのもの。相手のrevive 0を見逃さず即座にDecで叩き落としつつも、それに乱されることなく魔法を唱え上げ発動する隙のない華麗な戦闘シーンを見ることができます。デビュー時点での戦績はこんなもんです。ああもうマミさん美人だし強いしかわいいな。ティロフィナーレはほんとはattackループにしたかったのですが、書けるだけのSKI言語力が僕にはまだありませんでした・・・
まあこいつ自身が0番スロット使用者に対するメタみたいなもんではありますが、あっと言わせる新戦術で出し抜いていただけるよう、これからもYet Another Unofficial Judge for ICFP Contest 2011ではみなさんの挑戦をお待ちしております。例えば林崎さんのN0Y2CAtkQbは、途中から全く0番スロットを使わないで動作するそうです。
ICFPC2011 参加記録
ICFPコンテスト2011に参加してきました。
近年は予定がかぶったりでまともに参加できていませんでしたが、今回は久々にちゃんと参加できました。実は遠隔でなく泊まり込みで参加するのは初めての体験です。
ひとまず実装や作戦の詳細に関してはチームのページ https://github.com/tanakh/ICFP2011 も参照していただくことにして、コンテスト終了後に使い方を覚えたgit logから私の時系列を思い出せる限り復元してみます。
- -3 days 計算機パワーが必要な問題を想定し、haskellの並列・分散計算の勉強を始める
- parは過去の遺物であると聞いて衝撃
- forkIOでグリーンスレッドを立てまくるだけでマルチコアプログラムが書ける衝撃
- msgpack-rpcを使って型つきrpcプロトコルがいとも簡単に書ける衝撃
- STMはメモリと言うからIntくらいしか突っ込めないのかと思い込んでいたが文字通り任意の型が突っ込める衝撃
- だもんでとにかくSTMを使えば使い回しとか共有とか並列プログラムが思い通りに書けちゃう衝撃
- -40:00 自前で可視化が必要な問題を想定し、openframeworksというのでビジュアライザを準備し始める
- 00:00 コンテスト開始
- 02:18 IOモナドベースのAI開発用DSLを作る
- 02:52 とりあえず何もしないAIを記述
昼飯時で最初の作戦会議、僕と田中さんがシミュレータ、桜庭さんと林崎さんがAI作りで分業しようということに
- 05:28 田中さんのシミュレータを検証すべくランダムに手を打つAIを記述
- 05:41 ２つのシミュレータを比較するプログラムを書く
この頃の主な仕事はジャッジと田中さんのシミュレータを比較して不一致報告
- 08:40 AI開発班によりゾンビの使い方が解明されはじめる。ゾンビなのでSayakaと命名。
- 09:30 おかげでシミュレータのゾンビ周りの不一致が見え始める
- 10:00 ゾンビを起動させる部分は面倒くさいから丸ごと未実装だと言うので無いと困るといったらそんなの10分で書けると豪語するからストップウォッチのスイッチを入れる
- 10:10 本当に10分55秒で実装される衝撃
それからもしばらくシミュレーターの不一致を洗い出す仕事が続く
しばらくシミュレーター比較器を改善したり比較したりする作業が続く。
シミュレータのバグとシミュレータ比較器のバグを分離するのがどうしても難しいので、シミュレータを信じて、AIライブラリのモナド化を並行してやってもらうことに
- 26:00 比較器に「１戦目の棋譜を記録し」「２戦目ではそれを再現するダミーAIを使う」機能が搭載。乱数を使うAIでも、seedを保存したりすることなく比較作業に使えるように
- 27:00 田中さんによるLTGモナドが完成
- 27:40 さっそくSitting DuckやRandomなどシンプルなAIをLTGモナド化
- 28:00 SayakaのLTGモナドへの移植を開始。と思ったらなんとIOをLTGに置換しただけで何事もなく動く衝撃。
思えば最初にIOベースのライブラリを作っておいて本当によかった
- 29:00 LTGモナドで書かれた戦略を集めたライブラリを作り始める。名前はSoulGems
- 31:00 チーム内リーグ戦システムを作り始める
- 34:00 日台同時放送開始
- 36:00 AI開発班により、ゾンビの中でhelp i i爆撃を行うという最後まで主力となるAIが投稿される。林崎さんによりKyoukoと命名。
- 37:00 本格的に並列コンテストを開催しはじめる
- 37:20 林崎さんがKyoukoの最適化に着手
この晩から、林崎さんが訳がわからない勢いでKyoukoを最適化していくのを見て桜庭さんがポカーンとしながらも解説してくれるその説明も付いていけない理解できないのでポカーンとしながらも仲間の健闘を祈る作業が始まる。主な仕事は次々に出てくるモデルの強さとバグをリーグ戦で検証すること
- 39:00 それでもKyoukoの読める部分を変えてみたバリアントをいろいろ作る。あんまり強くない・・・
- 40:00 日台同時放送終了
- 45:00 攻撃を受けて復帰モードに入った際、全スロットをreviveしようとしていたのを、重要なスロットのみreviveする変更を提案。首の皮が繋がればいいということでMamisanと命名。しかしリーグ戦の結果は「試合が終了しない」という謎のもの。
実はこのころのAIには実はまだ無限ループに陥るパスが残っていたので、リーグサーバが悪いのかAIが悪いのかAIに施した改良が悪いのかはっきりせず辛かった。
- 47:00 19日の朝、みんなが寝ているうちに目がさめたので、LTGモナドに敵味方の過去の行動の統計を収集しAIに提供する機能をつける
まあ、試合中にこれを有効利用するまでには至りませんでしたが
- 51:00 この日もKyoukoはどんどん速くなる
- 53:30 ゾンビを埋め込むためにAttackを撃つための犠牲を先頭2スロットではなく少し隙間をあけた２スロットにしておく修正を提案。Help Bombへの耐性が上がることを発見。
２つのふくらみがないことにより鉄壁を誇ることからHomuと命名
- 56:06 Kyoukoに潜んでいたバグがついに取れる
- 58:00 終盤戦、バイタルが1〜2のスロットがほとんどになるので、単にループでdecを撃つルーチンを桜庭さんに作ってもらう。MadanNoButouと命名。しかし強くならなかったので棄却。
コンテスト後、僕が組み込む時に「ループを構築する」ルーチンを忘れて「準備されているはずのループを撃つ」ルーチンだけ組み込んでいたことが原因と判明。痛恨のミス。
- 59:00 偶数番スロットをひたすらreviveするだけのAIを作成。helpゾンビでは焼き切れない。代わりはいくらでもあることからKyubeyと命名。
- 62:30 Kyoukoのバグが取れた版にMamisanを再び組み込む。守る範囲を変えたバリアントを多数作ってリーグ戦により強さを比較。QB-(n)による蠱毒。「生存スロットが歯抜けになる順にrevive(Kyubey式)」「10スロット(最低限)だけ守る」が最善ということに。
- 63:30 目覚ましい成長を遂げたKyoukoに、終盤のヨセ、改良されたゾンビ切り口作成ルーチン、QB-10を組み込んだY2CAtkQbを出荷。事実上の最終版となる。
10時間あまり時間を残して余裕の雰囲気、あるいはこれ以上改善手の見つからない手詰まり感が漂う。
- 63:00 AI開発班、仮想敵を求めてAttackを連打するAIを作り始める。Yumaと命名。
残念ながらバグが取りきれず、コンテスト中の実戦投入には至りませんでした。
- 仮眠
- 68:00 READMEを書く
- 仮眠
- 72:00 拍手に目覚めるとコンテストは終わっていた。
命令列の最適化なら任せろとばかりAIを際限なく速くしていく林崎さん、使いやすくまた信頼に足るDSLライブラリを短時間で作り出す田中さん、困難なバグ取りや実装でも合理的に必要となれば根気よく作っていく桜庭さんの姿に感銘を受けました。僕としては一人ではICFPCに三日でコードを投げることすら覚束ないような実力ですがこのようなチームに招いてもらって光栄です。４人目として入ることで１人増えた以上の効果をもたらす、ような動きができていたとしたら、それはとっても嬉しいな、と思います。
何と言うか趣味の一致したチームだったのと、Haskellを垂直軸として水平分業できたのが幸いし、充実した７２時間となりました。あと僕の知っている限りでは今年の問題はICFPC史上最高の傑作です。チームの皆様、参加者の皆様、ジャッジの皆様、本当にありがとうございました。
流体力学 on Paraiso が かんせいした！
見よ！流体力学ソルバーのParaiso実装を！
cell2 <- proceedSingle 1 (dt/2) dR cell cell -- まず時間1次精度でdt/2だけ進めておいて、 cell3 <- proceedSingle 2 dt dR cell2 cell -- それを使ってもとの量をdtだけ進める。
ありのままの姿で書かかれた２次のルンゲ・クッタ法を！
interpolate order i cell = do let shifti n = shift $ compose (\j -> if i==j then n else 0) -- i軸方向、nマスの平行移動を定義 a0 <- mapM (bind . shifti ( 2)) cell -- 2マス平行移動を全ての変数に適用、 a1 <- mapM (bind . shifti ( 1)) cell -- 1マス平行移動を全ての変数に適用、 a2 <- mapM (bind . shifti ( 0)) cell -- 0マス平行移動を全ての変数に適用、 a3 <- mapM (bind . shifti (-1)) cell -- -1マス平行移動を全ての変数に適用、 intp <- sequence $ interpolateSingle order <$> a0 <*> a1 <*> a2 <*> a3 -- 各自由度ごとに補完関数を適用。
TraversableとApplicativeを使って一般的に書かれた空間補完を！
let timescale i = dR!i / (soundSpeed cell + abs (velocity cell !i)) -- 各マスごと、各方向ごと、にタイムステップの上限が決まるので、 dts <- bind $ foldl1 min $ compose timescale -- まず各マスの中で方向ごとのminを取る。 dtG <- bind $ cflG * reduce Reduce.Min dts -- さらに全マス上のグローバルなminを取る。 dt <- bind $ broadcast dtG -- 求まった最小のタイムステップをブロードキャスト。
抽象的なreduceとbroadcastで書かれたこれ実装の大変さや計算時間なんてまったく考えてないだろっていうタイムステップ上限の計算を！
lesta <- starState shockStar shockLeft left -- 左の元状態left から衝撃波後の状態lestaを rista <- starState shockStar shockRight right -- 右の元状態rightから衝撃波後の状態ristaを求め let selector a b c d = -- セレクタを定義し select (0 `lt` shockLeft) a $ select (0 `lt` shockStar) b $ select (0 `lt` shockRight) c d mapM bind $ selector <$> left <*> lesta <*> rista <*> right -- ４つのうちのどれかを選ぶ。
流体の全自由度をひとまとめに扱って(ここではleft, lesta, rista, right)記述された計算や分岐の数々を！
いや、正直同じ条件の分岐を複数生成するのはどうにかしたいのですが・・・
次元の数*1、流体の自由度の数、空間の補完、時間積分の次数、リーマンソルバーの実装などの部品がほぼ直交的に書けてしまう。ある部分を実装するときは関係ない部分は意識しないですむ、書いてしまえば他の部分で何を選ぼうと組み合わせられる、という感じなのでとても楽しいです。これに対して出てくるコードはいまのところ同じ計算を何度もするようなぶよぶよのコードなので、大いに改善の余地ありです。
実装について
たぶん以下のようにするとサンプルがうごくはず
git clone https://github.com/nushio3/Paraiso.git cd Paraiso/ cabal configure cabal install cd examples/Hydro/ make lib #環境にもよりますが make #数分かかるかも ./kh.out
Builder
ざっくり説明しますと、まずLanguage.Paraiso.OM.BuilderにいるBuilderモナドというやつが、いわゆるフロントエンド担当です。抽象構文木を構築します。こいつの正体は、構築中のデータフローグラフ＋αを持ったStateモナドです。
type Builder vector gauge val = State (BuilderState vector gauge) val
Builderモナドはいくつかの予約語(load, store, imm, reduce, broadcast, shift, loadIndex)の入出力に現れるほか、Additive, Ring, Fieldなど型クラスのインスタンスになって各種の演算子を取り揃えています。Builderモナド同士を演算すると、
- 引数のBuilderモナドをまず実行してデータフローグラフの入り口となるノードを作って返させ、
- そこからエッジを出し、演算を行うノードを新しく追加し、
- 演算結果を表すノードを作って返す
という処理を行うモナドになるので、Buiderモナドで作った複雑な数式をrunするとあら不思議、その数式を計算するデータフローグラフがひとりでに組み上がるというしくみです。
このグラフはOrthotope-Machine(OM)という仮想マシンのレジスタを操作するもので、OMのレジスタは要素の型(Int, Float, Double, ...)と、配列変数なのかただの変数なのか、程度の区別があります。レジスタの表現として、Valueという、レジスタの型や大きさの情報を型として持っているデータ型と、DynValueという、型や大きさの情報を値レベルに落として持っているデータ型があります。Builderモナドが内部で組み立てるグラフの頂点は単一の型を持たないといけないのでDynValueを使います。ただしBuilderモナドが受け付けたり返したりするのは常にValueなので、Builderモナドを使う限り、うっかり型がおかしい演算を組み立てたりはしないようになっています。
Generator
一方、バックエンド担当はBinderモナドです。こいつはexposeすらされてない闇のモナドです。
type Binder v g a = State (BinderState v g) a
Binderも基本構造だけはシンプルで
addBinding cursor = do ... lhs <- leftHandSide cursor ... rhs <- rightHandSide preCursor bindingModify $ Map.insert cursor (lhs ++ " = " ++ rhs ++ ";") leftHandSide = cursorToSymbol LeftHand rightHandSide cur = do ... when (allocStrategy (getA node0) == Alloc.Delayed) $ addBinding cur cursorToSymbol RightHand cur
addBindingはleftHandSideにrightHandSideを代入するコードを生成し、rightHandSideは自分の値を計算してくれるようなaddBindingを呼び出し・・・という仕組みで再帰的にコードを生成します。そこかしこで直接文字列をいじってCのコードを吐いているので気持ち悪いです。文字列じゃなくてCの構文木を組み立てるような形にしたいもんですが、なんか良いライブラリないですかね。
最適化部
そんなものはない
一応必要なとこしかコード生成しないので、dead code eliminationだけは入ってると言えなくもないです。もとのアルゴリズムの並列性をそこなわない形でグラフにもつことには成功したわけで、こっからががんばりどころです！
*1:いま公開してる版は微妙に手を抜いて次元依存の部分がありますがその気になれば完全に消しちゃえるはず
Arch Linux
継ぎ目すら無い美しいローリングアップデートで評判のArch Linuxを主力採用してみようかと思うが、アーチの本ってなんかあるんだろうか。ぱっと見つかったのは
Arch Linux Handbook 2.0: A Simple, Lightweight Handbook
- 作者: Dusty Phillips
- 出版社/メーカー: Createspace
- 発売日: 2010/10/13
- メディア: ペーパーバック
- クリック: 34回
- この商品を含むブログ (1件) を見る
まあ、wikiが充実してるからいいのかな。
Paraisoうごきはじめた
Paraisoでとにかく何か動いているように見えるものが生成できるようになりました。
https://github.com/nushio3/Paraiso/
遊び方はREADMEに書いてあります。ライフゲームのルールを記述したソースはこれで、本質的なとこだけ抜き出すと
adjVecs :: [Vec2 Int] adjVecs = zipWith (\x y -> Vec :~ x :~ y) [-1, 0, 1,-1, 1,-1, 0, 1] [-1,-1,-1, 0, 0, 1, 1, 1] buildProceed :: Builder Vec2 Int () buildProceed = do cell <- bind $ load Rlm.TLocal (undefined::Int) $ Name "cell" neighbours <- fmap (map return) $ forM adjVecs (\v -> shift v cell) num <- bind $ foldl1 (+) neighbours isAlive <- bind $ (cell `eq` 0) && (num `eq` 3) || (cell `eq` 1) && (num `ge` 2) && (num `le` 3) store (Name "cell") $ select isAlive (1::BuilderOf Rlm.TLocal Int) 0
です。おぼろげに、adjVectsでずらして、足し算して、おなじみの生存判定をして、結果を返してることが分かると思います。あと、所々明示的に型を書かないといけないのが残念です。
残念ながら、今は未実装の部分もあり、強烈な見落とし（グラフのエッジの順番って保存されない・・・）があったのをadhocに誤魔化した所あり、そもそもあんまり大したコードは生成できず、Cのコードを生成してる部分はgdgdで、GPUとかMPI対応もまだまだこれからです。そもそも上のコードだってbindとかsequenceAとかfmapとかforMを適切に挟まないと動かないので使えたもんじゃなくて、QQでもっと手軽にしたいところです。自慢できるところがあるとすれば任意のn次元配列に対応してるところとか(THとか使わずに)、中間表現の１行ごとにメモリに置くか計算して済ますか選べるのでこう見えて指数関数的パターン数のコードが生成可能で、自動最適化への道がわずかに開きかかっていることぐらいでしょうか。
が、今までにないアプローチで多次元配列を操作するコードが生成できたということを今日は記念したいと思います。
