Scheinbar unnötiger Fall im Unifikationsalgorithmus in SICP

Question

Ich versuche, den Unifikationsalgorithmus in SICP hier

Insbesondere in dem Verfahren „extend-if-möglich“, gibt es eine Prüfung (der erste Ort, die mit Sternchen „*“), die, wenn die rechte Hand „Ausdruck“ zu sehen ist, überprüft eine Variable, die bereits gebunden ist etwas im aktuellen Rahmen:

(define (extend-if-possible var val frame)
  (let ((binding (binding-in-frame var frame)))
    (cond (binding
       (unify-match
        (binding-value binding) val frame))
      ((var? val)                      ; *** why do we need this?
       (let ((binding (binding-in-frame val frame)))
         (if binding
             (unify-match
              var (binding-value binding) frame)
             (extend var val frame))))
      ((depends-on? val var frame)
       'failed)
      (else (extend var val frame)))))

Der zugehörige Kommentar lautet:

"Im ersten Fall, wenn die Variable, die wir zu passen versuchen, ist nicht gebunden, sondern der Wert, den wir versuchen, es zu entsprechen mit selbst einem (anderen) Variable, ist es notwendig, zu prüfen, ob der Wert gebunden ist, und wenn ja, um seinen Wert zu entsprechen. wenn beide Parteien zu dem Spiel ungebunden sind, können wir entweder auf den anderen binden. "

Allerdings kann ich nicht von einem Fall denken, wenn dies tatsächlich erforderlich ist.

Was ist es spricht, I denken , ist, wo Sie die folgenden Rahmenbindungen haben könnten zur Zeit vorhanden:

{?y = 4}

Und werden dann gebeten, "extendIfPossible", um eine Bindung von? Z? Y.

Mit diesem „*“ überprüfen vorhanden, wenn Sie gefragt zu verlängern? „Z“ mit „? Y“, sehen wir, dass „? Y“ bereits bis 4 gebunden ist, und versuchen Sie dann rekursiv zu vereinigen? „Z“ mit " 4" , die bei uns zur Verlängerung der Rahmen mit den Ergebnissen? "z = 4".

Ohne die Kontrolle, würden wir den Rahmen mit nur „? Z = y“ am Ende erstreckt. Aber in beiden Fällen, so lange? Z nicht bereits auf etwas anderes gebunden ist, ich sehe das Problem nicht.

Beachten Sie, wenn? Z had bereits gebunden worden, um etwas anderes dann wird der Code nicht der Teil erreichen „*“ gekennzeichnet (wir bereits rekursiv zu vereinen mit dem, was hätte? Z hatte bereits angepasst).

Nachdem es vorbei denken, ich habe erkannt, dass es vielleicht eine Art Argument für die Erzeugung eines „einfachsten“ MGU (allgemeinster Unifikator). z.B. Sie könnten eine MGU mit einer minimalen Anzahl von Variablen, die auf andere Variablen wollen ... das heißt, wir eher die Substitution erzeugen würden {? x = 4,? y = 4} als die Substitution {? x = y,? y = 4} ... aber ich glaube nicht, diesen Algorithmus kann dieses Verhalten in jedem Fall garantiert, denn wenn man danach gefragt zu vereinen „(? x 4)“ mit „(? y? y)“, dann würden Sie noch am Ende mit {? x = y, & Delta; y = 4}. Und wenn das Verhalten nicht garantiert werden kann, warum die zusätzliche Komplexität?

Ist meine Argumentation hier alle richtig? Wenn nicht, was ist ein Gegenbeispiel, wo die „*“ Überprüfung notwendig ist, ein richtig MGU?

zu erzeugen,

Answer 1

Das ist eine gute Frage!

Ich denke, der Grund ist, dass Sie wollen nicht am Ende mit kreisförmigen Bindungen wie { ?x = ?y, ?y = ?x }. Insbesondere wäre vereinigende (?x ?y) mit (?y ?x) geben Sie das Rondell oben, wenn Sie die Prüfung verzichtet. Mit der Prüfung erhalten Sie den Rahmen {? X = y}, wie erwartet.

Rund Bindungen in einem Rahmen sind schlecht, weil sie Funktionen ausführen Ersetzungen mit dem Rahmen, wie instantiate verursachen können, in einer Endlosschleife laufen.

Answer 2

Ohne sie würden Sie nicht bekommen das allgemeinste Einige. Es gibt noch Arbeit sei getan werden. Vereinigende x und y