Curso intermedio de programación en Prolog

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.

COMPARTE ESTE ARTÍCULO

COMPARTIR EN FACEBOOK
COMPARTIR EN TWITTER
COMPARTIR EN LINKEDIN
COMPARTIR EN WHATSAPP
SIGUIENTE ARTÍCULO