Wie funktioniert Append-to-Form? (SICP's Abschnitt über Logic Programming)

Question

Ich arbeite derzeit durch SICP Abschnitt über Logic Programming, aber ich steckte in den Beispielen in Bezug auf logische Schlussfolgerungen, vor allem die Append-to-Form-Regeln. Wie arbeiten Sie? Was ich nicht ganz verstehe, ist, wie die zweite Regel die erste Liste durchsucht. Zum Beispiel gegeben:

(Regel (append-to-Form() y y)??)

(Regel (append-to-Form (U v) y (u?.???. ? z)) (append-to-Form v y z))

a) Wie erreichen wir aus:?

;;; 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) Und was Kampf dieses:

;;; 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) Und schließlich:

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

würde ich in den spezifischen mentalen Schritte Interesse erforderlich ist, um die Regelanpassungs auszuführen.

Vielen Dank im Voraus.

Answer 1

Spielen Sie den Interpreter, indem Sie ein Stück Papier nehmen und jeden einzelnen Schritt aufschreiben. Für jeden Schritt notieren Sie, welche Regel ausgelöst wurde und welche Variable an welchen Wert gebunden war.

Zum Beispiel:

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

löst die Regel

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

mit

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

Hinweis: z in der ursprünglichen Abfrage soll von einer anderen Variable sein z? im Regelkörper benennen Sie daher die Regel? z in? z_2 um. Eine Liste (1 2 3) erzeugt, wenn sie an (& thgr; a. & Thgr; b) angepasst ist, & thgr; a = 1, & thgr; b = (2 3) wie wenn eine Liste gelöscht wird.

Diese Bindungen an den Körper der Regel angewendet (append-to-form ?v ?y ?z) So bekommen wir

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

wieder die

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

und löst eine andere Regel wird: (rule (append-to-form() ?y ?y)) Bindung Z_3 bis (c d)?. Dann Rekursion tritt in,? Z_2 wurde als definiert (b.? Z_3),? Z, wie definiert wurde (a.? Z2)

die ursprüngliche Abfrage (append-to-form (a b) (c d) ?z) zu den Bindungen angewandt wird, in dem? Z = (a. (b (cd).)) und gibt (append-to-form (a b) (c d) (a b c d))

der Rest der Übungen für den Leser überlassen;)

die entscheidenden Begriffe hier sind pattern-Matching und Vereinigung, die bei section 4.2.2 gefunden werden kann. Der gesamte Abfrage-Evaluator ist wirklich das schwierigste Stück in SICP, also nicht entmutigen. Es ist die Mühe wert. Versuchen Sie, den Code (in einem R5RS-Schema) auszuführen und damit zu experimentieren, z.