SKIコンビネータを使ってチャーチ数の2を表せない程度の能力の私がLazy Kを紹介して周りの人間にも嗜んでもらいたいエントリー
チャーチ数そのものが何たるかは分かった気がするが、それをSとKで表せない。私にもっとコンビネータを！
とか垂れ流すだけでは何だかさびしくなってきたので、ここを読んでる私の知り合いもしくは自分の理解の確認にも発信してみる。Unlambdaはパッと見でウゲッてなるだろうからLazy Kで。まぁどっちも変わらんが。
あといつものように正確性は疑わしい。
以下は上に書いてあることの繰り返し。Lazy Kはプログラミング言語。3つの組み込み関数があり、それ以外は存在しないし、新しい名前の関数を作ることもできない。あと関数以外の何者も存在しない。で、その3つの関数というのがKとSとIで、それぞれJavaScript的に書いてみると、
- function K(x) {return function(y) {return x;};}
- function S(x) {return function(y) {return function(z) {return x(z)(y(z));};};}
- function I(x) {return x;}
となる。上記全ての関数は一つの引数を取って戻り値を返す関数であり、これらの組み合わせによって記述する関数もまた全てそうなる。あとIはS(K)(K)と等価であるので実は必要ないが、ないと面倒なのである。それから表記法。JavaScript ... Lazy Kという対で並べてみる。
- X(Y) ... XY
- X(Y)(Z) ... XYZ
- X(Y(Z)) ... X(YZ)
というような感じで。XYZ本当は他にもUnlambda記法とかそのほかの書き方も存在するのだが、どんな表記法だろうができることに変わりはないし、これが一番親しみやすい書き方だと思うので割愛する。あと入出力。これに関してはもう上のサイトを見ていただきたく。断片的に説明すると、ここまで読んだなら分かると思うが、そもそもこの言語には数値そのものズバリを表現するものが存在しない。存在しないのでこの言語に存在するものを使って数値を表現する必要がある。というわけで再びJavaScript的なもので。
- function 0(f) {return function(x) {return x;};}
- function 1(f) {return function(x) {return f(x);}
- function 2(f) {return function(x) {return f(f(x));}
- function 3(f) {return function(x) {return f(f(f(x)));}
というように、数値nを「fを受けとって「xを受けとってfをxにn回適用する関数」を返す関数」と定義する、これをチャーチ数という。で、入力というのはZzz
