Freeモナドを超えた!?operationalモナドを使ってみよう
限定版IOみたいなモナドを簡単に作れたら、コードが分離できるしテストもしやすくなるのになあ…
数か月前なら、
と返されるだろう。だが今は違う。Freeモナドよりも簡単にモナドを作れるモナド、Operationalモナドがあるのだ。
Freeモナドについて復習しよう。FreeモナドはFunctorを基にMonadを作れる構造であり、Functorで自分自身を包むことによってモナドの力を得ている*2。FunctorそのものはDeriveFunctor拡張を使って簡単に作れる。
{-# LANGUAGE DeriveFunctor #-} import Control.Monad.Free data CharIO a = PutCh Char a | GetCh (Char -> a) | LiftIO (IO a) deriving Functor putCh ch = wrap $ PutCh ch (return ()) getCh = wrap $ GetCh return liftIO = wrap . LiftIO . fmap return
CharIOを標準入出力上で動かす場合は以下のようになる。
type MyIO = Free CharIO runCharIO :: Free CharIO a -> IO a runCharIO (Free (PutCh ch cont)) = putChar ch >> runCharIO cont runCharIO (Free (PutCh cont)) = getChar >>= runCharIO . cont runCharIO (Free (LiftIO m)) = m >>= cont runCharIO (Pure a) = return a
チャーチエンコード(Boehm-Berarducciエンコード?)されたバージョンはより高速に動作する。
import Control.Monad import Control.Monad.Free.Church type MyIO = F CharIO runCharIO :: MyIO a -> IO a runCharIO m_ = runF m_ return w where w (PutCh ch cont) = putChar ch >> cont w (GetCh cont) = getChar ch >>= cont w (LiftIO m) = join m
ここからが本題
ところが、Operationalモナドはより簡単にモナドを構成できる。ここでは、実装の一つであるfree-operationalパッケージを使う。
{-# LANGUAGE GADTs #-} import Control.Monad.Operational.Simple -- 必要なアクションの型を並べる data CharIO x where GetCh :: CharIO Char PutCh :: Char -> CharIO () LiftIO :: IO a -> CharIO a type MyIO = Program CharIO getCh :: Program CharIO Char getCh = singleton GetCh putCh :: Char -> Program CharIO () putCh = singleton . PutCh liftIO :: IO a -> Program CharIO a liftIO = singleton . LiftIO
驚くべきことに、Functorすら使わずにモナドを作れる。しかも、他のモナドに変換するのも非常に簡単だ。
runCharIO :: MyIO a -> IO a runCharIO = interpret advent where advent GetCh = getChar advent (PutCh ch) = putChar ch advent (LiftIO m) = m
なぜこんなことができるのか――そこには、Coyoneda*3と呼ばれるFunctorの力が隠されていた。
{-# LANGUAGE GADTs, Rank2Types #-} data Coyoneda t x where Coyoneda :: t r -> (r -> a) -> Coyoneda t a instance Functor (Coyoneda t) where fmap f (Coyoneda t g) = Coyoneda t (f . g) liftCoyoneda :: t a -> Coyoneda t a liftCoyoneda t = Coyoneda t id
なんとこのCoyonedaは、ただのデータ型からFunctorを生み出せるのだ!!
Operationalモナド(上の例ではProgram)は、本質的には以下のようになっている。
type Program t = Free (Coyoneda t)
何もないところからFunctorが作れて、FunctorがあればMonadが作れる――したがって何もないところからMonadを作れる、という理屈だ。
それは、元の構造をアクションに変形するsingleton関数によって表現できる。
-- liftCoyoneda :: t a -> Yoneda t a -- liftF :: Functor f => f a -> Free f a singleton :: t a -> Program t a singleton = liftF . liftCoyoneda
あとはinterpretを定義すれば、adventのような関数を与えるだけで動かせる。
interpret :: Monad m => (forall x. instr x -> m x) -> Program instr a -> m a interpret eval (Free (Coyoneda t f)) = eval t >>= interpret eval . f interpret _ (Pure a) = return a
欲しいアクションの型を並べれば、freeなモナドが手に入る。
じゃあいつ使うか?
今でしょ!
追記: minioperationalという、シンプルかつ高速なOperationalモナドの実装を作ったのでぜひ使ってみてほしい。
Indexed Monadの世界
もっと、モナドの力を引き出したくはないか?
え?アクションの前後で型を変えたい?いやいやいや、モナドは自己関手の圏上の単なるモノイドだよ、そんなことができ…る…!?えっ、できるの…マジで…?
できる。そう、Haskellならね。
{-# LANGUAGE QuasiQuotes #-} import Control.Monad.Indexed.State import Control.Monad.Indexed import Language.Haskell.IndexedDo hoge :: IxState Int [Int] () hoge = [ido|do imodify (*10) imodify show imodify reverse imodify (++"123") imodify $ map fromEnum |]
*ghci> runIxState hoge 42
((),[48,50,52,49,50,51])
明らかに、計算の途中で型が変わっている! 勿論、型さえ合えばループや条件分岐を使うこともできる。
この何やら恐ろしいモナドのようなものが一体どういう仕組みになっているのか、じっくり調べてみよう。
IxStateの定義はこうだ。
newtype IxState i j a = IxState { runIxState :: i -> (a, j) }
Stateモナドのような形をしているが、これは状態の型が変わるため、Monadのインスタンスにはできない。ならば…より多くの制約を持ったモナドを作ればよい。
class IxMonad m where -- indexedパッケージで提供されているクラスとは多少異なるので注意 ireturn :: a -> m i i a ibind :: (a -> m j k b) -> m i j a -> m i k b
このiやjといったパラメータ(添字)によって、アクションが正しく合成されるということが保証できる。これがIndexed monadである。
すると、IxStateをそのインスタンスにできる。
instance IxMonad IxState where ireturn a = IxState $ \s -> (a, s) ibind f m = IxState $ \s -> let (a,s') = runIxState m s in runIxState (f a) s'
しかし、足りないものがある。そう…do記法だ。Indexed monadの力をフルに使うために、indexed-do-notationというパッケージを作った。これは、普通のdo記法とまったく同じようにindexed monadを扱うことができる。使うには、普通のdo記法を[ido|…|]で包めばよい(QuasiQuotes拡張を有効にする必要がある)。
こうして我々は、モナドを超えるモナド、インデックスド・モナドを手に入れたのだ。
Free indexed monad
モナドに対してFreeモナドがあるように、インデックス付きモナドにもインデックス付きFreeモナドがある。早速作ってみよう。
{-# LANGUAGE GADTs #-} data IxFree f i j x where Pure a :: a -> IxFree i i a Free :: f i j (IxFree f j k a) -> IxFree f i k a
パラメータが増えた点を除けば普通のFreeモナドと変わらない。それは実装も同じだ。
instance IxFunctor f => IxMonad (IxFree f) where ireturn = Pure ibind k (Pure a) = k a ibind k (Free f) = Free $ imap (ibind k) f
IxFunctorはFunctorのindexed版。fmapの代わりに、添字の関係を保存しつつ中身だけを変えるimapが定義されている。
class IxFunctor f where imap :: (a -> b) -> f i j a -> f i j b
そして、IxFreeは、IxFunctorによってIxMonadを生成できるのだ。
このIxFreeを使って、Coqのタクティクスのようなものを作ってみよう。ゴールの書き換えが添え字の変化に対応している。
{-# LANGUAGE QuasiQuotes, GADTs #-} import Control.Monad.Indexed -- indexed import Control.Monad.Indexed.Free -- indexed-free import Language.Haskell.IndexedDo -- indexed-do-notation import Control.Applicative import Data.Void -- void data Proof i j x where Intro :: (p -> a) -> Proof (p -> q) q a Apply :: (p -> q) -> a -> Proof q p a instance IxFunctor Proof where imap f (Intro g) = Intro (f . g) imap f (Apply e a) = Apply e (f a) intro :: IxFree Proof (a -> b) b a intro = Free $ Intro ireturn apply :: (a -> b) -> IxFree Proof b a () apply p = Free $ Apply p (ireturn ()) exact :: a -> IxFree Proof a b () exact p = Free $ Apply (const p) (ireturn ())
以下のように証明が書ける。当然、証明が間違っていると型エラーになる(ここ重要)。
ex0 :: IxFree Proof ((a -> b) -> (b -> c) -> a -> c) () () ex0 = [ido|do ab <- intro bc <- intro a <- intro apply bc apply ab exact a |] ex1 :: IxFree Proof ((Either a b -> Void) -> (a -> Void, b -> Void)) () () ex1 = [ido|do e <- intro exact (e . Left, e . Right) |] ex1' :: IxFree Proof ((a -> Void, b -> Void) -> (Either a b -> Void)) () () ex1' = [ido|do (ha, hb) <- intro e <- intro case e of Left a -> exact $ ha a Right b -> exact $ hb b |]
驚くべきことに、この証明から実際のHaskellのプログラムを作ることも可能だ。
runProof :: Show r => IxFree Proof a b r -> a runProof (Pure r) = error $ "Unexpected end of proof" ++ show r runProof (Free (Intro f)) = runProof . f runProof (Free (Apply a cont)) = a (runProof cont)
*ghci> :type runProof ex0
runProof ex0 :: (a -> b) -> (b -> c) -> a -> c
*ghci> runProof ex0 (+11) (*3) 11
66
いやはや、indexed monad恐るべし…
オレはようやくのぼりはじめたばかりだからな このはてしなく遠いモナド坂をよ…
8つの質問で、Lazy K業界の現状を知る
Lazy系の会社の隆盛があって、仕様が定められたのが8年ぐらい前だろうか。 コンビネータ産業の人材動向が、今どうなってるかって?
大方の予想より凄惨ですよ。
それが分かる方法がある。Lazy K技術者に技術力を問う8つの質問によってだ。
Lazy K業界のエンジニアの平均レベルを知りたくって、いろんな会社さんのLazy K開発者(経験者)向けに以下のようなつ8の質問をしていない。
その8つの質問というのはこんな問題だ。
Lazy K技術者に技術力を問う8の質問
- ラムダ抽象ではなくコンビネータで表現するメリットを一言で表してください。(筆記回答)
- 入出力の終端を表現する方法は何ですか?(筆記回答)
- チャーチエンコーディングとスコットエンコーディングの違いを端的に説明してください。(筆記回答)
- 任意の関数に対して不動点を求めるコードはどれですか?(選択回答)
S I I (S (S (K S) K)) I
S S K (S (K (S S (S (S S K)))) K)
((S (K S) K) (K (S I I))) ((S (K S) K) (K (S I I)))
S I I (S (K (S S (S (S S K)))) K)
- Lazy Kのプログラムにおいて、いきなりスタックがあふれる不具合が発生しました。原因として何が考えられますか?(筆記回答)
- 与えられたタプルやリストに対してcarとcdrをそれぞれ適用するのはなぜNGなのかメカニズムを説明してください。
- 与えられたチャーチ数の階乗を求める関数をSとKとIの組み合わせで書いてください。
- JavaScriptでHTML要素をid属性の指定により取得するメソッドは何ですか?(筆記解答)
過去に実施した平均点
この8問について、私が出会ったエンジニアに解答してもらった平均正解数は、 なんと8点満点中SII(SII)である。
内訳的な話
うろ覚えになってしまってるだろうから満点は無理でも、ちゃんとLazy Kをやってるエンジニアさんであれば4問は解けるだろう。筆記解答については相当甘くつけるから尚更だ。例えば、1問目「コンビネータのメリット」は、「簡約が確実かつ簡単」ならニジュウマルだが、「変数名を考える必要がない」でも「シンプルに書ける」でもマルで、それらに類する説明ならちょっと分かりにくくても、なんでも正解にしてる。
スタックあふれの問題は、経験していなかったから知らないから何も言えなくてもまぁいいだろう。 (10年やっててもスタックオーバーフローの込み入ったトラブルを経験しないなんて運がいい人なのだろうか、悪い人なのだろうか) 「getElementById」なんてほとんど白紙解答。不動点コンビネータだって自分で簡約すればわかる話だが、そんな状況である。1、2日目ではなく3-10年生であり、SKIバリバリとの触れ込みなのだ。 設計やチームリードやコミュニケーションを得意としている人ではない。プログラマー対象なんだぜ。 (ウチの会社では平均8点ほどあった。これは基礎教育をやってれば当たり前の点数だろう)
これぞ現在のLazy K業界の実態
でも私は、ここ数年茨城でLazy Kの護符などの錬成をやっていた経験から納得がいく。
基礎教育なしに、1年目0円でラムダ計算→2年目コンビネータ論理→3年目ちょっと型理論 仕事と割り切った中で、フレームワークに乗っ取ったコードを書き続ける→その後10年経過 という流れのキャリアパスを通ってきた人にまったく出会っていない。
そもそも業界が存在しないのが現実ではないか。
淘汰という概念が存在しない業界
統計としては母数が少なすぎる(-∞桁程度)し、母集団を変えれば別の所感が得られるだろう。 しかしながら、ヤバいのは淘汰という概念がそもそもないことだ 特に東京は仕事量がないから、こういうレベルの人でも危機感なく生き残ってしまう。 このところ景気がいいせいもあって、正解数1問だった人もすぐに稼働現場が決まっていないようだ。 こういうエンジニアたちが大勢集まってLazy K開発をするのだ。
結果として、一部の出来る人には余計に負荷がかかるだろうなと思う。
いままで私は楽観主義者だから、
関数型言語は適用簡約産業だったけど、これからは抽象除去産業になっていく。 必然的にコンビネー汰の時代になり、優秀な簡約器が生き残るだろう。 と思っていた。
しかし現実は、もっと凄惨な世界を経て時代が進んでいくようだ。
元ネタ
Freeモナドでゲームを作ろう!第3回: Haskellは手続き型言語
※最新のfree-gameを想定しているので、古いバージョンを使っている方は今すぐアップグレード(cabal update && cabal install free-game)してください。
7週間以上開きましたが、第3回です。ここからはどんどんプログラムを組み上げていきます。
コードが長くなったのでGitHubに上げました。重要な所に絞り、どのようにしてプログラムを組むかを解説していきたいと思います。
当たり判定について(Collision.hs)
説明が面倒なので省略。円、線分、およびそれらの集合同士がどこで衝突しているかを計算することができます。
Prelude Data.Vect Collision> Primitive (Circle 5 (V2 0 0)) `collisions` Primitive (LineSegment (V2 5 0) (V2 (-7) 2)) :: Maybe (V2 Float) Just (V2 (-2.0) 2.0)
世界を作る(Types.hs)
Types.hsでは、世界に存在する物体の型と形状を定義しています。フィールド名が_で始まるような代数的データ型を定義し、makeLensesするというのは前回と変わりませんね。
data Pack = Pack { _packPos :: V2 Float , _packVel :: V2 Float } makeLenses ''Pack packShape :: Getter Pack Fig packShape = packPos . to (Primitive . Circle 15)
前回定義したものに加えて、Getterなるものが出てきていますね。これは文字通りGetterで、Lensの特殊な場合です。to :: (s -> a) -> Getter s a
によって関数からGetterを作ることができます。
また、LensやGetterなどはすべて(.)で合成できます。
(.) :: Lens' a b -> Lens' b c -> Lens' a c
メインの処理(main.hs)
プログラムは世界を状態とするStateモナドで統一しています。mainの処理はこれだけ。
main :: IO (Maybe ()) main = runGame def $ evalStateT gameMain $ (世界の初期状態)
そして、本体であるgameMainも非常にシンプルなものです。
gameMain :: TheGame () gameMain = do addPack $ Pack (V2 320 360) (V2 4 (-3)) forM_ [60,140,220] $ \y -> do addBlock $ Block (V2 60 y) addBlock $ Block (V2 160 y) addBlock $ Block (V2 480 y) addBlock $ Block (V2 580 y) forever $ do updateBar updatePacks updateBlocks tick
そして、lensをふんだんに活用してupdateBar, updatePack, updateBlocksを実装するだけですね。
さりげなくfree-game 0.3.2.3の新機能、loadBitmaps :: FilePath -> Q [Dec]も登場しています。指定したディレクトリ内の画像をすべて読み込んで定義してくれる関数です。
Lensの技
彼には72通りの型があるから、何て呼べばいいのか…
確か、最初に会ったときは…
zoom :: Monad m => Lens' s t -> StateT t m a -> StateT s m a
そう、指定されたフィールド(
Lens' s t
)を状態とするアクションを実行する関数だ。まぁ…いい関数だったよ。
これを使うと、いちいち対象を指定するLensを書かなくて済むので非常に便利です。コンテナのすべての要素に作用するLensであるeachと組み合わせることで、foreachのような処理が簡潔に書けます。
updateBlocks :: TheGame () updateBlocks = zoom (blocks . each) $ use blockPos >>= (`translate` fromBitmap _block_png)
Lensは一見難解ですが、use
, .=
, each
, to
の使い方さえ覚えておけば、あとは手続き型言語の要領で分かりやすいコードを作ることができます。また、以下のような演算子も覚えておくと便利です。
(<~) :: MonadState s m => Lens' s t -> m t -> m () -- l <~ mはm >>= (l .=)と同じ。 (%=) :: MonadState s m => Lens' s t -> (t -> t) -> m () -- 指定した関数を使って更新する。Lens版modify
まとめ
無事それっぽいものができました。勿論、これで終わりではありません!次回からは、ゲームの本質的な部分を記述していきます。
モナド変換子の速さを測ってみる
mtl(実装はtransformers)で提供されているモナド変換子のLazy版とStrict版で、どのくらいパフォーマンスの差が出るか調べてみた。また、私がCPS(継続渡しスタイル)で実装したものとも比較してみた。
比較方法
{-# LANGUAGE FlexibleContexts #-} import Control.Monad.Reader.Class import Control.Monad.Reader as R import Control.Monad.Reader.CPS as RC import Control.Monad.Writer.Lazy as WL import Control.Monad.Writer.Strict as WS import Control.Monad.Writer.CPS as WC import Data.Monoid import Control.Monad.State.Class import Control.Monad.State.Lazy as SL import Control.Monad.State.Strict as SS import Control.Monad.State.CPS as SC askTest :: MonadReader Int m => (m () -> Int -> t) -> t askTest f = f (replicateM_ 10000000 ask) 42 tellTest :: MonadWriter (Sum Int) m => (m () -> t) -> t tellTest f = f (forM_ [1..1000000] $ tell . Sum) getTest :: MonadState Int m => (m () -> Int -> t) -> t getTest f = f (replicateM_ 10000000 get) 42 putTest :: MonadState Int m => (m () -> Int -> t) -> t putTest f = f (forM_ [1..10000000] put) 42 modifyTest :: MonadState Int m => (m () -> Int -> t) -> t modifyTest f = f (replicateM_ 1000000 (modify succ)) 0
のそれぞれの関数で3回時間を測り、もっとも短かったものを結果とする。
結果
Target | Lazy | Strict | CPS |
---|---|---|---|
askTest runReader | 0.90s | 0.84s | |
tellTest runWriter | 1.56s | 1.34s | 1.14s |
getTest runState | 5.58s | 0.70s | 0.41s |
putTest runState | 5.54s | 1.14s | 0.81s |
modifyTest runState | 0.61s | 0.39s | 0.08s |
やはり、StrictのほうがLazyよりも数段速い。だが、CPS版はさらに速い。継続の力、恐るべし…
まとめ
モナドはCPSで実装しよう。
ヘッズのための純粋関数型言語「Lazy SLYR」
ドーモ、変数スレイヤーです。
Brainf*ckめいた派生言語が作られる前に、ニンジャスレイヤーを基にしたニンジャヘッズのための言語「Lazy SLYR」を作ってみた。
◆Brainfuck派生ではない◆ ◆Lazy K派生でもない◆ ◆独自性重点◆ ◆純粋な◆
Hello, world!
イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエ!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエ!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエ!!!!!!!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエ!!!!!!!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエエ!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエ!!!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエ!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエエ!!!!!!!!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエエ!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエエ!!!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエ!!!!!!!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエエエエエエエエ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエエエ!!!!イヤーッ!イヤーッ!イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!アバーッ!イヤーッ!イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!アイエ!
はじめに
関数の表記としてラムダ抽象を使う。xを引数にとりEを返す関数をλx. Eと表記する(λx y… z. Eはλx.λy.…λz. Eの略記)。gに対するfの適用をf gとする。
カラテ(文法)
- イヤーッ![X][Y]…YにXを適用する。
コトダマ(組み込みの値)
- グワーッ!…λx. x (λx y. x) (λx y z. x z (y z)) (λx y. x)に相当する。
- イヤーッ!イヤーッ!グワーッ!グワーッ!グワーッ!でλx y. xになる。
- イヤーッ!グワーッ!イヤーッ!グワーッ!グワーッ!でλx y z. x z (y z)になる。
- アバーッ!…λx. xに相当する。
- ゴウランガ!…不動点コンビネータ(後述)。
- サヨナラ!…評価した瞬間に爆発四散してプログラムを終了する。
- アイエエエ…エ!!!!…!…チャーチ数(後述)。
最低限「イヤーッ!」「グワーッ!」があればプログラムが作れるようになっているため、コードは肥大しがち。インガオホー!
チャーチエンコーディング・ジツ
アロンゾ・チャーチ=サンの発明したジツで、自然数とリストを以下のようにエンコードする。
- 5 -> λsucc zero. succ (succ (succ (succ (succ zero))))
- [A, B, C, D, E] -> λcons nil. cons A (cons B (cons C (cons D (cons E nil))))
Lazy SLYRではバイト列をチャーチエンコーディングされた自然数(チャーチ数)のチャーチエンコーディングされたリストで表現し、プログラムは入力であるバイト列を受け取りバイト列を返す関数となる。なお、リストにスコットエンコーディングを使うLazy Kとは互換性がない。いいね?
アイエエエエ!!!!と叫ぶことで、(「エ」の数×10) + (「!」の数-1)を表すチャーチ数が作れる。
リカージョン・オン・フィクスド・ポイント
ゴウランガ!は任意の関数の不動点を求めるワザ。これによって再帰が表現できる。スゴイ!
- イヤーッ!ゴウランガ![F] → イヤーッ![F]イヤーッ!ゴウランガ![F]
フィボナッチ数を列挙するプログラムではゴウランガ!が4つも使われている。
処理系
処理系(Haskell製)はGitHubにある。ゴウランガ!処理系のソースコードはなんと70行未満だ!
Windows向けバイナリはこちら。
Freeモナドを使っている方、あるいはこれから使う方へ
FreeモナドのベースとなるFunctorは、GHCのDeriveFunctor拡張を使って、対象のデータ型にderiving Functorをつけることで
できます。
例
{-# LANGUAGE DeriveFunctor #-} import Control.Monad.Free data CharIOBase a = GetCh (Char -> a) | PutCh Char a | EmbedIO (IO a) deriving Functor type CharIO = Free CharIOBase
とすると、
https://github.com/ghc/ghc/blob/ghc-7.6.2-release/compiler/typecheck/TcGenDeriv.lhs#L1407 の規則に従い、
instance Functor CharIOBase where fmap f (GetCh g) = GetCh (f . g) fmap f (PutCh c a) = PutCh c (f a) fmap f (EmbedIO m) = EmbedIO (fmap f m)
のようなインスタンスが生まれます。