定義できない関数will-stop?

The Little Schemer

引数で与えられた関数が停止するかどうか調べる関数will-stop?を書いてみろよ。
あ、問題を簡単にするために、引数で与える関数の引数は空リストしか考えなくていいや。

というLeftcolumn氏の仰せです。

まず、will-stop?の引数として、lengthを考える。
lengthの引数に空リストしか考えなくていいい、とのことで

gosh> (length '())
0

だから、will-stop?の引数にlengthを食わせると評価は止まる。
つまり、(will-stop? length)は#tへ評価されるわけだな。
簡単、簡単。


次はwill-stop?にeternity関数（定義は最後）を食わせてみる。
eternityは評価が止まらない関数だから、(will-stop? eternity)は#fへと評価される、と。
これも簡単。


次に、will-stop?に次のような関数を食わせてみる。

(define last-try
  (lambda (x)
    (and (will-stop? last-try) (eternity x))))

うむ、ちょっと難しくなったぞ。でも、wiil-stop?の値としては#tか#fの2種類しかない。
しらみつぶしに調べても、2種類。ということで、どっちも調べる。

  • (will-stop? last-try)が#fの場合

(will-stop? last-try)は#fだから、(and (will-stop? last-try) (eternity x))の部分は常に#fだ。
...って、おい！(last-try '())の計算止まっちゃったよ。
「(will-stop? last-try)の値が#f、つまりlast-tryを引数にwill-stop?を評価すると計算が止まらない」という前提で始めたけど、last-tryの計算が終了してしまった。

  • (will-stop? last-try)が#tの場合

(and (will-stop? last-try) (eternity x))の値を決めるには(eternity x)が決まらないといけない。
だけど、(eternity x)は評価が終わらない関数。
つまり、いつまでたっても(and (will-stop? last-try) (eternity x))の値は決まらない。
(last-try '())の計算は終わらないわけだな。
...って、前提は(will-stop? last-try)が#tだったじゃんか！


ってな感じで、どう仮定をしても結論は仮定と全く逆になってしまうわけだ。
こりゃ関数の評価が終了するかどうかを事前に知る関数は定義できなさそうだねー、ってことで終了。


面白いなぁ。凝り固まった頭に、いい体操になった。


最後にeternity関数の定義をば。

(define eternity
  (lambda (x)
    (eternity x)))