#*** Combinator Birds Advent Calender ***
このAdvent Calenderは，Combinator Birds(Combinator論理)についての知識が全くない様な人に対して，Combinator Birdsを紹介するノリで書かれています．できるだけ複雑な知識は仮定しないようにはしていますが，わかりにくいところ等があったらごめんなさい．
この記事の中には幾つもの誤りが含まれている可能性があります．おかしいところがあれば遠慮なく突っ込んでください．Combinator とは，難しく言うと、「自由変数を含まないラムダ式」あたりになるんでしょうか．
正確なことや細かいことはおいておいて，とりあえずCombinatorの世界に触れていただくことをメインに考えてこの記事を書くこととします．
もしCombinator Birdsに興味を持ってくれたならば，数学パズル ものまね鳥をまねるを是非読んでみてください．
Combinator Birdsの一覧は，ここなどにあります．
二日目まではCombinator Birds自身の説明の説明もおりまぜていきますので，結構長くなりますが，三日目以降は短くなっちゃってます．
とある森に，何種類かの鳥がいます．その森にいるすべての鳥は，何らかの鳥の名前を聞くと，何らかの鳥の名前を返します．また，同じ鳥の名前を同じ鳥に聞かせると，同じ名前が常に帰ってくるものとします．(任意の鳥Aについて，それぞれ任意の鳥であるx,yを考えると，x = y ⇒ A x = A yが成り立つという事です．* ただし一般に逆は成り立ちません． * )
一般にある鳥Aにある鳥Bの名前を聞かせることを
(A B)
と書きます． すると， *** 「鳥Aに鳥Bの名前を聞かせた時に返ってくる鳥の名前」が返ってきます *** ．
それを，つまりある鳥Aに，ある鳥Bの名前を聞かせて，その返答がある鳥の名前Cであることを
(A B) = C
と書くこととします．
例えば，この森には恒等鳥(Identity Bird)という鳥がいます．この鳥は，何らかの鳥の名前を聞くと，その名前をそのまま返します． これを，
(I x) = x
と書きます．(IはIdentity Birdの頭文字です)
今，上のAが恒等鳥であるとすると，
(I B)
となり，Iはある鳥の名前を聞くと，その鳥の名前をそのまま返す鳥だったので，
(I B) = B
となります．この鳥の性質により，Bの名前が帰って来ました．
また，細かいことですが，「任意の鳥A,Bについて，任意の鳥xについて，「C x = A (B x)」 となる鳥Cが存在する」ということを仮定しておきます，よくわからないなら無視してもあんまり問題ないです．
よくわからない？大丈夫です，具体例を見ていけばきっとわかるです！
この鳥は，「任意の鳥の名前xを聞くと，「任意の鳥の名前yを聞くと，xという名前を返す鳥」の名前を返す鳥」です．
ややこしい？
噛み砕いて行きましょう．
鳥の性質を，書いてみると
(K x) = (任意の鳥の名前yを聞くと，xという名前を返す鳥)
となります．
まだいまいちよくわからないですね，右辺の括弧の中身を考えてみましょう．
括弧の中身の鳥は，鳥の名前を聞くと，その名前を忘れて，常にxという鳥の名前を返します．
この括弧の中の鳥の名前を今仮にAとすると，
(A y) = x
と表すことができます．
括弧の中の鳥が判明したので，さっきのチョウゲンボウに戻ってみます． 括弧をさっきの鳥に直して，
(K x) = A
を得ます．しかし，イマイチよくわかりません．
もう少し整理してみましょう．
今，
(A y) = x
かつ，
(K x) = A
であることから，
((K x) y) = x
を得ます．(一つ目の式の中に二つ目の式の右辺のAを代入しています)
括弧が多くて，なんだか見にくいですね．
一番外側の括弧はなくても明らかですので，今後省略しちゃいましょう．
(K x) y = x
まだ括弧があります．鳥の名前が複数並んでる時は，左から解釈していくことと定めてしまって，この括弧も外しちゃいましょう．つまり
A B C
と，鳥の名前が並んでいた時には，
(A B) C
であると解釈しましょう，ということです． 一般に上の鳥と，
A (B C)
は同じでは無いことに注意してください！
これらの省略記法によって，
K x y = x
を得ます．
この鳥には幾つかの面白い性質があります．見ていくことにしましょう．
一般に，鳥Aに対して
A x = A y ⇒ x = y
は成り立ちません．例えば，異なる鳥x,yについて
(K z) x = z = (K z) y
が成り立ちますが，x,yは異なる鳥と仮定しました．
しかし，この鳥チョウゲンボウ(K)は，
K x = K y ⇒ x = y
が成立します．何故ならば，任意の鳥zについて，
(K x) z = x
が成立します．今，
K x = K y
ですから，
(K y) z = x
も成立します．これと，
(K y) z = y
とを合わせて，
x = (K x) z = (K y) z = y
を得ます．
チョウゲンボウ(Kestrel)という鳥がいます．この鳥の性質は，
「ある鳥の名前xを聞くと，「ある鳥の名前yを聞くと，xという名前を返す鳥」の名前を返す鳥」
です．
これはつまり，
K x y = x
ということです． わかりづらいならば，この鳥のことを「ある鳥の名前を2つ聞き，前者の名前を返す鳥」だと思ってもらっても，構わないかもしれません．
この鳥は，数多くの鳥を発見していくときに役立つ基本的でとても重要な鳥です．
以下はだいたいおまけです．さらっと読み流してください．
この鳥，チョウゲンボウKをラムダ式で書くと
K = λx.λy. x
と書けます．ラムダがごちゃごちゃしてるのでまとめて，
λxy. x
とも略記します．
（HaskellのPreludeにおける関数constですね．
この鳥は，「ある鳥の名前xを聞くと，「ある鳥の名前yを聞くと，「ある鳥zの名前を聞くと，「「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥」の名前を返す鳥」の名前を返す鳥」の名前を返す鳥」です．激しく訳がわかりません．書いてる私がすでに混乱しています．
昨日と同じように噛み砕いて行きましょう．
まず，この鳥Sは，ある鳥の名前xを聞くと，なんかややこしい名前を返す鳥でした．
S x = (ある鳥の名前yを聞くと，「ある鳥zの名前を聞くと，「「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥」の名前を返す鳥」の名前を返す)
まだ訳がわかりません，しばいたろか，って感じです． 「ある鳥の名前yを聞くと，「ある鳥zの名前を聞くと，「「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥」の名前を返す鳥」の名前を返す鳥」 について考えて行きましょう． 今仮にこの鳥の名前をAとします． すると，
A y = (ある鳥zの名前を聞くと，「「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥」の名前を返す鳥)
ちょっと簡単になったもののまだいまいちわかんないですね． 「ある鳥zの名前を聞くと，「「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥」の名前を返す鳥」へ行きましょう． この鳥の名前を仮にBとしましょう． すると，
B z = (「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥)
「xにzの名前を聞かせると返ってくる鳥」と「yにzの名前を聞かせると返ってくる鳥」の名前はそれぞれ，
(xにzの名前を聞かせると返ってくる鳥) = x z
(yにzの名前を聞かせると返ってくる鳥) = y z
ですから，
B z = (x z) (y z)
と書けます．左側の括弧は，複数の鳥が並んだ場合，左から解釈していくと昨日定めたので省略することができるので，
B z = x z (y z)
と書けます． ここからはもう簡単です，途中でおいた名前にこれを代入していくだけです．
A y = (ある鳥zの名前を聞くと，「「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥」の名前を返す鳥)
でしたので，
A y = B
です． さらに
S x = A
ですから，
(S x) y = B
そして，
B z = x z (y z)
とあわせて，
S x y z = x z (y z)
を得ます． これがこの鳥の正体です！
ムクドリ(Starling)という鳥がいます．この鳥の性質は，
「ある鳥の名前xを聞くと，「ある鳥の名前yを聞くと，「ある鳥zの名前を聞くと，「「xにzの名前を聞かせると返ってくる鳥」に「yにzの名前を聞かせると返ってくる鳥」の名前を聞かせた時返ってくる鳥」の名前を返す鳥」の名前を返す鳥」の名前を返す鳥」
です．
つまり，
S x y z = x z (y z)
となります．
なんとこの鳥は， *** チョウゲンボウ(K)と組み合わせることで，任意の鳥を表すことができます *** ！
この鳥もまた，「任意の鳥の名前を3つ取り，それらの名前をそれぞれx,y,zとすると，(x z (y z)の表す鳥)の名前を返す鳥」だと考えることもできます．
昨日と今日は初回なので長々と書いてきましたが，明日以降は少し短くなると思います．
S = λxyz. x z (y z)
となります．
(この鳥を表す関数はPreludeには無いです．<*>
この鳥は，「ある鳥の名前xを聞いて，その名前xを返す鳥」です． この鳥の性質を
I x = x
と表します．
これは，一番単純な鳥です．
先ほどと同じ例ですが，この鳥に任意の鳥の名前xを聞かせると，
I x = x
となり，その鳥の名前が返ってきます．
昨日，一昨日の例と比べるとはるかに簡単ですね．
昨日書いたように，すべての鳥はSとKによって表せます． よってこの鳥Iもまた，SとKによって表せます． 表し方は一つではなく無数に有りますが，代表的な表し方として，
S K K
があります．
S K K x = K x (K x) = x
となり， ** IはSKKと表せます ** ． この他にも無数に表し方は存在します．例えばSKSなどもIになります． しかし，慣習としてSKKとしてしばしば表されますのでここではしたがっておきましょう，実はそのほうが便利なことも少し有りますし．
恒等鳥(Identity Bird (aka Idiot))は，
「ある鳥の名前xを聞いて，その名前xを返す鳥」
です．
I x = x
I = λx. x
(Preludeのid関数ですね．
この鳥は「ある鳥の名前xを聞くと，「ある鳥の名前yを聞くと，「ある鳥の名前zを聞くと，「xに「yにzの名前を聞かせると返ってくる鳥の名前」を聞かせると返ってくる鳥の名前」を返す鳥の名前」を返す鳥の名前」を返す鳥の名前を返す鳥」です． いつも通りこの鳥の性質を調べて行きましょう．
B x = (ある鳥の名前yを聞くと，「ある鳥の名前zを聞くと，「xに「yにzの名前を聞かせると返ってくる鳥の名前」を聞かせると返ってくる鳥の名前」を返す鳥の名前」を返す鳥)
もう一段階，「ある鳥の名前yを聞くと，「ある鳥の名前zを聞くと，「xに「yにzの名前を聞かせると返ってくる鳥の名前」を聞かせると返ってくる鳥の名前」を返す鳥の名前」を返す鳥」は，
A' y = (ある鳥の名前zを聞くと，「xに「yにzの名前を聞かせると返ってくる鳥の名前」を聞かせると返ってくる鳥の名前」を返す鳥の名前)
まだまだ，
C' z = (xに「yにzの名前を聞かせると返ってくる鳥の名前」を聞かせると返ってくる鳥の名前)
「yにzの名前を聞かせると返ってくる鳥の名前」は，
y z
ですので，
C' z = (xに(y z)を聞かせると返ってくる鳥の名前)
となり，
C' z = (x (y z))
となりますので，
A' y = C'
とあわせて，
A' y z = (x (y z))
が得られ，さらに，
B x y z = x (y z)
を得ます．
B = S (K S) K
となります．実際，
(S (K S) K) x y z
= ((K S) x (K x)) y z
= (S (K x)) y z
= (K x) z (y z)
= x (y z)
となり，確かにBとなっています．
ルリツグミ(Bluebird)の性質は，「ある鳥の名前xを聞くと，「ある鳥の名前yを聞くと，「ある鳥の名前zを聞くと，「xに「yにzの名前を聞かせると返ってくる鳥の名前」を聞かせると返ってくる鳥の名前」を返す鳥の名前」を返す鳥の名前」を返す鳥の名前を返す鳥」で，
B x y z = x (y z)
と表されます．
B = λxyz. x(yz)
(Preludeの(.)関数そのものですね?
この鳥に，任意の鳥の名前xを聞かせると，xにxの名前を呼びかけた時の反応を返します．
M x = x x
MにMを呼びかけた場合，なんだかヤバイことになります．
M M = M M = M M = M M = ...
これは明らかに名前の解決が終了しません．
これを利用して，
Ω = M M
と定義することにより，Ωを「失敗」，「非停止」，などの意味を持たせることがあります．
Y = S L L
Y A
= S L L A
= L A (L A) ・・・ (あ)
= A ((L A) (L A))
= A (L A (L A))
= A (Y A) ・・・ (∵ (あ))
L x y = x (y y)
L I x = I (x x) = (x x) = M x
いきなりですが，この鳥は次のような性質を持ちます．
X x = x S K
この鳥は，１種類ですべての鳥を表すことができます．
KとSが表せるので，任意の鳥が表せます．
X (X (X X)) = K
証明は長いのでここに置いときます．
また，
X (X (X (X X))) = S
なぜなら，
X (X (X (X X)))
= X (K) (∵上式より)
= K S K
= S
です．
####### Copyright (C) 2012 nonamea774(nnn74,[email protected],https://twitter.com/nonamea774)
####### Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
#######
Combinator Birds Advent Calender by nonamea774 is licensed under a Creative Commons 表示 - 継承 3.0 非移植 License.
もったいないから公開