« Introducción al Apren… « || Inicio || » Clasificación Supervi… »

Una introducción a Prolog

Última modificación: 7 de Enero de 2014, y ha tenido 4089 vistas

Etiquetas utilizadas: ||

Habitualmente, programar un ordenador 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.

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 (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) y en 1995 se normaliza con el correspondiente estándar ISO.

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 versatil 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++, Java o Haskell, y en algunos aspectos podría considerarse más potente. 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.

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 hayamos 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 (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í).

Los elementos de un programa en Prolog

Los hechos

Un hecho es un predicado (relación) entre objetos. Su sintaxis en Prolog es relacion (objeto, objeto, ...). Ha de tenerse en cuenta lo siguiente:

  • 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.

Por ejemplo, un hecho es: 


edad(juan,27).

Las reglas

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. Por ejemplo:


mayor_de_edad(X) :- edad(X,E), E>18.

Las variables

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.

La estructura de un programa en Prolog

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.

Un ejemplo de Lógica Proposicional

Vamos a comenzar dando un ejemplo que ya hemos analizado en las clases de teoría 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_negrases_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:

\[ es\_ungulado \wedge tiene\_rayas\_negras \rightarrow es\_cebra\]

La fórmula anterior se representa 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) cada una de las reglas y los hechos:


:- 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).

Importante: SWI-Prolog no adimte predicados no definidos previamente. Para solventar este problema hemos de indicar a SWI-Prolog que admita este tipo de predicados poniendo en la primera línea de nuestro fichero la siguiente directiva:


:- set_prolog_flag(unknown,fail).

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 (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 linea, o líneas, siguientes a la interacción del usuario):


% 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

Nota: Observa cómo se cargan ficheros en Prolog...

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. El estado inicial consta de un único problema (es_cebra). 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 1). Sustituimos el problema por el cuerpo de la regla. dando lugar a la pila de problemas es_ungulado, tiene_rayas_negras. Para el primer problema (es_ungulado) tenemos dos reglas cuyas cabezas coinciden (las reglas 2 y 3). Consideramos en primer lugar la regla 2, 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 3, que genera la pila de problemas es_mamífero, tiene_pezuñas, tiene_rayas_negras. 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 Lógica de Primer Orden

 

Primer ejemplo

Para mostrar un ejemplo que contiene elementos de un lenguaje de primer orden vamos a trabajar sobre la siguiente base de conocimientos:

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 clausulas:


located_in(atlanta,georgia). % Clause 1
located_in(houston,texas). % Clause 2
located_in(austin,texas). % Clause 3
located_in(toronto,ontario). % Clause 4

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 clausulas (geo.pl):


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:

Hechos:

  • 6 y 12 son divisibles por 2 y por 3.
  • 4 es divisible por 2.

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 X [ divide(2,X) \wedge divide(3,X) \rightarrow divide(6,X)] \]
y su representación Prolog es


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:


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)podemos determinar los números divisibles por 6 de la siguiente forma:


?- 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 muestra 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:


0 + Y = Y
s(X) + Y = s(X+Y)

que se traduce en las fórmulas de primer orden:

\[\forall Y [suma(0,Y,Y)]\]

\[\forall X,Y,Z [suma(X,Y,Z) \rightarrow suma(s(X),Y,s (Z))]\]

y éstas en Prolog:


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 defnició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):


?- 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 sólo tiene un sucesor con la regla 2, 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 \(X = a − b \leftrightarrow X + a = b\) y plantear la pregunta:


?- 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:


?- 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:

« Introducción al Apren… « || Inicio || » Clasificación Supervi… »