Schemer のための「すぐ理解できるYコンビネータ」

ラムダ計算の説明などによく登場するYコンビネータ(不動点コンビネータ)ですが、
「ラムダだけで再帰関数を定義できる」というのはわかってもYコンビネータを使った関数の定義は複雑ですし、
そもそもYコンビネータ自体の定義からしてどうなってるのかよくわからないので、少し難解です。

しかし、Schemer (Schemeプログラマ) 向けには簡単に理解できる説明があります。
Scheme でよく使う call-with というイディオムがありますが、これを使うことで
「Yコンビネータとは call-with-myself である」と言えるのです。

具体例で説明します。

自分が書いているプログラムが正しく動くと信じてプログラムを書く感覚

次のような記事が話題になっていたんだけど、少し感じるところがあったのでメモっとく。ただの自分の感覚なので、結論とかは特にない。

『難しいプログラムでは自分がいままで書いたコードが正しく動くと信じて残りのコードを書く必要がある -- Medium』

多分この元記事の方は複雑なプログラムのことについて言っていて、俺の考えてるような単純な例ではなかろうと思うんだけど、自分の場合は結構単純なプログラムであっても再帰が関わってくるとそう感じる場合がある。単純にループにできそうにないやつ（本質的に再帰的なやつ）とか。

例えば Scheme でリストの長さを返す関数 length は次のように定義できる。

(define (length lst)
 (if (null? lst)
     0
     (+ 1 (length (cdr lst)))))

これも実際には再帰呼出しのlengthを書くところではlengthが正しく動くことを信じて書いてるわけではあるけど、再帰呼出しのlengthが最後に出てくるので（末尾再帰という意味ではなくて記述上の順番として）、これまで書いた部分が正しいという確信を得やすいのもあって、あんまり「 length が正しく動くかどうかわかんないけど正しく動くと信じて書く」って感覚はない。（単純すぎるってのもあるかもしれんが）

次に、「同じくリストの長さを返す関数、ただしリストの最後から連続した偶数要素の部分がある場合その長さはカウントしない」という関数 length2 を考えてみる。

例えば

(length2 '(1 2 3 4 5)) => 5
(length2 '(1 2 3 4 5 6)) => 5
(length2 '(1 2 3 4 5 6 6 6)) => 5
(length2 '(1 2 3 4 5 6 6 6 7)) => 9

のような感じだ。

length2 を再帰で書くとこうなる:

(define (length2 lst)
 (if (null? lst)
     0
     (let ((rest (length2 (cdr lst))))
       (if (and (zero? rest)
                (even? (car lst)))
           0
           (+ 1 rest)))))

# リストの要素が数字じゃない場合とかの処理は本質じゃないので割愛

こういう場合に (let ((rest (length2 (cdr lst)))) の部分を書くときは、「length2はまだ完成してないんだけど、これから書く部分も含めて全部正しく動くはずだぜ」という感覚を強く感じながら書いてる。

まぁlength2も蓄積変数を1個余分に導入するだけで簡単にループにできそうですけどね。

『プログラミングGauche』を読んだ

フムフムヌクヌクアプアア本としても知られる『プログラミングGauche』を最近読みました(今3周目を読んでます)。

読後の感想ですが、ひとことで言えば『Scheme すごい、Gauche 楽しい』って感じです。
プログラミング自体の初心者には向きませんが、ほかの言語を知っていれば難易度の勾配もゆるやかで、無理なく読み進められる良い本だと思います。

とくに面白かったのは7章（手続き）、18章（マクロ）、 19章（継続）あたりです。
関数プログラミングに触れたことがない人は、7章まで読むとその面白さを体験できると思います。Common Lispを触ったことがある自分でも、Lisp-1での関数プログラミングの気持ちよさは特筆すべきものがありました。あとLispのパワーを顕著に体感できるのが18,19章です。こういうのを知ってしまうと Scheme ならアレができるのに、とか思ってしまいそうです。

以下、Scheme/Gauche/本書に関して面白かったところとかをつらつら書いてみます：