resueltos - ¿Cómo funciona Prolog a través de consultas recursivas usando succ?

listas en prolog

Question

¿Puede alguien explicarme por qué esta consulta de prólogo funciona de la manera en que lo hace? La definición es:

add(0,Y,Y). 
add(succ(X),Y,succ(Z)):- add(X,Y,Z).

Dado este:

?-  add(succ(succ(succ(0))),  succ(succ(0)),  R).

Aquí está el rastro de la consulta:

Call:  (6)  add(succ(succ(succ(0))),  succ(succ(0)),  R) 

Call:  (7)  add(succ(succ(0)),  succ(succ(0)),  _G648) 

Call:  (8)  add(succ(0),  succ(succ(0)),  _G650) 

Call:  (9)  add(0,  succ(succ(0)),  _G652) 

Exit:  (9)  add(0,  succ(succ(0)),  succ(succ(0))) 

Exit:  (8)  add(succ(0),  succ(succ(0)),  succ(succ(succ(0)))) 

Exit:  (7)  add(succ(succ(0)),  succ(succ(0)), 
                                              succ(succ(succ(succ(0))))) 

Exit:  (6)  add(succ(succ(succ(0))),  succ(succ(0)), 
                                                succ(succ(succ(succ(succ(0))))))

La parte que más me confundió acerca de ese tutorial fue el hecho de que en el primer argumento, el succ es despojado y recursivo. Sin embargo, aunque recursivo, R gana ... ¿CÓMO? Además, ¿de dónde viene el cero en la primera salida (9)? Soy nuevo en Prolog, y estoy tratando de entender el lenguaje para una tarea. Cualquier ayuda muy apreciada. Gracias de antemano.

Nota: para cualquier persona interesada, el enlace a este tutorial es http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse9

Answer 1

Verá, call y exit son verbs , acciones que el intérprete intenta resolver la consulta que plantea. Luego, un trazo expone detalles del trabajo real realizado y le permite verlo en perspectiva histórica.

Cuando Prolog debe elegir una regla (una call ), utiliza el name que le da (llamado functor ) e intenta unify cada argumento en el encabezado de la regla. Entonces decimos habitualmente que Prolog considera también la arity , es decir, el número de argumentos, para la selección.

Unification intenta ''hacer iguales'' dos términos, y los resultados dignos de mención son los llamados bindings de variables. Ya sabes que las variables son esos nombres que comienzan en Uppercase . Dichos nombres identifican valores no especificados en las reglas, es decir, son placeholders de placeholders para los argumentos. Para evitar confusiones, cuando Prolog muestra la traza, las variables se renombran para que podamos identificarlas, porque el detalle relevante son las identities o enlaces establecidos durante la prueba.

Luego ves tales símbolos _G648 en traza. Se quedan para los argumentos que aún no se han instanciado de la meta llamada, es decir, R y Z R es único (se produce justo en la llamada de nivel superior), por lo que este Prolog guarda amablemente el nombre amigable para el usuario, pero Z proviene del programa, potencialmente ocurre varias veces y luego se renombra.

Para responder a esta consulta

?-  add(succ(succ(succ(0))),  succ(succ(0)),  R).

Prolog intenta primero hacer coincidir

add(0,Y,Y). 

y fallar porque succ (succ (succ (0)) no se puede hacer igual a 0. Entonces intenta

add(succ(X),Y,succ(Z)) :- add(X,Y,Z).

por lo tanto, debe resolver estos enlaces (a la izquierda los términos de la persona que llama):

succ(succ(succ(0))) = succ(X)
succ(succ(0)) = Y
R = Z

Puedes ver por qué X se convierte en succ(succ(0)) , y tenemos un nuevo objetivo que probar, es decir, el cuerpo de regla add(X,Y,Z) con los enlaces recién establecidos:

agregar (succ (succ (0)), succ (succ (0)), _ G648)

y así sucesivamente ... hasta que X se convierta en 0 y el objetivo coincida

add(0,Y,Y).

Entonces Y se convierte en succ (succ (0)), y también vale la pena dar un valor a Z en la regla de llamada.

HTH

Answer 2

"¿De dónde viene el cero en la primera salida (9)?"

La llamada add(0, succ(succ(0)), _G652) se unifica con la primera cláusula que dice que si el primer argumento de add es cero, entonces el segundo y el tercero son iguales. En esta situación particular, la variable _G652 convierte en succ(succ(0)) .

"Sin embargo, aunque recursivo, R gana ... ¿CÓMO?"

Este es el resultado de la aplicación de la segunda cláusula. Esta cláusula establece (más o menos) que primero se succ del primer argumento, luego se add recursively y, finalmente, se agrega otra "capa" de succ al tercer argumento que vuelve de esta llamada recursiva.

El add predicado no es más que una implementación directa de adición en la aritmética Peano: http://en.wikipedia.org/wiki/Peano_axioms#Addition