|
Curso intermedio de programación en Prolog |
Algoritmos y técnicas de programación
Los algoritmos utilizados en Prolog estan intimamente ligados a los términos y su estructura anidada/recursiva. Por eso, la técnica de programación por excelencia es la recursividad. Sin embargo existen técnicas propias del lenguaje como son los bucles de fallo. En este capítulo repasamos todas ellas.
Recursividad
La recursividad es la técnica por antonomasia para programar en Prolog. El lector ya habrá notado que en Prolog no existen bucles for, while, do-while, ni sentencias case, ni otras construcciones absurdas. En Prolog no hacen falta.
Todos los términos en Prolog pueden ser recursivos, y gracias a la unificación, podemos recorrer sus argumentos a voluntad. La estructura de datos más significativa con respecto a la recursividad son las listas, por eso centraremos nuestros ejemplos en ellas.
La estructura de las cláusulas de un predicado recursivo es muy simple. Como ejemplo veamos un predicado que calcula la longitud de una lista:
% La longitud de la lista vacia es cero
longitud([],0).
% La longitud de una lista es la longitud
% del resto mas uno. Como el contenido
% de la cabeza no nos interesa,
% utilizamos la variable anonima
longitud( [_|Resto], Longitud) :-
longitud(Resto,LongitudResto),
Longitud is LongitudResto+1.
Observe como el primer objetivo de la segunda cláusula es una llamada al propio predicado que estamos definiendo. Para evitar que un predicado se llame a sí mismo infinitamente debemos estar seguros de que existe almenos un caso en el que termina. Este caso se contempla en la primera cláusula y se denomina caso básico.
Otro ejemplo interesante es el predicado que concatena dos listas, que es reversible:
% Concatenar vacio con L es L...
concatena([],L,L).
% Para concatenar dos listas, sacamos
% la cabeza de la primera lista,
% luego concatenamos el resto con la segunda lista
% y al resultado le ponemos la cabeza
% de la primera lista como
% cabeza del resultado...
concatena([Cabeza|Resto],Lista,[Cabeza|RestoConcatenado]):-
concatena(Resto,Lista,RestoConcatenado).
Parámetros de acumulación
La técnica de parámetros de acumulación se suele utilizar en combinación con la recursividad. Consiste en un argumento auxiliar (o varios de ellos) que almacena la solución parcial en cada paso recursivo. Cuando llegamos al caso base, la solución parcial es la solución total.
longitud2_aux([],Parcial,Parcial).
longitud2_aux([_|Resto],Parcial,Result) :-
NParcial is Parcial+1,
longitud2_aux(Resto,NParcial,Result).
longitud2(Lista,Longitud) :-
longitud2_aux(Lista,0,Longitud).
En este ejemplo, el valor inicial del parámetro de acumulación es cero. Este valor inicial es importante para que la solución sea correcta. Por eso hemos creado el predicado longitud2/2, que se asegura el correcto uso del parámetro de acumulación. El predicado longitud2_aux/3 no debería ser ejecutado directamente.
La ventaja del parámetro de acumulación es que genera recursividad de cola, esto es, la llamada recursiva es siempre la última en ejecutarse. Esto permite a los compiladores optimizar considerablemente el uso de recursos ocasionado por la recursividad. La desventaja es que los predicados podrían resultar no reversibles.
Sentencias "case"
A modo meramente anecdótico indicamos como podría simularse una típica estructura "case" (de selección) propia de los lenguajes imperativos. Así el siguiente algoritmo:
case Dato of
1 : corromper_archivos;
2 : cancelar;
3 : formatear_disco;
end;
Se expresaría en Prolog de la siguiente manera:
case(1) :-
!,
corromper_archivos.
case(2) :-
!,
cancelar.
case(3) :-
!,
formatear_disco.
Bucles de fallo
Los bucles de fallo constituyen una técnica de programación que permite recorrer una serie de elementos y aplicarles una operación. De la misma manera que un bucle for o while.
Los bucles de fallo están basados en la capacidad para obtener varias soluciones y el backtracking para recorrerlas. La estructura general de un bucle de fallo es la siguiente:
bucle :-
generador(UnaSolucion),
filtro(UnaSolucion),
tratamiento(UnaSolucion),
fail.
bucle.
El predicado generador/1 es el encargado de enumerar los datos a tratar en cada paso del bucle. Es decir, cada una de sus soluciones será un elemento a tratar en el bucle.
El predicado filtro/1 es opcional y permite seleccionar qué elementos se van a tratar y cuales no.
El predicado tratamiento/1 es el encargado de hacer algo con el dato. Es algo así como el cuerpo de un bucle for.
Finalmente, el predicado fail/0, que esta predefinido, se encarga de que ocurra el bucle forzando el backtracking. Además incluimos una cláusula para que el bucle en sí no falle después de haberse ejecutado.
Ejemplo
El siguiente ejemplo recorre los números del uno al diez y los escribe por pantalla.
generador(Desde,_,Desde).
generador(Desde,Hasta,Valor) :-
Desde < Hasta,
NDesde is Desde+1,
generador(NDesde,Hasta,Valor).
tratamiento(Numero) :-
display(Numero),
nl.
bucle :-
generador(1,10,Numero),
tratamiento(Numero),
fail.
bucle.
En este caso no hemos utilizado filtro. El predicado generador/3 se encarga de generar los números del uno al diez. El predicado display/1 está predefinido y simplemente escribe un término por la salida standard. El predicado nl/0 también está predefinido y se encarga de escribir un salto de línea por la salida standard.
La negación por fallo
La negación en Prolog consiste en un predicado predefinido llamado '\+'/1. La negación recibe como argumento un objetivo. Si dicho objetivo tiene éxito la negación falla y viceversa. Por ejemplo: \+ (X > 5) es equivalente a X =< 5.
Parece simple, pero la negación encierra una pequeña trampa. Dicha negación no es la negación lógica sino la negación por fallo.
Esto significa que Prolog asume que aquellos objetivos que no tienen solución (fallan) son falsos. Esto se denomina asunción de mundo cerrado porque damos por supuesto que todo aquello que no se puede deducir (porque no ha sido escrito en el programa) es falso.
La negación por fallo solamente coincide con la negación lógica cuando el objetivo negado es un término cerrado (no contiene variables libres). El programador es el responsable de asegurarse esta condición.
Piense cuál es el motivo de esta condición: cuando un objetivo falla sus variables no se ligan. No obstante, su negación tiene éxito, entonces ¿ a qué valor ligamos las variables de dicha negación ?.
Ejemplo
Consideremos el siguiente programa:
estudiante(luis).
estudiante(juan).
informatico(luis).
hobby(X,musica) :-
informatico(X),
estudiante(X).
Y ahora ejecutamos el siguiente objetivo: \+ hobby(X,musica), es decir, queremos saber a quién no le gusta la música como hobby.
La negación lógica (y el sentido común) nos diría que el hobby de Juan no es la música. Sin embargo, Prolog dice que no hay nadie a quien no le guste la música.
Recuerde... en Prolog todos los predicados son falsos hasta que se demuestre lo contrario. El problema es que a veces no se puede demostrar.
© Copyright 2000-2001
Angel Fernández Pineda.
 |
 |
 |
Publicado por: manuel delgado |
|
|
