caso aparentemente desnecessário no algoritmo de unificação em SICP

Question

Eu estou tentando entender o algoritmo de unificação descrito no SICP aqui

Em particular, no procedimento "estender-se-possível", há uma verificação (o primeiro lugar marcadas com asterisco "*"), que está a verificar para ver se a "expressão" mão direita é uma variável que já está ligado a algo no quadro atual:

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

Os estados comentário associado:

"No primeiro caso, se a variável que estamos tentando jogo não está ligado, mas o valor que estamos a tentar combiná-lo com é em si uma variável (diferente), é necessário verificar se o valor é amarrado e, em caso afirmativo, para coincidir com o seu valor. Se ambas as partes do jogo são desacoplado, podemos ligar nem para a outra. "

No entanto, não posso pensar em um caso em que este é realmente necessário.

O que é que está falando, eu pensar , é o lugar onde você pode ter as seguintes ligações quadro atualmente presentes:

{?y = 4}

E são, então, pediu para "extendIfPossible" uma ligação a partir de? Z para? Y.

Com que "*" cheque presente, quando solicitado a estender "? Z" com "? Y", vemos que "? Y" já está ligado a 4, e depois de forma recursiva tentar unificar "? Z" com " 4" , o que resulta nos que se prolongam com o quadro com "? z = 4".

Sem o cheque, que acabaria estendendo o quadro com apenas "? Z =? Y". Mas em ambos os casos, desde que? Z ainda não estiver ligado a alguma outra coisa, eu não vejo o problema.

Note, se? Z estiveste já foi vinculado a alguma outra coisa, em seguida, o código não alcançar a parte marcada "*" (já teríamos recursed a unificação com o quê? Z já tinha sido combinado com).

Depois de pensar sobre isso, eu percebi que poderia haver algum tipo de argumento para gerar uma "simples" MGU (mais geral Unificador). por exemplo. você pode querer uma MGU com um número mínimo de variáveis ??referentes a outras variáveis ??... isto é, nós preferimos gerar a substituição {? x = 4,? y = 4} do que a substituição {? x =? y,? y = 4} ... mas eu não acho que este algoritmo poderia garantir esse comportamento em qualquer caso, porque se você pediu para unificar "(? x 4)" with "(? y? y)", então você faria ainda acabar com {? x =? y,? y = 4}. E se o comportamento não pode ser garantida, porque a complexidade adicional?

É o meu raciocínio aqui todos corretos? Se não, o que é um contra-exemplo onde o cheque "*" é necessário para gerar um correta MGU?

Answer 1

Essa é uma boa pergunta!

Eu acho que a razão é que você não quer acabar com ligações circulares como { ?x = ?y, ?y = ?x }. Em particular, unificando (?x ?y) com (?y ?x) lhe daria a moldura circular acima se omitido o cheque. Com o cheque, você começa a moldura {? X =? Y} como esperado.

ligações circulares em um frame são más, porque eles podem causar funções realizando substituies usando o quadro, tal como instantiate, para ser executado num ciclo infinito.

Answer 2

Sem ele, você não iria obter o mais geral unificador. Há ainda estaria trabalho a ser feito:. Unificar x e y