4.3 Các biến thể của Scheme — Nondeterministic Computing (tính toán phi tất định)

Trong phần này, chúng ta mở rộng Scheme evaluator để hỗ trợ một mô hình lập trình gọi là nondeterministic computing ("tính toán phi tất định") bằng cách tích hợp vào evaluator một cơ chế hỗ trợ tìm kiếm tự động. Đây là một thay đổi sâu sắc hơn nhiều đối với ngôn ngữ so với việc giới thiệu lazy evaluation (đánh giá lười) ở mục 4.2.

Nondeterministic computing, giống như stream processing (xử lý luồng), hữu ích cho các ứng dụng “generate and test” ("tạo và kiểm tra"). Hãy xem xét bài toán bắt đầu với hai danh sách các số nguyên dương và tìm một cặp số nguyên — một từ danh sách thứ nhất và một từ danh sách thứ hai — sao cho tổng của chúng là số nguyên tố. Chúng ta đã thấy cách xử lý điều này bằng các phép toán trên finite sequence (dãy hữu hạn) ở mục 2.2.3 và với infinite streams (luồng vô hạn) ở mục 3.5.3. Cách tiếp cận của chúng ta là tạo ra dãy tất cả các cặp có thể và lọc ra các cặp có tổng là số nguyên tố. Việc chúng ta thực sự tạo toàn bộ dãy cặp trước như ở Chương 2, hay xen kẽ giữa việc tạo và lọc như ở Chương 3, không ảnh hưởng đến hình ảnh cốt lõi về cách tổ chức tính toán.

Cách tiếp cận nondeterministic gợi ra một hình ảnh khác. Hãy tưởng tượng đơn giản rằng chúng ta chọn (bằng một cách nào đó) một số từ danh sách thứ nhất và một số từ danh sách thứ hai, rồi yêu cầu (bằng một cơ chế nào đó) rằng tổng của chúng là số nguyên tố. Điều này được biểu diễn bằng procedure (thủ tục) sau:

(define (prime-sum-pair list1 list2)
  (let ((a (an-element-of list1))
        (b (an-element-of list2)))
    (require (prime? (+ a b)))
    (list a b)))

Thoạt nhìn, thủ tục này dường như chỉ lặp lại phát biểu của bài toán, thay vì chỉ ra cách giải quyết nó. Tuy nhiên, đây là một nondeterministic program hợp lệ.¹

Ý tưởng then chốt ở đây là các biểu thức trong một ngôn ngữ nondeterministic có thể có nhiều hơn một giá trị khả dĩ. Ví dụ, an-element-of có thể trả về bất kỳ phần tử nào của danh sách cho trước. Nondeterministic program evaluator sẽ hoạt động bằng cách tự động chọn một giá trị khả dĩ và ghi nhớ lựa chọn đó. Nếu một yêu cầu tiếp theo không được thỏa mãn, evaluator sẽ thử một lựa chọn khác, và tiếp tục thử các lựa chọn mới cho đến khi việc đánh giá thành công, hoặc cho đến khi hết lựa chọn. Cũng giống như lazy evaluator giúp lập trình viên không phải bận tâm đến chi tiết về cách giá trị được trì hoãn và buộc thực hiện, nondeterministic program evaluator sẽ giúp lập trình viên không phải bận tâm đến chi tiết về cách các lựa chọn được thực hiện.

Thật hữu ích khi so sánh các hình ảnh về thời gian mà nondeterministic evaluation và stream processing gợi ra. Stream processing sử dụng lazy evaluation để tách biệt thời điểm khi luồng các câu trả lời khả dĩ được tạo ra khỏi thời điểm khi các phần tử thực tế của luồng được sinh ra. Evaluator hỗ trợ ảo giác rằng tất cả các câu trả lời khả dĩ đều được bày ra trước mắt ta trong một dãy phi thời gian. Với nondeterministic evaluation, một biểu thức đại diện cho việc khám phá một tập hợp các "thế giới khả dĩ", mỗi thế giới được xác định bởi một tập hợp các lựa chọn. Một số thế giới khả dĩ dẫn đến ngõ cụt, trong khi những thế giới khác có giá trị hữu ích. Nondeterministic program evaluator hỗ trợ ảo giác rằng thời gian phân nhánh, và các chương trình của chúng ta có những lịch sử thực thi khả dĩ khác nhau. Khi chúng ta gặp ngõ cụt, ta có thể quay lại một điểm lựa chọn trước đó và tiếp tục theo một nhánh khác.

Nondeterministic program evaluator được triển khai dưới đây được gọi là amb evaluator vì nó dựa trên một special form (dạng đặc biệt) mới gọi là amb. Chúng ta có thể gõ định nghĩa prime-sum-pair ở trên vào vòng lặp điều khiển của amb evaluator (cùng với định nghĩa của prime?, an-element-of, và require) và chạy thủ tục như sau:

;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))

;;; Starting a new problem
;;; Amb-Eval value:
(3 20)

Giá trị trả về thu được sau khi evaluator liên tục chọn các phần tử từ mỗi danh sách, cho đến khi tìm được một lựa chọn thành công.

Mục 4.3.1 giới thiệu amb và giải thích cách nó hỗ trợ nondeterminism thông qua cơ chế tìm kiếm tự động của evaluator. Mục 4.3.2 trình bày các ví dụ về nondeterministic programs, và mục 4.3.3 đưa ra chi tiết cách triển khai amb evaluator bằng cách sửa đổi ordinary Scheme evaluator.

4.3.1 Amb và Search

Để mở rộng Scheme hỗ trợ nondeterminism, chúng ta giới thiệu một special form mới gọi là amb.² Biểu thức

(amb ⟨e₁⟩ ⟨e₂⟩ … ⟨eₙ⟩)

trả về giá trị của một trong $n$ biểu thức $\langle\mspace{1mu} e_{i}\rangle$ một cách “mơ hồ” (ambiguously). Ví dụ, biểu thức

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

có thể có sáu giá trị khả dĩ:

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

Amb với một lựa chọn duy nhất sẽ tạo ra một giá trị thông thường (đơn).

Amb không có lựa chọn nào — biểu thức (amb) — là một biểu thức không có giá trị chấp nhận được. Về mặt thao tác, ta có thể coi (amb) là một biểu thức khi được đánh giá sẽ khiến quá trình tính toán “thất bại”: quá trình bị hủy bỏ và không tạo ra giá trị nào. Sử dụng ý tưởng này, ta có thể biểu diễn yêu cầu rằng một biểu thức predicate p phải đúng như sau:

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

Với amb và require, ta có thể triển khai an-element-of procedure đã dùng ở trên:

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

An-element-of thất bại nếu danh sách rỗng. Ngược lại, nó trả về một cách mơ hồ hoặc phần tử đầu tiên của danh sách, hoặc một phần tử được chọn từ phần còn lại của danh sách.

Chúng ta cũng có thể biểu diễn các phạm vi lựa chọn vô hạn. Thủ tục sau đây có thể trả về bất kỳ số nguyên nào lớn hơn hoặc bằng một số $n$ cho trước:

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

Điều này giống như stream procedure integers-starting-from được mô tả ở mục 3.5.2, nhưng có một điểm khác biệt quan trọng: Stream procedure trả về một đối tượng đại diện cho dãy tất cả các số nguyên bắt đầu từ $n$, trong khi amb procedure trả về một số nguyên duy nhất.³

Về mặt trừu tượng, ta có thể hình dung rằng việc đánh giá một biểu thức amb khiến thời gian phân nhánh, trong đó quá trình tính toán tiếp tục trên mỗi nhánh với một trong các giá trị khả dĩ của biểu thức. Ta nói rằng amb đại diện cho một nondeterministic choice point ("điểm lựa chọn phi tất định"). Nếu chúng ta có một máy với số lượng bộ xử lý đủ lớn và có thể cấp phát động, ta có thể triển khai việc tìm kiếm một cách trực tiếp. Quá trình thực thi sẽ diễn ra như trên một máy tuần tự, cho đến khi gặp một biểu thức amb. Tại thời điểm này, nhiều bộ xử lý hơn sẽ được cấp phát và khởi tạo để tiếp tục tất cả các quá trình thực thi song song được ngụ ý bởi lựa chọn đó. Mỗi bộ xử lý sẽ tiếp tục tuần tự như thể nó là lựa chọn duy nhất, cho đến khi hoặc kết thúc do gặp thất bại, hoặc tiếp tục phân nhánh thêm, hoặc hoàn tất.⁴

Mặt khác, nếu chúng ta có một máy chỉ có thể thực thi một tiến trình (hoặc một vài tiến trình đồng thời), ta phải xem xét các lựa chọn theo cách tuần tự. Có thể hình dung việc sửa đổi một evaluator để chọn ngẫu nhiên một nhánh để theo mỗi khi gặp một choice point. Tuy nhiên, lựa chọn ngẫu nhiên có thể dễ dàng dẫn đến các giá trị thất bại. Ta có thể thử chạy evaluator nhiều lần, đưa ra các lựa chọn ngẫu nhiên và hy vọng tìm được một giá trị không thất bại, nhưng tốt hơn là systematically search ("tìm kiếm có hệ thống") tất cả các đường thực thi khả dĩ. amb evaluator mà chúng ta sẽ phát triển và sử dụng trong phần này triển khai một tìm kiếm có hệ thống như sau: Khi evaluator gặp một ứng dụng của amb, nó ban đầu sẽ chọn phương án đầu tiên. Lựa chọn này có thể tự nó dẫn đến một lựa chọn khác. Evaluator sẽ luôn chọn phương án đầu tiên tại mỗi choice point. Nếu một lựa chọn dẫn đến thất bại, evaluator sẽ automagically⁵ backtrack ("quay lui") về choice point gần nhất và thử phương án tiếp theo. Nếu hết phương án tại bất kỳ choice point nào, evaluator sẽ quay lui về choice point trước đó và tiếp tục từ đó. Quá trình này dẫn đến một chiến lược tìm kiếm được gọi là depth-first search ("tìm kiếm theo chiều sâu") hoặc chronological backtracking ("quay lui theo trình tự thời gian").⁶

Driver loop

Driver loop cho amb evaluator có một số đặc điểm bất thường. Nó đọc một biểu thức và in ra giá trị của lần thực thi đầu tiên không thất bại, như trong ví dụ prime-sum-pair đã trình bày ở trên. Nếu chúng ta muốn xem giá trị của lần thực thi thành công tiếp theo, ta có thể yêu cầu interpreter quay lui và cố gắng tạo ra một lần thực thi không thất bại thứ hai. Điều này được báo hiệu bằng cách gõ ký hiệu try-again. Nếu nhập bất kỳ biểu thức nào khác ngoài try-again, interpreter sẽ bắt đầu một bài toán mới, loại bỏ các phương án chưa được khám phá trong bài toán trước. Dưới đây là một ví dụ tương tác:

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

4.3.2 Các ví dụ về Nondeterministic Programs

Mục 4.3.3 sẽ mô tả cách triển khai amb evaluator. Tuy nhiên, trước tiên, chúng ta sẽ đưa ra một số ví dụ về cách nó có thể được sử dụng. Ưu điểm của nondeterministic programming (lập trình phi tất định) là chúng ta có thể lược bỏ các chi tiết về cách tìm kiếm được thực hiện, từ đó biểu đạt chương trình ở mức trừu tượng cao hơn.

Logic Puzzles

Câu đố sau (lấy từ Dinesman 1968) là ví dụ điển hình của một lớp lớn các câu đố logic đơn giản:

Baker, Cooper, Fletcher, Miller và Smith sống ở các tầng khác nhau của một tòa nhà chung cư chỉ có năm tầng. Baker không sống ở tầng trên cùng. Cooper không sống ở tầng dưới cùng. Fletcher không sống ở tầng trên cùng hoặc tầng dưới cùng. Miller sống ở tầng cao hơn Cooper. Smith không sống ở tầng liền kề với Fletcher. Fletcher không sống ở tầng liền kề với Cooper. Hỏi mỗi người sống ở tầng nào?

Chúng ta có thể xác định ai sống ở mỗi tầng một cách trực tiếp bằng cách liệt kê tất cả các khả năng và áp đặt các ràng buộc đã cho:⁷

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require
     (distinct? (list baker cooper fletcher 
                      miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require
     (not (= (abs (- smith fletcher)) 1)))
    (require 
     (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))

Khi đánh giá biểu thức (multiple-dwelling) sẽ cho kết quả:

((baker 3) (cooper 2) (fletcher 4)
 (miller 5) (smith 1))

Mặc dù procedure đơn giản này hoạt động, nhưng nó rất chậm. Bài tập 4.39 và 4.40 sẽ thảo luận một số cải tiến khả dĩ.

Phân tích cú pháp ngôn ngữ tự nhiên

Các chương trình được thiết kế để chấp nhận ngôn ngữ tự nhiên làm đầu vào thường bắt đầu bằng việc cố gắng parse (phân tích cú pháp) đầu vào, tức là so khớp đầu vào với một cấu trúc ngữ pháp nào đó. Ví dụ, chúng ta có thể thử nhận dạng các câu đơn giản gồm một article (mạo từ) theo sau bởi một noun (danh từ) và tiếp theo là một verb (động từ), chẳng hạn như “The cat eats.” Để thực hiện phân tích như vậy, chúng ta phải có khả năng xác định part of speech (loại từ) của từng từ riêng lẻ. Ta có thể bắt đầu với một số danh sách phân loại các từ khác nhau:⁸

(define nouns 
  '(noun student professor cat class))

(define verbs 
  '(verb studies lectures eats sleeps))

(define articles '(article the a))

Chúng ta cũng cần một grammar (ngữ pháp), tức là một tập hợp các quy tắc mô tả cách các thành phần ngữ pháp được tạo thành từ các thành phần đơn giản hơn. Một ngữ pháp rất đơn giản có thể quy định rằng một câu luôn gồm hai phần — một noun phrase (cụm danh từ) theo sau bởi một verb — và rằng một noun phrase gồm một article theo sau bởi một noun. Với ngữ pháp này, câu “The cat eats” sẽ được phân tích như sau:

(sentence
 (noun-phrase (article the) (noun cat))
 (verb eats))

Chúng ta có thể tạo ra một phân tích như vậy bằng một chương trình đơn giản có các procedure riêng cho từng quy tắc ngữ pháp. Để phân tích một câu, ta xác định hai thành phần cấu thành của nó và trả về một danh sách gồm hai phần tử này, được gắn nhãn bằng ký hiệu sentence:

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-word verbs)))

Tương tự, một noun phrase được phân tích bằng cách tìm một article theo sau bởi một noun:

(define (parse-noun-phrase)
  (list 'noun-phrase
        (parse-word articles)
        (parse-word nouns)))

Ở mức thấp nhất, việc phân tích cú pháp quy về việc lặp lại kiểm tra xem từ chưa được phân tích tiếp theo có thuộc danh sách các từ của loại từ yêu cầu hay không. Để triển khai điều này, chúng ta duy trì một biến toàn cục *unparsed*, là phần đầu vào chưa được phân tích. Mỗi lần kiểm tra một từ, ta yêu cầu rằng *unparsed* không được rỗng và nó phải bắt đầu bằng một từ thuộc danh sách đã chỉ định. Nếu đúng, ta loại bỏ từ đó khỏi *unparsed* và trả về từ đó cùng với loại từ của nó (nằm ở đầu danh sách):⁹

(define (parse-word word-list)
  (require (not (null? *unparsed*)))
  (require (memq (car *unparsed*) 
                 (cdr word-list)))
  (let ((found-word (car *unparsed*)))
    (set! *unparsed* (cdr *unparsed*))
    (list (car word-list) found-word)))

Để bắt đầu phân tích cú pháp, tất cả những gì chúng ta cần làm là gán *unparsed* bằng toàn bộ đầu vào, thử phân tích một câu, và kiểm tra rằng không còn gì sót lại:

(define *unparsed* '())
(define (parse input)
  (set! *unparsed* input)
  (let ((sent (parse-sentence)))
    (require (null? *unparsed*))
    sent))

Bây giờ chúng ta có thể thử parser và kiểm tra rằng nó hoạt động với câu thử nghiệm đơn giản:

;;; Amb-Eval input:
(parse '(the cat eats))

;;; Starting a new problem
;;; Amb-Eval value:
(sentence 
 (noun-phrase (article the) (noun cat))
 (verb eats))

amb evaluator hữu ích ở đây vì nó cho phép biểu đạt các ràng buộc phân tích cú pháp một cách thuận tiện với sự hỗ trợ của require. Tuy nhiên, khả năng tìm kiếm tự động và quay lui thực sự phát huy tác dụng khi chúng ta xét đến các ngữ pháp phức tạp hơn, nơi có nhiều lựa chọn về cách phân tách các đơn vị.

Hãy thêm vào ngữ pháp của chúng ta một danh sách prepositions (giới từ):

(define prepositions 
  '(prep for to in by with))

và định nghĩa một prepositional phrase (cụm giới từ) — ví dụ “for the cat” — là một preposition theo sau bởi một noun phrase:

(define (parse-prepositional-phrase)
  (list 'prep-phrase
        (parse-word prepositions)
        (parse-noun-phrase)))

Bây giờ chúng ta có thể định nghĩa một sentence (câu) là một noun phrase (cụm danh từ) theo sau bởi một verb phrase (cụm động từ), trong đó một verb phrase có thể là một verb hoặc một verb phrase được mở rộng bởi một prepositional phrase (cụm giới từ):¹⁰

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-verb-phrase)))

(define (parse-verb-phrase)
  (define (maybe-extend verb-phrase)
    (amb 
     verb-phrase
     (maybe-extend 
      (list 'verb-phrase
            verb-phrase
            (parse-prepositional-phrase)))))
  (maybe-extend (parse-word verbs)))

Nhân tiện, chúng ta cũng có thể mở rộng định nghĩa của noun phrase để cho phép những cấu trúc như “a cat in the class.” Cái mà trước đây chúng ta gọi là noun phrase, bây giờ sẽ gọi là simple noun phrase (cụm danh từ đơn), và một noun phrase giờ đây sẽ là hoặc một simple noun phrase hoặc một noun phrase được mở rộng bởi một prepositional phrase:

(define (parse-simple-noun-phrase)
  (list 'simple-noun-phrase
        (parse-word articles)
        (parse-word nouns)))

(define (parse-noun-phrase)
  (define (maybe-extend noun-phrase)
    (amb 
     noun-phrase
     (maybe-extend 
      (list 'noun-phrase
            noun-phrase
            (parse-prepositional-phrase)))))
  (maybe-extend (parse-simple-noun-phrase)))

Ngữ pháp mới của chúng ta cho phép phân tích các câu phức tạp hơn. Ví dụ:

(parse '(the student with the cat 
         sleeps in the class))

cho ra kết quả:

(sentence
 (noun-phrase
  (simple-noun-phrase (article the) 
                      (noun student))
  (prep-phrase (prep with)
               (simple-noun-phrase
                (article the)
                (noun cat))))
 (verb-phrase
  (verb sleeps)
  (prep-phrase (prep in)
               (simple-noun-phrase
                (article the)
                (noun class)))))

Lưu ý rằng một đầu vào nhất định có thể có nhiều cách phân tích hợp lệ. Trong câu “The professor lectures to the student with the cat,” có thể là giáo sư đang giảng bài cùng với con mèo, hoặc là sinh viên có con mèo. Chương trình nondeterministic của chúng ta tìm ra cả hai khả năng:

(parse '(the professor lectures to 
         the student with the cat))

cho ra kết quả:

(sentence
 (simple-noun-phrase (article the) 
                     (noun professor))
 (verb-phrase
  (verb-phrase
   (verb lectures)
   (prep-phrase (prep to)
                (simple-noun-phrase
                 (article the) 
                 (noun student))))
  (prep-phrase (prep with)
               (simple-noun-phrase
                (article the) 
                (noun cat)))))

Yêu cầu evaluator thử lại sẽ cho ra:

(sentence
 (simple-noun-phrase (article the) 
                     (noun professor))
 (verb-phrase (verb lectures)
              (prep-phrase 
               (prep to)
               (noun-phrase
                (simple-noun-phrase
                 (article the) 
                 (noun student))
                (prep-phrase 
                 (prep with)
                 (simple-noun-phrase
                  (article the) 
                  (noun cat)))))))

4.3.3 Triển khai Amb Evaluator

Việc đánh giá một biểu thức Scheme thông thường có thể trả về một giá trị, có thể không bao giờ kết thúc, hoặc có thể báo lỗi. Trong nondeterministic Scheme (Scheme phi tất định), việc đánh giá một biểu thức ngoài những khả năng trên còn có thể dẫn đến việc phát hiện ra một ngõ cụt, khi đó quá trình đánh giá phải backtrack (quay lui) về một choice point (điểm lựa chọn) trước đó. Việc diễn giải nondeterministic Scheme trở nên phức tạp hơn bởi trường hợp bổ sung này.

Chúng ta sẽ xây dựng amb evaluator cho nondeterministic Scheme bằng cách sửa đổi analyzing evaluator (bộ phân tích và thực thi) ở mục 4.1.7.¹¹ Giống như trong analyzing evaluator, việc đánh giá một biểu thức được thực hiện bằng cách gọi một execution procedure (thủ tục thực thi) được tạo ra từ quá trình phân tích biểu thức đó. Sự khác biệt giữa việc diễn giải Scheme thông thường và Scheme phi tất định sẽ hoàn toàn nằm ở các execution procedure.

Execution procedures và Continuations

Hãy nhớ rằng các execution procedure của ordinary evaluator nhận một đối số: environment (môi trường thực thi). Ngược lại, các execution procedure trong amb evaluator nhận ba đối số: environment, và hai procedure gọi là continuation procedures (thủ tục tiếp diễn). Việc đánh giá một biểu thức sẽ kết thúc bằng việc gọi một trong hai continuation này: Nếu việc đánh giá cho ra một giá trị, success continuation (tiếp diễn thành công) sẽ được gọi với giá trị đó; nếu việc đánh giá dẫn đến phát hiện một ngõ cụt, failure continuation (tiếp diễn thất bại) sẽ được gọi. Việc xây dựng và gọi các continuation thích hợp chính là cơ chế mà nondeterministic evaluator sử dụng để thực hiện backtracking.

Nhiệm vụ của success continuation là nhận một giá trị và tiếp tục quá trình tính toán. Cùng với giá trị đó, success continuation được truyền thêm một failure continuation khác, sẽ được gọi sau này nếu việc sử dụng giá trị đó dẫn đến ngõ cụt.

Nhiệm vụ của failure continuation là thử một nhánh khác của quá trình phi tất định. Bản chất của ngôn ngữ phi tất định nằm ở chỗ các biểu thức có thể biểu diễn các lựa chọn giữa nhiều phương án. Việc đánh giá một biểu thức như vậy phải tiếp tục với một trong các phương án đã chỉ ra, mặc dù chưa biết trước phương án nào sẽ dẫn đến kết quả chấp nhận được. Để xử lý điều này, evaluator chọn một trong các phương án và truyền giá trị này cho success continuation. Cùng với giá trị này, evaluator tạo và truyền kèm một failure continuation có thể được gọi sau đó để chọn một phương án khác.

Một thất bại được kích hoạt trong quá trình đánh giá (tức là một failure continuation được gọi) khi chương trình của người dùng rõ ràng từ chối hướng xử lý hiện tại (ví dụ, một lời gọi đến require có thể dẫn đến việc thực thi (amb), một biểu thức luôn thất bại — xem mục 4.3.1). Failure continuation hiện có tại thời điểm đó sẽ khiến choice point gần nhất chọn một phương án khác. Nếu không còn phương án nào để xem xét tại choice point đó, một thất bại tại choice point trước đó sẽ được kích hoạt, và cứ thế tiếp tục. Failure continuation cũng được gọi bởi driver loop khi nhận yêu cầu try-again, để tìm một giá trị khác của biểu thức.

Ngoài ra, nếu một thao tác side-effect (tác động phụ) — chẳng hạn như gán giá trị cho một biến — xảy ra trên một nhánh của quá trình xuất phát từ một lựa chọn, thì khi quá trình đó gặp ngõ cụt, có thể cần phải hoàn tác tác động phụ trước khi thực hiện lựa chọn mới. Điều này được thực hiện bằng cách để thao tác side-effect tạo ra một failure continuation có nhiệm vụ hoàn tác tác động phụ và lan truyền thất bại.

Tóm lại, failure continuation được tạo ra bởi:

• Các biểu thức amb — để cung cấp cơ chế lựa chọn phương án thay thế nếu phương án hiện tại do biểu thức amb chọn dẫn đến ngõ cụt;
• Top-level driver — để cung cấp cơ chế báo lỗi khi đã hết các lựa chọn;
• Các phép gán — để chặn các thất bại và hoàn tác phép gán trong quá trình backtracking.

Các thất bại chỉ được khởi tạo khi gặp ngõ cụt. Điều này xảy ra:

• nếu chương trình người dùng thực thi (amb);
• nếu người dùng nhập try-again tại top-level driver.

Failure continuation cũng được gọi trong quá trình xử lý một thất bại:

• Khi failure continuation được tạo bởi một phép gán hoàn tất việc hoàn tác tác động phụ, nó sẽ gọi failure continuation mà nó đã chặn, để lan truyền thất bại trở lại choice point đã dẫn đến phép gán này hoặc về mức top-level.
• Khi failure continuation của một amb hết các lựa chọn, nó sẽ gọi failure continuation ban đầu được truyền cho amb, để lan truyền thất bại trở lại choice point trước đó hoặc về mức top-level.

Cấu trúc của evaluator

Các syntax procedure (thủ tục cú pháp) và data-representation procedure (thủ tục biểu diễn dữ liệu) cho amb evaluator, cũng như analyze procedure cơ bản, giống hệt với các thủ tục trong evaluator ở mục 4.1.7, ngoại trừ việc chúng ta cần thêm các syntax procedure để nhận diện special form amb:¹²

(define (amb? exp) (tagged-list? exp 'amb))
(define (amb-choices exp) (cdr exp))

Chúng ta cũng phải thêm vào phần dispatch trong analyze một mệnh đề để nhận diện special form này và tạo ra một execution procedure thích hợp:

((amb? exp) (analyze-amb exp))

Top-level procedure ambeval (tương tự phiên bản eval ở mục 4.1.7) sẽ phân tích biểu thức được cung cấp và áp dụng execution procedure thu được cho environment (môi trường) đã cho, cùng với hai continuation (tiếp diễn) được truyền vào:

(define (ambeval exp env succeed fail)
  ((analyze exp) env succeed fail))

Một success continuation là một procedure nhận hai đối số: giá trị vừa thu được và một failure continuation khác sẽ được dùng nếu giá trị đó dẫn đến một thất bại tiếp theo. Một failure continuation là một procedure không nhận đối số nào. Do đó, dạng tổng quát của một execution procedure là:

(lambda (env succeed fail)
  ;; succeed is (lambda (value fail) …)
  ;; fail is (lambda () …)
  …)

Ví dụ, thực thi:

(ambeval ⟨exp⟩
         the-global-environment
         (lambda (value fail) value)
         (lambda () 'failed))

sẽ cố gắng đánh giá biểu thức đã cho và sẽ trả về hoặc giá trị của biểu thức (nếu đánh giá thành công) hoặc ký hiệu failed (nếu đánh giá thất bại). Lời gọi ambeval trong driver loop được trình bày bên dưới sử dụng các continuation procedure phức tạp hơn nhiều, cho phép tiếp tục vòng lặp và hỗ trợ yêu cầu try-again.

Phần lớn độ phức tạp của amb evaluator xuất phát từ cơ chế truyền các continuation qua lại khi các execution procedure gọi lẫn nhau. Khi đọc đoạn mã dưới đây, bạn nên so sánh từng execution procedure với procedure tương ứng trong ordinary evaluator ở mục 4.1.7.

Simple expressions

Các execution procedure cho các loại biểu thức đơn giản nhất về cơ bản giống với các thủ tục trong ordinary evaluator, ngoại trừ việc cần quản lý các continuation. Các execution procedure này đơn giản là thành công với giá trị của biểu thức, đồng thời truyền tiếp failure continuation mà chúng nhận được.

(define (analyze-self-evaluating exp)
  (lambda (env succeed fail)
    (succeed exp fail)))

(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env succeed fail)
      (succeed qval fail))))

(define (analyze-variable exp)
  (lambda (env succeed fail)
    (succeed (lookup-variable-value exp env)
             fail)))

(define (analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (analyze-sequence 
                (lambda-body exp))))
    (lambda (env succeed fail)
      (succeed (make-procedure vars bproc env)
               fail))))

Lưu ý rằng việc tra cứu một biến luôn “thành công”. Nếu lookup-variable-value không tìm thấy biến, nó sẽ báo lỗi như thường lệ. Một “thất bại” như vậy cho thấy lỗi lập trình — tham chiếu đến một biến chưa được ràng buộc; đây không phải là dấu hiệu cho thấy chúng ta nên thử một lựa chọn phi tất định khác thay cho lựa chọn hiện tại.

Conditionals và sequences

Conditionals cũng được xử lý tương tự như trong ordinary evaluator. Execution procedure được tạo bởi analyze-if sẽ gọi predicate execution procedure pproc với một success continuation kiểm tra xem giá trị của predicate có đúng hay không, và tiếp tục thực thi consequent hoặc alternative. Nếu việc thực thi pproc thất bại, failure continuation ban đầu của biểu thức if sẽ được gọi.

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env succeed fail)
      (pproc env
             ;; success continuation for evaluating
             ;; the predicate to obtain pred-value
             (lambda (pred-value fail2)
               (if (true? pred-value)
                   (cproc env succeed fail2)
                   (aproc env succeed fail2)))
             ;; failure continuation for
             ;; evaluating the predicate
             fail))))

Sequences cũng được xử lý giống như trong evaluator trước đó, ngoại trừ các thao tác trong subprocedure sequentially cần thiết để truyền các continuation. Cụ thể, để thực thi tuần tự a rồi đến b, ta gọi a với một success continuation sẽ gọi b.

(define (analyze-sequence exps)
  (define (sequentially a b)
    (lambda (env succeed fail)
      (a env
         ;; success continuation for calling a
         (lambda (a-value fail2)
           (b env succeed fail2))
         ;; failure continuation for calling a
         fail)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc 
                            (car rest-procs))
              (cdr rest-procs))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence: ANALYZE"))
    (loop (car procs) (cdr procs))))

Definitions và assignments

Definitions là một trường hợp khác mà chúng ta phải xử lý cẩn thận để quản lý các continuation, vì cần phải đánh giá biểu thức definition-value trước khi thực sự định nghĩa biến mới. Để thực hiện điều này, definition-value execution procedure vproc được gọi với environment, một success continuation, và failure continuation. Nếu việc thực thi vproc thành công, thu được giá trị val cho biến được định nghĩa, biến sẽ được định nghĩa và thành công được truyền tiếp:

(define (analyze-definition exp)
  (let ((var (definition-variable exp))
        (vproc (analyze 
                (definition-value exp))))
    (lambda (env succeed fail)
      (vproc env
             (lambda (val fail2)
               (define-variable! var val env)
               (succeed 'ok fail2))
             fail))))

Assignments thú vị hơn. Đây là nơi đầu tiên chúng ta thực sự sử dụng các continuation, thay vì chỉ truyền chúng đi. Execution procedure cho assignment bắt đầu giống như cho definition. Nó trước tiên cố gắng lấy giá trị mới sẽ gán cho biến. Nếu việc đánh giá vproc thất bại, phép gán thất bại.

Tuy nhiên, nếu vproc thành công và chúng ta tiến hành gán, ta phải xem xét khả năng rằng nhánh tính toán này có thể thất bại sau đó, khi đó sẽ cần backtrack để hoàn tác phép gán. Do đó, chúng ta phải sắp xếp để hoàn tác phép gán như một phần của quá trình backtracking.¹³

Điều này được thực hiện bằng cách truyền cho vproc một success continuation (được đánh dấu “*1*” bên dưới) lưu giá trị cũ của biến trước khi gán giá trị mới và tiếp tục từ phép gán. Failure continuation được truyền kèm với giá trị của phép gán (được đánh dấu “*2*” bên dưới) sẽ khôi phục giá trị cũ của biến trước khi tiếp tục thất bại. Nói cách khác, một phép gán thành công sẽ cung cấp một failure continuation để chặn một thất bại xảy ra sau đó; bất kỳ thất bại nào lẽ ra sẽ gọi fail2 thì thay vào đó sẽ gọi thủ tục này, để hoàn tác phép gán trước khi thực sự gọi fail2.

(define (analyze-assignment exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze 
                (assignment-value exp))))
    (lambda (env succeed fail)
      (vproc env
             (lambda (val fail2)    ; *1*
               (let ((old-value
                      (lookup-variable-value 
                       var 
                       env)))
                 (set-variable-value!
                  var 
                  val 
                  env)
                 (succeed 
                  'ok
                  (lambda ()    ; *2*
                    (set-variable-value! 
                     var
                     old-value
                     env)
                    (fail2)))))
               fail))))

Procedure applications

Execution procedure (thủ tục thực thi) cho applications (lời gọi thủ tục) không chứa ý tưởng mới nào ngoại trừ độ phức tạp kỹ thuật trong việc quản lý các continuation. Độ phức tạp này phát sinh trong analyze-application, do cần phải theo dõi success continuation và failure continuation khi chúng ta đánh giá các toán hạng. Chúng ta sử dụng một procedure get-args để đánh giá danh sách các toán hạng, thay vì một phép map đơn giản như trong ordinary evaluator.

(define (analyze-application exp)
  (let ((fproc (analyze (operator exp)))
        (aprocs (map analyze (operands exp))))
    (lambda (env succeed fail)
      (fproc env
             (lambda (proc fail2)
               (get-args 
                aprocs
                env
                (lambda (args fail3)
                  (execute-application
                   proc args succeed fail3))
                fail2))
             fail))))

Trong get-args, hãy chú ý cách việc duyệt xuống danh sách các execution procedure aproc bằng cdr và xây dựng (cons) danh sách args kết quả được thực hiện bằng cách gọi từng aproc trong danh sách với một success continuation gọi đệ quy get-args. Mỗi lời gọi đệ quy này đến get-args có một success continuation mà giá trị của nó là phép cons đối số vừa thu được vào danh sách các đối số đã tích lũy:

(define (get-args aprocs env succeed fail)
  (if (null? aprocs)
      (succeed '() fail)
      ((car aprocs) 
       env
       ;; success continuation for this aproc
       (lambda (arg fail2)
         (get-args 
          (cdr aprocs)
          env
          ;; success continuation for
          ;; recursive call to get-args
          (lambda (args fail3)
            (succeed (cons arg args)
                     fail3))
          fail2))
       fail)))

Việc áp dụng procedure thực tế, được thực hiện bởi execute-application, được tiến hành giống như trong ordinary evaluator, ngoại trừ việc cần quản lý các continuation.

(define (execute-application 
         proc args succeed fail)
  (cond ((primitive-procedure? proc)
         (succeed 
          (apply-primitive-procedure 
           proc args)
          fail))
        ((compound-procedure? proc)
         ((procedure-body proc)
          (extend-environment 
           (procedure-parameters proc)
           args
           (procedure-environment proc))
          succeed
          fail))
        (else (error "Unknown procedure type: 
                      EXECUTE-APPLICATION"
                     proc))))

Evaluating amb expressions

Special form amb là yếu tố then chốt trong ngôn ngữ nondeterministic. Ở đây, chúng ta thấy bản chất của quá trình diễn giải và lý do cần theo dõi các continuation. Execution procedure cho amb định nghĩa một vòng lặp try-next để lần lượt duyệt qua các execution procedure cho tất cả các giá trị khả dĩ của biểu thức amb. Mỗi execution procedure được gọi với một failure continuation sẽ thử giá trị tiếp theo. Khi không còn phương án nào để thử, toàn bộ biểu thức amb sẽ thất bại.

(define (analyze-amb exp)
  (let ((cprocs
         (map analyze (amb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices) 
             env
             succeed
             (lambda ()
               (try-next (cdr choices))))))
      (try-next cprocs))))

Driver loop

Driver loop cho amb evaluator phức tạp do cơ chế cho phép người dùng thử lại khi đánh giá một biểu thức. Driver sử dụng một procedure gọi là internal-loop, nhận đối số là một procedure try-again. Ý tưởng là khi gọi try-again sẽ tiếp tục với phương án chưa thử tiếp theo trong quá trình đánh giá phi tất định. Internal-loop hoặc gọi try-again khi người dùng nhập try-again tại driver loop, hoặc bắt đầu một lần đánh giá mới bằng cách gọi ambeval.

Failure continuation cho lời gọi ambeval này sẽ thông báo cho người dùng rằng không còn giá trị nào nữa và gọi lại driver loop.

Success continuation cho lời gọi ambeval tinh tế hơn. Chúng ta in ra giá trị thu được và sau đó gọi lại internal loop với một procedure try-again có thể thử phương án tiếp theo. Procedure next-alternative này là đối số thứ hai được truyền cho success continuation. Thông thường, chúng ta coi đối số thứ hai này là một failure continuation sẽ được dùng nếu nhánh đánh giá hiện tại thất bại sau đó. Tuy nhiên, trong trường hợp này, chúng ta đã hoàn tất một lần đánh giá thành công, nên có thể gọi nhánh “thất bại” thay thế để tìm thêm các lần đánh giá thành công khác.

(define input-prompt  ";;; Amb-Eval input:")
(define output-prompt ";;; Amb-Eval value:")

(define (driver-loop)
  (define (internal-loop try-again)
    (prompt-for-input input-prompt)
    (let ((input (read)))
      (if (eq? input 'try-again)
          (try-again)
          (begin
            (newline)
            (display 
             ";;; Starting a new problem ")
            (ambeval 
             input
             the-global-environment
             ;; ambeval success
             (lambda (val next-alternative)
               (announce-output 
                output-prompt)
               (user-print val)
               (internal-loop 
                next-alternative))
             ;; ambeval failure
             (lambda ()
               (announce-output
                ";;; There are no 
                 more values of")
               (user-print input)
               (driver-loop)))))))
  (internal-loop
   (lambda ()
     (newline)
     (display 
      ";;; There is no current problem")
     (driver-loop))))

Lời gọi ban đầu đến internal-loop sử dụng một procedure try-again thông báo rằng không có vấn đề hiện tại và khởi động lại driver loop. Đây là hành vi sẽ xảy ra nếu người dùng nhập try-again khi không có quá trình đánh giá nào đang diễn ra.