問題4.45-4.49

sicp

随分久しぶりで何やってたか思い出せないです。どうやら前回はamb評価器でパズルを解いてたみたいです。なので今回は次の自然言語の構文解析についてやります。

4.45

;;; Amb-Eval input:
(parse '(the professor lectures to the student in the class with the cat))
;;; Starting a new problem 
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb-phrase (verb-phrase (verb lectures) (prep-phrase (prep to) (simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class)))) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat)))))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(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 in) (noun-phrase (simple-noun-phrase (article the) (noun class)) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat)))))))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb-phrase (verb lectures) (prep-phrase (prep to) (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class)))))) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat)))))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb lectures) (prep-phrase (prep to) (noun-phrase (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class)))) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat)))))))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(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 in) (noun-phrase (simple-noun-phrase (article the) (noun class)) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat)))))))))

;;; Amb-Eval input:
try-again
;;; There are no more values of
(parse '(the professor lectures to the student in the class with the cat))

括弧の位置が違います。つまり前置詞のかかりかたの違いです。
面倒なのでこれで許してください。

4.46

parse-wordを見ると分かります。例えば、

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

"the cat eats."という文についてamb評価器が右から評価される場合、parse-sentenceを評価しようとしてまず(parse-word verbs)を評価します。この時(require (memq (car *unparsed*) (cdr word-list)))の部分で(car *unparsed*) == 'theが(cdr word-list) == verbsのメンバーであることが要求されていますが、theは冠詞なので動詞のリストに含まれることはありません。なのでどのような入力に対しても構文解析が実行されないことになります。

4.47

try-againを繰り替えすと終わらなくなります。ambの非演算子の順序を替えるといきなり無限ループに突入します。
後者の方はよく考えると当然で、parse-verb-phraseを永遠に再帰呼び出ししてるからです。
前者は(parse-word verbs)がマッチすると値が返ってくるので、マッチしている間はparse-verb-phraseの無限ループに陥らないからだと思われます。ということで前のに戻しておきましょう。

4.48

僕英語苦手なんで、形容詞だけにします。
形容詞といっても、be動詞とか入れると面倒なので冠詞と名詞の間に形容詞が入るような句を名詞句に追加します。また形容詞+名詞の部分を形容詞句とします。形容詞はいくつくっつけても文法的にはたぶん正かったような気がするので、これに注意します。
つまり、

  • 名詞句=単純名詞句+前置詞句+...
  • 単純名詞句=冠詞+形容詞句 or 冠詞+名詞
  • 形容詞句=形容詞+...+形容詞+名詞

です。

まず適当に形容詞リストを作ります。

(define adjectives '(adj easy difficult fast fat thin tall small awesome big))

単純名詞句を変更します。

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

形容詞句生成手続きを書きます。

(define (parse-adjective-phrase)
  (maybe-adjective-extend (list (parse-word adjectives))))
(define (maybe-adjective-extend adj-phrase)
  (amb adj-phrase
       (maybe-adjective-extend (cons 'adj-phrase
                                     (append adj-phrase
                                             (list (parse-word nouns)))))
       (maybe-adjective-extend (append adj-phrase
                                       (list (parse-word adjectives))))))

これでおけーなはずです。形容詞句のtag付けの形式が他のと若干互換ないような感じでいまいちですが。

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

;;; Amb-Eval input:
try-again
;;; There are no more values of
(parse '(the big fat cat eats))

;;; Amb-Eval input:
(parse '(the big fat fast awesome cat in the class with the professor sleeps))
;;; Starting a new problem 
;;; Amb-Eval value:
(sentence (noun-phrase (noun-phrase (simple-noun-phrase (article the) (adj-phrase (adj big) (adj fat) (adj fast) (adj awesome) (noun cat))) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class)))) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun professor)))) (verb sleeps))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(sentence (noun-phrase (simple-noun-phrase (article the) (adj-phrase (adj big) (adj fat) (adj fast) (adj awesome) (noun cat))) (prep-phrase (prep in) (noun-phrase (simple-noun-phrase (article the) (noun class)) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun professor)))))) (verb sleeps))

;;; Amb-Eval input:
try-again
;;; There are no more values of
(parse '(the big fat fast awesome cat in the class with the professor sleeps))

;;; Amb-Eval input:
(parse '(the big fat cat eats the thin student))
;;; Starting a new problem 
;;; There are no more values of
(parse '(the big fat cat eats the thin student))

他動詞には対応してなかった。
あとすごくどうでもいいんですけど、big fat catは中学生のころ読んで結構気に入ってました。でぶねこって妙にかわいいような気がします。

4.49

ambで(car *unparsed*)を含む品詞の語群から語を生成すればいいと思うんだけど、applyが使えないから簡単にかけない。というかambは特殊形式だったからどっちにしろ使えないや。
そうすると、parse-wordの中にamb式を埋め込まないといけないのかな。ググるとそうみたいなので書いてみます。

(define (parse-word word-list)
  (require (not (null? *unparsed*)))
  (require (memq (car *unparsed*) (cdr word-list)))
  (set! *unparsed* (cdr *unparsed*))
  (let ((tag (car word-list)))
    (list tag
          (cond
            ((eq? tag 'noun)
             (amb 'student 'professor 'cat 'class))
            ((eq? tag 'verb)
             (amb 'studies 'lectures 'eats 'sleeps))
            ((eq? tag 'prep)
             (amb 'for 'to 'in 'by 'with))
            ((eq? tag 'adj)
             (amb 'easy 'difficult 'fast 'fat 'thin 'tall 'small 'awesome 'big))
            ((eq? tag 'article)
             (amb 'the 'a))
            (else
             (error "illegal tag" tag))))))

で実行してみます。

;;; Amb-Eval input:
(parse '(the big fat cat eats in the class))
;;; Starting a new problem 
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (adj-phrase ((adj easy) (adj easy)) (noun student))) (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (adj-phrase ((adj easy) (adj easy)) (noun student))) (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun professor)))))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (adj-phrase ((adj easy) (adj easy)) (noun student))) (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun cat)))))

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (adj-phrase ((adj easy) (adj easy)) (noun student))) (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun class)))))

退屈というより意味不明な文ですね。なんか4.50で改善するとか書いてありますけどどうやるんでしょうか。


とりあえず今日はここまで。