[ 目次, 前節, 次節, 索引 ]

(list (amb 1 2 3) (amb 'a 'b))

(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)

   一つの選択もないamb---式(amb)---は受け入れる値のない式である. 操作的には(amb)は評価すると, 計算を「失敗」させる式と考える: 計算は流失し, 値は生じない. この考えを使い, 特定の述語式pは真でなければならないという要求を次のように表す.

(define (require p)
  (if (not p) (amb)))

ambとrequireがあれば, 上で使ったan-element-of手続きを

(define (an-element-of items)
  (require (not (null? items)))
  (amb (car items) (an-element-of (cdr items))))

   また無限の範囲の選択を表すことが出来る. 次の手続きは与えられたあるn に等しいか, それより大きい整数を返す可能性を持つ.

(define (an-integer-starting-from n)
  (amb n (an-integer-starting-from (+ n 1))))

   抽象的にはamb式の評価は時を多くの分岐に分け, 各分岐では式の一つの可能な値を使って計算が続くと考えられる. ambは 非決定的な選択点(nondeterministic choice point)を表現するという. 動的に割り振られる十分な数の処理装置を持つ計算機があれば, 探索は直截的な方法で実装出来る. 実行はamb式に出会うまで逐次的な計算機のように進行する. amb式に出会うとより多くの処理装置が割り振られ, 選択を示す並列実行のすべてが継続するよう初期化される. 各処理装置は, それが唯一の選択であるかのように, 失敗に出会って終了するか, 更に分岐するか, 終了するかまで逐次的に進行する.45

   他方ただ一つのプロセス(またはほんの僅かなプロセス)しか実行出来ない計算機を持っているなら, 別のやり方で逐次実行することを考えなければならない. 選択点に出会うと, 追従すべき道をランダムに取り上げるよう評価器を修正することを考える. しかしランダムな選択はすぐに失敗へと導かれる. ランダムな選択をし, 失敗でない値を見出すまで評価器を何度も走らせてもよいが, すべての可能な実行経路を 規則的に探索する(systematically search)のがよい. 本節で開発し作業するamb評価器は次のような規則的探索を実装する: 評価器がambの作用に出会うと, まず第一の道を選択する. この選択は更に選択点に導かれるかも知れない. 評価器は常に各選択点で, まず第一の道を選ぶ. 選択が失敗に終れば, 評価器は オートマジカリー46 に最も近い選択点へ バックトラック(backtrack)し, 次の道を試みる. ある選択点ですべての道を調べ尽くしたとすると, 評価器は直前の選択点までバックアップし, そこから再開する. このプロセスは 深さ優先探索(depth-first search)または時間的バックトラック (chronological backtracking)として知られる探索戦略へ通じる. 47

駆動ループ

;;; 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 (quote (1 3 5 8)) (quote (20 35 110)))

;;; Amb-Eval input:
(prime-sum-pair '(19 27 30) '(11 36 58))
;;; Starting a new problem
;;; Amb-Eval value:
(30 11)

(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)))))

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high))
        (hsq (* high high)))
    (let ((j (an-integer-between i high)))
      (let ((ksq (+ (* i i) (* j j))))
        (require (>= hsq ksq))
        (let ((k (sqrt ksq)))
          (require (integer? k))
          (list i j k))))))

43 非決定性プログラミングのambの考えは, 1961年に John McCarthyが初めて書いた. (McCarthy 1967参照)

44 実際, 非決定的に一つの選択を返すことと, すべての選択を返すこととの違いは, われわれの視点に依存する. 値を使うプログラムの視点からは, 非決定性選択は一つの値を返す. プログラムを設計するプログラマの視点からは, 非決定性の選択は可能性としてすべてのあり得る値を返し, 計算は分岐してそれぞれの値は別個に調べられる.

45 これは絶望的に非効率な機構だと反論するかも知れない. 容易に記述出来る問題も, この方法では何百万もの処理系を必要とするであろうし, 殆んどの時間, これらの処理系の大方は暇であろう. この反論は歴史の中でいわれるべきである. 記憶装置は高価な商品だと考えられてきた. 1964年には1メガバイトのRAMは40万ドルした. いまではどのパソコンも数メガバイトのRAMを持ち, 殆んどの時間, そのRAMの大方は使われない. 大量生産の電子機器の値段を過小評価するのは困難である.

46 オートマジカリー:「自動的に, ただし何らかの理由により(一般にはあまりにも複雑なために, あるいはあまりにも見苦しいために, あるいはおそらくあまりにも明白なために)話し手が説明する気にもなれないようなやり方で」 (Steele 1983, Raymond 1993)

47 自動探索戦略をプログラム言語へ 統合するのは長く変化に富んだ歴史を持つ. 非決定性アルゴリズムが探索と自動バックトラックを使って, プログラム言語に巧妙に組み込めるだろうということは, Robert Floyd(1967)が最初に提案した. Carl Hewitt(1969)は自動時間的バックトラックを積極的に支援した Plannerというプログラム言語を発明し. 組込みの深さ優先探索戦略を用意した. Sussman, Winogradおよび Charniak(1971)は, この言語の部分集合 MicroPlannerを実装し, 問題解決とロボットの計画などの仕事に使った. 論理や定理証明から生じた同様の考えはエディンバラやマルセーユでの Prologという優美な言語の創成に導いた(これについては4.4節で論じる). 自動探索について長い挫折の後, McDermottと Sussman(1972)は Conniverという言語を開発した. これは探索戦略をプログラマの制御のもとにおく機構を持っていた. しかしこれは扱い難いことが分ったので, Sussmanと Stallman(1975)は, 電気回路の記号解析の方法を研究しながら, より制御しやすい解決法を見出し, 事実を接続する論理的依存を追跡することに基づく, 時間的でないバックトラック法を開発した. この技法は 依存主導バックトラック (dependency-directed backtracking)として知られるようになった. 彼らの方法は複雑だが, 冗長な探索をあまりしないので, かなり効率のよいプログラムが作れた. Doyle(1979)と McAllester(1978, 1980)はStallmanとSussmanの方法を一般化, 明確化し, 探索を形式化する新しいパラダイムを開発した. それは 首尾一貫システム(truth maintenance)といわれている. 新しい問題解決システムはすべてある程度の首尾一貫システムを基盤に使っている. 首尾一貫システムを構築する優れた方法と, 首尾一貫システムを使った応用については Forbusおよび deKleer 1993を参照のこと. Zabih, McAllesterおよび Chapman 1987は, ambに基づいたSchemeの非決定性拡張を述べている. これは本節に述べた解釈系と同様だが, 時間的バックトラックでなく, 依存主導バックトラックを使っているので, 遥かに複雑である. Winston 1992には, 両方のバックトラックの紹介がある.

[ 目次, 前節, 次節, 索引 ]