kb84tkhrのブログ

何を書こうか考え中です

Scheme手習い(16) Yコンビネータ

ラスボス1来ました

Yコンビネータってのはこれ
正確には適用順Yコンビネータって言うらしいです

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

何がなんだかわかりません
こんなの読んでふむふむとかわかっちゃう人がいるんでしょうか
恐ろしいです

順番に見ていくしかありません

(define ...)は何ですか。

何でしょうか

では、再帰的定義とは何ですか。

何でしょう
哲学でしょうか

これはあのlength関数ですか。

(define length
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (length (cdr l)))))))

そうですね

次の関数は何をするものでしょう。

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 (eternity (cdr l))))))

なんでしょうか
lengthとそっくりですけど、eternityってあの無限ループするやつでしょうか

空リストの長さを決めますが、ほかには何も決めません。

確かにおっしゃるとおりです
「決める」より「求める」と書いたほうが馴染みがある感じ

> ((lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (eternity (cdr l))))))
   '())
0
> ((lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (eternity (cdr l))))))
   '(1))
(応答なし)

eternityの次くらいに部分的な関数ですね

この関数は便宜上length0と呼びます
eternityのところをlength0自身に置き換えてやると
判定できる要素数がひとつ増えて空リストまたは1要素のリストの長さを求める関数になります

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 ((lambda (l)
                   (cond
                     ((null? l) 0)
                     (else (add1 (eternity (cdr l))))))
                 (cdr l))))))

これはlength1
この調子でlength2、length3とどんどん置き換えてやれば
任意の数までの要素を含むリストの数が数えられるようになります

でも無限の関数は書くことはできません。

そうですね

これらのプログラムにはすべてlengthに似た関数があります。おそらくこの関数を抽象化する必要があるのでしょう。

どんどん置き換えるかわりに関数呼び出しにするってことですね
DRY原則

lengthと似ているけれども(lambda (length) ...)で始まる関数が必要です。

なにがしたいんでしょうか

このことでしょうか。

((lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))
 eternity)

ははーん
defineで名前を付けられないからlambdaの引数にして名前を付けるってわけですね
どうやらここがひとつのミソ

これはlength0を生成します。

たしかに、lengtheternityに置き換えてやればlength0そのものです
length1は以下のようになります
length0のeternityの部分をlength0に置き換えてやればできあがり

((lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))
 ((lambda (length)
    (lambda (l)
      (cond
        ((null? l) 0)
        (else (add1 (length (cdr l)))))))
  eternity))

引数を置き換えてやればlength1になることはすぐ確認できます
length2から先も同様
でもなにかよくなったんでしょうか?
eternityのあたりでひとひねりしたらいいことありそうな予感はします

近いですが、まだ繰り返しがあります。

そうですね。コピペコーディングはよくないです

lengthを引数として取り、lengthに似た関数を返す関数に名前をつけましょう。

lengthを引数として取り、lengthに似た関数を返す関数」っていうのはこれですね

(lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))

名前をつけるにはlambdaの引数にすればいいんでした

((lambda (mk-length)
   ...)
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

これで、...のところでは「lengthを引数として取り、lengthに似た関数を返す関数」を
mk-lengthと書けるようになりました
lengthを引数として取り、lengthに似た関数を返す関数」にeternityを渡したものが
length0でしたので、length0はこうなります

((lambda (mk-length)
   (mk-length eternity))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

length0のeternityのところをlength0自身に置き換えるとlength1になるんでした

((lambda (mk-length)
   (mk-length
    (mk-length eternity)))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

おお、重複が消えました
D・R・Y! D・R・Y!
これでたくさん書いても平気です

((lambda (mk-length)
   (mk-length
    (mk-length
     (mk-length
      (mk-length eternity)))))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

あとは無限に書けばできあがり!

再帰とはどんなものですか。

任意の関数へのmk-lengthの適用が無限に連鎖しているようなものです。

任意の関数?
ってeternityのこと?

実際に無限の連鎖が必要ですか。

もちろん、そんなことはありません。

長さを調べたいリストは有限ですもんね

何回必要かを推測することはできるでしょうか。

長くても100個まで、とか仕様書に書いてあればいいんですけどそうでなければ無理
たぶん100個くらいで充分なんで、とか言ったら品証の人が怒るんじゃないですかね

十分に大きな数を推測しなかったことはいつわかりますか。

最も内側のmk-lengthに渡されたeternityを実行するときです。

eternityを呼んじゃったら負けですね

この時点でeternityに対してmk-lengthをもう一回実行するように書くとどうなりますか。

言ってる意味がわかりません

どんな関数がmk-lengthに渡されるのか誰も気にしないので、

どうせeternityは呼ばれちゃいけないので、何を渡しても同じ
だからさっき「任意の関数」って言ってたんですね

最初にmk-lengthを渡すこともできますね。

まあいいんじゃないですかね
なんで渡したいのか知りませんけど

そうすれば、eternityに対してmk-lengthを適用した結果をcdrに対して
適用することで、連鎖をもう一段先に進めることができます。

ええとどういうことですか
ええとええと

長過ぎるリストを引数にとったとき、これまで(eternity (cdr l))ってなってた呼び出しが
((mk-length eternity) (cdr l))になってくれるってことですかね

最初にeternityを渡すのをやめてmk-lengthを渡すってことは、

((lambda (mk-length)
   (mk-length eternity))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

eternitymk-lengthに変えるってことですね

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

eternityがどっかいっちゃいました
さっき思ってたことと違いますね
わかりません!

脳内で動かしてみます
空リストを渡せば0が返ります

空でないリストを渡すとlength0は無限ループに入りましたがこれはどうなるでしょう
連鎖がもう一段先に進むでしょうか?
(1)を渡してみます
lnull?ではないので、(length (cdr l)) つまり(mk-length '())が呼ばれます
ここでmk-length(lambda (length) ...)lengthには'()が渡されます
なんかおかしいです

さらにlengthmk-lengthという名前に変更することさえできます。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (mk-length (cdr l))))))))

どういうリファクタリングでしょうか
間違いじゃないのはわかるんですけど

なぜ、こんなことをしたいのでしょうか。

気になりますね

すべての名前は同等ですが、ある名前はほかのものよりさらに同等なのです。

何を言っているんでしょうか

そうです。名前は一貫性を持って使えば、それでよいのです。

いややっぱ目的が見えてないと

そしてmk-lengthlengthよりさらに同等な名前なのです。

そう言われてもわかりませんが、今や渡されてるのはmk-lengthですからね
そういうことでしょうか

mk-lengthmk-lengthに渡される今となっては、この引数をさらなる再帰
生成するのに使えますか。

はい。mk-lengthを1回適用すればlength1が得られます。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((mk-length eternity) (cdr l))))))))

mk-length(mk-length eternity)になりました
(mk-length eternity)はまんまlength0ですので
さっきと違って再帰呼び出しがエラーになりません
全体としてはlength1になります

(((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond ((null? l) 0)
            (else (add1 ((mk-length eternity) (cdr l))))))))
 l)

の値はなんですか。ここでl(apples)です。

ここは練習

  (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l))))))))
   '(apples))

スタート
全体を見ると1〜6行目が関数で、7行目が引数
引数はこのままでいいので関数の方を変形します
1〜6行目の中では、1〜2行目が関数で、3〜6行目が引数
(mk-length mk-length)mk-lengthを3〜6行目のコードで置き換えます

= (((lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l)))))))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l))))))))
   '(apples))

今度は、1〜4行目の関数に、5〜8行目の関数を引数として与えます

= ((lambda (l)
     (cond ((null? l) 0)
           (else (add1 (((lambda (mk-length)
                           (lambda (l)
                             (cond ((null? l) 0)
                                   (else (add1 ((mk-length eternity) (cdr l))))))) 
                         eternity) (cdr l))))))
   '(apples))

1〜7行目の関数に、(apples)を引数として与えます
内側のlは内側のlambdaの引数なので置き換えません

= (cond ((null? '(apples)) 0)
        (else (add1 (((lambda (mk-length)
                        (lambda (l)
                          (cond ((null? l) 0)
                                (else (add1 ((mk-length eternity) (cdr l))))))) 
                      eternity) (cdr '(apples))))))

(null? '(apples))ではないので、

= (add1 (((lambda (mk-length)
            (lambda (l)
              (cond ((null? l) 0)
                    (else (add1 ((mk-length eternity) (cdr l))))))) 
          eternity)
         '()))

1〜4行目の関数に、eternityを引数として与えます
あとはもういいかな

= (add1 ((lambda (l)
           (cond ((null? l) 0)
                 (else (add1 ((eternity eternity) (cdr l)))))) 
         '()))
= (add1 (cond ((null? '()) 0)
              (else (add1 ((eternity eternity) (cdr '()))))))
= (add1 0)
= 1

できました
複雑な形でどこから手をつければいいか悩みますが、感覚でなんとか

これは2回以上できますか。

はい。mk-lengthを自分自身に渡し続ければ、必要なだけ実行することができます。

次の関数はなんと呼ぶのがよいでしょう。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((mk-length mk-length) (cdr l))))))))

もちろん、lengthです。

ああそうですね
理屈上はね

ってこれ動くの!

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 ((mk-length mk-length) (cdr l))))))))
   '(1 2 3))
3

てっきりYコンビネータが完成するまで動かないものだと思ってました
動くと思ってみればたしかに動かない理由はないですね
(mk-length mk-length)がつまりlengthそのものって感じ