Cuando Prolog trata de satisfacer un objetivo, como en nuestro último caso X=pericles, busca, de arriba hacia abajo, en el conjunto de reglas de nuestro programa, algún predicado que coincida con la pregunta en cuestión. Esto es, si la pregunta es, como en nuestro caso, madre(morticia,X), busca un predicado binario cuyo nombre coincida con “madre”. En este caso el resolvente será el conjunto formado por madre(morticia,X).
La primera regla que encuentra en la base de datos es “madre(morticia, pericles)”. Es aquí donde buscará el mgu entre la consulta en cuestión y la regla obtenida de la base. El mgu en este caso es X=pericles. Se aplica la sustitucion en el resolvente, que ahora queda vacío, con lo cual la respuesta a nuestra consulta es el conjunto de sustituciones aplicadas, en este caso X=pericles. A modo de repaso, diremos que el algoritmo de resolución trabaja del siguiente modo:
El resolvente inicial es nuestra pregunta: madre(morticia,X). El algoritmo busca, como dijimos, la primera regla cuya consecuente coincida con la consulta a realizar. Esto en Prolog, por cuestiones de implementación tiene un orden. Es decir, la búsqueda se hace de arriba hacia abajo en el conjunto de reglas que forma nuestro programa lógico. El algoritmo encuentra la regla madre(morticia,pericles).
Ahora tratará de buscar un mgu entre la regla hallada y la consulta inicial. Allí es donde encuentra X=pericles
Una vez hecho esto, intentará reemplazar la consulta del resolvente por los predicados que existan en la cabeza o antecedente de la regla usada. Como nuestra regla no tiene parte derecha (se trata de un hecho), la consulta se reemplaza por el conjunto vació. Como el resolvente tenía un solo predicado, todo el resolvente nuevo queda vacío, con lo cual se termina el algoritmo. Es aquí donde Prolog responde con las sustituciones aplicadas, en este caso X=pericles. Esto es lo que se muestra en pantalla.
Hagamos un ejemplo un poco más complejo. Volvamos a escribir el programa Prolog, numerando las reglas y agregando al final dos cláusulas más:
-
padre_de(homero, pericles).
-
padre_de(homero, merlina).
-
padre_de(desconocido, homero).
-
padre_de(desconocido, lucas).
-
madre(morticia, pericles).
-
madre(morticia, merlina).
-
madre(laAbuela, homero).
-
varon(homero).
-
varon(pericles).
-
varon(lucas).
-
mujer(morticia).
-
mujer(merlina).
-
mujer(laAbuela).
-
hija(X, Y) :- madre(Y, X), mujer(X).
-
hija(X, Y) :- padre_de(Y, X), mujer(X).
Ahora, la consulta que consideraremos es la siguiente:
?- hija(merlina, X)
Los pasos serían los siguientes:
Buscar una regla que unifique con la consulta (que es nuestro resolvente). Unifica con la regla 14 usando la sustitución X=merlina,
Se reemplaza el resolvente original por el nuevo resolvente que será el antecedente de la regla 14 a la cual se le aplica la sustitución X=merlina. El nuevo resolvente queda: madre(Y ,merlina) , mujer(merlina)
De nuestro nuevo resolvente, tomamos el predicado de más a la izquierda, y buscamos nuevamente una regla cuyo consecuente que unifique con él. Esta regla es la 6) con la sustitución Y=morticia. Aplicamos esta sustitución a todo el resolvente que queda: madre(morticia, merlina) , mujer(merlina). Ojo! si en el segundo predicado del resolvente hubiera alguna variable Y, ésta también sería sustituida por morticia. Como la regla 6) no tiene antecedente, entonces en el resolvente se reemplaza por el conjunto vacío y el nuevo resolvente queda: mujer(merlina)
De este resolvente, tomamos nuevamente el predicado de más a la izquierda (en este caso es el único que queda) y buscamos en la base una regla que coincida en su consecuente. Encontramos la regla 12). En este caso no hay sustituciones. La regla 12) no tiene antecedente, por lo tanto en nuestro resolvente se reemplaza por el vacío y el resolvente queda también vacío. Esto implica que el algoritmo terminó y entonces retorna las sustituciones encontradas, en este caso Y=morticia.
Aquí hay algo muy importante sobre Prolog. Si pidiéramos una segunda respuesta, es decir si tipeáramos “;” en el intérprete, Prolog tendría que ir en busca de otra solución. Para esto, tiene que volver atrás hasta algún punto en donde se pueda seleccionar otra regla diferente. Si esto es posible, entonces aplica el algoritmo visto pero con esta segunda chance de selección. Si no es posible seleccionar otra regla, responde “no”. A este mecanismo de volver atrás para seleccionar otra regla se lo llama backtracking. No solamente se usa backtracking para obtener múltiples respuestas a una consulta, sino también cuando Prolog no llega a ninguna solución siguiendo un primer camino. En este caso vuelve atrás para encontrar otra regla que le permita deducir la consulta que realizamos.
En nuestro último ejemplo, supongamos que pedimos una segunda respuesta utilizando “ ; ”, entonces Prolog sigue con lo siguiente:
Volvemos al punto en donde se hizo la última selección de una regla, y esto nos lleva al momento en que seleccionamos la regla 12). Vemos si hay alguna otra regla que coincida con nuestro resolvente (mujer(merlina)) y vemos que no hay otra regla. Entonces seguimos buscando más arriba y vemos que antes de la regla 12) usamos la regla 6). Nuestro resolvente en ese caso era madre(Y, merlina). Buscamos otra regla que coincida con esta y vemos que si bien las reglas 5) y 7) coinciden en el nombre del predicado, no hay sustitución posible, por lo tanto ninguna de las dos se pueden usar. Seguimos yendo hacia atrás, siempre gracias al backtracking, y nos remontamos a la regla 14). Esta vez, en vez de aplicar la regla 14), usamos la regla 15) con la sustitución Y=merlina. Esto nos lleva a construir el nuevo resolvente, que será: padre_de(Y, merlina) , mujer(merlina).
Tomamos el primer predicado de nuestro resolvente y tratamos de buscar en nuestra base una regla que coincida con él. Encontramos esta vez la regla 2) usando la sustitución Y=homero. Aplicamos la sustitución a todo el resolvente y reemplazamos el primer predicado por el antecedente de la regla 2). Como es vacío, el nuevo resolvente queda: mujer(merlina), que igual que en el caso anterior, coincide con la regla 12). Reemplazamos el predicado de nuestro resolvente por el antecedente de la regla 12), lo que da un resolvente vacío. De esta manera, Prolog responde con las sustituciones aplicadas, en este caso Y=homero. En este punto, si ingresamos nuevamente un “;” Prolog responde “no”.
IMPORTANTE: El algoritmo de Prolog siempre selecciona las reglas de arriba hacia abajo, y en el caso de tratarse del resolvente, los predicados a resolver los selecciona de izquierda a derecha. Esto es así por cuestiones de implementación, dado que la regla de resolución de Robinsón no indica orden de selección.