una resumen resultados recursividad recorrer organigrama miembro metas listas lista ejemplos contar clausula prolog infinite-loop failure-slice successor-arithmetics non-termination

resumen - recorrer listas en prolog



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

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 programa original prod (A, B, C) no utiliza esas vinculaciones, y en su lugar recurse con A, B sin consolidar.

Si intercambiamos suma, prod obtenemos 2 enlaces útiles de suma 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, suma (K, M, P)), cuando se invoca prod3 con P desconocido, nuevamente tenemos un bucle que no termina, pero en suma.

?- 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).

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 programas que utilizan successor-arithmetics 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 programa 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 programa lógico puro monotónico y arroje algunos objetivos false . Si el segmento de falla resultante no termina (universalmente), tampoco el programa original lo hará. En tu ejemplo, considera:

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

Estos objetivos false ayudan a eliminar adornos irrelevantes en su programa: 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 objetivo. 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 programa, ¡ debe modificar su programa 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 programa.

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 here !

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)terminates_if b(A),b(B);b(A),b(C).

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

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

prod3(A,B,C)terminates_if 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 programa y agrega objetivos false manualmente! ¡La parte restante te mostrará la clave!

Como una última sugerencia: debe agregar un objetivo 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) :- false. prod2(s(N), M, P) :- sum(M, K, P), prod2(N,M,K), false. sum(0, M, M). sum(s(N), M, s(K)) :- false, 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 ...