SICP 読み (218) 4.3.2 非決定性プログラムの例
昨晩のエントリは日本語がぶち壊れている。休みに疲労回復をしなければイケナいんですが、そうなってないのが非常にナニ。
問題 4.45
こつこつ机上でヤリたいのですが、手続きがとっちらかっててワケワカなのが敗因かもしれない、とゆー事で以下に整理してみる事に。
(define *unparsed* '())
(define (parse input)
(set! *unparsed* input)
(let ((sent (parse-sentense)))
(require (null? *unparsed*))
sent))
(define nouns '(noun student professor cat class))
(define verbs '(verb studies lectures eats sleeps))
(define articles '(article the a))
(define prepositions '(prep for to in by with))
(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)))
(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)))
(define (parse-prepositional-phrase)
(list 'prep-phrase
(parse-word prepositions)
(parse-noun-phrase)))
(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-sentense が終わった時点で *unparsed* が null になってないと駄目という事か。で、問題の_The professor lectures to the student in the class with the cat._という文なんですが、最初の_The professor_については固定で lectures 以降の文節 (って言えばよいのかなぁ) の評価が異なる、という方向で検討してみます。そうすれば parse-verb-phrase が _lectures to the students in the class with the cat_ をどう解析するか、に限定できるんですが甘いかな。
とりあえずこつこつ捌いてみる。
まず最初に parse-verb-phrase が呼び出された時点で maybe-extend には (verbs lecture) が渡されて amb がそれを戻します。がしかし、*unparsed* には以降の文節が残ったままなんでアウト。
次に maybe-extend に渡すリストなんですが、とりあえず parse-prepositional-phrase を呼び出さないとマズい。ええとこれは
'(prep-phrase (prep to) (simple-noun-phrase (article the) (noun student)))
を戻すのか。で、
(verb-phrase (verb lecture) (prep-phrase (prep to) (simple-noun-phrase (article the) (noun student))))
が maybe-extend に渡されて amb でそれが戻りますが _in the class with the cat_が *unparsed* に残ってるのでアウト認定。さらに上記のリストが maybe-extend に渡される、と。あ、違うな。以下だ。(ちょっと中略
(verb-phrase (verb-phrase (verb lecture) (prep-phrase (prep to) (simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class))))
で、これも *unparsed* に残りがあるのでアウト認定。さらに以下が maybe-extend に。
(verb-phrase (verb-phrase (verb-phrase (verb lecture) (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))))
ここで *unparsed* は空なので最初に parse-verb-phrase が戻すのはこれになるはず。これは教室の中のネコと一緒に教授が学生にレクチャ、でいいのかな。
で、try-again されたらどこに戻るのか、というと。
次
どこだろう。(何
まず、parse-verb-phrase の次に行こうとするのかなぁ。ここでも次は無いし、_with the cat_を戻した parse-prepositional-phrase というか parse-noun-phrase でも NG。てコトは
(verb-phrase (verb-phrase (verb lecture) (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 in) (noun-phrase (simple-noun-phrase (article the) (noun class)) (prep-phrase (prep with) (nou-phrase (simple-noun-phrase (article the) (noun cat))))))
になるのか。合わせると以下。
(verb-phrase (verb-phrase (verb lecture) (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) (nou-phrase (simple-noun-phrase (article the) (noun cat)))))))
もうワケワカ。ここで *unparsed* は空になるので、これが次の解か。これはネコと一緒の教室 (って何だ) の中で教授が学生にレクチャ、になるんかな。意味分からん。
これ、本当に五通りあるんかな。
その次
ちょっとパターン見切れてる感じではあるんですが微妙かも。次は
(verb-phrase (verb lecture) (prep-phrase (prep to) (simple-noun-phrase (article the) (noun student))))
まで戻る感じかなぁ。
(prep-phrase (prep to) (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (simple-noun-phrase (article the) (noun class)))))
が最初なんですが、これは *unparsed* に残りがあるんで NG。次の候補は何だ。これか。
(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)))))))
入れ子深スギ。この次ってどうなるんだろ。とりあえずこれビンゴ認定のはずなんで全体としては以下のようになるはず。
(verb-phrase (verb lecture) (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))))))))
これは_ネコと一緒のクラス_の中にいる学生に教授がレクチャ、で良いのだろうか。これで三つ目。本当にあと二つあるのかなぁ。イキオイついちゃって止まりません。(を
さらに次
入れ子が深いのでさらに範囲を限定してみよう。最初からココだけ見てれば良かったのかも、とは言え以下が上記のナニ。
(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)))))))
これ、_with the cat_の次は無い。こうなるの??
(prep-phrase (prep to) (noun-phrase (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)))))
これは、_ネコと一緒な_クラスの中にいる学生に教授がレクチャって微妙。しかもスデにどこにバックトラックするのか分からん。ぱっと見以下??
(prep-phrase (prep to) (noun-phrase (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (noun-phrase (noun-phrase (simple-noun-phrase (article the) (noun class))) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat))))))))
これは三つ目とどう違うんだろうか。てか、入れ子が微妙だぞ。セットになってない。こうなるのかなぁ。
(prep-phrase (prep to) (noun-phrase (simple-noun-phrase (article the) (noun student)) (prep-phrase (prep in) (noun-phrase (noun-phrase (simple-noun-phrase (article the) (noun class))) (prep-phrase (prep with) (simple-noun-phrase (article the) (noun cat)))))))
駄目だ。時間も無いし別途実機で確認。きちんと図で整理すべきだな、これは。でも具体的にどうすれば良いのかは不明。(とほほほ
実機で確認
最初、
(parse '(The professor lectures to the student in the class with the cat))
ってやってて、解はなーんも無し、という返答がありアセる。で、以下が評価させた結果をそのまま貼り付けたモノです。一部整形済み。
;;; 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))
;;; Amb-Eval input:精査が大変。今から見てみます。って微妙に合ってたり違ってたりするな。マンガというかリストにしてみたら以下な感じなんだろうか。これって五通り限定なのかなぁ。
(((1 2) 3) 4) ;; 最初 ((1 2) (3 4)) ;; 二番目 ((1 (2 3)) 4) ;; 三番目 (1 ((2 3) 4)) ;; 四番目 (1 (2 (3 4))) ;; 五番目
うーん。成程と言えば良いのかどうかさえ不明。(何
答え合わせな結果としては、最初と四番目、五番目は合ってる模様。二番目は微妙に違ってて、三番目が全然ダメ。三番目で verb-phrase の入れ子は取れる、と読んでたのが敗因ッス。上記リストのイメージが出来てれば、もう少しなんとかなったんだけどなぁ。後悔先に立たず、です。
