Lenguaje de programación PROLOG

INTRODUCCIÓN

PROLOG es un lenguaje de programación declarativo. Los lenguajes declarativos
se diferencian de los lenguajes imperativos o procedurales en que están basados en
formalismos abstractos (PROLOG está basado en la lógica de predicados de primer
orden y LISP, otro lenguaje de programación declarativa, en lambda calculo), y por
tanto su semántica no depende de la máquina en la que se ejecutan. Las sentencias
en estos lenguajes se entienden sin necesidad de hacer referencia al nivel máquina
para explicar los efectos colaterales. Por tanto, un programa escrito en un lenguaje
declarativo puede usarse como una especificación o una descripción formal de un
problema. Otra ventaja de los programas escritos en lenguajes declarativos es que
se pueden desarrollar y comprobar poco a poco, y pueden ser sintetizados o
transformados sistemáticamente.

MARCO TEÓRICO

PROLOG es un lenguaje de programación muy útil para resolver problemas que
implican objetos y relaciones entre objetos. Está basado en los siguientes
mecanismos básicos, que se irán explicando a lo largo de este capítulo:

· Unificación
· Estructuras de datos basadas en árboles
· Backtracking automático
La sintaxis del lenguaje consiste en lo siguiente:
· Declarar hechos sobre objetos y sus relaciones
· Hacer preguntas sobre objetos y sus relaciones

· Definir reglas sobre objetos y sus relaciones

Los hechos PROLOG
Para explicar los fundamentos de PROLOG vamos a utilizar el típico ejemplo de
las relaciones familiares.
Para decir que Laura es uno de los dos progenitores de Damián, podríamos declarar
el siguiente hecho PROLOG:

progenitor(laura, damian).

“progenitor” es el nombre de la relación o nombre de predicado y “laura” y
“damian” son los argumentos. Los hechos acaban siempre con punto. Nosotros
interpretaremos que Laura, primer argumento de la relación, es la madre de
Damián, segundo argumento de la relación. Sin embargo, este orden es arbitrario y
cada programador puede darle su propio significado. Los nombres de las relaciones
y los argumentos que se refieren a objetos o personas concretas se escribirán con
minúscula.
Otros ejemplos de hechos pueden ser los siguientes:

le_gusta_a(juan,maria).

valioso(oro).

tiene(juan,libro).

da(juan,libro,maria).

Los nombres también son arbitrarios y el programador decidirá la interpretación
que haga de ellos. La relación le_gusta_a(juan,maria) es equivalente a la relación
a(b,c), aunque para que la interpretación sea más sencilla, se recomienda que los
nombres se elijan de forma que ayuden a su interpretación.
Los hechos no tienen que reflejar el mundo real necesariamente, pero será única y
exclusivamente lo que PROLOG tomará como verdadero. Un conjunto de hechos
(también llamados cláusulas), junto con un conjunto de reglas, forman lo que se
llama una base de datos PROLOG.

Las preguntas PROLOG
Sobre un conjunto de hechos se pueden realizar una serie de preguntas. Por
ejemplo:

?- le_gusta_a(juan,maria).

PROLOG busca automáticamente en la base de datos si existe un hecho que se
puede unificar (es decir, tiene el mismo nombre de predicado, el mismo número de
argumentos ¾o aridad ¾ y cada uno de los argumentos tiene el mismo nombre,
uno a uno) con el hecho que aparece en la pregunta. PROLOG contestará “SI” si
encuentra ese hecho y “NO” si no lo encuentra. La contestación “NO” no implica
que el hecho sea falso (aunque sí lo sea para nuestra base de datos), sino que no se
puede probar (en general) que sea verdadero con el conocimiento almacenado en la
base de datos.

Para realizar preguntas más interesantes, como por ejemplo, qué le gusta a María o
cuáles son los padres de Damián, se usarán las variables. En PROLOG las variables
empiezan por mayúscula. Por ejemplo:
?-le_gusta_a(maria,X).

?-progenitor(Y,damian).

Búsqueda primero en profundidad

Primero se expande el nodo más profundo del árbol de búsqueda. No es un método completamente óptimo; su complejidad temporal O(bm) y su complejidad espacial es O(bm), en donde m es la profundidad máxima. Los árboles de búsqueda cuya profundidad es muy grande o infinita, invalidan la utilidad de este método.
Sólo si la búsqueda conduce a un callejón sin salida (un nodo sin meta que no tiene expansión), se revierte la búsqueda y se expanden los nodos de niveles menos profundos.

Búsquedas Bidireccionales

Ayuda a reducir notablemente la complejidad temporal, aunque no siempre pueda utilizársele.
La cantidad de memoria que necesita puede hacerla poco práctica.
Es básicamente, una búsqueda simultánea que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún punto intermedio.

Búsqueda: Primero en profundidad con iteraciones

Se emplea la búsqueda con límite de profundidad, pero los límites van aumentando hasta encontrar una meta. Es completa y óptima; su complejidad temporal es O(bd) y su complejidad espacial es O(bd).

Búsqueda de profundidad limitada

Se pone un límite a la búsqueda preferente por profundidad. Si el límite fuera igual a la profundidad del estado meta más superficial, se reduce al mínimo la complejidad espaciotemporal.

Búsqueda de costo uniforme

Primero se expande el nodo hoja de menor costo. Es un método completo y, a diferencia de la
búsqueda preferente por amplitud, es óptimo incluso si el costo de cada uno de los operadores
es distinto. Su complejidad espacio-temporal es la misma que la de la búsqueda preferente por
amplitud.
Siempre se tiene un costo o unidades. Los costos deben ser positivos, caso contrario no se
aplica esta búsqueda.

Búsqueda primero en anchura

Búsqueda preferente por amplitud(anchura)
Primero se expande el nodo más superficial del árbol de búsqueda. Es un método completo,
óptimo para operadores de costo unitario. Su complejidad espacio-temporal es O(bd). En
muchos casos, la complejidad espacial impide que sea práctico.
Debo expandir la profundidad (d) antes de expandir la profundidad siguiente (d+1) empezando
por la izquierda. d = profundidad nodo raíz = estado inicial.