3

私は現在、論理プログラミングに関するSICPのセクションで作業していますが、論理的推論、特にフォームへの追加ルールに関する例で立ち往生しています。それらはどのように機能しますか？私がよく理解していないのは、2番目のルールが最初のリストをどのようにcdr-downするかです。たとえば、次のようになります。

（ルール（フォームに追加（）？y？y））

（ルール（フォームに追加（？u。？v）？y（？u。？z））（フォームに追加？v？y？z））

a）どのように連絡しますか：

;;; Query input:
(append-to-form (a b) (c d) ?z)

to

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

b）そしてこれはどうですか：

;;; Query input:
(append-to-form (a b) ?y (a b c d))

to

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

c）そして最後に：

;;; Query input:
(append-to-form ?x ?y (a b c d))

to

;;; Query results:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))

ルールマッチングを実行するために必要な特定の精神的なステップに興味があります。

前もって感謝します。

4

1 に答える 1

3

一枚の紙を取り、すべてのステップを書き留めて通訳をします。ステップごとに、トリガーされた/トリガーされる可能性のあるルールと、どの変数がどの値にバインドされたかを書き留めます。

例えば：

(append-to-form (a b) (c d) ?z)

ルールをトリガーします

(rule (append-to-form (?u . ?v) ?y (?u . ?z)) 
  (append-to-form ?v ?y ?z))

と

?u = a, ?v = (b), ?y = (c d), ?z = (a . ?z_2)

注: 元のクエリの ?z は、ルール本体の ?z とは異なる変数であると想定されているため、ルールの ?z を ?z_2 に名前変更します。リスト (1 2 3) が (?a . ?b) に一致すると、リストを car/cdr するときのように ?a = 1, ?b = (2 3) が生成されます。

これらのバインディングはルールの本体に適用され(append-to-form ?v ?y ?z)ます

(append-to-form (b) (c d) ?z_2)

再びなる

(append-to-form () (c d) ?z_3)

そして、別のルールをトリガーします: (rule (append-to-form () ?y ?y))?z_3 を (cd) にバインドします。その後、再帰が開始され、?z_2 は (b . ?z_3) として定義され、?z は (a . ?z2) として定義されました。

元のクエリ(append-to-form (a b) (c d) ?z)は、?z = (a . (b . (cd))) のバインディングに適用され、返されます(append-to-form (a b) (c d) (a b c d))

残りの演習は読者に任せます ;)

ここで重要な概念は、セクション 4.2.2にあるパターン マッチングと統合です。クエリ評価全体は、SICP で最も難しい部分なので、落胆しないでください。努力する価値は十分にあります。コードを (R5RS スキームで) 実行して、トレースを追加するなど、いじってみてください。

于 2010-12-11T17:40:19.810 に答える