Lenguaje PROLOG: Conceptos 

1. Introducción.

2. Bases del lenguaje PROLOG.

3. Definición de Hechos, Metas y Predicados en PROLOG

4. Definición y funcionamiento de la Máquina PROLOG

5. Bibliografía

PROLOG constituye la primera realización práctica de un concepto de programación orientado más a modelar la forma de entender un tipo de problemas que a la forma concreta de calcular las soluciones de esos problemas. Esto quiere decir que se debe realizar un esfuerzo para modelar formalmente los enunciados que definen los problemas en lugar de aportar los pasos concretos que resuelven dicho problema. Por ejemplo, si se nos plantea el problema de resolver el factorial de un número, podemos modelar el enunciado como: factorial(1)=0 y factorial(N)=N*factorial(N-1), en lugar de especificar de forma imperativa los pasos individuales que resuelven el factorial a través de asignaciones y operaciones.

Por tanto, para entender la programación lógica, lo que necesitamos es adaptar nuestro lenguaje a un lenguaje matemático más formal que nos permita expresar nuestros enunciados de manera que puedan ser resueltos de modo general, automáticamente.

La máquina PROLOG, como se verá más adelante, no es más que un demostrador automático de teoremas. Por tanto, nosotros debemos expresar nuestro problema en forma de premisas y teoremas para que la máquina PROLOG pueda demostrarlos y, por tanto, aportarnos las soluciones que buscamos.

Evidentemente, para comprender las bases de la programación lógica es necesario tener unos conocimientos mínimos de la lógica matemática que se aplica y se utiliza en estos casos. Por lo tanto, en el anexo proporcionado al final de la documentación se describe brevemente el significado de "Cálculo Proposicional", "Cálculo de Predicados" y "Método de Resolución".

[ÍNDICE]

Centrémonos ahora en comentar las diferencias existentes entre metodología declarativa e imperativa, observando las ventajas e inconvenientes que supone usar este nuevo paradigma frente al método tradicional imperativo al que estamos acostumbrados.

[ÍNDICE]

Como se ha comentado, la programación declarativa supone especificar formalmente los enunciados utilizando la lógica de predicados de manera que la máquina PROLOG sea capaz de interpretar e inferir soluciones a partir de esos enunciados. En un lenguaje imperativo, sin embargo, no sólo hemos de preocuparnos de entender el significado del enunciado del problema sino que debemos escribir nosotros mismos cada uno de los pasos e instrucciones que la máquina debe ejecutar para resolverlo. Esta es la diferencia más notable entre ambas metodologías. Podemos especificar más las diferencias, pero al final, todas se resumen en la que acabamos de enunciar:

• Los lenguajes declarativos no se basan en la máquina Von Newman sino en modelos matemáticos.
• Los lenguajes declarativos, en contra de lo que hacen los imperativos, intentan ser referencialmente transparentes, es decir, la misma expresión siempre da los mismos resultados.
• En un lenguaje declarativo el control lo lleva la máquina, sin embargo en un lenguaje imperativo el control depende exclusivamente del programador.
• Los lenguajes declarativos son independientes de la máquina, sin embargo los imperativos se basan en el lenguaje máquina en el que se apoyan, teniendo como instrucción principal la asignación.
• El concepto de variable en un lenguaje imperativo es un objeto cuyo valor puede cambiar en el tiempo, en cambio, en los lenguajes declarativos las variables son objetos cuyo valor no se conoce, y que, una vez que se le asocia un valor, conserva dicho valor hasta el final.

[ÍNDICE]

• La principal ventaja de los lenguajes declarativos es que son independientes de la máquina y, como se ha comentado, referencialmente transparentes.
• Además la cantidad de código que debemos escribir es menor, aunque la representación formal de estos problemas puede resultar, en ocasiones, poco evidente.
• Podemos desentendernos del control. Aunque aquí existe una limitación: no podemos hacerlo totalmente. Por ello, PROLOG nos proporciona formas, un tanto artificiales, de manejo de este control.
• Los datos pueden ser tanto de entrada como de salida y se pueden utilizar datos parcialmente construidos, es decir, podemos empezar a ejecutar sin contar con todos los datos.
• Es difícil representar la negación.

[ÍNDICE]

Para construir programas en Prolog es necesario convertir los conceptos expresados en lenguaje natural en un lenguaje basado en la lógica de primer orden, con el fin de obtener las cláusulas de Horn tras el proceso de conversión adecuado, ya que Prolog trabaja, precisamente, con este tipo de cláusulas. Básicamente, nuestro trabajo va a consistir en especificar adecuadamente los enunciados y reglas básicas para resolver un determinado problema de forma general. Después le plantearemos a Prolog el conjunto de objetivos (problemas específicos para un problema general dado), que queremos que resuelva.

En definitiva, nuestros programas estarán formados por:

• La base de conocimientos: Hechos + Reglas de Inferencia.
• El conjunto de objetivos o metas.

Para comprender adecuadamente los conceptos expresados hasta ahora, veamos una serie de definiciones básicas: predicado, hecho, regla de inferencia y meta.

Un predicado especifica la relación existente entre los argumentos del mismo. El número de argumentos a los que se aplica dicho predicado se denomina aridad. Con un predicado podemos representar algo que sucede en el mundo real (hecho), o una regla (regla de inferencia), que nos permite deducir hechos que suceden en ese dominio mediante la aplicación de la misma. La sintaxis de Prolog para especificar un predicado es la siguiente:

nombre_predicado(arg1, arg2, ... , argN). (En el caso de que el predicado represente un hecho).

(En el caso de que el predicado represente una regla de inferencia).

Las reglas de inferencia se pueden definir como la especificación de una relación entre predicados y argumentos que permiten plasmar el hecho de que si la parte derecha del predicado se cumple, se cumple la parte izquierda. El eje lo proporciona el símbolo ":-" que representa para nosotros la implicación lógica (en lógica "® "). Las comas (","), representan el símbolo de conjunción (en lógica "Ù "), y el punto y coma (";"), representa el símbolo de disyunción (en lógica "Ú "). En la Tabla 1 se representan estas correspondencias.

Como se observa, las reglas de inferencia permiten llevar a cabo la deducción de metas. Para que las reglas de inferencia sean aplicables, en general, deberá existir un conjunto de hechos sobre los que apoyarse para que las demostraciones se puedan realizar. Las metas representan los problemas específicos, basados en los problemas generales expresados en la base de conocimientos que deseamos que el demostrador automático de teoremas resuelva. Si nos fijamos, para escribir programas en Prolog, siempre debemos tener en cuenta que el demostrador resuelve las metas comenzando por los predicados situados en la zona superior (de arriba a abajo), y para cada predicado el proceso de unificación se lleva a cabo de izquierda a derecha, ver Figura 1.

Una vez que hemos comprobado el funcionamiento general del demostrador, pasemos a estudiar como llevar a cabo la correcta especificación de las bases de conocimientos.

[ÍNDICE]

En el campo de la Inteligencia Artificial es muy habitual implantar agentes que se pueden considerar como entidades que poseen un conocimiento de su mundo capaces de razonar sobre las posibles acciones que pueden emprender. Este tipo de agentes adoptan tareas nuevas en forma de metas perfectamente definidas. Pueden inferir y razonar conocimientos en función de los hechos que conocen de su mundo y de las reglas de inferencia que permiten deducir propiedades de éste que no resultan completamente evidentes [Russel, 1996]. La construcción de agentes o programas que desempeñan labores de este tipo se puede realizar mediante el uso de lenguajes lógicos adaptados a la resolución de esta clase de cuestiones. Como hemos visto, la forma de llevar a cabo la implantación de un agente consiste en estudiar el mundo o ámbito donde va a tener que trabajar y definir ese dominio mediante una sintaxis adecuada al lenguaje utilizado. El componente medular de un agente basado en el conocimiento es su base de conocimientos, junto con el mecanismo de inferencia que se utilice para realizar las deducciones. Para nosotros, el mecanismo o motor de inferencia que vamos a usar va a ser la máquina Prolog.

La construcción, por tanto, de la base de conocimientos es el punto crucial que nos debe ocupar en este curso, por ello, en este punto y en los siguientes, comentaremos las reglas básicas que se deben tener en cuenta para implementar adecuadamente nuestro conocimiento acerca de los problemas que queremos resolver y veremos cómo plantear las metas al demostrador de teoremas (motor de inferencia), de Prolog.

La máquina virtual Prolog toma como entrada nuestra base de conocimientos expresada en forma clausal, nuestro objetivo, también expresado en forma clausal, y genera una respuesta afirmativa en caso de que el objetivo se pueda demostrar aplicando el conocimiento almacenado en la base. La Figura 2 muestra un esquema gráfico de lo que acabamos de comentar.

Resolver un problema, por tanto, es construir adecuadamente la base de conocimientos, y esta base expresada en lenguaje Prolog junto con el conjunto de metas especificadas constituirán nuestro programa.

Los programas que se pueden resolver utilizando esta metodología son muchos y muy variados. Desde la manipulación de bases de datos hasta la construcción de sistemas expertos, sin olvidar la compresión del lenguaje natural, resolución de juegos, diseño de compiladores, etc.

Un programa Prolog probablemente utilizará predicados recursivos, es decir, nuestro problema se expresa en términos de sí mismo aplicado sobre un conjunto de datos distintos que tiende a convertirse en el conjunto de datos que satisface el caso o casos triviales del proceso de recursión. Por ejemplo, en el caso del problema del factorial, vamos calculando sucesivamente el factorial de un número decrementado del nivel anterior. Este número se aproxima cada vez más a 0, que es justamente el caso trivial de este proceso recursivo. Una vez que se alcanza este caso, las llamadas recursivas retornan los datos de salida y se produce lo que todos conocemos como vuelta atrás.

Cuando sea necesario construir un programa usando técnicas recursivas en Prolog, hemos de recordar que los objetivos intentarán satisfacerse mediante una búsqueda que comienza por los predicados situados en la zona superior, y para cada uno de ellos el proceso de unificación se realizará de izquierda a derecha. Evidentemente, para conseguir un funcionamiento adecuado en el procedimiento de resolución hemos de construir la base de conocimientos adecuadamente, situando primero los casos triviales o específicos y a continuación los casos más generales.

Igualmente, si ciertas realidades del mundo que se desea representar, se pueden expresar mediante una regla de inferencia en lugar de hacerlo con un conjunto de hechos, elegiremos la primera opción, de modo que en nuestra base de conocimientos, tendremos solamente los hechos que son necesarios para deducir otros que se pueden razonar a través de reglas. Por ejemplo, si deseamos construir parte de nuestro árbol genealógico y establecemos como dominio en el que vamos a trabajar el de las madres y abuelas, solamente será necesario definir el predicado madre para representar hechos del tipo "Ana es madre de Pepa", "Pepa es madre de Luisa", etc. Sin embargo el predicado abuela no se implementará como un hecho, aunque podría hacerse, sino como una regla de inferencia ya que ese suceso ocurrido en el mundo que estamos representando se puede deducir en función del hecho "ser madre".

[ÍNDICE]

Evidentemente, las bases de conocimientos se construyen con el fin de que preguntemos al agente sobre nuevos hechos del mundo deducidos de dicha base. El agente debe poseer un motor de inferencia para llevar a cabo el proceso de deducción de forma automática. Para nosotros, Prolog va a constituir nuestro "motor de inferencia". Por tanto, nos queda saber como hemos de plantear los objetivos y como funciona la inferencia en Prolog (máquina virtual Prolog).

En este apartado vamos a centrarnos en estudiar las respuestas proporcionadas por Prolog a los objetivos que le podemos plantear.

El objetivo se plantea como un predicado nuevo basado en el conocimiento que tenemos. La máquina virtual o intérprete intentará unificar dicho predicado con los existentes en la base de conocimientos. Si puede unificarlo con alguno, nos dará una respuesta afirmativa. En caso contrario, proporcionará una respuesta negativa.

Prolog comienza a buscar de arriba a abajo en la secuencia de predicados y para cada predicado de izquierda a derecha. Pues bien, vamos a examinar ahora el método de ejecución para cada caso, es decir, si el predicado es un hecho, una regla de inferencia, etc. Además, será necesario concretar como se realiza el proceso de recursión y backtracking a través de algunos ejemplos sencillos.

[ÍNDICE]

En este caso sólo tenemos un conjunto de predicados que expresan los hechos o afirmaciones que se producen en el mundo real.

La forma de proceder de la máquina Prolog, será por tanto, el intento de unificación con alguno de ellos.

Supongamos que nuestro objetivo es:

El árbol de búsqueda generado sería el que se muestra en la Figura 3.

[ÍNDICE]

Las reglas de inferencia permiten relacionar hechos o situaciones del mundo real para deducir otros hechos que, en principio, no son evidentes sin la utilización de dicha reglas.

Cuando en Prolog tenemos una sentencia de la forma "predicado(argumentos):-predicado2(argumentos).", la máquina intenta unificar la parte izquierda de la regla mediante la demostración de la parte derecha. Dicha parte derecha se convierte en un subobjetivo a resolver. Las entradas y salidas se proporcionan a través de los argumentos, y se pueden utilizar variables locales o auxiliares para realizar cálculos que sólo afectan a esa parte derecha. De esta forma, en cada nivel de llamadas dichas variables locales funcionan del mismo modo que en cualquier lenguaje imperativo, ya que se consideran direcciones independientes unas de otras que sólo sobreviven en su nivel de llamada.

Supongamos una base de conocimientos como la siguiente:

Para satisfacer el objetivo "pred3(arg1, arg2, arg3)." se genera el árbol de búsqueda de la Figura 4.

[ÍNDICE]

Para estudiar este ejemplo, vamos a utilizar el ejemplo del cálculo del máximo común divisor. Hemos de apuntar, que el proceso se realizará de la misma forma que en el caso anterior. Lo único que hay que tener en cuenta es que es necesario controlar el orden en que se colocan los predicados para evitar una ejecución no deseada, ya que toda solución recursiva debe evolucionar hacia el caso trivial.

En cada nivel de recursión, las variables locales son independientes y se localizan en direcciones de memoria distintas.

El árbol de búsqueda generado para encontrar la solución "mcd(7, 5, R)." se muestra en la Figura 5.

[ÍNDICE]

En el punto anterior, hemos observado como funciona la máquina Prolog a la hora de resolver objetivos planteados sobre distintos tipos de bases de conocimientos. Es conveniente ilustrar todos los conocimientos adquiridos hasta ahora observando como se resuelven distintos problemas mediante un lenguaje lógico. Por ello, veamos un resumen de algunos ejemplos comentados hasta ahora.

Tras la exposición de estos pequeños ejemplos, pasemos a realizar un programa un poco más grande. Vamos a construir una base de conocimientos que nos permita resolver objetivos o preguntas relacionadas con el código de la circulación de vehículos.

[CÓDIGO FUENTE VP HTML] [ZIP CON FUENTES VPR] [EJECUTABLE VP] [DOCUMENTACIÓN HTML]

[ÍNDICE]

Hasta ahora, conocemos como se pueden modelar problemas reales utilizando la metodología declarativa lógica. Pero además, es necesario, definir formalmente qué es la máquina o intérprete Prolog. En este apartado nos centraremos en la definición y muestra del funcionamiento interno de este intérprete, examinando como se realiza el proceso de resolución, a través del método de unificación, y como se llevan a cabo las tareas de recursión y backtracking.

Un intérprete Prolog es un demostrador de teoremas sobre Cláusulas de Horn que trabaja Top-Down, y que emplea Resolución Lineal con Función de Selección. La entrada al intérprete es un conjunto de cláusulas definidas C, junto con la especificación de la meta G0, como ya se vio en apartados anteriores. El proceso del intérprete consiste en una búsqueda incremental por backtracking en el espacio (organización en forma de árbol), de refutaciones posibles a G0 [Adarraga, 1994].

[ÍNDICE]

La unificación se realiza, para cada predicado, de izquierda a derecha, y para cada conjunto de predicados, de arriba a abajo. Se pueden unificar variables con constantes, siempre que la variable no esté instanciada. Si la variable está instanciada, el hecho de hacer unificación entre ambas se corresponde con la situación de unificación de dos constantes. Para que dos constantes se puedan unificar ambas han de ser iguales.

Vemos que las instanciación es un caso de unificación en la que a una variable no instanciada se le asigna un valor.

También podemos observar que no es necesario definir los tipos de las variables locales usadas dentro de cada regla de inferencia. Cuando las variables se instancian a un valor, entonces todas las operaciones que se realicen con dicho valor deberán tener en cuenta el tipo especificado. Por ejemplo, si una variable se instancia al valor 5, todas las comparaciones posteriores se harán con números y no con átomos del tipo pepe, blas ó similar.

El proceso de unificación intenta casar un predicado con otro para comprobar si son absolutamente iguales, cuando es posible hacer sustituciones, éstas se realizan de manera que los predicados que se están unificando se tornen completamente iguales y proporcionen un resultado de ÉXITO.

[ÍNDICE]

Ya se ha comentado en puntos anteriores: Prolog utiliza un sistema de backtracking para resolver una meta propuesta. El procedimiento de backtracking consiste en generar un árbol de búsqueda de todas las posibles resoluciones que puede tener la meta en función de la base de conocimientos. Esto significa, que el algoritmo itera hasta que encuentra una solución. Cada vez que los predicados fallan y no son unificables se va generando una nueva rama hasta encontrar la solución deseada, de esta forma se va construyendo el árbol de búsqueda.

Puede ser que un problema se pueda resolver de varias formas. Es, por tanto, posible especificar que deseamos una nueva solución. El intérprete Prolog ignora la solución encontrada hasta ahora y construye el árbol de búsqueda hasta generar una nueva solución o encontrar que ésta no existe.

Cuando un predicado se demuestra en función de una llamada a sí mismo, la llamada se convierte en un subobjetivo casi idéntico al objetivo a cumplir, salvo por el conjunto de datos sobre el que se aplica. Cuando se consigue la demostración de los subobjetivos generados en el proceso de recursión, se produce lo que se denomina vuelta atrás de la recursión, que funciona igual que en cualquier lenguaje.

No hemos de confundir recursividad con backtracking. Los predicados recursivos los diseñamos nosotros mientras que el procedimiento de backtracking es intrínseco al método de refutación que se usa para demostrar las metas.

Para comprender mejor lo expuesto hasta ahora, vamos a examinar un par de ejemplos de uso forzado de backtracking para obtener nuevas soluciones y de uso de predicados recursivos.

[ÍNDICE]

[Adarraga, 1994] Adarraga, Pablo. Zaccagnini José Luis. "Psicología e Inteligencia Artificial". Editorial Trotta. 1994.

[Giannesini, 1986] PROLOG. Addison-Wesley Iberoamericana, 1986.

[Russell, 1996] Russell, Stuart. Norvig, Peter. "Inteligencia Artificial. Un enfoque moderno". Editorial Prentice Hall. 1996.

[ÍNDICE]