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の実装がまだないので出力分は省略。
