¿Cuáles son los pros y los contras de usar la iteración manual de la lista frente a la recursión a través del error

Question

Me topa con esto todo el tiempo, y nunca estoy seguro de qué manera atacarlo. A continuación hay dos métodos para procesar algunos datos de la temporada.

Lo que estoy tratando de determinar es si usar el método 1 o 2, y cuáles son los pros y los contras de cada uno, especialmente grandes cantidades de información.

methodone parece un desperdicio ya que los hechos están disponibles, ¿por qué molestarse en construir una lista de ellos (especialmente una gran lista). Esto también debe tener implicaciones de memoria si la lista es lo suficientemente grande. Y no aprovecha la función de rastreo natural de Prolog.

methodtwo aprovecha el retroceso para hacer la recursión para mí, y supongo que sería mucho más eficiente en cuanto a la memoria, pero ¿es una buena práctica de programación en general hacer esto? Podría decirse que es más feo seguirlo, y ¿podría haber otros efectos secundarios?

Un problema que puedo ver es que cada vez que se llama fail, perdemos la capacidad de devolver algo al predicado de llamada, por ejemplo. si fue methodtwo(SeasonResults), ya que fallamos continuamente el predicado a propósito. Entonces methodtwo necesitaría afirmar hechos para almacenar el estado.

Probablemente (?) El método 2 sería más rápido ya que no tiene (grandes) listas de procesamiento que hacer?

Me imagino que si tuviera una lista, entonces methodone sería el camino a seguir ... ¿o siempre es así? ¿Podría tener sentido en cualquier condición afirmar la lista de hechos usando methodone y luego procesarlos usando el método dos? Completa locura?

Pero, de nuevo, he leído que afirmar los hechos es un negocio muy "caro", por lo que el manejo de la lista podría ser el camino a seguir, incluso para listas grandes?

¿Alguna idea? ¿O a veces es mejor usar uno y no el otro, dependiendo de (qué) situación? p.ej. para la optimización de la memoria, use el método 2, incluidos los hechos de afirmación y, para el método de uso de velocidad 1? Método

season(spring). 
season(summer). 
season(autumn). 
season(winter). 

% Season handling 
showseason(Season) :- 
    atom_length(Season, LenSeason), 
    write('Season Length is '), write(LenSeason), nl. 

% ------------------------------------------------------------- 
% Method 1 - Findall facts/iterate through the list and process each 
%-------------------------------------------------------------- 
% Iterate manually through a season list 
lenseason([]). 
lenseason([Season|MoreSeasons]) :- 
    showseason(Season), 
    lenseason(MoreSeasons). 


% Findall to build a list then iterate until all done 
methodone :- 
    findall(Season, season(Season), AllSeasons), 
    lenseason(AllSeasons), 
    write('Done'). 

% ------------------------------------------------------------- 
% Method 2 - Use fail to force recursion 
%-------------------------------------------------------------- 
methodtwo :- 
    % Get one season and show it 
    season(Season), 
    showseason(Season), 

    % Force prolog to backtrack to find another season 
    fail. 

% No more seasons, we have finished 
methodtwo :- 
    write('Done'). 

Answer 1

uno parece un desperdicio ya que los hechos están disponibles, ¿por qué molestarse creación de una lista de ellos (especialmente una lista grande). Esto también debe tener implicaciones de memoria si la lista es lo suficientemente grande.

Sí, el método 1 tiene memory (n) memoria. Su principal beneficio es que es declarativo, es decir, tiene un significado lógico directo.

El método 2, el "bucle controlado por fallas" como lo llaman los programadores de Prolog, toma memoria constante, es de procedimiento y puede ser preferido cuando se hacen cosas de procedimiento (extra-lógicas) de todos modos; es decir, en el código de E/S está bien usarlo.

Tenga en cuenta que SWI-Prolog tiene una tercera forma de escribir este bucle:

forall(season(S), showseason(S)). 

esto sólo funciona si tiene éxito showseason para cada unión de season(S).

Answer 2

Si se utiliza findall ya, por qué no maplist así:

findall(S, season(S), L), maplist(showseason, L). 

Ambos no son en el núcleo Prolog lógica pura. Y sí, asigna una lista completa para todas las soluciones.

Su segundo método se denomina "bucle controlado por fallas" y no hay nada de malo en él, excepto que no hay forma de llegar a las soluciones anteriores después del retroceso por falla. Es por eso que findall es extra-lógico. Internamente, podría ser implícito como un bucle impulsado por falla que almacena sus resultados intermedios a través de la afirmación. Por lo tanto, el segundo también es conceptualmente más limpio, además de no asignar memoria adicional. Suele emplearse en predicados de "nivel superior" de controlador (es decir, UI).

Answer 3

Veamos su ejemplo. Es muy simple, así que lo imaginaremos más complejo. Sin embargo, parece que da por hecho que los efectos secundarios son esenciales. Déjame preguntarte un poco:

En tu ejemplo, has hecho un descubrimiento muy interesante: los nombres de todas las estaciones son de la misma longitud. ¡Qué visión tan revolucionaria! Pero espera, ¿es realmente cierto? La manera más directa de verificar esto, es:

?- season(S), atom_length(S,L). 
S = spring, 
L = 6 ; 
S = summer, 
L = 6 ; 
S = autumn, 
L = 6 ; 
S = winter, 
L = 6. 

No hay necesidad de findall/3, sin necesidad de write/1.

Para obtener un mayor número de respuestas, la inspección visual no es práctica. Imagina 400 estaciones. Pero podemos verificar esto con:

?- season(S), atom_length(S,L), dif(L,6). 
false. 

Así que ahora sabemos con certeza que no hay una estación de una longitud diferente.

Esa es mi primera respuesta a su pregunta:

Como el tiempo que pueda, utilizar la cáscara de nivel superior y los procedimientos secundarios no efectuar su propio! Estira las cosas un poco más para evitar los efectos secundarios por completo. Esta es la mejor manera de evitar los bucles impulsados ​​por fallas desde el principio.

hay más razones por las que se pegue a la cáscara de nivel superior es una buena idea:

• Si los programas pueden ser fácilmente consultados en el nivel superior, será trivial para agregar casos de prueba para ellos.

• La shell toplevel es utilizada por muchos otros usuarios y, por lo tanto, está muy bien probada. Tu propia escritura es a menudo defectuosa y no probada. Piensa en las limitaciones. Piensa en escribir carrozas. ¿Usará write/1 para flotadores también? ¿Cuál es la forma correcta de escribir flotantes para que puedan leerse con precisión? Hay es una forma de hacerlo en iso-prolog. Aquí está la respuesta:

En ISO, writeq/1,2, write_canonical/1,2, write_term/2,3 con la opción quoted(true) garantía de que los flotadores pueden leerse con precisión. Es decir, son los mismos w.r.t.(==)/2

• La cáscara de nivel superior que muestra el texto Prolog válida. De hecho, ¡la respuesta en sí misma es una consulta! Se puede volver a pegar en el topevel, solo para obtener la misma respuesta. De esta manera aprenderá los detalles más exóticos pero inevitables de Prolog, como citas, escapes y horquillado. Es prácticamente imposible aprender la sintaxis de lo contrario, ya que los analizadores de Prolog a menudo son extremadamente permisivos.

• Su programa será probablemente más accesible al razonamiento declarativo.

Muy probablemente, los dos procedimientos methodone y methodtwo son incorrectas: Se le olvidó una nueva línea después de escribir Done. Entonces methodone, methodone contiene una línea confusa. ¿Cómo probar eso fácilmente?

Pero veamos un poco más en su programa. Lo que es tan típico de los bucles impulsados ​​por fallas es que comienzan inocentemente como algo que hace "solo" efectos colaterales, pero tarde o temprano tienden a atraer también más partes semánticas. En su caso, atom_length/2 está oculto en el bucle controlado por falla completamente inaccesible a las pruebas o al razonamiento.

consideraciones de eficiencia

sistemas Prolog menudo implementan fracaso por desasignar una pila. Por lo tanto, los bucles impulsados ​​por falla no requerirán un recolector de basura. Es por eso que la gente cree que los bucles impulsados ​​por fallas son eficientes. Sin embargo, este no es necesariamente el caso. Para un objetivo como findall(A, season(A), As), cada respuesta para A se copia en algún espacio. Esta es una operación trivial para algo así como átomos, pero imagina un término más grande. Di:

 
blam([]). 
blam([L|L]) :- blam(L). 

bigterm(L) :- length(L,64), blam(L). 

En muchos sistemas, findall/3 o assertz/1 para este gran término se congelará el sistema.

Además, sistemas como SWI, YAP, SICStus tienen basureros bastante sofisticados. Y usar menos bucles impulsados ​​por fallas ayudará a mejorar esos sistemas aún más, ya que esto crea una demanda de more sophisticated techniques.