「Rust、C、アセンブリによる実装からのアプローチ　並行プログラミング入門」(オライリー)は、並行プログラミングに関係する様々なトピックが扱われていて、その中にλ計算もありました。
「λ計算自体は、並行プログラミングを学ぶ上で本質的に不要かもしれないが、λ計算の持つ形式的な記述能力とその考え方は、平行プログラミングの意味を厳密にとらえるための助けとなるだろう。」とあります。

不動点コンビネータの箇所を読んでいて、そういえば以前Lazy Kというプログラム言語を調べたことを思い出し、復習してみました。(えっ、10年も前だった)

http://bitlife.me/archives/tag/lazy-k

Lazy K は、わずかSKIという3文字でプログラムが記述可能です。(実質IをSKKに変換できるので2文字)
数値や条件分岐、ループも表現できるしくみを持っていることから、可能となります。
SKIは以下のλ計算を表します。

S = λxyz.xz(yz)
K = λxy.x
I = λx.x

このルール駆使して、三文字に置き換えていくようです。
難しい概念ゆえ、文章読むだけでなく動かしてみないと理解できない、ということからいろいろ試しました。

当時と同じ環境を作ってまずは動作確認をしてみました。

(lazy-def ‘(test x) ‘(cdr x))
(print-as-cc (laze ‘test))

SI(K(KI))

記事通りできました。こういうの残しておくと楽ですね。
ここで　Lazyコマンドに渡すべくSKI文字列をいろいろとschemeプログラムを作って試しましたが、なかなか思い通り動いてくれません。サンプルもありますが、schemeからコンバートしたもので結局バイナリーファイルを眺めているようで、schemeとlazy-kの関係性みたいなものがわかりませんでした。

http://legacy.e.tir.jp/wiliki?%CB%DD%CC%F5%3A%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0%B8%C0%B8%ECLazy_K
http://esoteric.sange.fi/essie2/download/lazy-k.zip　(lazyコマンド、サンプル一式)

そのような中、schemeとの橋渡しになるような記事があり、とても参考になりました。

「究極の関数型言語による至高のHello, world!」
https://rst76.hatenablog.com/entry/20121204/1354629448

ここではHello,Worldという文字列を出力するための仕組みが説明されていますが、これでも長いため、たった一文字”H”だけ出力するプログラムにしてみました。

(load “lazier.scm”)
(load “prelude.scm”)
(load “prelude-numbers.scm”)
(lazy-def ‘(hello input) ‘(cons 72 end-of-output))
(print-as-cc (laze ‘hello))

コマンド

lazy -e “K(S(SI(K(S(K(SII(S(S(KS)K)I)))(S(S(KS)K)(S(S(KS)K)(S(SII)I(S(S(KS)K)I)))))))(K(K(SII(SII(S(S(KS)K)I))))))”

結果

H

たった一文字表示でこれだけかかります。
結局、lazy-kで出力させる(プログラム結果を見る)ということは、チャーチ数で文字コードを表現してやる必要があり、最初のサンプルが動いたことから(‘(test x) ‘(cdr x))、ロジック部分だけ考えればなんとかなると思っていたことはかなり甘かったといえます。

そこで本質的なことを理解する必要があると思い、調べていたところ下記がとても参考になりました。
「おとうさん、ぼくにもYコンビネータがわかりましたよ！」
https://nowokay.hatenablog.com/entries/2009/04/09#1239268405

また、λ計算の変換方法については下記がとても詳しいかったです。
「高階ことりちゃんと学ぶSKIコンビネータ」
http://www.tatapa.org/~takuo/kotori_ski/

最後に、コンビネータによる繰り返しを確認しました。
https://www.fixedpoint.jp/2007/02/14/y.html

(define Z
(lambda (f)
((lambda (x) (f (lambda (y) ((x x) y))))
(lambda (x) (f (lambda (y) ((x x) y)))))))

;Value: z

1 ]=> (define fact
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))

;Value: fact

1 ]=> ((Z fact) 5)

;Value: 120

ZはZコンビネータといい、Yコンビネータが無限ループしてしまうため、その変形です。
よくある再帰プログラミングの代表的な例の階乗計算ですが、注目すべき部分は無名関数でゆえ自分自身を呼び出せていません。これをZコンビネータに適用することにより繰り返し処理を実現しています。
それがどうした、と言われればそれまでですが、私はこれでコンビネータと言われる意味が理解できた気がしました。
コンビネータが表現しているものそのものは直感的でないのですが、組み合わせるとその働きがはっきりするといった触媒的なものにも感じます。
しかしネット上に意外と情報が多かったのは、興味を持つ人が多いということなのでしょう。
私ももっと探求していきたいです。