exerise 4.45-49

再掲その2。変な操作したんかなぁ・・・。まぁ日記の下書きはこっちで持ってるからいいけど。

4.3の Parsing natural language の演習分。
長いので続きから

exercise 4.45

"the professor lectures to the student in the class with the cat"
をparseに渡すと5種類の答えが返ってくるので違いを説明せよ。てな問題。
まずは以下に5種類答えが出るかチェック。

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

確かに5種類存在する。

1だと"猫がいる教室の中で、教授は生徒に講義する"
5だと"教授は猫がいる教室の中の生徒に講義する"

となってて確かに解釈が変わってくる。

exercise 4.46

ambではoperandsの評価を左から行っている。他の順序にするとプログラムが動かなくなる理由を説明せよ。

一番初期のparse-sentenceを見てみる。

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

operandsは左から右に評価されていくので、
(parse-noun-phrase) -> (parse-word-verbs)
と順に評価されている。
もしこの順序が逆だと、最初に parse-word-verbs が呼ばれるが
その時点での *unparsed* は元の文のままで、carにmemqしても動詞が出てこなくて失敗する。
(parse-noun-phrase が先に呼ばれていると、 *unparsed*は(eats)となっていて上手くいく)
まぁ破壊的操作が引数の評価順序に依存しているから当然失敗するわな。

ちなみにan-integer-starting-fromとかも、operandsが右から評価されてくと失敗するかと思ったが、ambはspecial-formなのでambの評価順に依存でしており、operandsの評価順とは無関係って感じかな。

exercise 4.47

Loisたんが「parse-verb-phraseはこう書いた方が綺麗だおwww」と提案したが、上手く動くか、そしてambの評価順に影響されるか。

Loisたんのコードは以下。

(define (parse-verb-phrase)
  (amb (parse-word verbs)
       (list 'verb-phrase
             (parse-verb-phrase)
             (parse-prepositional-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)))

上記のLoisのコードだと、上手く動いてもtry-againすると処理が戻ってこなくなったり、そもそもパース対象の文によっては最初から処理が戻らなくなる。
Loisのコードは(parse-word verbs)で失敗すると、

(parse-word verbs)が失敗 -> (list ...) の (parse-verb-phrase) を呼ぶ。-> (parse-word verbs)がまた失敗 -> 以下無限ループ。

と失敗したら永遠とループしていって終わらない。
実際に、"the student with the cat sleeps"
をパースさせようとすると、最初は名詞をsimple-noun-phraseと仮定して進むが、withが動詞の判別で失敗して無限ループに入る。

ちなみに元々のコードの方は、maybe-extendの引数の(parse-word verbs)が失敗するとそこでバックトラックして前に戻るように出来ている。
maybe-extendに処理が入る時のは(parse-word verbs) は成功した時のみ。

exercise 4.48

もっと文法拡張しようぜ！！ だとさ。
副詞や形容詞を追加したり、もっと込み入った文を扱うようにしたらいいらしい。

正直めんどいので副詞だけ追加してみた。

(define adverbs '(adverb loudly eagerly))

(define (parse-adverbe-phrase)
  (list 'adverb-phrase
        (parse-word adverbs)))

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

動詞+目的語+副詞 の場合は 動詞+目的語 で verb-phrase になってくれて上手く行くので書いてない気分。

;;; Amb-Eval input:
(parse '(the professor lectures to the student eagerly))

;;; Starting a new problem 
;;; 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)))) (adverb-phrase (adverb eagerly))))

;;; Amb-Eval input:
try-again

;;; There are no more values of
(parse '(the professor lectures to the student eagerly))

と副詞ができた気分になったので次へ。うーん、もう少し真面目にやるべきか・・・。

exercise 4.49

parse-wordの部分を変更したりしてsentenceの生成を行え。

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

(define (parse-word word-list)
  (list (car word-list) (an-element-of (cdr word-list))))

(define (generate-sentence)
  (parse-sentence))

実行

;;; Amb-Eval input:
(generate-sentence)

;;; Starting a new problem 
;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (noun student)) (verb studies))

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(sentence (simple-noun-phrase (article the) (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) (noun student)) (verb-phrase (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))) (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) (noun student)) (verb-phrase (verb-phrase (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))) (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) (noun student)) (verb-phrase (verb-phrase (verb-phrase (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))))

再帰が止まらんのでひたすらfor the student を付ける素敵な文生成器が出来上がりましたとさ。
maybe-extendの引数に回数指定でもかけておけば変わりそうだが、それでもマシな文章ができる気がしないのでここまで。

ということで次は4.3.3か。