SICP 4.3 Variations on a Scheme -- Nondeterministic Computing

ここは全く予備知識の無い分野。Prologへの布石の様に思える。

ノート

非決定論的コンピューティング？
評価器に「automatic search」を組み込む。遅延評価よりも言語に対して大きな変更となる。

非決定論的コンピューティングは『生成してテストする』タイプのアプリケーションに向いている。
これまでに二つの正の整数の和が素数となる組み合わせを探すやり方を二通り実装した。どちらにしても取り得る全ての組み合わせを生成して和が素数であるかを確認していた。組み合わせを作る部分は問題としては本質的な部分ではなかった。

『aはlist1のある数で、bはlist2のある数。このaとbに於いて(prime? (+ a b))を満足するaとbをリストにする』みたいなプログラム。

普通の言語の実行モデルではrequireの所で条件が成り立たなければ、別のa、bの組み合わせを生成してもう一度チェックする様なループ（もしくは再帰）で書かれていたが、非決定論的コンピューティングの実行モデルではrequireが成り立たないとaとbを選んだ所まで戻ってもう一度進む。

なので組み合わせも含めて値の候補を選ぶ部分と、失敗した時に候補を選び直す箇所まで逆戻りする仕組みを実行モデル自身が勝手にやってくれて、プログラムとして書く必要がない様なシステム。

非決定論的コンピューティングでは式が複数の値の候補を持っている。システムがその候補から一つ値を選び（どれを選んでどれが残っているのかはちゃんと管理して）式の評価を進めて、評価が失敗したら候補を選んだ所まで戻って来る仕組みをサポートする。

4.3.1 Amb and Search

The expression (amb ... ) returns the value of one of the n expressions ``ambiguously.''

ambiguously（曖昧に）とか言われても意味は分からない。要は、まずどれかを選んで返すので返す値は普通の値。ポイントは

過去に選んだ候補、今選んだ候補、残っている候補は管理されている事
この先の式の評価が失敗した時にここまで戻って来るので、その時には残っている候補から値を選ぶ事

この仕組みがシステムによってサポートされる。値が返ってからは普通に式の評価が進む。

ambiguouslyと言う言葉は余り気にしないで読み進めた方が良さそう。

(list (amb 1 2 3) (amb 'a 'b))は６つの値を持つ可能性があるが、この式を評価した時に一遍に６つのペアに展開される訳ではない。まずどれかの組み合わせが出来てその先の式の評価に進む。もし式の評価が失敗するとここに戻って来る。

ambに値の候補が一つしか無いときはただの値と同じ。式の評価に失敗してここに戻って来ても他に候補は無いので更に前のambまで戻る事になる。

ambに値が無い状態は式の評価の失敗を意味する。つまり(amb)が評価された時点で直近のambで値を選んだ地点まで戻る事を意味する。

requireは述語をテストして失敗したら意図的に(amb)を評価してシステムに直近のambで値を選んだ地点まで逆戻りさせる。

（恐らく）ambはリストを引数に取れない（一つの値として扱ってしまう）。手続きではないのでapplyは使えない。なので、リストの中から候補を選ぶのにan-element-ofの様な手続きが必要になる。ambはまず(car items)を候補に選びその先の評価で失敗した場合には(an-element-of (cdr items))から候補を選ぶ。ambは構文なので引数は必ずしも直ぐには評価されず、ここで(an-element-of (cdr items))が評価されると思う。(cdr items)に候補が残っていればそこから値が選ばれるが、残っていなければrequireに失敗してもっと前方のamdの箇所まで戻る事になる。

an-integer-starting-fromはan-element-ofの(cdr items)の部分を(+ n 1)で毎回生成している状態。まずnを選び、失敗して戻って来たら(an-integer-starting-from (+ n 1))が呼ばれてn+1が選ばれる、と言う事を失敗して戻って来る度に繰り返す。an-integer-starting-fromと言う名前はストリームの時の様にn以降の全ての整数のリストの様に思えるが、n以降のどれか一つの値である。

amdが選択のポイントで、ここにプログラムが到達した時点で選択肢の数だけプロセス（かスレッド）をforkして（テキストはプロセッサの例で説明しているが）、それぞれのプロセスにひとつひとつの選択肢を割り当ててその後の計算を進める様にイメージしても良い。

あるいはamdに到達した時点で本当に適当に値を選んで評価を進める事も可能。だが、ここでは系統立てで候補を最初から順番に選んで、選んだ値がその先の評価で失敗した場合には選択したポイント（失敗した所から直近の選択ポイント）まで戻って（バックトラック）して残りの候補からまた選び直して成功するまで評価を続ける。ある選択ポイントに戻った時に候補が残っていなければ更に一つ前の選択ポイントまで戻る。この候補の探しかたは『深さ優先探索』（あるいはchronologycal backtrack：訳語は良く分からない）である。

これはforkしたプロセス達は取り敢えずサスペンドしておいて一つが失敗したら次のプロセスを進めるのと同じ事。メモリを共有するスレッドでは難しいがプロセスをforkするモデルは実装不可能ではないかも。システムのプロセス数の制限に引っ掛かるかもしれないけど。

Driver loop

amd評価器のdriver-loopは問題が与えられると成功した結果を表示する。ここでtry-againとタイプすると強制的に失敗した事にしてバックトラックして次の候補を試す。try-again以外をタイプすると前の問題は忘れて次の評価を始める。

ここで4.3.3節の実装を取り込む。実装の詳細は再び4.3.3節で検討する。4.1.7節のanalyzeを分離した実装をベースにするとの事だが、脚注にある様にletが実装されている事が前提なので、Exercise 4.22の結果をベーストする。

まずは動かしてみる。

;;; Amb-Eval input:
(amb 1 2 3)

;;; Starting a new problem ;;; Amb-Eval value:
1
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
2
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
3
;;; Amb-Eval input:
try-again
;;; There are no more values of
(amb 1 2 3)
;;; Amb-Eval input:
.

可変長引数をサポートしていないので、仕方が無いのでlistをプリミティブとして登録して。

;;; Amb-Eval input:
(list (amb 1 2 3) (amb 'a 'b))

;;; Starting a new problem ;;; Amb-Eval value:
(1 a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(1 b)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(2 a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(2 b)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(3 a)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(3 b)
;;; Amb-Eval input:
try-again
;;; There are no more values of
(list (amb 1 2 3) (amb 'a 'b))
;;; Amb-Eval input:
.

(amb 'a 'b)の方が後から評価されている事が分かる。
an-element-ofの動作確認。

;;; Amb-Eval input:
(define (require p)
  (if (not p) (amb)))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(define (an-element-of items)
  (require (not (null? items)))
  (amb (car items) (an-element-of (cdr items))))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(an-element-of '(1 3 5 8))

;;; Starting a new problem ;;; Amb-Eval value:
1
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
3
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
5
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
8
;;; Amb-Eval input:
try-again
;;; There are no more values of
(an-element-of '(1 3 5 8))
;;; Amb-Eval input:
.

an-integer-starting-fromの動作確認。

;;; Amb-Eval input:
(an-integer-starting-from 10)

;;; Starting a new problem ;;; Amb-Eval value:
10
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
11
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
12
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
13
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
14
;;; Amb-Eval input:
.

比較演算子、not、remainderをプリミティブとして登録して。

;;; Amb-Eval input:
(define (square x)
   (* x x))
(define (divides? a b)
   (= (remainder b a) 0))
(define (find-divisor n test-divisor)
   (cond ((> (square test-divisor) n) n)
         ((divides? test-divisor n) test-divisor)
         (else (find-divisor n (+ test-divisor 1)))))
(define (smallest-divisor n)
   (find-divisor n 2))
(define (prime? n)
   (= n (smallest-divisor n)))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(define (require p)
  (if (not p) (amb)))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(define (an-element-of items)
  (require (not (null? items)))
  (amb (car items) (an-element-of (cdr items))))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(define (prime-sum-pair list1 list2)
  (let ((a (an-element-of list1))
        (b (an-element-of list2)))
    (require (prime? (+ a b)))
    (list a b)))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))

;;; Starting a new problem ;;; Amb-Eval value:
(3 20)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(3 110)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(8 35)
;;; Amb-Eval input:
try-again
;;; There are no more values of
(prime-sum-pair '(1 3 5 8) '(20 35 110))
;;; Amb-Eval input:
(prime-sum-pair '(19 27 30) '(11 36 58))

;;; Starting a new problem ;;; Amb-Eval value:
(30 11)
;;; Amb-Eval input:
.

Exercise 4.35

(define (an-integer-between min max)
  (require (<= min max))
  (amb min (an-integer-between (+ min 1) max)))

requireで条件をつけてあげればOK。
動作確認。

;;; Amb-Eval input:
(define (an-integer-between min max)
  (require (<= min max))
  (amb min (an-integer-between (+ min 1) max)))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(an-integer-between 10 15)

;;; Starting a new problem ;;; Amb-Eval value:
10
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
11
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
12
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
13
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
14
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
15
;;; Amb-Eval input:
try-again
;;; There are no more values of
(an-integer-between 10 15)
;;; Amb-Eval input:

ピタゴラス数を探す。

;;; Amb-Eval input:
(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high)))
    (let ((j (an-integer-between i high)))
      (let ((k (an-integer-between j high)))
        (require (= (+ (* i i) (* j j)) (* k k)))
        (list i j k)))))

;;; Starting a new problem ;;; Amb-Eval value:
ok
;;; Amb-Eval input:
(a-pythagorean-triple-between 1 20)

;;; Starting a new problem ;;; Amb-Eval value:
(3 4 5)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(5 12 13)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(6 8 10)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(8 15 17)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(9 12 15)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(12 16 20)
;;; Amb-Eval input:
try-again
;;; There are no more values of
(a-pythagorean-triple-between 1 20)
;;; Amb-Eval input:
.

Exercise 4.36

組み合わせi、j、kを生成してrequireで失敗した時にはkを選び直す事になる。an-integer-betweenを使っている時にはkが上限に達するとjを選び直す。これを繰り返して更にjが上限に達するとiを選び直している。
ところがan-integer-starting-fromを使うとkを選び直す時に上限が無いので、kだけを更新してiとjは永久に更新されないので上手く動作しない。

requireを増やしてもバックトラックがkのambより前には戻らない。なのでiだけは上限無しにして、jとkはiに関連づけて上限を決める。
iとjは交換可なので1<=j<=iとする。kの最小値は√2iだがここではi<=k<=2iとする。

(define (a-pythagorean-triple)
  (let ((i (an-integer-starting-from 1)))
    (let ((j (an-integer-between 1 i)))
      (let ((k (an-integer-between i (* 2 i))))
        (require (= (+ (* i i) (* j j)) (* k k)))
        (list i j k)))))

実行結果

;;; Amb-Eval input:
(a-pythagorean-triple)

;;; Starting a new problem ;;; Amb-Eval value:
(4 3 5)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(8 6 10)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(12 5 13)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(12 9 15)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(15 8 17)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(16 12 20)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(20 15 25)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(21 20 29)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(24 7 25)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(24 10 26)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(24 18 30)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(28 21 35)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(30 16 34)
;;; Amb-Eval input:

Exercise 4.37

こちらの方が効率は良い筈。そもそも組み合わせとして二組の数しか扱っていないのでkを走査しない分、効率は良い。
実際の計算速度の観点で、最初のrequireで余計なkは生成しない様にして「フレームを作る」「平方根を取る」「integer?」の分だけ節約しているとも言えるが、その為に「hsqの計算」「ksqの計算」「require」が増えているのでこれに関しては微妙。

プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート