portable - prolog online

Prólogo y limitaciones de retroceder

Question

Esta es probablemente la implementación más trivial de una función que devuelve la longitud de una lista en Prolog

count([], 0).
count([_|B], T) :- count(B, U), T is U + 1.

Una cosa acerca de Prolog que todavía no puedo entender es la flexibilidad de usar variables como parámetros.

Entonces, por ejemplo, puedo ejecutar count([a, b, c], 3). y ponte true También puedo ejecutar count([a, b], X). y recibe una respuesta X = 2. .. Curiosamente (al menos para mí) es que también puedo ejecutar count(X, 3). y obtenga al menos un resultado, que se parece a X = [_G4337877, _G4337880, _G4337883] ; antes de que el intérprete desaparezca en un ciclo infinito. Incluso puedo ejecutar algo realmente "flexible" como count(X, A). y obtenga X = [], A = 0 ; X = [_G4369400], A = 1. X = [], A = 0 ; X = [_G4369400], A = 1. , que obviamente está incompleto pero de alguna manera realmente agradable.

Por lo tanto, mi pregunta multifacética. ¿Puedo explicar de alguna manera a Prolog que no mire más allá del primer resultado al ejecutar count(X, 3). ? ¿De alguna manera puedo hacer que Prolog genere cualquier cantidad de soluciones para el count(X, A). ? ¿Existe una limitación de qué tipo de soluciones puedo generar? ¿Qué pasa con este predicado específico que me impide generar todas las soluciones para todos los posibles tipos de consultas?

Answer 1

La respuesta que obtienes para el count(X,3) consultas count(X,3) realidad no es impar en absoluto. Estás preguntando qué listas tienen una longitud de 3. Y obtienes una lista con 3 elementos. El ciclo infinito aparece porque las variables B y U en el primer objetivo de su regla recursiva están libres. No tienes nada antes de ese objetivo que podría fallar. Por lo tanto, siempre es posible seguir la recursión. En la versión de CapelliC tienes 2 objetivos en la segunda regla antes de la recursión que fallan si el segundo argumento es más pequeño que 1. Quizás sea más claro si consideras esta versión ligeramente alterada:

:- use_module(library(clpfd)).

count([], 0).
count([_|B], T) :-
    T #> 0,
    U #= T - 1,
    count(B, U).

Su consulta

?- count(X,3).

no coincidirá con la primera regla sino con la segunda y continuará recursivamente hasta que el segundo argumento sea 0. En ese punto, la primera regla coincidirá y arrojará el resultado:

X = [_A,_B,_C] ?

El jefe de la segunda regla también coincidirá pero su primer objetivo fallará porque T=0 :

X = [_A,_B,_C] ? ;
no

Sin embargo, en su versión anterior, Prolog intentará el objetivo recursivo de la segunda regla debido a las variables independientes B y U y, por lo tanto, se repetirá infinitamente.

Answer 2

Esta es probablemente la implementación más trivial

Depende del punto de vista: considere

count(L,C) :- length(L,C).

Más corto y funcional. Y este también funciona para tu caso de uso.

editar

biblioteca CLP (FD) permite

:- use_module(library(clpfd)).

count([], 0).
count([_|B], T) :- U #>= 0, T #= U + 1, count(B, U).

?- count(X,3).
X = [_G2327, _G2498, _G2669] ;
false.

(más) respondiendo a los comentarios

Era claramente sarcasmo

No, lo siento por dar esta impresión. Fue un intento de darle una respuesta sintética a su pregunta. Todos los detalles de la implementación de longitud / 2, de hecho mucho más tiempo que su código, se han ponderado cuidadosamente para proporcionarnos un componente general y eficiente.

Debe haber algún concepto general

Yo llamaría (completo) a Prolog un concepto tan general. Desde el principio, Prolog requiere que resolvamos tareas computacionales que describan relaciones entre argumentos predicados. Una vez que hemos descrito nuestras relaciones, podemos consultar nuestra ''base de datos de conocimiento'', y Prolog intenta enumerar todas las respuestas, en un orden específico .

Los conceptos de alto nivel como la unificación y la primera búsqueda en profundidad (retroceso) son claves en este modelo.

Ahora, creo que estás buscando construcciones de segundo orden como var / 1, que nos permiten razonar acerca de nuestros predicados. Tales construcciones no pueden escribirse en (puro) Prolog, y una escuela de pensamiento en crecimiento requiere evitarlos, porque son bastante difíciles de usar. Así que publiqué una alternativa usando CLP (FD), que efectivamente nos protege en alguna situación. En este contexto específico de pregunta, en realidad nos brinda una solución simple y elegante.

No estoy tratando de volver a implementar la longitud

Bueno, soy consciente de esto, pero desde count / 2 aliases length / 2, ¿por qué no estudiar el modelo de referencia? (El sitio de SWI-Prolog solía tener una fuente navegable , pero parece que está roto en este momento)