モナドの六つの系統[Functor x Functor]

モナドは「アクション」を表す抽象的な構造である。モナドは、Haskellにさまざまな概念に対する記述能力をもたらす。

モナドの基礎

  • return :: a -> m a: 純粋な値をモナドで包む。
  • m >>= f :: m a -> (a -> m b) -> m b: モナドmに包まれた値をfに渡し、その結果として現れたモナドを結合する。
  • 固有アクション: それぞれのモナドに固有の方法でモナドを生み出す。
  • 実行: モナドに包まれた値を、より根源的な形に還元する。

モナド則

モナドに以下の三つの制約を課すことによって、最低限度の記述能力を保証している。

return a >>= k == k a
m >>= return == m
m >>= (\x -> k x >>= h) == (m >>= k) >>= h

より強い制約は、より強い力を生み出す。

モナドの分類

モナドは、以下の6つの系統に分類できる。

f:id:fumiexcel:20130605170915p:plain

隣り合っているものほど相性がよく、近い性質を持つことが多い。

内包系

Identity, Maybe, Either, [], Iterateeなど

値を何らかの形で包みつつ、モナドの性質を付与したもの。失敗する可能性のある計算に使用できるものも多い。ストリームを扱うモナドIterateeは、継続系の性質も併せ持つ。

  • Nothing :: Maybe a (固有アクション)計算をすべてに終わりにする。これが出現すると、(>>=)は一切意味をなさなくなる。

出力系

主にWriter

値を出力できるという性質を備えたモナド。

  • tell :: Monoid w => w -> Writer w () (固有アクション)モナドに値を送り込む。モナドが結合できるという制約から、送る値も結合可能でなければならない。

  • runWriter :: Writer w a -> (a, w) (実行)計算の結果と、書き込まれた値を取り出す。

環境系

主にReader

モナドの中で値を取り出し、自由に使用できるという性質を持つ。

  • ask :: Reader r r (固有アクション)環境から値を取り出す。

  • runReader :: Reader r a -> r -> a (実行)環境を設定し、その下で行われた計算の結果を求める。環境に持たせる値はどんなものでもよい。

世界系

IO, STM, ST, Q, Freeなど

現実を含む、世界に作用できる特殊なモナド。Haskellにおける、副作用を表現する唯一の方法である。

  • putStrLn :: String -> IO () (固有アクション)現実世界の標準出力に文字列を送る。

  • getLine :: IO String (固有アクション)現実世界の標準入力から、一行分の文字列を取り出す。

  • unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #)) (実行)GHCのIOの中身は、現実世界を受け取り、変更後の現実世界と結果を返す関数である。通常、我々がこの型 を目にすることはない。

  • liftF :: Functor f => f a -> Free f a (固有アクション)すべてのFunctorには、自由モナド(free monad)と呼ばれるモナドが対応する。自由モナドは強力な抽象化、コードの分離を行うことができる*1。

  • singleton :: t a -> Program t a (固有アクション)なんと、この世にはすべてのデータ型にモナドを対応させる仕組みが存在するのだ*2。筆者はこれを最強のモナドの一つだと確信している。

状態系

主にState

モナドの中なら、値を読み込んだり書き込んだりできる。

  • get :: State s s (固有アクション)現在の状態を読み込む。

  • put :: s -> State s () (固有アクション)現在の状態を置き換える。

  • runState :: State s a -> s -> (a, s) (実行)初期状態を与えて、結果と変更後の状態を取得する。

継続系のCodensityモナドを使うと、環境系モナドの性質を状態系モナドに変化させることができる。

継続系

Cont, CC, Parser, Codensity, Logicなど

「継続」と呼ばれる、計算の結果を受け取る関数を扱うモナド。表現力が高く、興味深い性質を示すものも多い。

  • cont :: ((a -> r) -> r) -> Cont r a (固有アクション)継続を受け取る関数からモナドを作る。rの型がわかっているとき、非常に柔軟な処理が可能となる。

  • runCont :: Cont r a -> (a -> r) -> r (実行)継続を渡し、計算の結果を求める。

  • dnew :: CC (Dynvar CC a) (固有アクション)限定継続モナドCCの中で、変更可能な変数*3を具現化する。IOなどの現実世界と関わる処理は一切ない。

ほとんどのモナドはこの継続系の変種として表現できるという面白い特徴を持つ。Logicモナドは継続系でありながら非常に内包系に近い特性を持つ*4。

まとめ

良いプログラムを書くには、これら六系統のモナドをバランス良く使いこなしていくことが大事である。

参考文献

*1:そろそろFreeモナドに関して一言いっとくか - モナドとわたしとコモナド

*2:Freeモナドを超えた！？operationalモナドを使ってみよう - モナドとわたしとコモナド

*3:Control.Monad.CC.Dynvar

*4:Control.Monad.Logic

Freeモナドを超えた！？operationalモナドを使ってみよう

限定版IOみたいなモナドを簡単に作れたら、コードが分離できるしテストもしやすくなるのになあ…

数か月前なら、

それ、Freeモナド*1でできるよ！

と返されるだろう。だが今は違う。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モナドの実装を作ったのでぜひ使ってみてほしい。

*1:昨年の冬、日本のコミュニティでやたら流行った

*2:詳しくは過去の記事を参照

*3:Data.Functor.Yoneda.Contravariant.Yonedaと等しい

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の質問

  1. ラムダ抽象ではなくコンビネータで表現するメリットを一言で表してください。(筆記回答)
  2. 入出力の終端を表現する方法は何ですか？(筆記回答)
  3. チャーチエンコーディングとスコットエンコーディングの違いを端的に説明してください。(筆記回答)
  4. 任意の関数に対して不動点を求めるコードはどれですか？(選択回答)
    1. S I I (S (S (K S) K)) I
    2. S S K (S (K (S S (S (S S K)))) K)
    3. ((S (K S) K) (K (S I I))) ((S (K S) K) (K (S I I)))
    4. S I I (S (K (S S (S (S S K)))) K)
  5. Lazy Kのプログラムにおいて、いきなりスタックがあふれる不具合が発生しました。原因として何が考えられますか？(筆記回答)
  6. 与えられたタプルやリストに対してcarとcdrをそれぞれ適用するのはなぜNGなのかメカニズムを説明してください。
  7. 与えられたチャーチ数の階乗を求める関数をSとKとIの組み合わせで書いてください。
  8. 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開発をするのだ。

結果として、一部の出来る人には余計に負荷がかかるだろうなと思う。

いままで私は楽観主義者だから、

関数型言語は適用簡約産業だったけど、これからは抽象除去産業になっていく。 必然的にコンビネー汰の時代になり、優秀な簡約器が生き残るだろう。 と思っていた。

しかし現実は、もっと凄惨な世界を経て時代が進んでいくようだ。

元ネタ

８つの質問で、Java SI業界の現状を知る - 山本大＠クロノスの日記

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

まとめ

f:id:fumiexcel:20130311220935p:plain

無事それっぽいものができました。勿論、これで終わりではありません！次回からは、ゲームの本質的な部分を記述していきます。

モナド変換子の速さを測ってみる

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向けバイナリはこちら。