HOME もうひとつの Scheme 入門 download 書き込む

18. 非決定性

1. 初めに

非決定性は問題を記述するだけで答えが得られるようにするアルゴリズムです。 プログラムは選択肢の中から条件に合うものを自動的に選び出します。 この手法を使うと論理プログラムを容易に書くことができます。

例えば、 

> (let ((i (amb 4 6 7))
      (j (amb 5 8 11)))
  (if (prime? (+ i j))
      (list i j)
      (amb)))
(6 5)
のようにすると '(4 6 7) と '(5 8 11) のうちから二つの数の和が素数になる組の１つを返します。 (amb 4 6 7) は、式が値を返すように 4, 6, 7 の中から適切に値を選び、同様に、 (amb 5 8 11) は、式が値を返すように 5, 8, 11 の中から適切に値を選びます。 (amb) は選ぶべき値が無いので失敗を表します。

実際は、amb は深さ優先の探索をしており、(amb c1 c2 c3 ...) は c1, c2, c3, ... を順番に試す探索経路を生成し、 (amb) はバックトラックをします。つまり、非決定性とは、深さ優先探索をプログラマーから隠蔽する 形式化ということができます。一度 amb を手に入れてしまえば、プログラマーは、コンピュータが実際に 何をやっているかを気にしないで論理プログラムを容易に書くことができます。

2. 非決定性の実装

非決定性の実装には継続とクロージャによるバックトラックを用います。 まず、大域変数 fail をそれ自身を書き直す関数として 定義することによってクロージャの連鎖を表します。

2.1. 関数による実装

最初に簡単のため関数を用いて非決定性を定義します。コードは以下の様になります。 まず、大域変数 fail を定義し、初期値をトップレベルに 'no-choise を返す関数にします (22--26 行目)。 次に、関数 choose のなかで fail を再定義することによってクロージャをつなげます。 行きどまりにきたら１つ前の fail を呼び出すことによってバックトラックを実現します。 関数 choose は以下のように動作します。
  1. 選択肢が無いときは (fail) を呼び出します。
  2. 選択肢があるときは、
    1. fail を fail0 に待避させて、継続を使います。
    2. その継続の中で、fail を定義しなおします。新しい fail は自分自身を fail0 に戻した後、 継続に残りの選択肢の choose を渡します。
    3. 継続の外に最初の選択肢を出します。

[code 1] 

01:     ;;; This function is re-assigned in `choose' and `fail' itself.
02:     (define fail #f)
03:     
04:     ;;; function for nondeterminsm
05:     (define (choose . ls)
06:       (if (null? ls)
07:           (fail)
08:         (let ((fail0 fail))
09:           (call/cc
10:            (lambda (cc)
11:               (set! fail
12:                     (lambda ()
13:                       (set! fail fail0)
14:                       (cc (apply choose (cdr ls)))))
15:               (cc (car ls)))))))
16:           
17:     ;;; write following at the end of file
18:     ;;; to initialize the value of the fail.
19:     (call/cc
20:      (lambda (cc)
21:        (set! fail
22:              (lambda ()
23:                (cc 'no-choise)))))
三平方の定理を満たす整数の組を探せるか試して見ましょう。 pythag が三平方の定義を満たす整数を探す関数です。 そのような整数の組が見つかればそのリストを返し、見つからなければ 引数なしで choose を呼び出してバックトラックします。

[sample 1] 

> (define (sq x)
  (* x x))
> (define (pythag a b c)   ;;; pythagorean triples
  (if (= (+ (sq a) (sq b)) (sq c))
      (list a b c)
      (choose)))
> (pythag (choose 1 2 3) (choose 3 4 5) (choose  4 5 6))
(3 4 5)

2.2. マクロによる実装

さて、実際の非決定演算子は引数に式を与えられることもあるので式の評価を制御するためにマクロ定義にする必要が あります。例えば、[sample 2] に示す関数は n 以上の整数の中から適切な値を返すようにしたいのですが、 関数定義の choose を使うと引数がすぐに評価されるためうまく行きません。

[sample 2] 

> (define (an-integer-starting-from n)
  (choose n (an-integer-starting-from (+ n 1))))
> (an-integer-starting-from 1)
;Aborting!: maximum recursion depth exceeded
そこで、[code 1] の関数定義を参考にして、非決定演算子マクロ amb を定義します ([code 2])。 マクロ定義の amb は [code 1] に示した choose と同じ構造をしており、再帰的に自分自身を呼び出します。 なお、[code 1] の 1--5 行目と 20--26 行目は流用します。

[code 2] 

01:     ;;; nondeterminsm macro operator
02:     (define-syntax amb
03:       (syntax-rules ()
04:         ((_) (fail))
05:         ((_ a) a)
06:         ((_ a b ...)
07:          (let ((fail0 fail))
08:            (call/cc
09:     	(lambda (cc)
10:     	  (set! fail
11:     		(lambda ()
12:     		  (set! fail fail0)
13:     		  (cc (amb b ...))))
14:     	  (cc a)))))))
マクロ定義の amb は [sample 3] に示すように引数が式でもちゃんと動作します。 [sample 3] 
> (define (an-integer-starting-from n)
    (amb n (an-integer-starting-from (+ n 1))))
> (an-integer-starting-from 1)
1
> (amb)
2
> (amb)
3
独習 Scheme ３週間や Dave Herman Code には、amb の引数を展開するコードが載っていますが、継続を２種類使うので少し複雑です。 [code 2] の様に再帰的に定義したほうがすっきりします。

2.3. 非決定性プログラムのための補助関数とマクロ

[code 3] に非決定性プログラムを簡潔に書くための補助関数を挙げます。これらの関数を使うと 非決定性プログラムが簡潔に書けます。
(set-of s)
s の成り立つ結果を全て返します。 set-of は以下の様に動作します。
  1. まず、5 行目で結果を保持するリスト acc を定義します。
  2. そして、6 行目で s の結果を v に代入し、それを acc にプッシュします。 let を使わないで、
    (set! acc (cons s acc))
    と書くと s は継続を使った式なので、 最後の値しか acc に反映されません。ちなみに、 fail の値は s を行うとき変化します。
  3. その後 fail を呼び出し、バックトラックして次の解を探します。fail は継続を使っているので、 6 行目で呼ばれたかのように振舞います。
  4. 可能な解が出尽くすと 9 行目の (reverse acc) が呼ばれ、見つかった解のリストを返します。
この定義は amb が最初の引数から順番に探索していくことを前提にしています。
(assert pred)
pred が成り立たないときはバックトラックします。
(an-integer-starting-from n)
非決定的に n 以上の整数を返します。
(number-between a b)
非決定的に a と b の間の整数を返します。

[code 3] 

01:     ;;; returning all possibilities
02:     (define-syntax set-of
03:       (syntax-rules () 
04:         ((_ s) 
05:           (let ((acc '())) 
06:             (amb (let ((v s)) 
07:                    (set! acc (cons v acc)) 
08:                    (fail)) 
09:                  (reverse acc))))))
10:     
11:     ;;; if not pred backtrack
12:     (define (assert pred)
13:       (or pred (amb)))
14:     
15:     ;;; returns arbitrary number larger or equal to n
16:     (define (an-integer-starting-from n)
17:       (amb n (an-integer-starting-from (+ n 1))))
18:     
19:     ;;; returns arbitrary number between a and b
20:     (define (number-between a b)
21:       (let loop ((i a))
22:         (if (> i b)
23:             (amb)
24:           (amb i (loop (+ i 1))))))
set-of を使うと [example 4] に示すように可能な解のセットが返ってきます。

[example 4] 

(define (prime? n)
  (let ((m (sqrt n)))
    (let loop ((i 2))
      (or (< m i)
          (and (not (zero? (modulo n i)))
               (loop (+ i (if (= i 2) 1 2))))))))

(define (gen-prime n)
  (let ((i (number-between  2 n)))
    (assert (prime? i))
    i))

(set-of (gen-prime 20))
;Value 12: (2 3 5 7 11 13 17 19)

3. 非決定性プログラムの例

SICP の問題 4.42. を解いてみましょう。 問題は以下の通りです：

５人の女子生徒が試験を受けた。彼女らの両親は結果に対し過度の関心を持っている、と彼女らは考えている。 そこで彼女らは自宅へ試験についての手紙を書くのに、誰もが１つの正しい情報と１つのうその情報を書こうと 約束した。以下は彼女らの手紙の関係する部分である。
Betty: 「Kitty は試験が２番で私は３番でした。」
Ethel: 「私がトップと聞いてうれしいでしょう。Joan が２ばんでした。」
Joan: 「私は３番でした。可哀想な Ethel はビリでした。」
Kitty: 「私は２番になりました。Mary は４番でしかありませんでした。」
Mary: 「私は４番でした。トップの座は Betty がとりました。」
５人の女子生徒の本当の順番はどうなっているのか。

[code 4] の様なプログラムを書いて解きます。

[code 4] 

01:     (define (xor a b)
02:       (if a (not b) b))
03:     
04:     (define (all-different? . ls)
05:       (let loop ((obj (car ls)) (ls (cdr ls)))
06:         (or (null? ls)
07:             (and (not (memv obj ls))
08:                  (loop (car ls) (cdr ls))))))
09:     
10:     ;;; SICP Exercise 4.42
11:     (define (girls-exam)
12:       (let ((kitty (number-between 1 5))
13:             (betty (number-between 1 5)))
14:         (assert (xor (= kitty 2) (= betty 3)))
15:         (let ((mary (number-between 1 5)))
16:           (assert (xor (= kitty 2) (= mary 4)))
17:           (assert (xor (= mary 4) (= betty 1)))
18:           (let ((ethel (number-between 1 5))
19:                 (joan (number-between 1 5)))
20:             (assert (xor (= ethel 1) (= joan 2)))
21:             (assert (xor (= joan 3) (= ethel 5)))
22:             (assert (all-different? kitty betty ethel joan mary))
23:             (map list '(kitty betty ethel joan mary) (list kitty betty ethel joan mary))))))
24:     
25:     ;;; Bad answer for ex 4.42
26:     (define (girls-exam-x)
27:       (let ((kitty (number-between 1 5))
28:             (betty (number-between 1 5))
29:             (mary (number-between 1 5))
30:             (ethel (number-between 1 5))
31:             (joan (number-between 1 5)))
32:         (assert (xor (= kitty 2) (= betty 3)))
33:         (assert (xor (= kitty 2) (= mary 4)))
34:         (assert (xor (= mary 4) (= betty 1)))
35:         (assert (xor (= ethel 1) (= joan 2)))
36:         (assert (xor (= joan 3) (= ethel 5)))
37:         (assert (all-different? kitty betty ethel joan mary))
38:         (map list '(kitty betty ethel joan mary) (list kitty betty ethel joan mary))))

[sample 5] (MIT-Scheme を用いて計測しました) 

(define-syntax cpu-time/sec
  (syntax-rules ()
    ((_ s)
     (with-timings
	 (lambda () s)
       (lambda (run-time gc-time real-time)
	 (write (internal-time/ticks->seconds run-time))
	 (write-char #\space)
	 (write (internal-time/ticks->seconds gc-time))
	 (write-char #\space)
	 (write (internal-time/ticks->seconds real-time))
	 (newline))))))
;Value: cpu-time/sec

(cpu-time/sec (girls-exam))
.03 0. .03
;Value 14: ((kitty 1) (betty 3) (ethel 5) (joan 2) (mary 4))

(cpu-time/sec (girls-exam-x))
.341 .29 .631
;Value 15: ((kitty 1) (betty 3) (ethel 5) (joan 2) (mary 4))

4. 終わりに

非決定性を用いるとまるで予知能力を持つようなプログラムを書くことができ、 論理プログラム、構文解析の分野で応用されています。 ただ、ここに示したプログラムは探索経路にループがある場合には使えません。

さらに詳しくは、 SICP 4.3. を見てください。 また、このページを書くにあたり 独習 Scheme ３週間 を参考にしました。

このページで示したコードは 付録につけておきますので気が向いたら ダウンロードして遊んでみてください。

HOME もうひとつの Scheme 入門 download 書き込む