SAKAI Masahiro - SICP::2003-06-03 Diff

  • Added parts are displayed like this.
  • Deleted parts are displayed like this.

= 4.3 Schemeの変形 - 非決定的計算

  酒井 政裕 <sakai at tom.sfc.keio.ac.jp>
  総合政策学部3年

= Schemeの非決定性計算

* 式はひとつ以上の可能な値を持ちえる
* 本節では、Schemeに自動探索のための機能を組み込むことで実現
* 自動探索はPrologでもやってるよね。

= 4.3.1 ambと探索

特殊形式amb

* (amb <e1> <e2> ... <en>) はn個の式<ei>のひとつの値を「曖昧に」返す
* 式をひとつももたないamb式は「失敗」を表す

= require

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

* (require p)はpが真でなくてはならないことをあらわす。
* => 偽ならば「失敗」する

= 例

リストの要素

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

* amb式の評価は時を多くの分岐に分け、
  各分岐では式の一つの可能な値が続くと考えられる。
  ambは非決定的な選択点を表現する。

* 実現方法
  * すべての分岐を並列に実行
  * バックトラッキングにより逐次的に実行。
    * 評価機は各選択点で第一の道を選択する
    * 「失敗」したら、直前の選択点にもどり次の道を選択する

本節ではバックトラッキングを選択

= 駆動ループ

* amb評価機は最初の成功した値しか表示しない
* 次の成功した値を表示するには、記号try-againでバックトラック

  
   > (prime-sum-pair '(19 27 30) '(11 36 58))
   (3 20)
   > try-again
   (3 110)
   ...

= 4.3.2 非決定性プログラムの例

* 単純な論理パズル
* 自然言語の構文解析

を例としてとりあげる。

= 論理パズル

非決定プログラムラムの長所

* 探索の仕方の細部を押し隠す事ができる
* => より高い抽象レベルで表現できる

= 自然言語の構文解析

* いわゆる バックトラッキング・パーサー
* 再起降下法

= 各語を分類するリスト

* (define nouns '(noun student professor cat class))
* (define verbs '(verb studies lectures eats sleeps))
* 先頭が品詞名
* 残りがその品詞の語

= 構文解析:例

「The cat eats」

  (sentense (naun-phrase (article the) (naun cat))
            (verb eats))

= 構文解析:実装 (1)

句構造文法の生成規則を、そのまま関数呼び出しに対応させる。

  ;; S -> NP V
  (define (parse-sentence)
    (list 'sentence
           (parse-noun-phrase)
           (parse-word verbs)))

  ;; NP -> A N
  (define (parse-noun-phrase)
    (list 'noun-phrase
          (parse-word articles)
          (parse-word nouns)))

= 構文解析:実装 (2)

* 最終的にはparse-wordによって語を扱う
* *unparsed* : 文のまだ読んでいない部分を入れておく
* *unparsed*の先頭が与えられた品詞であるかをチェックして読み進める

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

= 4.3.3 amb評価機の実装

値を評価したとき

* 通常のScheme
  (1) 値が返る
  (2) 停止しない
  (3) エラーになる

非決定性Schemeではこれに加えて、「袋小路」の可能性がある。

= 実行手続きと継続

継続 = その後に行われるべき計算の全体

= おまけ: CPS変換

* [[x]]ρ     = λk.(k (ρx) )
* [[λx.M]]ρ = λk.k(λv.λk'.([[M]](ρ[x|->v]) k') )
* [[E1 E2]]ρ = λk.[[E1]]ρ(λf.[[E2]]ρ(λa.f a k) )

でのkが継続。

= 実行手続きと継続 (2)

* 評価機の実行手続きは3つの引数をとる
  (1) 環境
  (2) 成功継続
  (3) 失敗継続

* 成功継続 = 値(と失敗継続)を受け取り計算を続行する手続き
* 失敗継続 = 非決定プロセスの別の道を試みる手続き

= 失敗継続が構成されるケース

* amb式 - 選択が袋小路に至ったときに別の選択をするため
* トップレベルの駆動ループ - 選択を使い切った時、失敗を報告する機構を用意するため
* 代入 - 失敗を横取りし、バックトラック中に代入を元に戻すため

= 評価機の構造

* 構文手続き, データ表現手続き, analyze は、amb特殊形式を扱うコード以外は、これまでとほぼ同様

= 評価機の構造 (2)

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

= 評価機の構造 (3)

実行形式の一般形は

  (lambda (env succeed fail)
     ;; succeed は (lambda (value fail) ...)
     ;; fail は (lambda () ...)
     ...)

* 複雑さの殆んどは実行手続きが互いに呼び出すときの、
  継続を引き渡す機構に由来する。

= 単純式

* 継続を管理すること以外は、これまでとほぼ同じ

= 単純式: 自己評価式

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

= 単純式: quoted

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

= 単純式: lambda

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

= 条件式と並び

* これも継続をたらいまわしにするだけ

= 条件式: if

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

= 並び

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

= 定義と代入

* 代入は、継続をたらい回しにするのではなく、実際に使う初めての場所
* => 失敗を横取りして、代入を戻す

= 定義

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

= 代入

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

= 手続きの作用 (1)

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

= 手続きの作用 (2)

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

= 手続きの作用 (3)

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

= amb式の評価

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

= 駆動ループ

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

= おしまい

さぁ、練習問題を解こう(^^;