Ejecutando cosas
Predicados y Objetivos
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 |
Tutoriales
