Un programa en Prolog se conforma de una serie de reglas. Pero antes de ver qué aspecto tiene veamos qué esperamos al ejecutarlo.
El usuario al usar un programa Prolog indicará un goal u objetivo del cual espera obtener soluciones en caso de que existan. La ejecución es la búsqueda de múltiples soluciones. Siempre.
Al iniciar la búsqueda se usarán las reglas definidas para obtener una primera solución. A continuación el usuario podrá, luego de analizar la solución, pedir otra. El programa mantiene un estado para seguir con la búsqueda. Suponiendo que exista una segunda solución, se informa de la misma manera y se podrá repetir el proceso. Eventualmente (si todo funciona bien) el programa indicará que no hay más soluciones.
Ésta es la manera en la que el usuario interactura con un intérprete de Prolog. Veremos también que es una forma de entender cómo funciona un programa paso a paso.
El programa más simple sería una enumeración explícita de hechos.
habla(juan, ruso). habla(juan, inglés). habla(maría, inglés). habla(pedro, ruso).
Una consulta estará formada por al menos una cláusula. En este caso hay una variable sin instanciar X y una constante ruso.
?- habla(X, ruso).
Es fácil ver que las soluciones posibles son aquellas donde X=juan y luego X=pedro.
Para obtenerlas, se recorren una por una las definiciones que coincidan, o unifiquen con habla(X, ruso). Internamente se puede pensar en un cursor que recorre los hechos a medida que se van pidiendo soluciones.
En un primer paso se inicializa la consulta y el cursor se ubicará en la definición del primer hecho, que, como coincide con habla(X, ruso), se unifica X=juan obteniendo la primer solución.
Luego el usuario podrá pedir una segunda solución. A continuación se buscarán las siguientes definiciones que puedan unicar con habla(X, ruso). Esto se logra recién en la última definición, dando lugar al segundo resultado, unificando ahora X=pedro. Notar que cada solución tiene una instanciación distinta en las variables.
Al pedir una tercera solución no se encontrarán más definiciones que unifiquen con el objetivo y se informará que no hay más soluciones.
habla(juan, ruso).habla(juan, inglés).habla(maría, inglés).habla(pedro, ruso).?- habla(X, ruso).↵X = juan;↵X = pedro;↵failLas consultas pueden estar formadas por más de una cláusula.
?- habla(A, I), habla(B, I)
Siguiendo con la analogía de las cláusulas como cajas, cada vez que se obtenga un resultado para la primera, se buscarán los resultados de la segunda. Es importante notar que cada clásula se resuelve teniendo en cuenta todas las definiciones y el valor de las variables en ese momento.
habla(juan, ruso).habla(juan, inglés).habla(maría, inglés).habla(pedro, ruso).?- habla(A, I), habla(B, I).A = juan, B = juan, I = ruso;A = juan, B = pedro, I = ruso;A = juan, B = juan, I = inglés;A = juan, B = maría, I = inglés;A = maría, B = juan, I = inglés;A = maría, B = maría, I = inglés;A = pedro, B = juan, I = ruso;A = pedro, B = pedro, I = ruso.En total hay ocho soluciones para el goal .
Para evitar las soluciones que se refieren a la misma persona se podría agregar la cláusa A \= B al final. Dicha cláusula tendrá solución si los valores son distintos.
?- habla(A, I), habla(B, I), A \= B.
La definición de predicados pueden ser, además de hechos, reglas.
Por ejemplo podríamos definir el predicado hablaCon/2 que represente si dos personas pueden hablar directamente una con la otra. El /2 indica que es un predicado binario.
hablaCon(A, B) :- habla(A, I), habla(B, I), A \= B.
Tal como un predicado puede constar de multiples definiciones de hechos, lo mismo sucede con las definiciones de reglas.
telepatía(maría, pedro). seComunican(A, B) :- telepatía(A, B). seComunican(A, B) :- hablaCon(A, B).
De esta forma A y B se comunican si tienen telepatía entre ellos o si pueden hablar (por compartir un idioma común).
Si bien no se exhibe, un predicado puede definirse en forma mezclada por hechos y reglas.
Cuando una cláusula que se intenta resolver corresponde a un predicado con múltiples definiciones se van iterando por las disintas definiciones que unifican. En los ejemplos anteriores eran hechos y por ende se resolvían directamente. Cuando la definición es una regla, se expanden las cláusulas
Al principio se intentará resolver usando la primera definición. En este caso queda como nuevo goal, luego de unificar y sustituir los parámetros, telepatía(maría, A).
En la búsqueda de otra solución se pasará, luego de que se propaguen los fail, a la segunda definición. Para resolverla se terminará usando la única regla para hablaCon(maría, A).
habla(juan, ruso).habla(juan, inglés).habla(maría, inglés).habla(pedro, ruso).hablaCon(A, B) :- habla(A, I), habla(B, I), A \= B.telepatía(maría, pedro).seComunican(A, B) :- telepatía(A, B).seComunican(A, B) :- hablaCon(A, B).?- seComunican(maría, A).El recorrido hasta ahora se corresponde con un recorrido DFS del árbol de ejecución.
Una vez que se comprende que el lenguaje permite expresar en forma concisa algorítmo de backtracking se puede ver la ejecucíon de un programa desde otras perspectivas.
Al fijar el goal inicial, se pueden tener las variables visibles al usuario de las cuales espera saber su valor en caso de encontrar una solución.
En el ejemplo anterior
1) seComunican(maría, A) con A = ?.
A continuación se puede dar un paso en resolver el goal. Esto se hace encontrando definiciones que unifican con la primer cláusla del goal. Como son reglas se deberá expandir el cuerpo de la misma como nuevo goal. Este proceso da varios resultados que eventualmente darán origen a las soluciones.
1.1) telepatía(maría, A) con A = ?.
1.2) hablaCon(maría, A) con A = ?.
Cada vez que se usa una definición hay que tener en cuenta la sustitución de la unificación. La A de las definiciones se correspondian con maría y las B con las A del goal.
Siguiendo con la rama 1.1, se usa la definición de un hecho. En este caso no se agrega ninguna cláusula dejando el goal vació ⟂ e indicando una solución al goal original.
1.1.1) ⟂ con A = pedro.
Entonces cada vez que se encuentra una definición para la primer claúsula, se la reemplaza por la parte derecha de la misma. Si en algún momento no se puede reemplazar la cláusula esa rama falla.
La rama 1.2 da origen a:
1.2.1) habla(maría, I), habla(A, I), maría \= A con A = ?.
Como solo hay un hecho que unifica con habla(maría, I) la rama 1.2.1 da origen a:
1.2.1.1) habla(A, inglés), maría \= A con A = ?.
Notar que ya no importa por qué se busca alguién que hable inglés.
Como hay dos hechos que unifican con habla(A, inglés) la última rama da origen a:
1.2.1.1.1) maría \= juan con A = juan.
1.2.1.1.2) maría \= maría con A = maría.
La primera reduce a:
1.2.1.1.1.1) ⟂ con A = juan.
mientras que la segunda falla.
A continuación se muestra el árbol completo. Al hacer click en los nodos se muestra la información que se usó para ese paso.
Y se puede elegir ver dicha información según el algoritmo de resolución.