Tutorial básico de programación en Prolog

Los predicados son los elementos ejecutables en Prolog. En muchos sentidos se asemejan a los procedimientos o funciones t�picos de los lenguajes imperativos.

Una llamada concreta a un predicado, con unos argumentos concretos, se denomina objetivo (en ingl�s, goal). Todos los objetivos tiene un resultado de �xito o fallo tras su ejecuci�n indicando si el predicado es cierto para los argumentos dados, o por el contrario, es falso.

Cuando un objetivo tiene �xito las variables libres que aparecen en los argumentos pueden quedar ligadas. Estos son los valores que hacen cierto el predicado. Si el predicado falla, no ocurren ligaduras en las variables libres.

�Ejemplos

El caso m�s b�sico es aqu�l que no contiene variables: son_hermanos('Juan','Maria'). Este objetivo s�lamente puede tener una soluci�n (verdadero o falso).

Si utilizamos una variable libre: son_hermanos('Juan',X), es posible que existan varios valores para dicha variable que hacen cierto el objetivo. Por ejemplo para X = 'Maria', y para X = 'Luis'.

Tambi�n es posible tener varias variables libres: son_hermanos(Y,Z). En este caso obtenemos todas las combinaciones de ligaduras para las variables que hacen cierto el objetivo. Por ejemplo, X = 'Juan' y Z = 'Maria' es una soluci�n. X = 'Juan' y Z = 'Luis' es otra soluci�n.

�Secuencias de objetivos

Hasta ahora hemos visto como ejecutar objetivos simples, pero esto no resulta demasiado �til.

En Prolog los objetivos se pueden combinar mediante conectivas propias de la l�gica de primer orden: la conjunci�n, la disyunci�n y la negaci�n.

La disyunci�n se utiliza bien poco y la negaci�n requiere todo un cap�tulo para ser explicada. En cambi� la conjunci�n es la manera habitual de ejecutar secuencias de objetivos.

El operador de conjunci�n es la coma, por ejemplo: edad(luis,Y),edad(juan,Z),X>Z. Parece sencillo, pero hay que tener en cuenta qu� ocurre con las ligaduras de las variables:

• En primer lugar, hay que ser consciente de que los objetivos se ejecutan secuencialmente por orden de escritura (es decir, de izquierda a derecha).
• Si un objetivo falla, los siguientes objetivos ya no se ejecutan. Adem�s la conjunci�n, en total, falla.
• Si un objetivo tiene �xito, algunas o todas sus variables quedan ligadas, y por tanto, dejan de ser variables libres para el resto de objetivos en la secuencia.
• Si todos los objetivos tienen �xito, la conjunci�n tiene �xito y mantiene las ligaduras de los objetivos que la componen.

Supongamos que la edad de Luis es 32 a�os, y la edad de Juan es 25:

• La ejecuci�n del primer objetivo tiene �xito y liga la variable "Y", que antes estaba libre, al valor 32.
• LLega el momento de ejecutar el segundo objetivo. Su variable "Z" tambi�n estaba libre, pero el objetivo tiene �xito y liga dicha variable al valor 25.
• Se ejecuta el tercer objetivo, pero sus variables ya no estan libres porque fueron ligadas en los objetivos anteriores. Como el valor de "Y" es mayor que el de "Z" la comparaci�n tiene �xito.
• Como todos los objetivos han tenido �xito, la conjunci�n tiene �xito, y deja las variables "Y" y "Z" ligadas a los valores 32 y 25 respectivamente.

�Varias soluciones

Hasta ahora todo parece sencillo, pero � qu� ocurre si uno o varios objetivos tienen varias soluciones ?. Para entender como se ligan las variables en este caso hemos de explicar en qu� consiste el backtracking en Prolog.

�Backtracking

Supongamos que disponemos de dos predicados p/1 y q/1 que tienen varias soluciones (el orden es significativo):

• p(1) tiene �xito.
• p(2) tiene �xito.
• q(2) tiene �xito.
• No hay m�s soluciones que �stas.

Y a continuaci�n consideramos la siguiente secuencia: p(X),q(X).

Ahora ejecutamos la secuencia tal y como explicamos en la lecci�n anterior:

• Ejecutamos p(X) con �xito y la variable queda ligada al valor 1 (primera soluci�n).
• Ejecutamos q(X), pero la variable ya no esta libre, luego estamos ejecutando realmente q(1). El predicado falla porque no es una de sus soluciones.
• La conjunci�n falla.

El resultado ha sido fallo, pero nosotros sabemos que para X = 2 existe una soluci�n para la conjunci�n.

Aqu� es donde entra en juego el backtracking. Esto consiste en recordar los momentos de la ejecuci�n donde un objetivo ten�a varias soluciones para posteriormente dar marcha atr�s y seguir la ejecuci�n utilizando otra soluci�n como alternativa.

El backtracking funciona de la siguiente manera:

• Cuando se va ejecutar un objetivo, Prolog sabe de antemano cuantas soluciones alternativas puede tener. En un futuro cap�tulo veremos c�mo puede llegar a saber esto. Cada una de las alternativas se denomina punto de elecci�n. Dichos puntos de elecci�n se anotan internamente y de forma ordenada. Para ser exactos, se introducen en una pila.
• Se escoge el primer punto de elecci�n y se ejecuta el objetivo eliminando el punto de elecci�n en el proceso.
• Si el objetivo tiene �xito se contin�a con el siguiente objetivo aplicandole estas mismas normas.
• Si el objetivo falla, Prolog d� marcha atr�s recorriendo los objetivos que anteriormente s� tuvieron �xito (en orden inverso) y deshaciendo las ligaduras de sus variables. Es decir, comienza el backtracking.
• Cuando uno de esos objetivos tiene un punto de elecci�n anotado, se detiene el backtracking y se ejecuta de nuevo dicho objetivo usando la soluci�n alternativa. Las variables se ligan a la nueva soluci�n y la ejecuci�n contin�a de nuevo hacia adelante. El punto de elecci�n se elimina en el proceso.
• El proceso se repite mientras haya objetivos y puntos de elecci�n anotados. De hecho, se puede decir que un programa Prolog ha terminado su ejecuci�n cuando no le quedan puntos de elecci�n anotados ni objetivos por ejecutar en la secuencia.

Adem�s, los puntos de elecci�n se mantienen aunque al final la conjunci�n tenga �xito. Esto permite posteriormente conocer todas las soluciones posibles.

�Ejemplo

La manera en que se ejecuta realmente nuestro ejemplo es la siguiente:

• Prolog tiene que ejecutar p(X) y sabe (en el futuro veremos por qu�) que existen dos soluciones. En consecuencia, anota dos puntos de elecci�n.
• Ejecutamos p(X) usando el primer punto de elecci�n, que se elimina en el proceso. Dicho objetivo tiene �xito y la variable queda ligada al valor 1 (primera soluci�n).
• Hay que ejecutar q(X) que solamente tiene un punto de elecci�n y queda anotado.
• Ejecutamos q(X) eliminando su (�nico) punto de elecci�n, pero la variable ya no est� libre, luego estamos ejecutando realmente q(1). El predicado falla porque no es una de sus soluciones.
• Comienza el backtracking, recorriendo los objetivos en orden inverso hasta encontrar un punto de elecci�n anotado.
• Nos topamos con el objetivo p(X). Se deshace la ligadura de la variable X, es decir, X vuelve a estar libre.
• Se encuentra un punto de elecci�n. La ejecuci�n sigue de nuevo hacia adelante.
• Ejecutamos de nuevo p(X), pero esta vez se usa el punto de elecci�n que hemos encontrado. Se liga la variable X al valor 2 que corresponde a la segunda soluci�n. El punto de elecci�n se elimina en el proceso.
• Hay que ejecutar q(X) que solamente tiene un punto de elecci�n y queda anotado.
• Ejecutamos q(X) eliminando su (�nico) punto de elecci�n, pero la variable ya no esta libre, luego estamos ejecutando realmente q(2). El objetivo tiene �xito esta vez.
• La conjunci�n tiene �xito manteniendo la ligadura de la variable X al valor 2.

�Predicados predefinidos (built-in)

Existen algunos predicados predefinidos en el sistema y que est�n disponibles en todo momento. El m�s importante es la igualdad: =/2. Este predicado tiene �xito si sus dos argumentos unifican entre s�, falla en caso contrario. Por ejemplo, el objetivo X = 3 provoca la ligadura de X al valor 3 puesto que unifican. Otro ejemplo es f(3) = f(X), que tambi�n liga X al valor 3.

Es muy importante no confundir la igualdad l�gica con la igualdad aritm�tica. Por ejemplo, X = 3 + 2 tiene �xito pero no resulta en X ligado a 5. De hecho, la variable X queda ligada al t�rmino +(3,2). La aritm�tica ser� discutida en un posterior cap�tulo.

Otros predicados predefinidos muy �tiles son los de comparaci�n aritm�tica. Naturalmente, estos no funcionan con cualquier t�rmino como argumento. Solamente sirven para n�meros (enteros y decimales).

Predicado	Significado
<	menor que
>	mayor que
=<	menor o igual que
>=	mayor o igual que
=:=	igualdad aritmetica
=\=	desigualdad aritmetica