第十八章 非確定性求值

介紹

非確定性是一種通過僅定義問題來解決問題的算法。非確定性程序自動選擇符合條件的選項。這項技術(shù)很適合邏輯編程。

例如，以下代碼返回一對數(shù)，其和是一個質(zhì)數(shù)。其中一個數(shù)從'(4 6 7)選取，另一個從'(5 8 11)選取。

(let ((i (amb 4 6 7))
      (j (amb 5 8 11)))
  (if (prime? (+ i j))
      (list i j)
      (amb)))
;Value 23: (6 5)

(amb 4 6 7) 從4，6和7中返回一個合適的數(shù)，(amb 5 8 11)從5，8和11中返回一個合適的數(shù)。如果沒有選出合適的值，(amb)返回假。

實際上，amb做了深度優(yōu)先搜索。(amb c1 c2 c3 ...)創(chuàng)建了搜索路徑依次檢查c1，c2，c3，…并回溯。因此，非確定性是一種幫程序隱藏搜索的抽象。一旦我們有了amb，我們可以很容易地編寫程序而無需思考計算機做了什么。

非確定性的實現(xiàn)

使用在非確定性中的回溯被實現(xiàn)為連接到繼續(xù)（continuation）的閉包鏈。這個鏈被一個全局參數(shù)fail表示，該參數(shù)是一個復寫自己的函數(shù)。

函數(shù)實現(xiàn)

第一步，我使用函數(shù)（名為choose）實現(xiàn)非確定性，演示于[代碼1]。我首先定義一個全局參數(shù)fail，它的初始值是一個將返回no-choice到頂層的函數(shù)（22-26行）。然后通過在函數(shù)choose中重新定義fail實現(xiàn)閉包鏈?；厮萃ㄟ^調(diào)用之前的fail實現(xiàn)。

函數(shù)choose有如下行為：

1. 如果沒有選項，調(diào)用(fail)。
2. 如果有任何選項，將fail儲存為fail0，并調(diào)用當前繼續(xù)（continuation）。在繼續(xù)（continuation）中重新定義fail。fail重新被賦值回存在fail0里的原值，并對余下的選項應(yīng)用（apply）choose。返回第一個選項到繼續(xù)（continuation）外面。

[代碼1]

;;; abbreviation for call-with-current-continuation
(define call/cc call-with-current-continuation)

;;; This function is re-assigned in `choose` and `fail` itself.
(define fail #f)

;;; function for nondeterminism
(define (choose . ls)
  (if (null? ls) 
    (fail)
    (let ((fail0 fail))
      (call/cc
        (lambda (cc)
          (set! fail (lambda ()
                       (set! fail fail0)
                       (cc (apply choose (cdr ls)))))
          (cc (car ls)))))))

;;; write following at the end of file
;;; initial value for fail
(call/cc 
  (lambda (cc)
    (set! fail (lambda ()
                 (cc 'no-choice)))))

讓我們看看choose是否可以找到畢達哥拉斯三元組。函數(shù)pythag用于尋找三元組。如果找到了，它返回一個表。如果沒有找到，調(diào)用無參數(shù)的choose，以回溯。

[例1]

(define (sq x)
  (* x x))
;Value: sq

;;; Pythagorean triples
(define (pythag a b c)
  (if (= (+ (sq a) (sq b)) (sq c))
      (list a b c)
      (choose)))
;Value: pythag

(pythag (choose 1 2 3) (choose 3 4 5) (choose  4 5 6))
;Value 16: (3 4 5)

宏實現(xiàn)

為了對S-表達式使用非確定性操作，必須把操作定義為宏。例如，[例2]中所示函數(shù)an-integer-starting-from應(yīng)該返回一個大于或等于n的整數(shù)，但是如果choose被以函數(shù)形式定義，它將不能正常工作，因為參數(shù)會立即求值。

[例2]

(define (an-integer-starting-from n)
  (choose n (an-integer-starting-from (1+ n))))
;Value: an-integer-starting-from

(an-integer-starting-from 1)
;Aborting!: maximum recursion depth exceeded

為了解決這一點，我們定義了一個和[代碼1]中定義一致但使用非確定性宏amb實現(xiàn)的choose。這個宏amb有和choose一樣的遞歸調(diào)用自己的結(jié)構(gòu)。

[代碼1]中的1-5行和20-26行在下面的代碼中得以重用。

[代碼2]使用MIT-Scheme編譯時，編譯器給出如下警告：

;Warning: Possible inapplicable operator ()

但是代碼可以正常工作。這些代碼在Petite Chez Scheme下也可以運行。即使我沒有試過其他Scheme實現(xiàn)，我認為amb的定義可以工作，只要它們遵守R5RS。MIT-Scheme編譯器不會對這個專門實現(xiàn)提出警告。

[代碼2]

;;; nondeterminism macro operator
(define-syntax amb
  (syntax-rules ()
    ((_) (fail))
    ((_ a) a)
    ((_ a b ...)
     (let ((fail0 fail))
       (call/cc
    (lambda (cc)
      (set! fail
        (lambda ()
          (set! fail fail0)
          (cc (amb b ...))))
      (cc a)))))))

宏定義，amb，在參數(shù)為S-表達式時也和其他值一樣正常工作。

[例3]

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

(an-integer-starting-from 1)
;Value: 1

(amb)
;Value: 2

(amb)
;Value: 3

在Teach Yourself Scheme in Fixnum Days 和Dave Hername Code中的amb實現(xiàn)使用',@(map ...)'展開參數(shù)。即使它們是直截了當?shù)亩x，但由于使用了兩次call/cc，它們某種程度上仍很復雜。[代碼2]所示的遞歸定義更簡單，即使展開的S-表達式會很復雜。

應(yīng)用于邏輯編程，使程序更簡潔

[代碼3]演示了非確定性應(yīng)用邏輯編程，使得程序更簡潔

[代碼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 (1+ n))))
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 (1+ i))))))

(set-of s)

返回滿足s的所有可能性。宏的行為如下：

1. （第5行）一個表（acc）被定義，它有所欲哦滿足s的結(jié)果。
2. （第6行）s的結(jié)果被賦給v，并加入到acc。如果結(jié)果沒有帶上v而直接被加入（如 (set! acc (cons s acc))），則會因為s使用了繼續(xù)（continuation）而只在acc中存儲了最后一個值。s改了了fail的值。
3. （第7，8行）在這之后，調(diào)用fail回溯。因為使用了繼續(xù)（continuation），函數(shù)fail行為就像在第6行被調(diào)用。
4. （第9行）當所有可能的選項被找到時，調(diào)用(reverse! acc)并返回所有的可能選項。

定義假設(shè)amb從最左邊參數(shù)開始搜索。

(assert pred)

如果謂詞為假,就回溯。

(an-integer-starting-from n)

非確定性地返回從n開始的整數(shù)。

(number-between a b)

非確定性地返回a和b之間的整數(shù)

[例4]演示了如何使用set-of。得到了所有小于20的質(zhì)數(shù)。

[例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)

邏輯編程的例子

讓我們來解決SICP中的習題4.42作為例子。問題如下：

五位女同學參加一場考試。她們的家長對考試結(jié)果過分關(guān)心。為此她們約定，在給家里寫信談到考試時，每個姑娘都要寫一句真話和一句假話。下面是從她們的信中摘出的句子：

貝蒂：“凱迪考第二，我只考了第三?！卑悹枺骸澳銈儜?yīng)該高興地聽到我考了第一，瓊第二。”瓊：“我考第三，可憐的艾賽爾考得最差?！眲P蒂：“我第二，瑪麗只考了第四?！爆旣悾骸拔沂堑谒模惖俚某煽冏罡??！?/p>

這五位姑娘的實際排名是什么？

[代碼4]給出了這個問題的解法。

[代碼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))))

(xor a b)以下條件滿足，返回#t:

• a是#t，b是#f，或者
• a是#f，b是#t。

(all-different? , ls)

當ls的所有元素都不相同時，返回#t。

(girls-exam)

是解決謎題的主要函數(shù)。它返回名字和排名的表。每次參數(shù)賦值后都調(diào)用了assert是為了有效地減少死分支的運行時間。(girls-exam-x)則是一個壞例子。它在為所有參數(shù)賦值之后調(diào)用assert。這種情況下，無謂地搜索了大量的死分支。[例5]顯示(girl-exam-x)的運行時間是(girl-exam)的10倍。

[例5]

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

小結(jié)

當你使用了非確定性和用于邏輯編程分析技術(shù)時，你就可以寫出看起來具有先見之明的程序。注意如果搜索路徑里有循環(huán)我們就不能使用本章的代碼。