La notación del sucesor de Prolog produce un resultado incompleto y un ciclo infinito

Comienzo a aprender Prolog y aprendí por primera vez sobre la notación del sucesor.

Y aquí es donde descubro cómo escribir los axiomas de Peano en Prolog.

Ver la página 12 del PDF :

sum(0, M, M). sum(s(N), M, s(K)) :- sum(N,M,K). prod(0,M,0). prod(s(N), M, P) :- prod(N,M,K), sum(K,M,P). 

Puse las reglas de multiplicación en Prolog. Luego hago la consulta:

 ?- prod(X,Y,s(s(s(s(s(s(0))))))). 

Lo que significa encontrar el factor de 6 básicamente.

Aquí están los resultados.

 X = s(0), Y = s(s(s(s(s(s(0)))))) ? ; X = s(s(0)), Y = s(s(s(0))) ? ; X = s(s(s(0))), Y = s(s(0)) ? ; infinite loop 

Este resultado tiene dos problemas:

  1. No se muestran todos los resultados, tenga en cuenta que falta el resultado X = 6, Y = 1.
  2. No se detiene a menos que presione Ctrl + C y luego elija abortar.

Entonces … mis preguntas son:

  1. ¿Porqué es eso? Intenté cambiar “prod” y “sum”. El código resultante me da todos los resultados. Y de nuevo, ¿POR QUÉ es eso? Sin embargo, todavía está muerto.
  2. ¿CÓMO resolver eso?

Leí la otra respuesta en bucle infinito. Pero agradecería que alguien respondiera basándome en este escenario. Me ayuda enormemente

Si desea estudiar las propiedades de terminación en profundidad, los progtwigs que utilizan aritmética sucesora son un objeto de estudio ideal: usted sabe a priori qué debe describir, para que pueda concentrarse en los detalles más técnicos. Necesitarás entender varias nociones.

Terminación universal

La forma más fácil de explicarlo es considerar el Goal, false . Esto termina iff Goal termina universalmente. Es decir: mirar los trazadores es la forma más ineficaz: le mostrarán solo un único camino de ejecución. ¡Pero necesitas comprenderlos a todos a la vez! Además, nunca mire las respuestas cuando desee la terminación universal, solo lo distraerán. Lo has visto arriba: obtuviste tres respuestas claras y correctas, solo entonces tu progtwig se repite. Así que es mejor “apagar” las respuestas con false . Esto elimina toda distracción.

Rebanada de falla

La siguiente noción que necesita es la de una porción de falla . Tome un progtwig lógico puro monotónico y arroje algunos objectives false . Si el segmento de falla resultante no termina (universalmente), tampoco el progtwig original lo hará. En tu ejemplo, considera:

 prod (0, M, 0): - falso .
 prod (s (N), M, P): -
     prod (N, M, K), falso,
     sum (K, M, P) .

Estos objectives false ayudan a eliminar adornos irrelevantes en su progtwig: la parte restante le muestra claramente por qué prod(X,Y,s(s(s(s(s(s(0))))))). no termina. No termina, porque ese fragmento no se preocupa por P en absoluto. Esperas que el tercer argumento ayude a hacer que termine el prod/3 , pero el fragmento te muestra que todo es en vano, ya que P no ocurre en ningún objective. No hay necesidad de marcadores habladores.

A menudo no es tan fácil encontrar cortes mínimos de falla. Pero una vez que encontró uno, es casi trivial determinar su terminación o más bien propiedades de no terminación. Después de un tiempo, puede usar su intuición para imaginar una porción, y luego puede usar su razón para verificar si esa porción es relevante o no.

Lo que es tan notable acerca de la noción de un segmento de falla es esto: si quiere mejorar el progtwig, ¡ debe modificar su progtwig en la parte visible en el fragmento de arriba! Mientras no lo cambie, el problema persistirá. Un segmento de falla es, por lo tanto, una parte muy relevante de su progtwig.

Inferencia de terminación

Eso es lo último que necesita: un inferencer de terminación (o analizador) como cTI le ayudará a identificar la condición de terminación rápidamente. ¡Mire las condiciones de terminación inferidas de prod/3 y la prod2/3 mejorada aquí !


Editar: Y dado que esta era una pregunta de tarea, no he publicado la solución final. Pero para dejarlo en claro, aquí están las condiciones de terminación obtenidas hasta el momento:

     prod (A, B, C) terminates_if b (A), b (B).
     prod2 (A, B, C) termina_si b (A), b (B);  b (A), b (C) .

¡Entonces el nuevo prod2/3 es estrictamente mejor que el progtwig original!

Ahora, depende de usted encontrar el progtwig final. Su condición de terminación es:

    prod3 (A, B, C) termina_si b (A), b (B); b (C).

Para empezar, intente encontrar el corte de falla para prod2(A,B,s(s(s(s(s(s(0))))))) ! Esperamos que termine, pero aún no lo hace. ¡Toma el progtwig y agrega objectives false manualmente! ¡La parte restante te mostrará la clave!

Como una última sugerencia: debe agregar un objective adicional y un hecho.


Editar: previa solicitud, aquí está el corte de falla para prod2(A,B,s(s(s(s(s(s(0))))))) :

 prod2 (0, _, 0): - falso .
 prod2 (s (N), M, P): -
    sum (M, K, P),
    prod2 (N, M, K), falso .

 sum (0, M, M).
 sum (s (N), M, s (K)): - falso ,
     sum (N, M, K) .

Tenga en cuenta la definición simplificada de sum/3 . Solo dice: 0 más cualquier cosa es cualquier cosa. No más. Como consecuencia, incluso el prod2(A,0,s(s(s(s(s(s(0))))))) más especializado prod2(A,0,s(s(s(s(s(s(0))))))) repetirá mientras que prod2(0,X,Y) termina elegantemente …

La primera pregunta (WHY) es bastante fácil de detectar, especialmente si se sabe acerca de la recursividad a la izquierda . sum(A,B,C) vincula a A y B cuando C está vinculado, pero el progtwig original prod (A, B, C) no utiliza esas vinculaciones, y en su lugar recurse con A, B sin consolidar.

Si intercambiamos sum, prod obtenemos 2 enlaces útiles de sum para la llamada recursiva:

 sum(M, K, P) 

Ahora M está vinculado, y se usará para terminar la recursión a la izquierda. Podemos intercambiar N y M, porque sabemos que el producto es conmutativo.

 sum(0, M, M). sum(s(N), M, s(K)) :- sum(N, M, K). prod3(0, _, 0). prod3(s(N), M, P) :- sum(M, K, P), prod3(M, N, K). 

Tenga en cuenta que si intercambiamos M, K (es decir, sum (K, M, P)), cuando se invoca prod3 con P desconocido, nuevamente tenemos un bucle que no termina, pero en sum.

 ?- prod3(X,Y,s(s(s(s(s(s(0))))))). X = s(s(s(s(s(s(0)))))), Y = s(0) ; X = s(s(s(0))), Y = s(s(0)) ; X = s(s(0)), Y = s(s(s(0))) ; X = s(0), Y = s(s(s(s(s(s(0)))))) ; false. 

OT Estoy perplejo por el informe cTI: prod3 (A, B, C) terminatesif si (A), b (B); b (A), b (C).

Intereting Posts