コンピュテーション」という本を読んでいる。155,740Amazon.co.jpで詳細を見る前半が形式言語とオートマトンの話で、決定性有限オートマトン→非決定性有限オートマトン→決定性プッシュダウンオートマトン→非決定性プッシュダウンオートマトン→決定性チューリングマシン→非決定性チューリングマシン、というように簡単なものから最強のものまで一巡りする。後半はラムダ計算とプログラミング?。RubyのProcだけでプログラムを書いてやろうという試みから始まる。(当然「int」とかも使わない。)型なしラムダ計算風のものをRubyで実装しようということである。この章にものすごい詰まるポイントが出てきた。それが表題のYコンビネーター。ちなみにこの本ではラムダ計算もRubyでやってるんだけど、絶対Javascriptのほうがわかりやすいと思う...。Rubyでは構文解析→AST構築用のライブラリがあるというのが強みだけど、ラムダ式をProcで書くのは読みづらい。このYコンビネーターを理解するのに3日くらいかかったけど、その三日間の中で一番役に立った記事が以下の記事。-IT戦記ここで改めてYコンビネーターの説明するのも面倒なのでぜひこの記事を読んで勉強してほしい。この記事だけだとわかりにくい点も多々あると思うので二点ほど補足説明。(本当はこの記事で出てくるのはYコンビネーターじゃなくてZコンビネーターというところも補足しておきたい...※)まず「Yコンビネーターとは何か」というと、ラムダ計算で再帰を実現するために必要なものだそうだ。bikkuri(n-1);}}といったように関数内で自分の名前を呼ぶことで自分を再帰呼び出しする。関数に名前をつけることができないとしたら?(ラムダ計算なので)当然自分に名前がないので、自分を呼ぶことができない。???(n-1);}}これを解決するのがYコンビネーター。Yコンビネーターの基本的な考えとしては、さきほどのbikkuriのように再帰する関数の引数にその関数自身を渡すというもの。f(n-1);}}これがわかるだけで、Yコンビネーターが何をやっているかとてもイメージしやすくなった。x)))と表わされるけど、ここでなんでxxなんてのがでてくるのかの理由が以上でわかると思う。(xという表記がわかりにくさを生む原因なんだけど、このxは値じゃなくて関数が入るところ)gという関数は、関数xを与えると内部でその関数xを呼ぶ関数x'を返す関数である。x)のだいたいの意味。(これも表記がわかりづらい。g(x(x))と書いてくれればいいのに。ラムダ式を書いているといったいこれはなんなのかわからなくなってしまうことがある。いう場合、きちんと各部分がなんなのか線を引きながら読むとわかりやすくなる。2;})(1);となるのはすぐわかると思うけど、(λf.(λx.f(λy.xxy))(λf.(λx.f(λy.xxy)))Mという式を与えられると一体何がなんなのか見失いやすい。(λx.f(λy.xxy))(λx.f(λy.xxy))に相当する関数)})(M);という意味。この二点を頭に入れたうえではじめに紹介した記事を読めばきっと理解できるはず。※RubyやJavascript、というか世の中のほとんどのプログラム言語では評価戦略の都合上Yコンビネーターを使うと無限に再帰呼び出しが発生してスタックオーバーフローを起こすそうだ。このためYコンビネーターをちょっと変えたZコンビネーターを使う。bikkuri(n-1);}}これはnが与えられ条件が評価されたうえでif節かelse節のどちらかだけを評価する。適切な引数が与えられれば再帰呼び出しのゴールにいずれたどり着くので無限ループにならない。(bikkuri("a");とかやってみれば...)しかしYコンビネーターを使った再帰的な関数呼び出しは各再帰的関数呼び出しステップで具体的な引数が与えられるまえに再帰的な関数を返すようになっている。そこで各再帰的関数呼び出しステップでちゃんと引数を与えて条件の評価を可能にすることで、if節かelse節どちらかだけを評価すればいいように改良したのがZコンビネーター、ということだと思っている。プログラミング系の記事で「Yコンビネーター」という言葉が出てきたら基本的にZコンビネーターをさしているんだけど、言葉選びは気をつけたほうがいいと思いますね。始めたブログも気づけば10年を超えてました。(bloggerから移転)ブログを書くことで自分と向き合っています。代ゼミ!第一志望は、ゆずれない。トップに戻るプライバシーポリシー・免責事項お問い合わせ未来世紀アラカワ引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。