SICP 4.3.2
4.45
The professor lectures to the student in the class with the cat
和訳と英語の対応がややこしいのでいったんまとめる。
文 sentence ::= verb-phrase + noun-phrase 動詞句 verb-phrase ::= verb + prep-phrase 名詞句 noun-phrase ::= simple-noun-phrase + prep-phrase 前置詞句 prep-phrase ::= preposition + noun-phrase 単純名詞句 simple-noun-phrase ::= article + noun 名詞 noun ::= student|professor|cat|class 動詞 verb ::= studies|lectures|eats|sleeps 冠詞 article ::= the|a 前置詞 preposition ::= for|to|in|by|with
- the professor
- lectures
- to the students
- in the class
- with the cat
として構文解析すると以下のようになる。 なお、意訳すると差分が不明瞭になるので直訳する。
(1) 1 + (2 + (3 + (4 + 5)))
教授は 生徒(教室(猫が居る)にいる)に 教える
(2) 1 + (2 + (3 + 4) + 5)
教授は 生徒(教室に居る)に 猫と教える
(3) 1 + (2 + (3 + 4 + 5))
教授は 生徒(教室に猫といる)に 教える
(4) 1 + (2 + 3 + (4 + 5))
教授は 教室(猫が居る)で 生徒に 教える
(5) 1 + (2 + 3 + 4 + 5)
教授は 猫と 教室で 生徒に 教える
4.46
unparsed から car で先頭要素を取り出して評価しているため、 amb も先頭要素から順に評価するようにしないと正しく動作しない。
(define (parse input) (set! *unparsed* input) (let ((sent (parse-sentence))) (require (null? *unparsed*)) sent)) (define (parse-sentence) (list 'sentence (parse-noun-phrase) (parse-verb-phrase)))
ここまでは特に問題なし。
parse-noun-phrase で問題が起きる。
(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))) (define (parse-simple-noun-phrase) (list 'simple-noun-phrase (parse-word articles) (parse-word nouns)))
左から右に評価する場合は noun-parse が先に評価される。これは問題ない(本文中の動き)。 右から左に評価する場合は、 maybe-extend が先に評価される。 maybe-extend の中では、 parse-prepositional-phraseが評価される。
(define (parse-prepositional-phrase) (list 'prep-phrase (parse-word prepositions) (parse-noun-phrase)))
ここで、 parse-word により unparsed が更新され、空になってしまうと、
(require (null? *unparsed*))
に引っかからなくなってしまい、後続のパターンが評価できなくなってしまう。
4.47
parse-verb-phrase が無限ループするため終了しない。
Louis の定義
(define (parse-verb-phrase) (amb (parse-word verbs) (list 'verb-phrase (parse-verb-phrase) (parse-prepositional-phrase))))
は、まず parse-word が評価される。
(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)))
word-list には verbs が渡されるので、 unparsed の先頭要素が動詞であれば (list verb 見つけた動詞) が返され、 unparsedにはcdr(見つけた動詞を除いた残りの文)が set! される。 unparsed の先頭要素が動詞以外の場合は require にヒットしないので ambの次の要素が評価される。(unparsedは更新されない) しかし、amb の次の要素は parse-verb-phrase であるため、最初に戻ってまた unparsed が動詞外の場合に入ってしまう。 結果、無限ループになるのでプログラムは終了しない。
4.48
副詞(adverb)句、形容詞(adjective)句をそれぞれ追加する。
(define adverbs '(adverb 副詞を列挙)) (define adjectives '(adjective 形容詞を列挙))
副詞句は、 parse-adverb-phrase を追加し、parse-verb-phrase から呼び出す。
(define (parse-adverb-phrase) (define (maybe-extend adverb-phrase) (amb adverb-phrase (maybe-extend (list 'adverb-phrase adverb-phrase (parse-prepositional-phrase))))) (maybe-extend (parse-word adverbs))) (define (parse-verb-phrase) (define (maybe-extend verb-phrase) (amb verb-phrase (maybe-extend (list 'verb-phrase verb-phrase (parse-adverb-phrase))) (maybe-extend (list 'verb-phrase verb-phrase (parse-prepositional-phrase))))) (maybe-extend (parse-word verbs)))
形容詞句は、 parse-simple-article-phrase と parse-article-phrase に追加。
(define (parse-simple-article-phrase) (list 'simple-article-phrase (parse-word articles) (parse-word adjectives))) (define (parse-article-phrase) (define (maybe-extend article-phrase) (amb article-phrase (maybe-extend (list 'article-phrase article-phrase (parse-word adjectives))))) (maybe-extend (parse-word articles)))
4.49
unparsed を処理していた部分で単語を出力するようにする。
(define (an-element-of items) (require (not (null? items))) (amb (car items) (amb (cdr items)))) (define (parse-word word-list) (list (car word-list) (an-element-of (cdr word-list)))) (define (generate-sentence) (parse-sentence))
動作するambの実装がまだないので出力分は省略。