問題4-35〜37

｢4.2.3 遅延評価リストとしてのストリーム｣の問題4-32〜34は飛ばしました。このトピックでは、ストリームからcarするまで遅延することができるということで、先頭要素さえも決まっていない状態でもストリームを扱うことができるということで、いろいろと使い道はありそうだと感じました。
そして、｢4.3 Schemeの変形---非決定性計算｣の節に入りました。非決定性言語では、ストリームから要素を選択するという作業を抽象化することができると捉えていますが、いまいち全貌を掴めないままでいます。問題を解きながら理解を深めていこうと思っています。
問題4-35。an-integer-betweenを実装します。二つの数値の間にある値を次々と取得する手続きです。

(define (an-integer-between low high)
  (require (<= low high))
  (amb low (an-integer-between (+ 1 low) high))))

lowがhighを越えると、requireは(amb)を返し、計算が失敗したと判断します。計算に失敗すると、バックトラックして、他の可能性を試みます。a-pythagorean-triple-betweenにおけるrequireの動きは、まずkがhighになるまで探索を繰り返します(本文の例文を見ると、後方のambが先に動くようですが、このあたりは実装を見ないとわかりません)。kがhighになってもrequireが要求する条件を満たさなければ、kを一つ戻して、jをインクリメントしていきます。このようにして、i,j,kの全てがhighになるか、requireの条件を満たすようになるまで、探索が続くのではないかと思います。
問題4-36。上記の通り、an-integer-betweenにはhighという停止条件があるため、その範囲内での探索に限定することができますが、これをan-integer-starting-fromにしてしまうと、永遠にインクリメントしていきますので、問題4-35の手続きでこれを使ってしまうと、iとjが1のまま、kがどんどん大きくなっていき、requireを満たす組み合わせを見つけることができないのではないのではないでしょうか。これを防ぐ為の手段についてまでは、思考を深めることができませんでした。
問題4-37。Benの実装の場合、an-integer-betweenを使っているのはiとjだけです。kについてはiとkをそれぞれ二乗して足した値をsqrtして、その結果が整数かどうかを調べることによって探索しています。そのため、k自体がan-integer-betweenによって一つずつ探索していくという操作がありません。問題4-35のバージョンでは、この処理がある分、非効率になってしまうのではないかと思いました。