**Una introducción a Prolog**
!!!side:1
Obsérvese que, según esta aproximación, el lenguaje permite hacer una descripción de las condiciones necesarias para que la inferencia de las condiciones que hemos expresado en el programa se conviertan en una solución al problema... pero no indica nada acerca de cómo intervenir en el motor de inferencia para que la solución se consiga por métodos específicos. Lo único que caracteriza que sea un lenguaje de programación lógica es que se haya expresado en un lenguaje lógico.
Habitualmente, programar un ordenador por medio de un lenguaje estándar significa dar una sucesión de tareas que, al ejecutarlas paso a paso, permiten resolver un problema concreto. Sin embargo, el proceso que se sigue en la **programación lógica** es completamente distinto: un programa en un lenguaje de programación lógica está formado por un conjunto de hechos, junto con un conjunto de condiciones que debe verificar la solución... el ordenador, usando un motor de inferencia, debe *deducir* la solución a partir de los hechos y las condiciones dadas [1].
!!!side:2
En este último país la programación lógica se incluyó como parte central del proyecto de ordenadores de quinta generación de los años ochenta.
**Prolog** (del francés, PROgrammation en LOGique) fue el primer lenguaje de programación basado en el paradigma de la programación lógica. Se implementó por primera vez a principios de los años setenta en la Universidad de Marsella (Francia), por un equipo dirigido por **A. Colmeraeur** y utilizando resultados de **R. Kowalski** (Universidad de Edimburgo). Aunque con ciertas dificultades iniciales, debido principalmente a la novedad del paradigma y a la escasa eficiencia de las implementaciones disponibles, el lenguaje se fue expandiendo rápidamente, sobre todo en Europa y en Japón [2] y en 1995 se normaliza con el correspondiente estándar ISO.
!!!note
Teniendo en cuenta que es un lenguaje de programación que se utiliza para resolver problemas en los que existen objetos y relaciones entre objetos, la programación en Prolog consiste simplemente en:
* declarar hechos sobre los objetos y sus relaciones,
* definir reglas sobre dichos objetos y relaciones, y
* hacer preguntas.
Uno de los posibles usos de Prolog es como lenguaje de programación interactivo, lo que quiere decir que el ordenador y el programador sostienen una especie de conversación donde Prolog espera que se le introduzcan los hechos y reglas que definen el problema que se quiere resolver y, a continuación, si se hacen las preguntas adecuadas, buscará las respuestas y las presentará por pantalla.
Pese a la impresión inicial de tener capacidades limitadas, Prolog es un lenguaje muy versátil que puede implementar cualquier tipo de algoritmo, no únicamente aquellos para los que fue diseñado, por lo que no es menos potente que lenguajes como C++, Python, Java o Haskell, y en algunos aspectos podría considerarse más potente y expresivo. La elección de un lenguaje u otro depende, como siempre, del tipo de problema que se quiere resolver y del objetivo que se tenga al resolverlo.
!!!side:3
Cuando se entra en más profundidad en Prolog, se descubre que también puede influir el orden en que se proporciona esa información, pero ese aspecto no lo debatiremos aquí.
Antes de comenzar a programar en Prolog se ha de tener en cuenta una importante consideración: es, con mucha probabilidad, radicalmente distinto a cualquier otro lenguaje de programación con el que hayas trabajado; en consecuencia, cuando se quiere resolver un problema con él, no debe intentar resolverse previamente en otro lenguaje con el fin de traducirlo luego a Prolog (algo que es relativamente fácil y común entre otros lenguajes)... aquí no hay que buscar un algoritmo que resuelva el problema, basta proporcionar las bases lógicas suficientes para que el motor de inferencia de Prolog lo resuelva por nosotros... pero hay de reconocer bien qué información básica va a permitir que Prolog realice su tarea [3].
# Elementos de un Programa
## Hechos
!!!def
Un **hecho** es un predicado (relación) entre objetos. Su sintaxis en Prolog es `relacion(objeto, objeto, ...)`. Ha de tenerse en cuenta las siguientes reglas sintácticas:
* Los nombres de las relaciones deben comenzar con una letra minúscula.
* Los objetos se escriben separados por comas y encerrados entre paréntesis.
* Al final del hecho debe ir un punto.
!!!ejemplo
Por ejemplo, un hecho es:
```
edad(juan,27).
```
## Reglas
!!!def
Las reglas funcionan como las fórmulas condicionales habituales en lógica. Reflejan que la verdad de un hecho depende de la verdad de otro hecho o grupo de hechos. Consta de una **cabeza** y un **cuerpo**, donde este último puede estar formado por varios hechos (también llamados **objetivos**). Su sintaxis general es:
```+
cabeza :- objetivo 1, objetivo 2, ..., objetivo n.
```
Formalmente, desde un punto de vista lógico, se interpretaría de la siguiente forma:
$$objetivo_1 \wedge \dots \wedge objetivo_n \rightarrow cabeza$$
Los objetivos van separados por comas (que representan conjunciones) y al final debe ir un punto.
!!!ejemplo
Por ejemplo:
```
mayor_de_edad(X) :- edad(X,E), E>18.
```
que se podría interpretar como: *Si la edad de `X` es `E`, y `E>18`, entonces `X` es mayor de edad*.
## Variables
Como hemos visto en el ejemplo anterior, los nombres de las variables deben comenzar con letra mayúscula o con el carácter (`_`). Existe una variable especial, la variable anónima o blanca, que se utiliza de la misma manera que las demás variables, pero nunca toma ningún valor.
# Estructura de un Programa
!!!note
La mayoría de los programas Prolog están organizados en cuatro secciones principales:
* **dominio**: donde se declaran los argumentos que utilizarán los predicados.
* **predicados**: donde se declaran todos los predicados no predefinidos que se utilizarán en las siguientes secciones.
* **objetivos**: esta sección permite ejecutar los programas de forma no interactiva, y por tanto, buscará la solución deseada tan pronto como se ejecute el programa. Como también es habitual usar Prolog de forma interactiva es frecuente ejecutar un programa y luego esperar a que se nos pregunte por los objetivos.
* **clausulas**: donde se escriben los hechos y las reglas que conocemos del dominio.
# Ejemplo en LP
Vamos a comenzar dando un ejemplo sencillo de [Lógica Proposicional](Curso_acelerado_LP.md.html) para resolverlo por medio de un programa en Prolog.
!!!ejemplo
Disponemos de una base de conocimiento compuesta por reglas sobre clasificación de animales y hechos sobre características de un cierto animal tal y como muestra la siguiente lista:
* Regla 1: Si un animal es ungulado y tiene rayas negras, entonces es una cebra.
* Regla 2: Si un animal rumia y es mamífero, entonces es ungulado.
* Regla 3: Si un animal es mamífero y tiene pezuñas, entonces es ungulado.
* Hecho 1: El animal es mamífero.
* Hecho 2: El animal tiene pezuñas.
* Hecho 3: El animal tiene rayas negras.
Nuestro objetivo es demostrar, a partir de esta base de conocimientos, que el animal es una cebra.
Para representar una regla, debemos elegir previamente los símbolos para los átomos que aparecen en la regla:
Para la regla 1, podemos elegir los símbolos `es_ungulado`, `tiene_rayas_negras` y `es_cebra`. La regla 1 puede representarse como: `Si es_ungulado y tiene_rayas_negras entonces es_cebra`. Usando las conectivas lógicas la expresión anterior se escribe mediante la fórmula:
$${\tt es\_ungulado} \wedge {\tt tiene\_rayas\_negras} \rightarrow {\tt es\_cebra}$$
que podemos escribir en Prolog mediante la cláusula:
```
es_cebra :- es_ungulado, tiene_rayas_negras.
```
Como se puede observar, la transformación ha consistido en invertir el sentido de la escritura y sustituir las conectivas por `:-` (condicional inversa) y `,` (conjunción).
Para representar los hechos basta elegir los símbolos de los átomos. Por ejemplo, el hecho 2 se representa en Prolog por:
```
tiene_rayas_negras.
```
Los hechos pueden verse como reglas con el cuerpo vacío.
Para representar la base de conocimiento en Prolog, se escribe en un fichero (por ejemplo, [**animales.pl**](http://www.cs.us.es/~fsancho/ficheros/prolog/animales.pl)) cada una de las reglas y los hechos:
```none
:- set_prolog_flag(unknown,fail). % Para que SWI-Prolog admita predicados no definidos
es_cebra :- es_ungulado, tiene_rayas_negras. % Regla 1
es_ungulado :- rumia, es_mamífero. % Regla 2
es_ungulado :- es_mamífero, tiene_pezuñas. % Regla 3
es_mamífero. % Hecho 1
tiene_pezuñas. % Hecho 2
tiene_rayas_negras. % Hecho 3
```
(Nota: lo que sigue al símbolo **%** se considera un comentario y no es procesado por Prolog).
!!!side:Ref-1
[SWI-Prolog's Home](http://www.swi-prolog.org/)
[GNU Prolog's Home](http://www.gprolog.org/)
!!!warn
SWI-Prolog no adimte predicados no definidos previamente. Para solventar este problema hemos de indicar a SWI-Prolog [Ref-1] que admita este tipo de predicados poniendo en la primera línea de nuestro fichero la siguiente directiva:
```
:- set_prolog_flag(unknown,fail).
```
!!!side:4
El símbolo `?-` es el prompt y lo que viene a continuación en su misma línea lo introduce el usuario. La respuesta de Prolog se muestra en la línea, o líneas, siguientes a la interacción del usuario.
Observa también en el código cómo se cargan ficheros en Prolog.
Una vez en Prolog, podemos cargar el fichero anterior e intentar ver si se puede deducir el resultado que buscábamos. Una sesión interactiva que hiciera esto en SWI-Prolog podría ser de la siguiente forma [4]:
```none
% library(win_menu) compiled into win_menu 0.00 sec, 29 clauses
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 6.2.6
Copyright (c) 1990-2012 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- [animales].
Yes
?- es_cebra.
Yes
```
La respuesta `Yes` indica que el sistema ha encontrado una prueba de `es_cebra` a partir de la base de conocimientos cargada en el fichero. El árbol de deducción que sigue Prolog es una búsqueda en profundidad que puede ser representado por la siguiente figura:
En este árbol, cada estado es una pila de problemas por resolver:
1. El estado inicial consta de un único problema (`es_cebra`).
2. A partir de este estado buscamos en la base de conocimientos una regla cuya cabeza coincida con el primer problema de la pila (en nuestro caso, esta búsqueda da como resultado la regla `R1`).
3. Sustituimos el problema por el cuerpo de la regla, dando lugar a la pila de problemas `es_ungulado, tiene_rayas_negras`.
4. Para el primer problema (`es_ungulado`) tenemos dos reglas cuyas cabezas coinciden (las reglas `R2` y `R3`).
5. Consideramos en primer lugar la regla `R2`, produciendo la pila de problemas `rumia, es_mamífero, tiene_rayas_negras`, que no coincide con la cabeza de ninguna regla, por lo que se produce un fallo y se considera la otra elección, la regla `R3`, que genera la pila de problemas `es_mamífero, tiene_pezuñas, tiene_rayas_negras`.
6. Cada uno de los problemas restantes coincide con uno de los hechos (reglas sin cuerpo), por lo que obtenemos una solución al problema inicial.
La siguiente figura muestra una representación del proceso que se sigue en la rama exitosa del árbol anterior:
# Ejemplos en LPO
## Primer ejemplo
Para mostrar un ejemplo que contiene elementos de un lenguaje de primer orden vamos a trabajar sobre la siguiente base de conocimientos:
!!!ejemplo: Hechos
1. Atlanta se encuentra en Georgia.
2. Houston y Austin se encuentran en Texas.
3. Toronto se encuentra en Ontario.
Que, usando el predicado `located_in`, podemos representar con las siguientes cláusulas:
```none
located_in(atlanta,georgia). % Clause 1
located_in(houston,texas). % Clause 2
located_in(austin,texas). % Clause 3
located_in(toronto,ontario). % Clause 4
```
!!!ejemplo:Reglas
1. Lo que está en Georgia o Texas, también está en USA.
2. Lo que está en Ontario, también está en Canadá.
3. Lo que está en USA o Canadá, también está en Norte América.
Que podemos representar con las siguientes cláusulas (**[geo.pl](http://www.cs.us.es/~fsancho/ficheros/prolog/geo.pl)**):
```none
located_in(X,usa) :- located_in(X,georgia). % Clause 5
located_in(X,usa) :- located_in(X,texas). % Clause 6
located_in(X,canada) :- located_in(X,ontario). % Clause 7
located_in(X,north_america) :- located_in(X,usa). % Clause 8
located_in(X,north_america) :- located_in(X,canada). % Clause 9
```
Observa que al estar trabajando con predicados que sí reciben argumentos ya no es necesario usar la directiva vista en el ejemplo anterior.
Vamos a ver cuál es el árbol de deducción que sigue Prolog para resolver la siguiente clausula:
```
located_in(toronto,north_america).
```
A continuación mostramos el proceso seguido por el motor de deducción para llegar al resultado final (afirmativo).
## Segundo ejemplo
Para mostrar un segundo ejemplo que contiene elementos de un lenguaje de primer orden vamos a trabajar sobre la siguiente base de conocimientos:
!!!ejemplo: Hechos
* 6 y 12 son divisibles por 2 y por 3.
* 4 es divisible por 2.
!!!ejemplo: Regla
Los números divisibles por 2 y por 3 son divisibles por 6.
Para representar esta base de conocimientos en Prolog usaremos las constantes `2`, `3`, `6` y `12` y el predicado binario `divide(X,Y)` que se verifica si `X divide a Y`. Los hechos se representarán entonces por medio de 5 cláusulas unitarias. La regla se puede expresar como:
$$\forall\ {\tt X}\ [ {\tt divide(2,X)} \wedge {\tt divide(3,X)} \rightarrow {\tt divide(6,X)}]$$
y su representación Prolog es
```none
divide(6,X) :- divide(2,X), divide(3,X).
```
que hace uso de la variable `X` y que se considera universalmente cuantificada de manera implícita. La representación en Prolog de la base de conocimientos completa sería:
```none
divide(2,6). % Hecho 1
divide(2,4). % Hecho 2
divide(2,12). % Hecho 3
divide(3,6). % Hecho 4
divide(3,12). % Hecho 5
divide(6,X) :- divide(2,X), divide(3,X). % Regla 1
```
Usando la base de conocimientos anterior (**[Divide.pl](.http://www.cs.us.es/~fsancho/ficheros/prolog/Divide.pl)**)podemos determinar los números divisibles por `6` de la siguiente forma:
```none
?- divide(6,X).
X = 6 ;
X = 12 ;
false.
```
La forma de interactuar con Prolog para obtener el resultado anterior es como sigue: después de obtener la primera respuesta se pide la búsqueda de otra solución pulsando punto y coma (`;`). Si en este proceso se obtiene como respuesta `false` significa que no hay más respuestas.
El árbol de deducción correspondiente a la sesión anterior se representa en la siguiente figura, donde se observa que el árbol tiene dos ramas de éxito y una de fallo. Además, el paso entre objetivos se ha ampliado: no se exige que el primer objetivo sea igual que la cabeza de una regla, sino que sea unificable (es decir, que exista una sustitución que los haga iguales). Por ejemplo, en el segundo paso el objetivo `divide(2,X)` se unifica con el hecho `divide(2,6)` mediante la sustitución de `X` por `6` (representada por `{X/6}`). Componiendo las sustituciones usadas en una rama de éxito se obtiene la respuesta.
## Tercer ejemplo
Vamos a poner a continuación un ejemplo algo más elaborado en el que se utiliza un lenguaje de primer orden que tiene símbolos de función. Este ejemplo nos permitirá presentar también un primer ejemplo de definición recursiva. Sobre él haremos diversas preguntas y analizaremos cómo Prolog consigue dar las soluciones.
Los números naturales se pueden representar mediante una constante `0` (que representa el cero) y un símbolo de función unitaria `s` (que representa la función sucesora). De esta forma, `0`, `s(0)`, `s(s(0))`, `...` representan los números naturales `0, 1, 2, ...`
Vamos a definir la relación `suma(X,Y,Z)` que se verifica si `Z = X + Y`. La definición, por recursión en el primer argumento, se basa en las identidades:
```none
0 + Y = Y
s(X) + Y = s(X+Y)
```
que se traduce en las fórmulas de primer orden:
$$\forall\ {\tt Y}\ [{\tt suma(0,Y,Y)}]$$
$$\forall\ {\tt X},{\tt Y},{\tt Z}\ [{\tt suma(X,Y,Z)} \rightarrow {\tt suma(s(X),Y,s (Z))}]$$
y éstas en Prolog:
```none
suma(0,Y,Y). % R1
suma(s(X),Y,s(Z)) :- suma(X,Y,Z). % R2
```
Vamos a ver cómo Prolog responde a diversas cuestiones a partir de esta definición. La primera cuestión es calcular la suma de `s(0)` y `s(s(0))`. La forma de plantear esta pregunta en Prolog, y la respuesta obtenida, sería (**[suma.pl](http://www.cs.us.es/~fsancho/ficheros/prolog/suma.pl)**):
```none
?- suma(s(0),s(s(0)),X).
X = s(s(s(0))).
```
El árbol de deducción seguido se muestra en la figura siguiente:
Para evitar conflicto entre las variables se cambian de nombre, añadiendo el índice `0` a las del objetivo inicial, y el nivel del nodo en el árbol para el resto de cláusulas del programa. El nodo inicial solo tiene un sucesor con la regla `R2`, porque es la cabeza de la única regla con la que unifica; efectivamente el átomo `suma(s(0),s(s(0)),X0)` no es unificable con `suma(0,Y1,Y1)` porque los primeros argumentos son átomos sin variables distintos y sí es unificable con `suma(s(X1),Y1,s(Z1))` mediante la sustitución `{X1/0, Y1/s(s(0)), X0/s(Z1)}` que, aplicada a ambos átomos, da el átomo `suma(s(0),s(s(0)),s(Z1))`. Lo mismo sucede con el segundo nodo. Finalmente, la respuesta se calcula componiendo las sustituciones realizadas en la rama de éxito a las variables iniciales: `X` se sustituye inicialmente por `X0`, en el primer paso se sustituye `X0` por `s(Z1)` y en el segundo se sustituye `Z1` por `s(s(0))` con lo que el valor por el que sustituye `X` es `s(s(s(0)))`.
La segunda cuestión es cómo calcular la resta de `s(s(s(0)))` y `s(s(0))`. Para ello no es necesario hacer un nuevo programa, basta con observar que ${\tt X = a - b} \Leftrightarrow {\tt X + a = b}$ y plantear la pregunta:
```none
?- suma(X,s(s(0)),s(s(s(0)))).
X = s(0) ;
false.
```
El árbol de deducción correspondiente se muestra en la figura siguiente:
La tercera cuestión es descomponer el número `2` en suma de dos números naturales; es decir resolver la ecuación `X + Y = 2`. Tampoco para este problema se necesita un nuevo programa, basta realizar la siguiente consulta:
```none
?- suma(X,Y,s(s(0))).
X = 0,
Y = s(s(0)) ;
X = s(0), Y = s(0) ;
X = s(s(0)),
Y = 0 ;
false.
```
Obteniendo las tres soluciones `2 = 0 + 2 = 1 + 1 = 2 + 0`. El árbol de deducción correspondiente se muestra en la figura siguiente:
# Bibliografía y Recursos
Puedes encontrar información mucho más completa en los siguientes enlaces y recursos:
* [Prolog Programming in Depth](http://www.covingtoninnovations.com/books.html#ppid), M.A. Covington, D. Nute, and A. Vellino. Second edition, Prentice-Hall, 1997.
* [Prolog programming for artificial intelligence](http://bit.ly/r0ERAx), I. Bratko. Pearson, 2001.
* [Prolog WikiBoook](http://en.wikibooks.org/wiki/Prolog).
* [Learn Prolog Now!](http://www.learnprolognow.org/lpnpage.php?pageid=online).
* [Prolog Problems](https://sites.google.com/site/prologsite/prolog-problems/).
* [Introducción a la programación lógica con Prolog.](http://www.cs.us.es/~jalonso/publicaciones/2006-int_prolog.pdf) Publicaciones del Grupo de Lógica Computacional. Universidad de Sevilla, 2006.
(insert menu.md.html here)