Scheme手習い(18) Yコンビネータ(3)
関数を再帰させることができればYコンビネータも峠を越えたんじゃないでしょうか
あとは、形を整えてやるだけのはずですから
defineなしで再帰できるようになった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))))))))先回りして目指す形はこれ
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l))))))))↓の、「lengthに似た関数」（なんか名前ないのかな）を与えれば再帰する関数になる
便利な関数を取り出したいってことです
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))元の形と目指す形を見比べると、(lambda (l) ...)の部分が
「lengthに似た関数」の中身に似てますね
元の形の(mk-length mk-length)がlengthに相当してるので
(mk-length mk-length)にlengthと名前をつけてやります
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))これで、「lengthに似た関数」の形が作れました
めでたしめでたし、ではなくて
> (((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))
'(1 2 3))
(応答なし)帰ってきません
しばらくすると「このプログラムはメモリを使いきりました」
何がおかしかったのか追ってみます
評価するには関数と引数を評価してやる必要がありますが
引数はこれ以上評価することはできませんので放置し関数部分に着目します
関数部分がまた(関数 引数)という形ですので上のlambdaのmk-lengthに
下のlambdaを入れてやります
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))わかりづらくなってきましたが前回で初めて再帰したバージョンの形に似ています
全体を見るとやはり(関数 引数)という形ですので上のlambdaのmk-lengthに
下のlambdaを入れてやります
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))))引数のほうが、一つ前に出てきた関数とそっくりの形になりました
引数自体が(関数 引数)という形ですのでこれを評価しようとすると
また同じ形が出てきて再現がありません
mk-lengthを自分自身に何度も何度も適用し続けているからです
そのとおりですね
なにせ
再帰とはどんなものですか。
任意の関数へのmk-lengthの適用が無限に連鎖しているようなものです。
というくらいですから
まさしく文字通りにできあがりました
実際は無限に続けなくても、リストの長さを出すのに十分なだけ繰り返したら
やめてしまっていいんですが
完全に関数の形が確定するまで続き、途中でやめちゃうことはできないってことなんでしょうね
(mk-length mk-length)に名前をつける前はなぜうまくいっていたかというと
elseの中に入っていたので必要なときにしか評価されなかったからということでしょう
一見無限に評価が続いてしまいそうだけど必要な分だけ評価すればいい、っていうと
Haskellで書けば解決しそうな気もしますが軽く検索してみたところでは
別の問題があって簡単じゃないようです
lengthを作る関数から(mk-length mk-length)を抽出した以上、それはそれ以上関数を返してはいません。
意味がわかりません
それって何
誰かおしえてください
でどうするかっていうと、ここが山場2かと思いますけど、
(mk-length mk-length)が1引数の関数を返すとすると、
(lambda (x) ((mk-length mk-length) x))も1引数の関数を返しますか。
返しますね
それが何か？
それでは、以上のことを
mk-lengthの自分自身への適用に対して行ってみましょう。
本ではなぜか(mk-length mk-length)をくくりだす前に戻ってコレやってから
あらためてくくり出し直してますが理由は読み取れてません
くくりだした形のほうで(mk-length mk-length)をlambdaに入れてやっても
同じ形ができあがります
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x) ((mk-length mk-length) x)))))これでまた動くようになってます
> (((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x) ((mk-length mk-length) x)))))
'(1 2 3))
3(mk-length mk-length)を(lambda (x) ((mk-length mk-length) x))に
書き換えたら何が起こって動くようになったんでしょうか
さっきと同じように評価していくと、同じようなステップをたどってこうなります
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x)
(((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x) ((mk-length mk-length) x))))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x) ((mk-length mk-length) x))))) x)))これも(関数 引数)の形ですが、引数の方がさっきは(関数 引数)の形だったものが
今度は(lambda (x) ((関数 引数) x))になってます
これは関数適用ではなくてひとつのラムダ式なのでそのままで関数を適用できます
ここがミソかな
適用するとこうです
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((lambda (x)
(((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x) ((mk-length mk-length) x))))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x) ((mk-length mk-length) x))))) x))
(cdr l))))))こんどは全体がひとつのラムダ式になりました
((lambda (x) ((mk-length mk-length) x)) (cdr l))を評価することになるのは
(null? l)が偽のときだけ
つまり必要な時しか評価しない、が実現されています
ここもミソだな
なのでこれでいったん評価が終わったことになって
この関数を(1 2 3)に適用してやると想定どおり3が返されるというわけです
ふう
いよいよ「lengthに似た関数」に名前をつけて外に出してやります
「lengthに似た関数」は一番外に出してやりたいので、全体をlambdaで囲みます
「lengthに似た関数」にはleという名前をつけます
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x) ((mk-length mk-length) x))))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))動きます
> (((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x) ((mk-length mk-length) x))))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
'(1 2 3))
3コレが完成版で上半分が適用順Yコンビネータと呼ばれてるそうです
たぶん(mk-length mk-length)が裸のままの形が素のYコンビネータ
なんで「適用順」Yコンビネータっていう名前なんでしょうね？
適用順に何かする、というより適用順に評価する処理系でも動くよ、っていう感じですが
(define ... )は正しく動作するといえますか。
言えるんですか？
確かに。いまや再帰とは何かを知っています。
再帰が何かを知っているのとdefineの動作とどういう関係があるんでしょうか
Yコンビネータの話のとっかかりは
(define ...)は何ですか
興味深い質問です。(define ...)はwill-stop?に対しては
うまく働かないことを見たばかりです。
でしたが何か解決したんでしょうか
わかりません
(Y Y)は何ですか。
想像もつきません
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))と
(lambda (le)
((lambda (f) (f f))
(lambda (f) (le (lambda (x) ((f f) x))))))ってなんとなく形は似てますけどね
何ともいえませんが一生懸命に動きます。
とにかくメモリを使いきってくれることはわかりました
