SICP 読み (219) 4.3.2 非決定性プログラムの例

モチ切れ状態なんですが、無理矢理進めてみます。gdgd になる可能性大。スルー気味に検討してみます。

問題 4.46

これは parse-verb-phrase とか parse-noun-phrase の作りがポイントではないかと。amb が次の選択を戻す時に再帰呼び出しを行ない、その時に渡される引数が次の選択になる、という事が例えば逆順で評価されると動かなくなる根拠ではないかなぁ。

問題 4.47

この問題面白い。けど、どういった形でバックトラックしてるのかがイメージできてないと微妙かも。とりあえず、_lectures to the student in the class with the cat_な動詞句についてヤッてみる。
とりあえず、parse-verb-phrase を見れば最初に以下のリストが出てくるのは分かる。

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

ここからどうバックトラックするか、というと_with the cat_の次は無いからこの名詞句での amb な次の要素は無い。ので_in the class_の次の amb な要素。この名詞句は

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

が

   (prep-phrase (prep in)
                (noun-phrase
                 (simple-noun-phrase (article the) (noun class)) 
                 (prep-phrase (prep with) 
			      (simple-noun-phrase (article the) (noun cat))))))

になる形。閉じ括弧の数は微妙。(何
イメージとしては '(((1 2) 3) 4) が '*1 になる形。

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

リストなソレのお陰でどこまでバックトラックするかがイメージできるな。次は_to the student_の次の要素を amb が出してくれれば良いのか。でもこれってどーゆー仕切りで

((1 (2 3)) 4)

になるのだろうか。ってこーゆールールになってるんだから、とゆーのが根拠なのか。これは何と言えばよいのか分かりませんが面白いなぁ。理解できれば問題 4.47 なソレよりもバックトラックな部分では直截に見えるんですがのう。

4.47 の手続き

これが例示されているソレをどう評価していくのか、も興味深い。parse-verb-phrase が二重三重に評価されていくように見える。この中に amb の呼び出しがあるとゆー事は、どーゆー事なのか。む、違うな。例示されているものは繰返しになってるハズ。
問題の手続きは amb の次の選択は異なる amb の選択に依存している。あらら、でも例示されているのも同じなのかな??
いや。これはループに見える。amb の次の選択は同じものしか戻らない、と言えば良いのかどうか。ちょっと違うようにも見える。ちなみに式の順が逆になったらもっとループ。
動作確認はスルーします。(何

*1:1 2) (3 4