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

論理パズル

Baker, Cooper, Fletcher, MillerとSmithは五階建てアパートの異る階に住んでいる. Bakerは最上階に住むのではない. Cooperは最下階に住むのではない. Fletcherは最上階にも最下階にも住むのではない. MillerはCooperより上の階に住んでいる. SmithはFletcherの隣の階に住むのではない. FletcherはCooperの隣の階に住むのではない. それぞれはどの階に住んでいるか.

   すべての可能性を数え上げ, 与えられた制限を課すことで直截的な方法により誰がどの階に住むか決めることが出来る:~48

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

   式(multiple-dwelling)を評価すると, 結果

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

五人の女子生徒が試験を受けている. 彼らの両親は結果に対し過度の関心を持っている--- と彼らは考えている. そこで彼らは自宅へ試験について手紙を書くのに, 誰もが一つの正しい情報と一つの嘘の情報を書こうと約束した. 次は彼らの手紙の関係する部分である:

• Betty: 「Kittyは試験が二番で私は三番でした.」

• Ethel: 「私がトップと聞いてうれしいでしょう. Joanが二番でした.」

• Joan: 「私は三番でした. 可哀想なEthelはビリでした.」

• Kitty: 「私は二番になりました. Maryは四番でしかありませんでした.」

• Mary: 「私は四番でした. トップの座はBettyがとりました.」

五人の女子生徒の本当の順番はどうか.

Mary Ann Mooreの父親はヨットを持っている. また彼の四人の友人: Downing大佐. Hall氏, Barnacle Hood卿, Parker博士のそれぞれも持っている. この五人のそれぞれはまた一人ずつ娘を持っていて, それぞれ自分のヨットに他の誰かの娘の名前をつけた. Barnacle卿のヨットはGabrielleであり, Moore氏はLornaを持っている; Hall氏はRosalind. Downing大佐所有のMelissaはBarnacle卿の娘の名前をとった. Gabrielleの父親はParker博士の娘の名前をつけたヨットを持っている. Lornaの父親は誰か.

自然言語の構文解析

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


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


(define articles '(article the a))

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

   このような構文解析は, 各文法規則に対しそれぞれの手続きを持つ単純なプログラムで生成出来る. 文を構文解析するには, その二つの構成部分を認識し, 記号sentenceのタグをつけた, その二つの要素のリストを返す:

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

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

   一番下のレベルでは, 構文解析は煮詰められ, 次の未解析の語は要求された品詞の語のリストのメンバーであるかの繰り返しチェックになる. この実装には未解析の入力である大域変数*unparsed*を維持する. 語をチェックする度, *unparsed*が空でなく, それが指示したリストにある語で始っていることを要求する. そうであればその語を*unparsed*から削除し, その語を品詞と共に返す(品詞はリストの先頭にある):51

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

   構文解析を開始するには, *unparsed*に入力文全体をおき, 文の構文解析を試み, 何も残っていないことをチェックする:

(define *unparsed* '())


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

   これで構文解析器を試み, 単純なテスト文には働くことが確認出来る:

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

   requireの助けがあれば, 構文解析の制約を表現するのが便利なので, ここではamb評価器は有用である. しかし自動探索とバックトラックは, 要素のいろいろな分解法が出てくる更に複雑な文法を考える時に本当に有効である.

   文法に前置詞のリスト

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

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

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

   ついでに名詞句の定義を改善し, 「a cat in the class」のようなものも許すように出来る. これまで名詞句と呼んでいたものは, 単純名詞句と呼ぶことにし, 名詞句は単純名詞句か前置詞句で拡大した名詞句とする:

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

   新しい文法は更に複雑な文の構文解析が出来る. 例えば

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

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

   ある入力は一つを超えた合法的構文解析を持つかも知れない. 「The professor lectures to the student with the cat」という文では, 教授が猫をつれて講義しているかも知れず, あるいは学生が猫をつれているかも知れない. われわれの非決定性プログラムは両方の可能性を見出す:

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

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

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

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

48 われわれのプログラムは次の手続きを使って, リストの要素が異るかどうか調べることが出来る:

(define (distinct? items)
  (cond ((null? items) true)
        ((null? (cdr items)) true)
        ((member (car items) (cdr items)) false)
        (else (distinct? (cdr items)))))

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