Caso aparentemente innecesario en el algoritmo de unificación en SICP

Question

Estoy tratando de entender el algoritmo de unificación descrito en SICP aquí

En particular, en el procedimiento '' extender si es posible '', hay un cheque (el primer lugar marcado con asterisco '' * '') que verifica si la mano derecha '' expresión '' es una variable que ya está vinculada a algo en el marco actual:

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

El comentario asociado dice:

" En el primer caso, si la variable que estamos tratando de hacer coincidir no está vinculada, pero el valor con el que estamos tratando de hacerla coincidir es en sí misma una variable (diferente), es necesario verificar si el valor está obligado, y si es así, para que coincida con su valor. Si ambas partes del partido no están vinculadas, podemos vincularnos entre sí.

Sin embargo, no puedo pensar en un caso en el que esto sea realmente necesario.

De qué está hablando, creo creo , es donde podría tener los siguientes enlaces de cuadros actualmente presentes:

{?y = 4}

Y luego se les pide que "extiendan si es posible" un enlace de? z a? y.

Con eso " * " marque el presente, cuando se le pida que extienda "? z " con '' y '', vemos que '' y '' ya está vinculado a 4, y luego intenta de forma recursiva unificar "? z " con " 4 " ;, lo que da como resultado que ampliemos el marco con "? z = 4 " ;.

Sin el cheque, terminaríamos extendiendo el marco con solo "? z =? y " ;. Pero en ambos casos, siempre que? Z no esté vinculado a otra cosa, no veo el problema.

Tenga en cuenta que si? ??z ya ya estaba vinculado a otra cosa, entonces el código no llega a la parte marcada " * " (ya habríamos recurrido a la unificación con qué? z ya había sido emparejado).

Después de pensarlo, me di cuenta de que podría haber algún tipo de argumento para generar un "más simple" MGU (Unificador más general). p.ej. es posible que desee una MGU con un número mínimo de variables que se refieran a otras variables ... es decir, preferimos generar la sustitución {? x = 4,? y = 4} que la sustitución {? x =? y,? y = 4} ... pero no creo que este algoritmo garantice este comportamiento en ningún caso, porque si le solicita que unifique " (? x 4) " con " (? y? y) " entonces todavía terminarías con {? x =? y,? y = 4}. Y si el comportamiento no se puede garantizar, ¿por qué la complejidad adicional?

¿Es correcto mi razonamiento aquí? Si no, ¿cuál es un contraejemplo donde el " * " es necesario verificar para generar una correcta MGU?

Answer 1

¡Esa es una buena pregunta!

Creo que la razón es que no desea terminar con enlaces circulares como {? x =? y,? y =? x} . En particular, unificar (? X? Y) con (? Y? X) le daría el marco circular de arriba si omite el cheque. Con el cheque, obtienes el marco {? X =? Y} como se esperaba.

Los enlaces circulares en un marco son malos, porque pueden causar que las funciones que realizan sustituciones usando el marco, como instantiate , se ejecuten en un bucle infinito.

Answer 2

Sin él, no obtendría el unificador más general . Todavía habría trabajo por hacer: unificar x e y.