『Scheme手習い』読書会 第14回
『Scheme手習い』読書会の14回目です。範囲としては9章途中(P153)〜9章末(P175)です。実際には友人に合わせることと復習を兼ねて9章頭から読んでいます。
defineなしに再帰的定義を作成する過程はすごいです。Yコンビネーターという関数を作成します。
- 9章 ……もう一度、もう一度、もう一度、……(続き)
- 全関数は答えを返してくれる関数、部分関数は答えを返してくれない場合がある関数。
- 関数alignが全関数かの確認。関数length*,関数weight*を用いて実施。
- これは本当にこれで全関数かどうか確認できたのか、僕には理解できない。
- 関数shuffleが全関数かの確認。反例として、ゴールに向けて進展しない引数の例を見つけることで部分関数であることを確認。
- 関数Cが全関数かどうかの確認。確認が難しい(数学的に証明されていない)例。
- 「ローター・コラッツ」による、「コラッツの問題」や「コラッツの予想」と呼ばれるものらしい。詳細はWikipedia参照。
- ローター・コラッツ - Wikipedia(ja)
- Lothar Collatz - Wikipedia(en)
- コラッツの問題 - Wikipedia(ja)
- Collatz conjecture - Wikipedia(en)
- 関数Aは全関数だが、計算量が大きく、現実的な時間で答えを返してくれないという例。
- 「ヴィルヘルム・アッカーマン」による、「アッカーマン関数」と呼ばれるものらしい。詳細はWikipedia参照。
- ヴィルヘルム・アッカーマン - Wikipedia(ja)
- Wilhelm Ackermann - Wikipedia(en)
- アッカーマン関数 - Wikipedia(ja)
- Ackermann function - Wikipeida(en)
- 関数will-stop?の定義が可能かの確認。停止性を確認する関数の定義である。停止性を確認する関数は正確に動作するものを作れないことが証明されている。
- 「アラン・チューリング」による「停止性問題」、または「クルト・ゲーデル」による「不完全性定理」に関連するものらしい。詳細はWikipedia参照。
- アラン・チューリング - Wikipedia(ja)
- Alan Turing - Wikipedia(en)
- 停止性問題 - Wikipedia(ja)
- Halting problem - Wikipedia(en)
- クルト・ゲーデル - Wikipedia(ja)
- Kurt Gödel - Wikipedia(en)
- ゲーデルの不完全性定理 - Wikipedia(ja)
- Gödel's incompleteness theorems - Wikipedia(en)
- defineとは何か。再帰的定義とは何か。(以下9章終わりまで続く内容)
- 今までdefineで名前を付け、それにより再帰呼び出しを行い、繰り返しを行ってきたことを確認。
- 関数lengthをdefineなしで書く。
- (1)長さ0のリストのみ答えを返す関数length0を定義(再帰呼び出し部分には答えを返さない関数を設定)
- (2)長さ1以下のリストに答えを返す関数length<=1を定義(再帰呼び出し部分にlength0を設定)
- (3)同様に長さn以下のリストに答えを返す関数を書こうとすると、関数定義が延々と続くことを確認
- 再帰のためには場合によっては無限の関数定義を書かないといけない、ができない。よって繰り返しされている部分の抽出を実施していく
- (4)再帰呼び出し部分の関数を引数に取る形に書き換える。
- (5)「関数を引数に取り、次に呼び出す関数を返す関数」に対して、length0の動きをするように関数を渡す形に書き換える。
- (6)length部分がdefine使用時に近い形になるように書き換え。
- (7)length部分を外に抜き出し、汎用的なものにする。
- この汎用的な部分をYコンビネーターと呼ぶらしい。本文中にはないが、不動点コンビネーターというものの一種らしい。
- Yコンビネーターは関数を引数にとり、その関数を呼び出す。呼び出し時の引数として、その関数が次に呼び出す関数(Yコンビネーターが引数に取った関数と同様のもの)を設定する。
- 不動点コンビネータ - Wikipedia(ja)
- Fixed point combinator - Wikipedia(en)
