PROLOG (PROgramming in LOGic) es un lenguaje de programación que se basa en el lenguaje de la Lógica de Primer Orden, diseñado por Alan Colmerauer en 1970, y que se utiliza para resolver problemas en los que entran en juego objetos y relaciones entre ellos. Por ejemplo, cuando decimos "Juan tiene un trompo", estamos expresando una relación entre un objeto (Juan) y otro objeto en particular (un trompo). Más aún, estas relaciones tienen un orden específico (Juan tiene el trompo y no al contrario).
Por otra parte, cuando realizamos una pregunta (¿Tiene Jorge una moto?) lo que estamos haciendo es averiguando sobre una relación. Además, también es posible usar reglas para describir relaciones: "dos personas son hermanos si ambos son hombres y tienen los mismos padres".
La programación en Prolog se clasifica como programación declarativa ya que se especifica qué se tiene que hacer, en contraposición con los lenguajes tradicionales que dicen cómo se debe hacer (programación imperativa). Asimismo, Prolog incluye algunos predicados predefinidos, ajenos la lógica formal, así como algunos extra-lógicos, que tienen un efecto lateral como write, read y otro grupo que sirve para expresar información de control. Por tanto, Prolog ofrece un sistema de programación práctico que tiene algunas de las ventajas de claridad y capacidad declarativa que ofrecería un lenguaje de programación lógica y, al mismo tiempo, nos permite un cierto control y operatividad.
Un programa en Prolog consiste en un conjunto de hechos (conocimiento) y un conjunto de reglas para manipular estos hechos. No hay declaraciones de tipo, inicializaciones u otras condiciones normales de los lenguajes de programación. Algunos ejemplos de hechos en Prolog son:
hombre(juan).
mujer(maria).
edad(juan,29).
edad(maria,25).
padre(juan,pedro).
padre(pedro,jaime).
oficina(maria, b3128).
amigo_de(maria,juan).
Los hechos consisten en:
Un nombre del predicado por ejemplo hombre, mujer, y oficina. Este debe comenzar con una letra minúscula.
Cero o más argumentos, tales como juan, b3128, y 29.
Observe que los hechos (y las reglas, y las preguntas) deben terminar con un punto.
Puede probar estos ejemplos de código en SWISH.
Un ejemplo de reglas en Prolog es:
abuelo(X,Y) :-
padre(X,Z),
padre(Z,Y).
El operador “:-'” se lee como “if'', mientras que la coma “,'' se lee como el operador “and”. La regla dice que “Y es abuelo del X si Z es el padre de X y Y es padre de Z”. Todos los argumentos que comienzan con una mayúscula (tal como X o Y) son variables. Las variables no se tratan como en lenguajes de programación convencionales - por ejemplo, no tienen que tener valores.
La ejecución de un programa en Prolog implica el hacer preguntas que se cargan del “programa” que consiste en un conjunto de hechos y de reglas. Por ejemplo, usted podría consultar:
? - abuelo(juan, jaime).
A lo cual Prolog daría la respuesta “Yes”. Si pedimos una secuencia de preguntas puede ser que obtengamos:
? - abuelo(juan, jaime).
Yes
? - abuelo(jaime, juan).
No
Las preguntas pueden tener variables en ellas, las que se pueden instanciar, es decir obtener un valor, cuando Prolog intenta contestar a la pregunta. Prolog mostrará todos los resultados de las instanciaciones que resultan de todas las variables en la pregunta. Esto resulta en un diálogo con el intérprete como el siguiente:
? - abuelo(juan,AbueloDeJuan).
AbueloDeJuan = jaime
Podemos también darle vuelta a la pregunta de la siguiente manera:
? - abuelo(Nieto, jaime).
Nieto = juan
Observe que las variables AbuelodeJuan y Nieto puede tomar valores de cualquier tipo. Asimismo, es posible consultar en la base de conocimiento (conjunto de hechos y reglas de Prolog), quien es abuelo de quien de la siguiente forma:
? - abuelo(Nieto, Abuelo).
Nieto = juan, abuelo = jaime;
no
Prolog pasa sistemáticamente por todos sus hechos y reglas e intenta encontrar todas las maneras que puede asociar variables a valores particulares para satisfacer la pregunta inicial. Con el siguiente ejemplo se ilustra otra característica importante del Prolog, dada esta base de conocimiento:
animal(león).
animal(cuervo).
tiene_plumas(cuervo).
ave(X) :-
animal(X),
tiene_plumas(X).
Luego de cargar este programa, si se hiciera la consulta ave(P), el sistema respondería P=cuervo.
El mecanismo que Prolog sigue internamente hace corresponder la pregunta anterior ave(P) con la cabeza de la regla ave(X), generando la nueva consulta animal(P) y luego tiene_plumas(P). Note que animal(P) puede ser satisfecho asignando (instanciando) P con el valor leon. Sin embargo, si Prolog continúa procesando con este valor llegará a la regla tiene_plumas(leon) la cual, de acuerdo al contenido de los hechos, no es verdad. Esto activa el mecanismo de backtracking (retroceso) en el cual el motor de inferencia de Prolog intenta buscar otro hecho del predicado animal que pudiera convertir en verdadera la pregunta, que corresponde a animal(cuervo). Esta prueba es cierta, así como tiene_plumas(cuervo), haciendo que toda la regla ave(P) sea cierta, con valor P = cuervo.
Estructuras de datos y sintaxis básica
Lo anterior mostró brevemente como los programas en Prolog consisten en hechos, reglas y preguntas. Los hechos declaran las cosas que siempre evalúan al valor lógico Verdadero. Las reglas declaran las cosas que evalúan a Verdadero dependiendo de algunas condiciones. Los hechos y/o las reglas se pueden utilizar para definir relaciones (o predicados). Éstos pueden contar con uno o más argumentos.
Las preguntas se utilizan para validar contra la base de conocimiento si ésta es Verdadera, incluyendo qué valores de variables asociadas se requieren para hacerlo verdad. Los hechos, las reglas y las preguntas son todas cláusulas de Prolog.
La estructura de datos fundamental en Prolog es el término. Los términos del Prolog incluyen:
Átomos o entidades simples, que no se pueden separar.
Números
Variables
Objetos estructurados, como
libro(titulo(cryptonomicon),autor(stephenson))
Las estructuras complejas como la mostrada previamente son útiles si deseamos agrupar información sobre una colección relacionada de objetos, o un objeto con componentes.
Correspondencia de términos (unificación)
La unificación (“matching”) aplicada junto con la regla de resolución es lo que nos permite obtener respuestas a las preguntas formuladas a un programa lógico. La unificación constituye uno de los mecanismos esenciales de Prolog, y consiste en buscar instancias comunes a dos átomos, uno de los cuales está en la cabeza de una cláusula y el otro en el cuerpo de otra cláusula. Prolog intentará hacerlos coincidir (unificarlos) mediante las siguientes reglas:
Una variable puede instanciarse con cualquier tipo de término, y naturalmente con otra variable. Si X es una variable no instanciada, y si Y está instanciada a cualquier término, entonces X e Y son iguales, y X quedará instanciada a lo que valga Y. Si ambas están no instanciadas, el objetivo se satisface y las dos variables quedan compartidas (cuando una de ellas quede instanciada también lo hará la otra).
Los números y los átomos sólo serán iguales a sí mismos. Evidentemente, también se pueden instanciar con una variable.
Dos estructuras son iguales si tienen el mismo nombre y el mismo número de argumentos, y todos y cada uno de estos argumentos son unificables.
El predicado de igualdad (=) es un operador infijo que intentará unificar ambas expresiones. Un objetivo con el predicado no igual (\=) se satisface si el = fracasa, y fracasa si el = se satisface.
Ejemplos:
?- X=juan, X=Y.
X=juan, Y=juan
?- juan=juan.
yes
?- juan=jose.
no
?- 1024=1024.
yes
?- “juan”=juan.
no
?- f(X,Y)=f(A).
no
Backtracking (reevaluación)
Al recibir una pregunta para que sea “probada”, Prolog recorre su lista de hechos y de reglas, en orden de arriba hacia abajo, buscando hechos o inicios de regla que hagan correspondencia con la pregunta. Cuando encuentra uno, almacena el lugar en la base de conocimiento hasta donde había llegado en su búsqueda, para que si la primera correspondencia no es satisfactoria pueda continuar y buscar más posibilidades. Como un ejemplo, suponga los siguientes hechos:
ave(tipo(loro), nombre(arturo))).
ave(tipo(canario), nombre(tweety))).
ave(tipo(canario), nombre(percy)).
A la base de conocimiento anterior se consulta la siguiente pregunta: ave(tipo(canario), nombre(X)). El motor de búsqueda de Prolog primero tratará de corresponder la pregunta con el primer hecho, pero falla porque loro no corresponde con canario. Entonces intentará hacer la correspondencia con el segundo hecho, y tiene éxito con X = tweety. Sin embargo, pondrá un indicador en el lugar donde fue encontró una solución, para que si una búsqueda subsiguiente falla, regresará a la posición marcada, para buscar más soluciones (por ejemplo, X = percy).
La reevaluación ("backtracking") consiste en volver a evaluar lo que se ha hecho e intentar resatisfacer los objetivos buscando una forma alternativa de hacerlo. Si se quieren obtener más de una respuesta a una pregunta dada, puede iniciarse la reevaluación pulsando la tecla «y» cuando Prolog acaba de dar una solución y pregunta «More (y/n) ?», con lo que se pone en marcha el proceso de generación de soluciones múltiples.
Vamos a ver dos conceptos ya utilizados y relacionados directamente con la reevaluación:
Satisfacer un objetivo: cuando Prolog intenta satisfacer un objetivo, busca en la Base de Conocimientos desde su comienzo, y:
- si encuentra un hecho o la cabeza de una regla que pueda unificar con el objetivo, marca el lugar en la base de conocimientos e instancia todas las variables previamente no instanciadas que coincidan. Si es una regla lo encontrado, intentará satisfacer los subobjetivos del cuerpo de dicha regla.
- si no encuentra ningún hecho o cabeza de regla que unifique, el objetivo ha fallado, e intentaremos resatisfacer el objetivo anterior.
Resatisfacer un objetivo: Prolog intentará resatisfacer cada uno de los subobjetivos por orden inverso, para ello intentará encontrar una cláusula alternativa para el objetivo, en cuyo caso, se dejan sin instanciar todas las variables instanciadas al elegir la cláusula previa. La búsqueda la empezamos desde donde habíamos dejado el marcador de posición del objetivo.
A continuación un ejemplo de una sesión interactiva de Prolog, que muestra los efectos del backtracking:
animal(mono).
animal(gallina).
animal(arana).
animal(mosca).
animal(cocodrilo).
gusta(mono,banana).
gusta(arana,mosca).
gusta(alumno,logica).
gusta(arana,hormiga).
gusta(cocodrilo,X) :- animal(X).
gusta(mosca,espejo).
regalo(X,Y) :- animal(X), gusta(X,Y).
?- regalo(X,Y).
X=mono, Y=banana
More (y/n)? y
X=arana, Y=mosca
More (y/n)? y
X=arana, Y=hormiga
More (y/n)? y
X=mosca, Y=espejo
More (y/n)? y
X=cocodrilo, Y=mono
More (y/n)? y
X=cocodrilo, Y=arana
More (y/n)? y
X=cocodrilo, Y=mosca
More (y/n)? y
X=cocodrilo, Y=cocodrilo
More (y/n)? y
no
Recursión
Las definiciones recursivas se encuentran frecuentemente en los programas Prolog, en los que algunos predicados están definidos recursivamente, es decir, el cuerpo de la cláusula se llama a sí mismo. En la recursividad debemos tener cuidado en que se cumplan las “condiciones de límite” (punto de parada cuando utilizamos recursividad). Podemos observar que en la llamada de la cláusula recursiva al menos uno de los argumentos crece o decrece, para así poder unificar en un momento dado con la cláusula de la condición de parada.
En la recursión encontramos dos partes:
la primera parte en la que descendemos y construimos el árbol hasta encontrar el valor que unifica con la condición de parada, y
una segunda parte en la que ascendemos por el árbol asignando valores a las variables que teníamos pendientes en las sucesivas llamadas.
Casi cualquier programa no trivial en Prolog implica el uso de predicados recursivos – o sea, predicados que se llaman a sí mismos. La idea básica es la misma de las funciones recursivas de los lenguajes de programación funcionales. Sin embargo, como Prolog no se basa en el uso de funciones o procedimientos, se utilizan los predicados recursivos.
Suponga que escribimos un predicado en Prolog para determinar si alguien es un antepasado de alguien más. Esto tiene una definición recursiva simple, expresada de la siguiente forma: X es antepasado de Y si X es padre de Y ó Z es padre de Y y X es antepasado de Z. Esto se escribe así:
ancestro(Persona, Antepasado):-
padre(Persona, Antepasado).
ancestro(Persona, Antepasado):-
padre(Persona, Padre), ancestro(Padre, Antepasado).
Note cómo el caso límite de la definición recursiva es una regla separada, precediendo el caso recursivo. Todos los predicados recursivos deben tener un caso límite, si no fallarían o entrarían en un lazo sin fin para siempre.
Asimismo, se debe tener cuidado de no escribir recursiones circulares (entrada en un loop infinito) y evitar la recursión izquierda (cuando una regla llama a un objetivo que es equivalente al objetivo original). Este tipo de problemas causarían que Prolog no termine nunca. A continuación un par de ejemplos sobre este tipo de condiciones:
Recursión circular:
padre(X,Y) :- hijo(Y,X).
hijo(A,B) :- padre(B,A).
Recursión izquierda:
persona(X) :- persona(Y), madre(X,Y).
persona(adan).
