INTRODUCCION
AL PROLOG © Javier Suárez Sanz,
1.996
- Introducción.
- La Quinta Generación.
- Programación Lógica.
- El lenguaje de programación
PROLOG.
- Hechos.
- Variables.
- Reglas.
- Operadores.
- Programación básica
en PROLOG.
- Un ejemplo sencillo.
- Introduccion al PD-PROLOG.
- La resolución de objetivos.
- El mecanismo de control
de PROLOG.
- Programación avanzada.
- Operadores especiales.
- Estructuras de datos: las listas.
- Recursividad.
- Entrada/Salida.
- Enlaces de interés
[
Indice ]
1. Introducción.
1.1. La Quinta Generación.
En Octubre de 1981, el
gobierno japonés y más concretamente
el Ministerio Japonés de Comercio
Internacional e Industria (MITI), anuncia
la puesta en marcha de un proyecto revolucionario
equiparable a la carrera del espacio norteamericana.
Están dispuestos a ofrecer al mundo
la siguiente generación, la Quinta
Generación de Ordenadores. Unas máquinas
de Inteligencia Artificial que pueden pensar,
sacar conclusiones, emitir juicios e incluso
comprender las palabras escritas y habladas.
Con este fin se crea el
ICOT (Institute for New Generation Computer
Technology) constituido por cuarenta brillantes
investigadores de las más importantes
empresas, y se les dota con todos los medios
necesarios para construir la nueva clase
de supercomputadoras.
El papel de PROLOG.
La Quinta Generación
prevé máquinas diseñadas
para el tratamiento lógico, de capacidades
análogas a las capacidades de anteriores
generaciones de ordenadores para tratar
operaciones aritméticas. Se trata
de ordenadores que tienen el PROLOG como
lenguaje nativo (lenguaje máquina),
con capacidad para procesar millones de
inferencias lógicas por segundo (LIPS).
1.2. Programación Lógica.
La programación
lógica es un paradigma de los lenguajes
de programación en el cual los programas
se consideran como una serie de aserciones
lógicas. De esta forma, el conocimiento
se representa mediante reglas, tratándose
de sistemas declarativos.
Una representación declarativa es
aquélla en la que el conocimiento
está especificado, pero en la que
la manera en que dicho conocimiento debe
ser usado no viene dado. El más popular
de los sistemas de programación lógica
es el PROLOG.
La programación lógica
en PROLOG.
Un programa escrito en
PROLOG puro, es un conjunto de claúsulas
de Horn. Sin embargo, PROLOG, como lenguaje
de programación moderno, incorpora
más cosas, como instrucciones de
Entrada/Salida, etc.
Una claúsula de
Horn puede ser ó bien una conjunción
de hechos positivos ó una implicación
con un único consecuente (un único
termino a la derecha). La negación
no tiene representación en PROLOG,
y se asocia con la falta de una afirmación
(negación por fallo), según
el modelo de suposición de
un mundo cerrado (CWA); solo es
cierto lo que aparece en la base de conocimiento
ó bien se deriva de esta.
Las diferencias sintácticas
entre las representaciones lógicas
y las representaciones PROLOG son las siguientes:
- En PROLOG todas las variables están
implícitamente cuantificadas universalmente.
- En PROLOG existe un símbolo explicito
para la conjunción "y" (","), pero
no existe uno para la disyunción
"o", que se expresa como una lista de
sentencias alternativas.
- En PROLOG, las implicaciones p --> q
se escriben alrevés q :- p, ya
que el interprete siempre trabaja hacia
atrás sobre un objetivo, como se
vera más adelante.
[ Indice
]
2. El lenguaje de programación
PROLOG.
PROLOG puede encontrarse
en múltiples versiones diferentes.
La más popular es la definida por
Clocksin y Mellish, y es la que se tratará
aquí. Afortunadamente, al ser tan
sencilla la sintaxis del PROLOG, las variaciones
entre distintas implementaciones son mínimas.
Los elementos fundamentales de un programa
PROLOG son los siguientes:
2.1 Hechos.
Expresan relaciones entre
objetos. Supongamos que queremos expresar
el hecho de que "un coche tiene ruedas".
Este hecho, consta de dos objetos, "coche"
y "ruedas", y de una relación llamada
"tiene". La forma de representarlo en PROLOG
es: tiene(coche,ruedas).
- Los nombres de objetos y relaciones
deben comenzar con una letra minúscula.
- Primero se escribe la relación,
y luego los objetos separados por comas
y encerrados entre paréntesis.
- Al final de un hecho debe ir un punto
(".").
El orden de los objetos
dentro de la relación es arbitrario,
pero debemos ser coherentes a lo largo de
la base de hechos.
2.2. Variables.
Representan objetos que
el mismo PROLOG determinar . Una variable
puede estar instanciada ó
no instanciada. Estar instanciada
cuando existe un objeto determinado representado
por la variable. De este modo, cuando preguntamos
"¿ Un coche tiene X ?", PROLOG busca en
los hechos cosas que tiene un coche y respondería:
X = ruedas.
instanciando la variable X con el
objeto ruedas.
- Los nombres de variables comienzan siempre
por una letra mayúscula.
Un caso particular es
la variable anónima, representada
por el carácter subrayado ("_").
Es una especie de comodín que utilizaremos
en aquellos lugares que debería aparecer
una variable, pero no nos interesa darle
un nombre concreto ya que no vamos a utilizarla
posteriormente.
2.3. Reglas.
Las reglas se utilizan
en PROLOG para significar que un hecho depende
de uno ó mas hechos. Son la representación
de las implicaciones lógicas del
tipo p ---> q (p implica q).
- Una regla consiste en una cabeza y un
cuerpo, unidos por el signo ":-".
- La cabeza está formada por un
único hecho.
- El cuerpo puede ser uno ó mas
hechos (conjunción de hechos),
separados por una coma (","), que actúa
como el "y" lógico.
- Las reglas finalizan con un punto (".").
La cabeza en una regla
PROLOG corresponde al consecuente de una
implicación lógica, y el cuerpo
al antecedente. Este hecho puede conducir
a errores de representación. Supongamos
el siguiente razonamiento lógico:
tiempo(lluvioso) ----> suelo(mojado)
suelo(mojado)
Que el suelo está,
mojado, es una condición suficiente
de que el tiempo sea lluvioso, pero no necesaria.
Por lo tanto, a partir de ese hecho, no
podemos deducir mediante la implicación,
que está, lloviendo (pueden haber
regado las calles). La representación
correcta en PROLOG, sería:
suelo(mojado) :- tiempo(lluvioso).
suelo(mojado).
Adviértase que
la regla está "al revés".
Esto es así por el mecanismo de deducción
hacia atrás que emplea PROLOG. Si
cometiéramos el error de representarla
como:
tiempo(lluvioso) :- suelo(mojado).
suelo(mojado).
PROLOG, partiendo del
hecho de que el suelo está mojado,
deduciría incorrectamente que el
tiempo es lluvioso.
Para generalizar una relación
entre objetos mediante una regla, utilizaremos
variables. Por ejemplo:
| Representación lógica |
Representación PROLOG |
| es_un_coche(X) ----> tiene(X,ruedas)
|
tiene(X,ruedas) :- es_un_coche(X). |
Con esta regla generalizamos
el hecho de que cualquier objeto que sea
un coche, tendrá ruedas. Al igual
que antes, el hecho de que un objeto tenga
ruedas, no es una condición suficiente
de que sea un coche. Por lo tanto la representación
inversa sería incorrecta.
El ámbito de las variables.
Cuando en una regla aparece
una variable, el ámbito
de esa variable es únicamente esa
regla. Supongamos las siguientes reglas:
(1) hermana_de(X,Y) :- hembra(X),
padres(X,M,P), padres(Y,M,P).
(2) puede_robar(X,P) :- ladron(X),
le_gusta_a(X,P), valioso(P).
Aunque en ambas aparece
la variable X (y la variable P), no tiene
nada que ver la X de la regla (1) con la
de la regla (2), y por lo tanto, la instanciación
de la X en (1) no implica la instanciacion
en (2). Sin embargo todas las X de una
misma regla sí que se instanciarán
con el mismo valor.
2.4. Operadores.
Son predicados predefinidos
en PROLOG para las operaciones matemáticas
básicas. Su sintaxis depende de la
posición que ocupen, pudiendo ser
infijos ó prefijos. Por ejemplo el
operador suma ("+"), podemos encontrarlo
en forma prefija '+(2,5)' ó bien
infija, '2 + 5'. También disponemos
de predicados de igualdad y desigualdad.
| X = Y |
igual |
| X \= Y |
distinto |
| X < Y |
menor |
| X > Y |
mayor |
| X =< Y |
menor ó igual |
| X >= Y |
mayor ó igual |
Al igual que en otros
lenguajes de programación es necesario
tener en cuenta la precedencia
y la asociatividad de los
operadores antes de trabajar con ellos.
En cuanto a precedencia,
es la típica. Por ejemplo, 3+2*6
se evalúa como 3+(2*6). En lo referente
a la asociatividad, PROLOG es asociativo
por la izquierda. Así, 8/4/4 se interpreta
como (8/4)/4. De igual forma, 5+8/2/2 significa
5+((8/2)/2).
El operador 'is'.
Es un operador infijo,
que en su parte derecha lleva un término
que se interpreta como una expresión
aritmética, contrastándose
con el término de su izquierda.
Por ejemplo, la expresión
'6 is 4+3.' es falsa. Por otra parte, si
la expresión es 'X is 4+3.', el resultado
será la instanciación de X:
Una regla PROLOG puede
ser esta:
densidad(X,Y) :- poblacion(X,P), area(X,A),
Y is P/A.
[
Indice ]
3. Programación básica en
PROLOG.
3.1 Un ejemplo sencillo.
Con los datos que conocemos,
ya podemos construir un programa en PROLOG.
Necesitaremos un editor de textos para escribir
los hechos y reglas que lo componen. Un
ejemplo sencillo de programa PROLOG es el
siguiente:
quiere_a(maria,enrique).
quiere_a(juan,jorge).
quiere_a(maria,susana).
quiere_a(maria,ana).
quiere_a(susana,pablo).
quiere_a(ana,jorge).
varon(juan).
varon(pablo).
varon(jorge).
varon(enrique).
hembra(maria).
hembra(susana).
hembra(ana).
teme_a(susana,pablo).
teme_a(jorge,enrique).
teme_a(maria,pablo).
/* Esta linea es un comentario */
quiere_pero_teme_a(X,Y) :- quiere_a(X,Y),
teme_a(X,Y).
querido_por(X,Y) :- quiere_a(Y,X).
puede_casarse_con(X,Y) :- quiere_a(X,Y),
varon(X), hembra(Y).
puede_casarse_con(X,Y) :- quiere_a(X,Y),
hembra(X), varon(Y).
Una vez creado,
lo salvaremos para su posterior consulta
desde el interprete PROLOG. Un programa
PROLOG tiene como extensión por defecto
'.PRO'. Le daremos el nombre 'relacion.pro'.
3.2 Introducción al PROLOG DE A.D.A. (AUTOMATA
DESIGN ASSOCIATES).
Este curso se basa en
el A.D.A. PROLOG y más concretamente
en su versión de Dominio Publico
PDPROLOG, disponible para
su descarga aquí (130K). Una
vez descomprimido, encontramos un archivo
ejecutable con nombre PDPROLOG.EXE. Lo ejecutamos
y nos aparecer la información referente
al autor y versión del programa.
A continuación aparece el símbolo
Se trata del prompt del
PROLOG, que nos indica que está dispuesto
para recibir comandos. Un comando siempre
debe finalizar con un punto (".").
[NOTA: En ningún
caso podremos introducir reglas ó
hechos directamente en el prompt ?- puesto
que PDPROLOG no dispone de un editor incorporado]
A continuación
se exponen algunos comandos básicos:
consult.
El predicado consult
está pensado para leer y compilar
un programa PROLOG ó bien para las
situaciones en las que se precise añadir
las cláusulas existentes en un determinado
fichero a las que ya están almacenadas
y compiladas en la base de conocimiento.
Su sintaxis puede ser una de las siguientes:
consult(fichero).
consult('fichero.ext').
consult('c:\ia\prolog\fichero').
recon.
El predicado recon
es muy parecido a consult,
con la salvedad de que las claúsulas
existentes en el fichero consultado, reemplazan
a las existentes en la base de hechos. Puede
ser útil para sustituir una única
claúsula sin consultar todas las
demás, situando esa claúsula
en un fichero. Su sintaxis es la misma que
la de consult.
[NOTA: El predicado
recon puede encontrarse como
reconsult en otras implementaciones
de PROLOG, tal como se indica en Clocksin
& Mellish.]
forget.
Tiene como fin eliminar
de la base de conocimiento actual aquellos
hechos consultados de un fichero determinado.
Su sintaxis es:
exitsys.
Este predicado nos devuelve
al sistema operativo.
3.3 La resolución de objetivos.
Ya hemos creado un programa
PROLOG [relacion.pro] y lo hemos cargado
en nuestro interprete PROLOG [consult(relacion)].
A partir de este momento podemos interrogar
la base de hechos, mediante consultas.
Una consulta tiene la
misma forma que un hecho.
Consideremos la pregunta:
?-quiere_a(susana,pablo).
PROLOG buscar por
toda la base de conocimiento hechos que
coincidan con el anterior.
Dos hechos coinciden si sus predicados son
iguales, y cada uno de sus correspondientes
argumentos lo son entre sí. Si PROLOG
encuentra un hecho que coincida con la pregunta,
responderá yes. En caso contrario
responderá no.
Además, una pregunta
puede contener variables. En este caso PROLOG
buscara por toda la base de hechos aquellos
objetos que pueden ser representado por
la variable. Por ejemplo:
?-quiere_a(maria, Alguien).
[NOTA: Alguien
es un nombre perfectamente válido
de variable, puesto que empieza por una
letra mayuscula.]
El resultado de la consulta
es:
Alguien = enrique
More (Y/N):
El hecho 'quiere_a(maria,enrique).'
coincide con la pregunta al instanciar la
variable Alguien con el objeto 'enrique'.
Por lo tanto es una respuesta valida, pero
no la única. Por eso se nos pregunta
si queremos obtener más respuestas.
En caso afirmativo, obtendríamos:
Alguien = susana
More (Y/N):y
Alguien = ana
More (Y/N):y
No.
?-
Las consultas a
una base de conocimiento se complican cuando
estas están compuestas por conjunciones
ó bien intervienen reglas en su resolución.
Conviene, por lo tanto, conocer cuál
es el mecanismo de control del PROLOG, con
el fin de comprender el porqué de
sus respuestas.
[ Indice
]
4. El mecanismo de control de PROLOG.
El mecanismo empleado
por PROLOG para satisfacer las cuestiones
que se le plantean, es el de razonamiento
hacia atrás (backward) complementado
con la búsqueda en profundidad
(depth first) y la vuelta atrás
ó reevaluación
(backtracking).
Razonamiento hacia atrás:
Partiendo de un objetivo a probar, busca
las aserciones que pueden probar el objetivo.
Si en un punto caben varios caminos, se
recorren en el orden que aparecen en el
programa, esto es, de arriba a abajo y de
izquierda a derecha.
Reevaluación: Si
en un momento dado una variable se instancia
con determinado valor con el fin de alcanzar
una solución, y se llega a un camino
no satisfactorio, el mecanismo de control
retrocede al punto en el cual se instanció
la variable, la des-instancia y si es posible,
busca otra instanciación que supondrá
un nuevo camino de búsqueda.
Se puede ilustrar esta
estrategia sobre el ejemplo anterior:
Supongamos la pregunta:
?-puede_casarse_con(maria,X).
PROLOG recorre la
base de conocimiento en busca de un hecho
que coincida con la cuestión planteada.
Lo que halla es la regla
puede_casarse_con(X,Y) :- quiere_a(X,Y),
varon(X), hembra(Y).
produciéndose
una coincidencia con la cabeza de la misma,
y una instanciación de la variable
X de la regla con el objeto 'maria'. Tendremos
por lo tanto:
(1) puede_casarse_con(maria,Y)
:- quiere_a(maria,Y), varon(maria), hembra(Y).
A continuación,
se busca una instanciación de la
variable Y que haga cierta la regla, es
decir, que verifique los hechos del cuerpo
de la misma. La nueva meta será:
De nuevo PROLOG recorre
la base de conocimiento. En este caso encuentra
un hecho que coincide con el objetivo:
instanciando la
variable Y con el objeto 'enrique'. Siguiendo
el orden dado por la regla (1), quedan por
probar dos hechos una vez instanciada la
variable Y:
varon(maria), hembra(enrique).
Se recorre de nuevo
la base de conocimiento, no hallando en
este caso ninguna coincidencia con el hecho
'varon(maria)'. Por lo tanto, PROLOG recurre
a la vuelta atrás, desistanciando
valor de la variable Y, y retrocediendo
con el fin de encontrar una nueva instanciación
de la misma que verifique el hecho (2).
Un nuevo recorrido de la base de hechos
da como resultado la coincidencia con:
Se repite el proceso
anterior. La variable Y se instancia con
el objeto 'susana' y se intentan probar
los hechos restantes:
varon(maria), hembra(susana).
De nuevo se produce
un fallo que provoca la desinstanciación
de la variable Y, así como una vuelta
atrás en busca de nuevos hechos que
coincidan con (2).
Una nueva reevaluación
da como resultado la instanciación
de Y con el objeto 'ana' (la última
posible), y un nuevo fallo en el hecho 'varon(maria)'.
Una vez comprobadas sin
éxito todas las posibles instanciaciones
del hecho (2), PROLOG da por imposible la
regla (1), se produce de nuevo la vuelta
atrás y una nueva búsqueda
en la base de conocimiento que tiene como
resultado la coincidencia con la regla:
(3) puede_casarse_con(maria,Y) :- quiere_a(maria,Y),
hembra(maria), varon(Y).
Se repite todo el
proceso anterior, buscando nuevas instanciaciones
de la variable Y que verifiquen el cuerpo
de la regla. La primera coincidencia corresponde
al hecho
que provoca la instanciación
de la variable Y con el objeto 'enrique'.
PROLOG tratará de probar ahora el
resto del cuerpo de la regla con las instanciaciones
actuales:
hembra(maria), varon(enrique).
Un recorrido de
la base de conocimiento, da un resultado
positivo en ambos hechos, quedando probado
en su totalidad el cuerpo de la regla (3)
y por lo tanto su cabeza, que no es más
que una de las soluciones al objetivo inicial.
X = enrique
More (Y/N): y
De esta forma se
generarán el resto de las soluciones,
si las hubiera.
[NOTA: Algunas
implementaciones PROLOG incorporan los comandos
'trace' y 'notrace' que activan y desactivan
la salida por pantalla del proceso de búsqueda.
No es el caso de PDPROLOG.]
Conclusión:
PROLOG utiliza un mecanismo
de búsqueda independiente de la base
de datos. Aunque pueda parecer algo retorcido,
es una buena estrategia puesto que garantiza
el proceso de todas las posibilidades. Es
útil para el programador conocer
dicho mecanismo a la hora de depurar y optimizar
los programas.
[ Indice
]
5. Programación avanzada.
Hasta ahora hemos visto
los aspectos fundamentales de PROLOG necesarios
para crear sencillos programas (ó
sistemas expertos). A continuación
se comentan algunos mecanismos que nos permitirán
crear programas más avanzados.
5.1 Operadores especiales.
El operador "corte".
El operador corte, representado
por el símbolo "!" nos da un cierto
control sobre el mecanismo de deducción
del PROLOG. Su función es la de controlar
el proceso de reevaluación, limitándolo
a los hechos que nos interesen. Supongamos
la siguiente regla:
regla :- hecho1, hecho2, !, hecho3, hecho4,
hecho5.
PROLOG efectuará
reevaluaciones entre los hechos 1, 2 sin
ningún problema, hasta que se satisface
el hecho2. En ese momento se alcanza el
hecho3, pudiendo haber a continuación
reevaluaciones de los hechos 3, 4 y 5. Sin
embargo, si el hecho3 fracasa, no se intentara
de ninguna forma reevaluar el hecho2.
Una interpretación
práctica del significado del corte
en una regla puede ser que "si has llegado
hasta aquí es que has encontrado
la única solución a este problema
y no hay razón para seguir buscando
alternativas".
Aunque se suele emplear
como una herramienta para la optimización
de programas, en muchos casos marca la diferencia
entre un programa que funciona y otro que
no lo hace.
El operador "not".
Se define de tal forma
que el objetivo not(X) se satisface solo
si fracasa la evaluación de X. En
muchos casos, puede sustituir al operador
corte, facilitando la lectura de los programas.
Por ejemplo:
a :- b, c.
a :- not(b), d.
Equivale a:
Sin embargo, en
términos de coste, el operador corte
es más eficiente, ya que en el primer
caso PROLOG intentará satisfacer
b dos veces, y en el segundo, solo una.
5.2 Estructuras de datos: Las Listas
La lista es una estructura
de datos muy común en la programación
no numérica. Es una secuencia ordenada
de elementos que puede tener cualquier longitud.
Ordenada significa que el orden de cada
elemento es significativo. Un elemento puede
ser cualquier término e incluso otra
lista. Se representa como una serie de elementos
separados por comas y encerrados entre corchetes.
Para procesar una lista,
la dividimos en dos partes: la cabeza y
la cola. Por ejemplo:
| Lista |
Cabeza |
Cola |
| [a,b,c,d] |
a |
[b,c,d] |
| [a] |
a |
[] (lista vacía) |
| [] |
no tiene |
no tiene |
| [[a,b],c] |
[a,b] |
[c] |
| [a,[b,c]] |
a |
[[b,c]] |
| [a,b,[c,d]] |
a |
[b,[c,d]] |
Para dividir una lista,
utilizamos el símbolo "|". Una expresión
con la forma [X | Y] instanciar X a la cabeza
de una lista e Y a la cola. Por ejemplo:
p([1,2,3]).
p([el,gato,estaba,[en,la,alfombra]]).
?-p([X|Y]).
X = 1,
Y = [2,3]
More (Y/N):y
X = el,
Y = [gato,estaba,[en,la,alfombra]]
5.3 La recursividad.
La recursividad es un
mecanismo que da bastante potencia a cualquier
lenguaje de programación. Veamos
un ejemplo de programación recursiva
que nos permitirá determinar si un
átomo es miembro de una lista dada:
(1) miembro(X,[X|_]).
(2) miembro(X,[_|Y]) :- miembro(X,Y).
La regla (1) es el caso
base de la recursión. Se evaluará
como cierta siempre que coincida la variable
X con la cabeza de la lista que se pasa
como argumento. En la regla (2) está
la definición recursiva. X es miembro
de una lista si lo es de la cola de esa
lista (la cabeza se comprueba en la regla
(1)).
La regla (1) es una simplificación
de la regla:
miembro(X,[Y|_]) :- X = Y.
La traza para el caso
de 'miembro(b,[a,b,c]).' es la siguiente:
(1) miembro(b,[a,b,c]) :-
b = a. ---> no.
(2) miembro(b,[a,b,c]) :- miembro(b,[b,c]).
(1) miembro(b,[b,c]) :- b = b.
---> yes.
Si necesitamos conocer
la longitud de una lista, emplearemos una
función recursiva como la siguiente:
longitud([],0).
longitud([_|Y],L1) :- longitud(Y,L2), L1
is L2 + 1.
Otro ejemplo muy típico
de función recursiva es el del factorial
de un número:
factorial(0,1) :- !.
factorial(X,Y) :- X1 is X-1, factorial(X1,Y1),
Y is X*Y1.
5.4 Entrada/Salida.
PROLOG, al igual que la
mayoría de lenguajes de programación
modernos incorpora predicados predefinidos
para la entrada y salida de datos. Estos
son tratados como reglas que siempre se
satisfacen.
write.
Su sintaxis es:
Las comillas simples encierran
constantes, mientras que todo lo que se
encuentra entre comillas dobles es tratado
como una lista. También podemos mostrar
el valor de una variable, siempre que esté,
instanciada:
nl.
El predicado nl fuerza
un retorno de carro en la salida. Por ejemplo:
write('linea 1'), nl, write('linea
2').
tiene como resultado:
read.
Lee un valor del teclado.
La lectura del comando read no finaliza
hasta que se introduce un punto ".". Su
sintaxis es:
Instancia la variable
X con el valor leido del teclado.
Se evalúa como
cierta siempre que lo tecleado coincida
con la constante entre paréntesis
(en este caso 'ejemplo').
[ Indice
]
6. Enlaces de interés
|
Microsoft explorer 6.0 
