大洗に行ってきたよ
はるアイコン鯖 Advent Calendar 2014 - Adventar
※現実で。
※現実で。
※現実で。
海岸
大洗磯前神社入口
絵馬
痛絵馬は西側に偏っている模様。
神社から見える水平線
石が置かれまくっている像
大洗駅内にて
大洗を3つの言葉で表すとすれば、「海」「レンガ」「ガールズ&パンツァー」だ。
この経験を生かし、はるアイコン鯖の大洗にレンガの建物をもっと増やし、ついでに石を置かれまくっている像も作りたい。
はるアイコン鯖の鳥取に製鉄プラントを作る計画が進行中ですが、最近忙しくてインできていないです。すみません…
関数型プログラミングとオブジェクト指向の抜き差し可能な関係について整理して考える
Googleで適当に検索すると
とズラリと出てくる。
関数型とオブジェクト指向という一見相反するプログラミングパラダイムの併用について理解した
プログラマが知るべき97のこと/関数型プログラミングを学ぶことの重要性
新人プログラマに知っておいてもらいたい人類がオブジェクト指向を手に入れるまでの軌跡
関数型プログラミングとオブジェクト指向の抜き差しならない関係について整理して考える
とそれなりに参考になりそうな情報はあるものの、無駄に複雑化されたオブジェクト指向をストローマンにするような記事ばかり(それだけ今までのオブジェクト指向にみんなうんざりさせられているのだろう)で、そろそろきちんと自分自身「関数型プログラミングとオブジェクト指向の切り離され方」についてはっきりさせておきたい、と考え、概念整理した結論を書きます。
まず端的な結論
結論を端的に言うと、
ストリーム変換器 + 手続きの自然変換*1 ⇔ オブジェクト指向
の関係になっている。
「関数型プログラミングとオブジェクト指向を臨機応変に併用する」
だとか、
「関数型プログラミングとオブジェクト指向のマルチパラダイムである」
とすると、今まで見えていなかった部分で概念の重複が起こり、いろいろややこしいことになる、理解においても実践においても混乱を招く、実際混乱を招いている、ということになります。
関数そのものから考える
茶番はここまで。ある純粋な関数fを考えてみよう。:の左は識別子名、右は型シグネチャである。
f : A → B
fは具体的な型Aの値を受け取り、Bを返す。fは純粋なので、いつ値を渡そうと、日本の首都が鳥取になろうと、同じ値を渡せば同じ値が返ってくる。
ところが実用上は、今までに受け取った値に応じて今後の動作を変えたい場面が多々ある。パーサーやWebアプリケーションなどがその例だ(Aに文字やリクエスト、Bにデータやレスポンスが入る)。それを表現するにはどうすればよいだろうか？Bだけではなく、「次のわたし」も一緒に返せばよいのだ。
data TransAB where
TransAB : (A → (B, TransAB)) → TransAB
runTransAB : TransAB → A → (B, TransAB)
このように、入力によって出力と次の状態が決まる概念をミーリマシン(mealy machine)と呼ぶ。
「次のわたしがある」という制約によって、関数の表現力が増したのだ。
さて、HaskellやPureScriptなどの一部の言語では、手続きそのものをデータ構造として扱うことが一般的に行われている。ある程度の型の表現力があれば、手続きと、手続きの間の関数も定義できる。
もっとも簡単な手続きを定義してみよう。
data Yo x where
Yo : Yo Result
見たとおり、Yoしかないので、Yoを超えることはできない。「Yoの結果に対して演算を行う」はできず、「Yoを2回」ももちろん無理。ましてや「前のYoが成功したらYoしない」など夢のまた夢だ。
これをなんとかするために、「モナド」という概念が作られた。下のようにYoの機能を増やすと、前のYoに依存したYoが可能になる。PureとBindの導入については、モナドとはモナドであるも参照されたい。
data Yo x where
Pure : a → Yo a
Bind : Yo a → (a → Yo b) → Yo b
Yo : Yo Result
Yoを具体的な動作に変換する、Haskellに非常に近い言語による実装を示した。
runYo : ∀ x. Yo x → IO x runYo Yo = do print "Yo" return Success runYo (Pure a) = return a runYo (Bind m k) = runYo m >>= runYo . k
手続きの変換を言葉で表すと「手続きの結果が何であっても、中身の構造を保つ関数」となる。最初に扱った純粋な関数と比べると、任意の結果に対応しなければならない分、より表現力が強い。圏論ではこういった変換を自然変換(natural transformation)と呼ぶ。ただ、runYoは純粋なので、いつYoを変換しても、具体的に行われる内容は変わらない。
ここまで紹介した、2種類の関数の発展を地図に描いてみよう。
変換器を「手続きへの適用」方向に伸ばし、自然変換を「状態依存」方向に伸ばした先に宝物がある気がしてこないだろうか？
変換器の領域を緩やかに進んでいた私に、「取舵一杯」となにかが告げた。そして、突如としてそれは姿を現した(表記の統一のために一般化された代数的データ型(GADT)を用いたが、実装に必須ではない)。
data Treasure m n where
Treasure : (∀ x. m x → n (x, Treasure m n)) → Treasure m n
runTreasure : Treasure m n → m x → n (x, Treasure m n)
ある手続きを受け取ると、その結果と次の状態を返す手続きを生み出す。初めて目にするが、とてもわかりやすい、不思議な感覚。
とりあえず、ミュータブルな変数を作ってみよう。
data Identity x where
Identity : a → Identity a
data GetSet s x where
Get : GetSet s s
Set : s → GetSet s ()
variable : s → Treasure (GetSet s) Identity
variable s = Treasure (handle s)
handle :: s → GetSet s a → Identity (a, Treasure (GetSet s) Identity)
handle s Get = Identity (s, variable s)
handle s (Set s') = Identity ((), variable s')
状態を保持する能力を確認できた。次に、この概念が関数のような性質を持つか確かめてみた。まず、恒等関数相当。
echo : Functor m ⇒ Treasure m m echo = Treasure (map (λx → (x, echo)))
(Haskellの場合、mapはfmapと読み替えてほしい)
続いて、合成。$はみんな大好き関数適用演算子(f x $ g y = f x (g y))。
(>>>) : Functor n ⇒ Treasure l m → Treasure m n → Treasure l n
Treasure m >>> Treasure n = Treasure $ λe → map
(λ((x, m'), n') → (x, m' >>> n'))
(n (m e))
確かに関数のようにふるまうようだ。
この構造は私に既視感を感じさせたが、その正体がわかった。OOPにおけるオブジェクトのようにふるまうのだ。
オブジェクトは内部状態を持ち、呼ばれたメソッドに応じて、必要があれば内部状態を更新し、副作用を引き起こす――ちょうど、手続きの変換とミーリマシンの両方の性質を持っている。
result = obj.Foo(x, y)
をこのやり方で解釈すると、
(result, obj') ← runTreasure obj (Foo x y)
という表現になる。
共通する性質は、「メソッドレベルの『手続き』を、実装レベルの『手続き』に変換」しつつ、「自分の状態を更新」するという点だ。
TreasureをObjectに改名して、典型的なOOPとの対応をまとめてみよう。
| 典型的OOP | 関数型OOP |
|---|---|
| プログラム | IO型の値 |
| クラス | Object M IO型の値の定義 |
| インスタンス | Object M IO型の参照*2 |
| コンストラクタ | Object M IOを生成する関数 |
| インターフェース | M |
| メソッド | M型の値 |
| フィールド | get : M sとset : s → M ()の存在 |
| 継承 | Object M' Mとの合成 |
| オーバーライド | Object M' Mの実装の一例 |
| 菱形継承 | メソッドへのパターンマッチ |
| ダックタイピング | 存在量化 |
| カプセル化 | メソッド以外のアクセス手段なし |
| This | 不要 |
| 不可能 | IOを制限されたクラス(Object M Limited) |
| 不可能 | クラスの実装そのものへの操作((>>>t)) |
オブジェクト指向の仕組みが、たった一つの型の特殊な場合として表現できるのは、なかなか魅力的ではないだろうか。
応用
さっそく、ObjectのHaskellによる実装を作った。Object型に加え、Objectのインスタンスとして利用するためのユーティリティ関数も備えている。
現在、callというゲームエンジンへの応用を試みている。リンク先のコードのように、いかにもオブジェクト指向らしい記述を実際に可能にしている。
結論
オブジェクト指向は、関数型プログラミングと相容れない何かではなく、実装するものだ。
元ネタ
Haskellでオブジェクト指向を再発明する
状態管理のモデル案: spawn/killモデルの実装を作ってみた。
worldsパッケージがそれだ(露骨な名前だが赦してほしい)。前の記事と違う点は、Worldがモナド変換子として実装されている点だけである。
worlds-exampleは画面内のキャラクターを方向キーで操作する例。メインのプログラムは以下のようになっている:
import Include import Types import qualified Entity.Player as Player import Assets main = runGameDefault $ runWorldT $ do player <- spawn $ Player.new (V2 240 240) forever $ do whenM (lift $ keyPress KeyLeft) $ player .! Player.Move L whenM (lift $ keyPress KeyRight) $ player .! Player.Move R whenM (lift $ keyPress KeyDown) $ player .! Player.Move D whenM (lift $ keyPress KeyUp) $ player .! Player.Move U player .! update lift tick
見ての通り、Player内部の状態には直接関与しない。一方、Playerの実装では、mainから受け取ったメッセージを解釈し、実際の動作と状態遷移に変換する。
{-# LANGUAGE GADTs #-} {-# LANGUAGE Rank2Types #-} {-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE FlexibleContexts #-} module Entity.Player where import Include import Types import Assets data States = States { _hp :: Float , _position :: Vec2 , _direction :: Direction , _animation :: Int } makeLenses ''States data Actions x where GetCoord :: Actions Vec2 Update :: Actions () Move :: Direction -> Actions () instance Updatable Actions where update = Update type Player s = Life (WorldT s Game) Actions () -- 命令を受け取る部分 handle :: (MonadState States m, FreeGame m) => Actions a -> m a handle GetCoord = use position handle Update = do d <- use direction n <- use animation p <- use position translate p $ bitmap $ playerBitmap (n `div` 5) d handle (Move d) = do case d of L -> position -= V2 2 0 R -> position += V2 2 0 U -> position -= V2 0 2 D -> position += V2 0 2 direction .= d animation += 1 life :: States -> Player s life s = Alive $ \e -> do (a, s') <- lift $ runStateT (handle e) s return (a, life s') new :: Vec2 -> Player s new p = life $ States { _hp = 8 , _position = p , _direction = R , _animation = 0 }
これはまさにカプセル化とメッセージパッシングであり、オブジェクト指向の実装であると言える。従来のオブジェクト指向と違う点は、インスタンス、メソッドなどの仕組み全てがファーストクラスであり、カスタマイズすることができることである。たとえば、メソッドをモナドにするのは、Operationalモナドを使えば高々2行の変更で可能だろう。
ゲーム開発などにおいてこのアプローチがどう使えるか、これからも調べていきたい。
追記
ドッペルゲンガーを作ってみた。インスタンスは霊本体と操作するクローンに分かれている。
haunt :: (Monad m, FreeGame m) => Name s Player.Actions r -> Life (WorldT s m) Identity () haunt she = go R where go d = Alive $ \(Identity pass) -> do r <- lift $ randomness (0 :: Int, 59) she .! Player.Move d if r == 0 then do i <- lift $ randomness (0, 3) return (pass, go (directions !! i)) else return (pass, go d) main = runGameDefault $ runWorldT $ do player <- spawn $ Player.new (V2 240 240) playerClone <- spawn $ Player.new (V2 320 240) doppelganger <- spawn $ haunt playerClone forever $ do whenM (lift $ keyPress KeyLeft) $ player .! Player.Move L whenM (lift $ keyPress KeyRight) $ player .! Player.Move R whenM (lift $ keyPress KeyDown) $ player .! Player.Move D whenM (lift $ keyPress KeyUp) $ player .! Player.Move U player .! update playerClone .! update doppelganger .! return () lift tick
状態管理のモデル案: spawn/killモデル
生と死のあるアクターを表現するためのモデルについて考えた(あくまで個人用メモ)。
以下の型変数sは世界の一意性、閉鎖性を表す。生命や名前を勝手に外に持ち出すことを防ぐために必要。
Life m a: 生命を表す型。aは生命の最終結果。Name s a: 生命に与えられた一意な名前。World s: 生命が住む世界を表すモナドで、以下の操作が可能。
spawn :: Life (World s) a -> World s (Name s a) -- 同じ世界に新しい生命を出現させる kill :: Name s a -> a -> World s () -- 同じ世界の生命を殺害する
world :: (forall s. World s a) -> Life Identity a
worldは中で起きた生と死を管理し、その過程をある種の命として表す。
これだけでは文字通り何もできないので、生命の間でコミュニケーションする何かが必要。
時間の概念をどのようにして表現するかも考えなければいけない。
(追記)アプローチ
生命自身の動作を表す新たな型変数eを追加する。
spawn :: Life (World s) e r -> World s (Name s e r) kill :: Name s e r -> r -> World s () contact :: Name s e r -> e a -> World s a
eはOperationalモナドやextensible effectsなどを使うことが想定される。
本日の料理: ヤングコーン、ピーマン、豚肉の炒め物
食材と処理
- にんにく1かけをみじん切りにする。
- ピーマンの実を適度な大きさに分割する。
- ヤングコーン(水煮)を小穂に対し斜めに切断する。
- 豚の細切れ肉を用意する。
調理
- フライパンを中火で熱する。
- フライパンにごま油を適量入れる。
- にんにくを入れて香りを引き出す。
- ピーマン、ヤングコーン、豚の細切れ肉の順に、間隔をおいて投入する。
- 食材に多少焦げ目がつくのを待つ。
- 中華スープの素を少量加える。
- 醤油を回しかける。
- 十数秒後、加熱を止めて完成。
Karakuriの導入(0) -状態をぶった切る！-
あるとき、私は思った――
「Getter、Setterと、状態を次に進める関数を持つ何かがほしい！そうすればゲームやユーザーインターフェイスなどがとても書きやすくなるのに……！」
私はそれをカラクリと名付けた。存在するかどうかわからない理想の構造を求めて…
オブジェクトの型をKとしよう。型A, Bに対するGetterが存在するならば、以下の関数が存在することになる。
getA :: K -> A getB :: K -> B
ここで積の性質を思い出そう。K -> (A, B)があればgetA、getBは自明だ。つまり、Getterは一つで十分ということになる。次に、X, YのSetterを考えよう。
setX :: X -> K -> K setY :: Y -> K -> K
和の性質により、Either X Y -> K -> Kが存在すれば、setX, setYの定義は自明になるので、Setterも一つで十分だ。そして、状態を更新する関数はK -> m Kとなる。それらを一つの型に詰め込むことでKarakuriが完成する。
data Karakuri m a b = Karakuri { look :: b , feed :: a -> Karakuri m a b , step :: m (Karakuri m a b) }
Karakuriはムーアマシンに相当し、lookは出力を取り出す関数、feedとstepは状態遷移にあたる。
KarakuriはApplicativeになるが、その仕組みはとても簡単だ。pure aはaを出すKarakuriになり、fを出力するKarakuriと、aを出力するKarakuriを(<*>)で合成するとf aを出力するKarakuriになる。
このKarakuriを使えば、状態が隠蔽されているが、一部分だけ制御できるオブジェクトが作れるのだ。次回はこれをもっと簡単に扱うためのモナドを導入してみよう。
継続渡しなHaskellライフ
CPS(Continuation passing style, 継続渡しスタイル)は、関数型プログラミングにおけるプログラムの書き方の一つである。CPSを導入する簡単な例をいくつか紹介しよう。
まず、入力された数値が3の倍数かどうかを判定するプログラムを作ってみよう。
foo :: IO Bool foo = do n <- readLn :: IO Int return (n `mod` 3 == 0)
ここで「CPS変換」なる儀式を行うと…こうなる！
foo' :: (Bool -> IO r) -> IO r foo' cont = do n <- readLn :: IO Int cont (n `mod` 3 == 0)
「なにこれ、returnを置き換えただけじゃねえか！意味わかんねー！」という声が聞こえてきそうだが、もう少し考えてみよう。
3の倍数が入力されたらFizz、5の倍数が入力されたらBuzz、15の倍数はFizzBuzz、それ以外は元の数を返すようなプログラムは、普通に考えればこのようになる。
bar :: IO (Either Int String) bar = do n <- readLn :: IO Int case (n `mod` 3, n `mod` 5) of (0, 0) -> return $ Right "FizzBuzz" (0, _) -> return $ Right "Fizz" (_, 0) -> return $ Right "Buzz" _ -> return $ Left n
barの結果はパターンマッチによって分岐することができるが、あることに気づくかもしれない。そう、条件分岐の結果を一旦代数的データ型に押し込み、それに対してさらに条件分岐を行おうとしているのだ……
さて、barをCPS変換するとこうなる。
bar' :: (Int -> IO r) -> (String -> IO r) -> IO r bar' left right = do n <- readLn :: IO Int case (n `mod` 3, n `mod` 5) of (0, 0) -> right "FizzBuzz" (0, _) -> right "Fizz" (_, 0) -> right "Buzz" _ -> left n
bar'の結果について分岐するには、Intが返ってきた場合の処理、Stringが返ってきた場合の処理をそれぞれ直接渡せばいいので、パターンマッチは不要だ。
打って変わって、今度はfooを4で割った商も一緒に返すように変更してみよう。
baz :: IO (Bool, Int) baz = do n <- readLn :: IO Int return (n `mod` 3 == 0, n `div` 4)
bazの結果であるタプルをBoolとIntに分解するには、やはりパターンマッチしなければいけない。そこでbazをCPS変換するとこのようになる。
baz' :: (Bool -> Int -> IO r) -> IO r baz' cont = do n <- readLn :: IO Int cont (n `mod` 3 == 0) (n `div` 4)
こちらは関数にBoolの値とIntの値が別々に渡されるので、タプルもパターンマッチも使う必要はない。
つまり、継続渡しスタイルを使うと計算の結果を代数的データ型を介さずに受け渡しできるのだ！そのメリットは明らかである。
CPSはattoparsecなどの様々なライブラリで利用されている。Haskellのプログラムを高速化したいならば、ぜひCPS変換することを検討してみてほしい。
