おとうさんにもわかるYコンビネータ！(絵解き解説編)

先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。

ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。

なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。

きしださんのエントリのおさらい

本題の前に、きしださんのエントリをおさらいしておきます。

Yコンビネータはただのオモチャじゃないんだよ
関数だけで色んな事が出来る
- 条件分岐をする関数ってのもある。
- 再帰(ループ)を作れる関数もある。←これがYコンビネータ。
- 数値も関数で表現できる。
つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！

って事が書いてありました。

普通のプログラミング言語では常識である、if文もfor文やwhile文も、仮引数以外の変数・変数代入も、果ては数値すらすべて使わずに、ただただ関数だけでそれらを「エミュレート」できちゃってます。関数というか、正確にはλという単純な文字列変換ルールだけでできちゃってます。
λSUGEEEEEEEEEEEEEEEEEEEEEE!!!!!!!!*2

きしださんのエントリの趣旨は、「λSUGEEEEEEEEEEEEEEEEEEEEEE!!!!!!!!」であって、Yコンビネータはその一部な訳ですが、そのお話の一部であるYコンビネータの所を、今回整理してみまず。絵が汚いのはご愛敬。

以下、本題。

関数ってのは、何かを入れたら、何かが出てくるモノだ

中学校で習いましたね。

関数に関数を入れたっていいじゃない

中学校では、関数に関数を入れるというのはやらなかったかも知れませんが、いいじゃないですか入れたって。

関数を入力とする関数のなかに、Yってのがある

通称Yと呼ばれるある関数があります。こいつは関数を入力として、関数を出力します*3。

Yから出力される関数の性質

このYが出力する関数(図では☆=Y(M))は、ある性質を持ちます。自分の元ネタであるYに入力した関数(図ではM)に入れると、また自分と同じ関数(図では☆=M(Y(M))=Y(M))が出てくるのです。Mからの出力である☆とMへの入力である☆とが同じという訳ですから、M(Y(M))=Y(M)と言う訳です。

Yから出力される関数の性質ーもういちどMに入れ直してみる

最初にMにY(M)を入力したときの出力はM(Y(M))ですね。それをもう一度Mに入れてます。すると出てくるのはM(M(Y(M)))と言う事になりますが、これもやはり同じく☆であり、Yから出てきたときの☆=Y(M)と同じです。つまり、M(M(Y(M)))=Y(M)と言う訳です。

Yから出力される関数の性質ー何度も何度もMに入れ直してみる

何遍やっても変わりませんね。M(M(M(M(M...M(Y(M)))...)))) = Y(M)です。Mにとって、Y(M)という入力は、変わらずにそのまま出てきてしまう特別な入力なのです。この特別な入力を不動点と言うらしいです。

…で？それと再帰／ループと何の関係があんの？

ですよねー。何回もMを適用(呼び出し)してるあたりがちょっと関係ありそうですけど。きしださんのエントリだと、ここが僕には解りずらかった。で、考えてみました。

もともと、再帰／ループがやりたかった

中学校で習った1次関数

$f(x) = 3x + 4$

は、 $\small f$ に $\small x$ を入力すると、 $\small 3x + 4$ を計算した結果が出力されます。

例えば、 $\small x$ として2を入力すると10が出力されます。

再帰というのは、関数が自分自身を使ってる事です。この関数 $\small f(x) = 3x + 4$ は再帰してません。でも例えば、それをちょっといじった、こんな関数にしてみます。

$f(x) = 3x + 4 + f(x-1)$

自分( $\small f$ )で自分( $\small f$ )を使っています。これが再帰です。

再帰する関数を図にしてみる

再帰する関数 $\small f(x) = 3x+4+f(x-1)$ を、ここまでと同様の絵にしてみます。

$\small 3x+4+f(x-1)$ の $\small x$ の所を入力として受け取って、?にそれを当てはめた結果が出力されます。

ちょっといじって、 $x$ じゃなくて $f$ の所を入力とする、別の関数 $F$ を作ってみる

ここで、 $\small x$ じゃなくてむしろ $\small f$ の所を入力として受け取るようにいじった、別の関数を作ってみます。

この関数は、関数を入力として受け取ります。そして、その関数を使う新しい関数を作って出力します。入力も出力も関数です。とくに再帰もしてないです。入力として関数を受け取ると、 $\small 3x+4+?(x-1)$ の $?$ の所にその関数を当てはめた結果が出力されます。

例えば、入力が $\small g(x)=2x$ という関数だったら、

$\small 3x+4+2(x-1)$ つまり $\small 5x+2$ という関数が出力されます。もちろん、この出力された関数は普通に使う事が出来る普通の関数です。例えば、1を入力したら7が出力されます。

この関数を $\small F$ と呼ぶ事にしましょう。

$F$ に $f$ を入力してみよう

$\small F$ は、関数を入力として受け取ります。ここで、もともとの関数 $\small f(x) = 3x+4+f(x-1)$ を入力してみましょう。

すると、出力されるのは、 $\small 3x+4+f(x-1)$ 。入力である $\small 3x+4+f(x-1)$ とまったく同じです。

関数 $\small F$ には、いろいろな関数を入力できますが、関数 $\small F$ にとって $\small f$ は特別な入力ですね。

$f$ は $F$ の不動点だ

$\small f$ は、そのままでも、 $\small F$ に入力した結果でも、まったく変わりません。このような特別な入力を、不動点というらしいです。
これを式で書くと、

$\LARGE f=F(f)$ (「 $\LARGE f$ は $\LARGE F$ の不動点である」と言っている式)

です。

$\small F$ の実体は $\small 3x+4+?(x-1)$ だったので、上記の式の右辺 $\small F(f)$ は $\small 3x+4+f(x-1)$ ( $\small ?$ に $\small f$ を当てはめた)です。

つまり、上の式は、

$\LARGE f=3x+4+f(x-1)$ (「 $\LARGE f$ は $\LARGE F$ の不動点である」と言っている式2)

と同じ事です。これは、上で $\small f$ の内容を決めたときの式とまったく同じです。 $\small f$ が、自分( $\small f$ )で自分( $\small f$ )を使っている＝再帰する関数であるという事を、式で書いたもの、そのものずばりです。

つまり、どういう事かというと、

「 $\LARGE f$ は $\LARGE F$ の不動点である」という事が、

「 $\LARGE f$ は再帰する関数である」という事と同じ！！*4。

という事です。

今の話は最初の方の図の下半分の例

$\small f$ や $\small F$ という具体例で考えてみた不動点ですが、これは、最初の方の図の下半分の例です。Mの例が $\small F$ 、☆の例が $\small f$ です。

実例を見てみた事で、下半分のリアリティが出たでしょうか。

じゃあ上半分は？

実例で見た説明を当てはめると、最初の方の図はこうなります。

Yと呼ばれるある関数は、入力された関数(例: $\small F$ )の不動点(例: $\small f$ )を出力します。不動点を出力するので、Yは、不動点演算子であるとか、Fixed point combinatorであるとかいうらしいです。Yの出力は不動点なので、Yに入力した関数(例: $\small F$ )にそれ(例: $\small f$ )を入力すると、そっくりそのままそれ(例: $\small f$ )が出力される、と言う訳です。

Yに入力するのは何でもいい訳じゃなくて、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数(入力も出力も関数)」です(もちろん $\small F$ もそうなってました)。そうするとYから、そいつの「不動点である関数」＝「再帰する関数」が出力されてきて、関数だけで再帰が出来るという訳です。めでたしめでたし。

Yコンビネータは、使い道がない？

Yコンビネータの一番偉いところは、そのおかげで、関数(正確にはλという単純な文字列変換ルール)だけでプログラムがすべて表現できるという事だと思います。それによって、プログラミングに関するいろんな原理の研究に数学のスーパーパワーを使いやすくなります。数学のスーパーパワーを使うと、完全に正しいと保証されたプログラミングに関する技術が産み出せます。その辺のさわりを、きしださんが解説されています。

きしださんは、

結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。
http://d.hatena.ne.jp/nowokay/20090413#1239617061

といいます。たしかにYコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。

じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？

さあ、Yコンビネータ(不動点 演算子)を使おう！

意味がない事はないと思います。Yコンビネータとか不動点とかで出てくる考え方は、理論だけじゃなく、実際のプログラミングでも応用できたりもします。ちょっとそれを見てみましょう。

…つづく

というわけで、Haskellやろうぜ！(おまけ)

いきなりですが、Haskellの宣伝です。

ぬぬ、スタックオーバーフロー。
これは、式がそのまま評価されてしまうことに問題があるようです。そこで遅延評価するための変換をいれてみます。
http://d.hatena.ne.jp/nowokay/20090409#1239268405

ぬぬ、またしてもオーバーフロー
これは、boolで真の場合も偽の場合の式もその場で評価されてしまって無限ループになってしまうためで、やっぱり遅延評価しないといけません。
http://d.hatena.ne.jp/nowokay/20090409#1239268405

きしださんのエントリで、普通のプログラミング言語の規則である評価順番が小さな躓きポイントとして挙げられていました。ただでも込み入った事を考えているのに、こういった躓きポイントは痛いです。それに、それを回避するために、本当は「正しい」はずのコードをもう一捻りして書き換えてやらなくてはいけないのも、めんどくさいしすっきりしません。

でも、Haskellなら大丈夫。デフォルトで遅延評価だからです。必要なところを必要なだけ評価していくので、このような問題は起きません。単純に正しく書いておけば、きちんと動くプログラムになってくれます。

さらに、Yコンビネータというか不動点演算子をこんなにすっきり書く事が出来ます。

y(f) = f(y(f))

このコードは、上で書いた

$\LARGE f=F(f)$ (「 $\LARGE f$ は $\LARGE F$ の不動点である」と言っている式)

に対して、

$\LARGE f=Y(F)$ (「 $\LARGE f$ は $\LARGE Y$ に $\LARGE F$ を入力した結果である(上の最後の図の上半分)」と言ってる式)

を当てはめた式、

$\LARGE Y(F)=F(Y(F))$ (" $\LARGE f$ "を" $\LARGE Y(F)$ "に書き換えた式)

そのものです。大文字と小文字が違うだけで、プログラムとこの式はまったく同じですね。定義をそのまま正しく書いてやるだけで、ちゃんと動くプログラムになってます。評価順とか関係ないです。すごいですHaskell。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門

posted with amazlet at 09.04.17

青木峰郎
ソフトバンククリエイティブ
売り上げランキング: 68076

Amazon.co.jp で詳細を見る

WebにHaskellの情報は結構ありますが、玄人向けです。「やさしいHaskell入門(A Gentle Introduction to Haskell)」というドキュメントがありますが、これは「天才な人にはやさしい」という意味なので気を付けて下さい。ふつうの人には、この本がふつうの意味でやさしいくていい感じです。興味が湧いた人は、まずこの本を読む事をお勧めします。

*1:何か元ネタがあるんでしょうか

*2:ちなみに、Smalltalkもif文やwhile/forなしの様ですね。Booleanのメソッド+クロージャ／クロージャのメソッド(?)+クロージャで実現しているようです。これはどういう算法なんでしょう?

*3:ざっくり言って、入力が関数で、出力も関数である関数をコンビネータと言います

*4:正確には、 $F$ への言及が無くなってるから、同じと言うより含意してる、といったところか