現在、コンビネータ理論の問題を解いて勉強している。そこで不思議に思うのが、概念が簡単なのになぜか複雑な式が生まれてしまうということだ。
例えば、次の式だ。
$$D\equiv[x,y,z].zxy$$
この$D$は変数$x,y,z$を受け取って変数$z,x,y$を返す関数だ。つまり、変数の内容を変えずに順序のみを変更しているだけのコンビネータだ。
I,K,Sコンビネータ
コンビネータ理論とは少数のコンビネータ$I,K,S$のみで計算をしようとする試みだ。
各コンビネータの特徴は以下の通り：
$Ix\rightarrow x$
$Kxy\rightarrow x$
$Sxyz\rightarrow xz(yz)$
実際$D$コンビネータの計算については、この記事を参考にしてほしい。
結論のみを示すと、$D$は次のように$I,K,S$のみで表される。
$$D\equiv[x,y,z].zxy\equiv[x].([y].([z].zxy)))$$
$$\equiv S(S(KS)(S(KK)(S(KS)(S(K(SI))K)))) (KK)$$となる。これはまるで呪文だ。
複雑さについての考察
単に３つの変数を巡回的に入れ替えているだけなのに、コンビネータの式がこんなに複雑になるとは非常に不思議だ。この複雑性は、どこから来るのだろうか。コンビネータの数を少なくしすぎたせいであろうか。それとも本質的にコンビネータの組み合わせ式は複雑になってしまうのだろうか。
考えたところ以下の点が挙げられる。
(1)本質的に入れ替え操作は難しいので、式が複雑になる。
(2)コンビネータを$S,K,I$に絞りすぎのため、式が複雑になる。
(3)ラムダ計算にもとづくコンビネータ理論は、内部状態を持たない。途中経過の値を維持できないので、式の形として保存しなけらばならないので複雑になる。チューリング機械に基づくvon Neumann型機械は値を対比するために記憶領域（メモリー）があるので、計算途中の値の一時保持には問題がない。
確かに、von Neumann型に基づく手続き型プログラミング言語であれば、以下のように記憶レジスターを使って書ける。
a := x;
x := z;
z := y;
y := a;
(4)自然言語でこの操作を表現するときに「ずらす」や「巡回させる」などの語彙で説明することができる。しかし、このことが可能なのは言語での高度な抽象化が条件となっている。アメリカ・インディアンの言語などにはそのような表現がない場合もある（漢語よ、ありがとう）。いかに我々が抽象的な言葉を意識せずに使っているか思い知らされる。
