問題4.58-4.68

質問言語続きです。

4.58

(rule (big-shot ?person)
      (and (job ?person (?department . ?rest))
           (supervisor ?person ?boss)
           (not (job ?boss (?department . ?r)))))

こんな感じ。

;;; Query input:
(big-shot ?x)
;;; Query results:
(big-shot (Scrooge Eben))
(big-shot (Bitdiddle Ben))

;;; Query input:
(and (big-shot ?x) (job ?x ?y))
;;; Query results:
(and (big-shot (Scrooge Eben)) (job (Scrooge Eben) (accounting chief accountant)))
(and (big-shot (Bitdiddle Ben)) (job (Bitdiddle Ben) (computer wizard)))

経理部門の黒幕になってみたい。

4.59

a.

;;; Query input:
(meeting ?department (Friday ?time))
;;; Query results:
(meeting whole-company (Friday 4pm))
(meeting administration (Friday 1pm))

b.

どうでもいいんですが、最初の文のAlyssa P. Hackerは驚かなかった、がよく分からない。

(rule (meeting-time ?person ?day-and-time)
      (or (meeting whole-company ?day-and-time)
          (and (job ?person (?dep . ?rest))
               (meeting ?dep ?day-and-time))))

c.

;;; Query input:
(meeting-time (Hacker Alyssa P) ?time)
;;; Query results:
(meeting-time (Hacker Alyssa P) (Friday 4pm))
(meeting-time (Hacker Alyssa P) (Wednesday 3pm))

4.60

;;; Query input:
(lives-near ?p1 ?p2)
;;; Query results:
(lives-near (Aull DeWitt) (Reasoner Louis))
(lives-near (Aull DeWitt) (Bitdiddle Ben))
(lives-near (Reasoner Louis) (Aull DeWitt))
(lives-near (Reasoner Louis) (Bitdiddle Ben))
(lives-near (Hacker Alyssa P) (Fect Cy D))
(lives-near (Fect Cy D) (Hacker Alyssa P))
(lives-near (Bitdiddle Ben) (Aull DeWitt))
(lives-near (Bitdiddle Ben) (Reasoner Louis))

うまく言葉にできないなぁ。なんだろう、lives-nearは?p1と?p2が同じ種類のオブジェクトをとる対称的な規則なので、システムの中ではこういうのに似たことをやっているので、

for (i=p; i<p_n; i++)
  for (j=p; j<p_n; j++)
    if (pred(i, j)) printf("(%d %d)\n", i, j);

2回でちゃう。(1 5)と(5 1)が出てくるのと同じこと。

こういう、

for (i=p; i<p_n; i++)
  for (j=i; j<p_n; j++)
    if (pred(i, j)) printf("%d %d\n", i, j);

ことができるなら回避できるけど、システムの性質的にできなさそう。
いや、がんばればできるんだろうか。でもたぶんやろうとするとかなり複雑なことになりそうだし、あんまりそういうことするためのシステムではないんじゃないかなぁ。などと思います。

4.61

;;; Query input:
(?x next-to ?y in (1 (2 3) 4))
;;; Query results:
((2 3) next-to 4 in (1 (2 3) 4))
(1 next-to (2 3) in (1 (2 3) 4))

;;; Query input:
(?x next-to 1 in (2 1 3 1))
;;; Query results:
(3 next-to 1 in (2 1 3 1))
(2 next-to 1 in (2 1 3 1))

4.62

まずSchemeでlast-pair作ります。

(define (last-pair lst)
  (if (null? (cdr lst))
      lst
      (last-pair (cdr lst))))

これから次の規則が分かります。

(rule (last-pair (?z . ()) (?z . ())))
(rule (last-pair (?w ?x . ?y) ?z)
      (last-pair (?x . ?y) ?z))

実行してみます。

;;; Query input:
(last-pair (3) ?x)
;;; Query results:
(last-pair (3) (3))

;;; Query input:
(last-pair (1 2 3) ?x)
;;; Query results:
(last-pair (1 2 3) (3))

;;; Query input:
(last-pair (2 ?x) (3))
;;; Query results:
(last-pair (2 3) (3))

合ってますね。
また、(last-pair ?x (3))は、これをみたす?xが無限に存在するので終わりません。

;;; Query input:
(last-pair ?x (3))
;;; Query results:

4.63

(rule (grandson ?g ?s)
      (and (son ?g ?p) (son ?p ?s)))
(rule (son ?m ?s)
      (and (wife ?m ?w) (son ?w ?s)))

sonて名前被ってるけどうまく動きますね。

;;; Query input:
(grandson Cain ?x)
;;; Query results:
(grandson Cain Irad)

;;; Query input:
(son Lamech ?x)
;;; Query results:
(son Lamech Jubal)
(son Lamech Jabal)

;;; Query input:
(grandson Methushael ?x)
;;; Query results:
(grandson Methushael Jubal)
(grandson Methushael Jabal)

しかしこの辺はほんと楽ですね。

4.64

Sussman先生はLouis嫌いなんでしょうか。

(rule (outranked-by ?staff-person ?boss)
      (or (supervisor ?staff-person ?boss)
          (and (outranked-by ?middle-manager ?boss)
               (supervisor ?staff-person ?middle-manager))))

(outranked-by (Bitdiddle Ben) ?who)

先にandのところでoutranked-byが評価されるからですね。そうすると?bossは社長に束縛されて、?middle-managerは未束縛のままoutranked-byを再帰的に呼び出す(*)。なので今度は?staff-personに可能な全ての人を調べることになります。すると社長の一つ下の人間はsupervisorのところでマッチしますが、他の人はそうではないのでまたoutranked-byにいきます。ここでも?middle-managerは未束縛、?bossは社長なので(*)に戻ります。これの繰り返しなので無限ループになります。

4.65

wheelって平より2つ以上の人ですね。

(rule (wheel ?person)
      (and (supervisor ?middle-manager ?person)
           (supervisor ?x ?middle-manager)))

wheelが生成する関係を見ればわかりやすいです。

;;; Query input:
(and (supervisor ?middle-manager ?person)
     (supervisor ?x ?middle-manager))
;;; Query results:
(and (supervisor (Scrooge Eben) (Warbucks Oliver))
     (supervisor (Cratchet Robert) (Scrooge Eben)))
(and (supervisor (Hacker Alyssa P) (Bitdiddle Ben))
     (supervisor (Reasoner Louis) (Hacker Alyssa P)))
(and (supervisor (Bitdiddle Ben) (Warbucks Oliver))
     (supervisor (Tweakit Lem E) (Bitdiddle Ben)))
(and (supervisor (Bitdiddle Ben) (Warbucks Oliver))
     (supervisor (Fect Cy D) (Bitdiddle Ben)))
(and (supervisor (Bitdiddle Ben) (Warbucks Oliver))
     (supervisor (Hacker Alyssa P) (Bitdiddle Ben)))

このように、Warbucks Oliverはwheelの関係を満たす人が4人いるため、4回出力されます。

4.66

4.65の出力結果から明らかなように、質問システムは必ずしもユーザーが期待した形で出力をするとは限らない。例えばsumでwheelを満たす人のsalaryの総額を見積もろうとしても、4.65のような出力が出てきたら正確な値を算出することはできない。
Benがこの状況を打開する方法の一つとして、queryを満たしたリストを検査して、同一オブジェクトの重複を削除することがあげられる。ただし、問題4.60で見たように、次のような

(lives-near (Hacker Alyssa P) (Fect Cy D))
(lives-near (Fect Cy D) (Hacker Alyssa P))

同じ意味を表すけれど形式的に違うような場合にも注意する必要がある。
実装してみようと頑張ってみましたができなかったのでとりあえずこれだけで勘弁してください。

4.67

正直まだ実装の細部まで把握してるかというとしてないので、イメージも湧かないです。後で思い出したらやります。

4.68

reverseをappendをつかって、まずSchemeで書いてみます。

(define (reverse lst)
  (if (null? lst)
      '()
      (append (reverse (cdr lst))
              (list (car lst)))))

これから次の規則が抽出できます。

(rule (reverse () ()))
(rule (reverse (?x . ?y) ?z)
      (and (reverse ?y ?w)
           (append ?w (?x) ?z)))

名前append-to-form長くて嫌なのでappendにしてます。実行します。

;;; Query input:
(reverse (1 2 3) ?x)
;;; Query results:
(reverse (1 2 3) (3 2 1))

;;; Query input:
(reverse ?x (1 2 3))
;;; Query results:

ということで両方に答えることはできません。二つ目のは、?zが(1 2 3)で(?x . ?y)が不定なのでandの最初の式(reverse ?y ?w)で?yと?wが不定であることより無限ループに入ります。そこでandの順番を変えると今度は1つ目のほうが無限ループに入ってしまうので、reverseはどちらか片方しか求めることができないようです。

とりあえず今日はここまで。