構文解析のプログラム例である。ここでは amb と require が、これまでと違った使いかたがされている。 例えば、require を単体で使ったり、amb の引数に amb や require を使ったりなどである。
require を単体で使った場合
... require ...
require 失敗時の戻り先は、前に amb がないので、プログラムの先頭まで戻る。そのまま終了する。
require 成功時はそのまま下の式を実行して最後まで行って終了する。
この場合、駆動ループは(require false)を発行するが、やはり amb がないので先頭まで戻って終了するだけである。
本文には出てこないが amb を単体で使った場合
... amb ...
プログラムはとりあえず最後まで実行して終了する。
その後、駆動ループが、(require false) を発行して、処理を amb に戻す。
これの繰り返し
つぎは、 amb の引数から require を実行するとき
(amb 1 (require1 ...) 2) ... (require2 ...) ...
ここで、amb が引数を遅延するかどうかについて、、、 amb は構文だが、引数は遅延する。バックトラックしたときに必要な引数のみ force する。
なお、amb評価器は、関数の引数は遅延しない。
require1 の失敗時の戻り先は、amb である。
amb は引数を遅延するから、amb を実行してから、require1 を実行するという順番になるから。
require2 の失敗時の戻り先は、amb である。
次に、 amb の引数から amb を実行するとき
(amb1 1 (amb2 10 20) 2) ... (require1 ...) ...
amb1 が 1 、2 を返しているときは、require1 の戻り先は amb1 である。
amb1 が amb2 を実行して 10 、20 を返しているときは、require1 の戻り先は amb2 である。
この場合、require1 の前に実行されているのは、amb2 だからである。
amb2 のリストが無くなったときの戻り先(バックアップ先)は、amb1 である。
結局、これは (amb1 1 10 20 2) と同じ探索をしたことになる。
つぎは、 amb の引数から amb と require を実行するとき
(amb1 1 (amb2 10 (require2 ...) 20) 2) ... (require1 ...) ...
require2 の戻り先は amb2 である。
require1 の戻り先は、上と同じ
amb2の戻り先(バックアップ先)も、上と同じ
次に、parse-verb-phrase の動作の解析
再帰関数になっているので、最初の2, 3回の動作を確認する
(parse-verb-phrase)
↓
(maybe-extend (parse-word verb))
↓
(amb '('verb eats) (thunk (maybe-extend (list '('verb eats) (parse-prepostional-phrase)))))
ここで見やすくするために、'('verb eats) は動詞と書き、(parse-prepostional-phrase)は前置詞句と書く、また thunk は省略する。あと (list 動詞 前置詞句) は 動詞＋前置詞句と書く。
(parse-verb-phrase) ... ↓ (amb 動詞 (maybe-extend 動詞＋前置詞句)) ↓ (amb 動詞 (amb 動詞＋前置詞句 (maybe-extend 動詞＋前置詞句+前置詞句))) ↓ (amb 動詞 (amb 動詞＋前置詞句 (amb 動詞＋前置詞句＋前置詞句 (maybe-extend ...)))) ...
という感じになる。これは、
動詞句 = 動詞 + [前置詞句]*
という構文解析の実装そのものである。
Ex. 4.45
この章で作られた構文解析の文法は以下の通りである。
文 = 動詞句 + 名詞句
動詞句 = 動詞 + [前置詞句]*
名詞句 = 単純名詞句 + [前置詞句]*
前置詞句 = 前置詞 + 名詞句
単純名詞句 = 冠詞 + 名詞
名詞 = student | professor | cat | class
動詞 = studies | lectures | eats | sleeps
冠詞 = the | a
前置詞 = for | to | in | by | with
これを元に手作業で構文解析をすると
(①The professor) (② lectures) (③ to th students) (④ in the class) (⑤ with the cat)
1. ① + (② + (③ + (④ + ⑤)))
2. ① + (② + (③ + ④) + ⑤)
3. ① + (② + (③ + ④ + ⑤))
4. ① + (② + ③ + (④ + ⑤))
5. ① + (② + ③ + ④ + ⑤)
の5通り。
これ以外、例えば ① + (② + ((③ + ④) + ⑤)) は、((③ + ④) + ⑤) の部分に当てはまる文法がない。
Ex. 4.46
前問の文章、
(①The professor) (② lectures) (③ to th students) (④ in the class) (⑤ with the cat)
を構文解析してみる。
動詞句の解析、(parse-verb-phrase) の結果は、
(amb ② (amb ②+③ (amb ②+③+④ (amb ②+③+④+⑤ (mayby ..(require false).. ) ))))
という感じになる。amb が引数を、右から先に評価し、左にバックトラックしていくとすると、 この amb が辿る順序は、
1回目 ②+③+④+⑤ 2回目 ②+③+④ 3回目 ②+③ 4回目 ②
となる。1回目 ②+③+④+⑤ が返されたときの文全体の解析結果は
①+(②+③+④+⑤)
となる。これは正しい。
2回目 ②+③+④ が返されたとき、文全体の解析結果は
①+(②+③+④)
となる。⑤はどこにもつかない。なぜなら、2回目 ②+③+④ が返されたとき、*unparsed* は空になっているからだ。⑤は1回目に解析されたとき *unparsed* から消されているからだ。なお、2回目の②+③+④の部分は、maybe の引数で与えられている。*unparsed*から取り出すのではない。
結局 *unparsed* が空なので、構文解析は終了し、⑤なしの間違った結果になる。正しくは①+(②+③+(④+⑤)) という結果にならないといけない。
amb が右から左に評価する場合、⑤を*unparsed*から取り出す操作が各回で必要になってしまう。しかし、*unparsed*から⑤を取り出せるのは1回だけなので、うまくいかない。
*unparsed* から語を取り出せるのは1回だけということを考慮してプログラムを作らないといけない。こんな考慮が必要なのは、amb が処理を戻すとき、大域変数を元に戻さないためである。