Javier Suárez Sanz, Abril 1.996
(Convertido a HTML por Nacho Cabanes, abril 2.000;
este texto está disponible en http://www.nachocabanes.com)
1. Introducción.
1.1 La Quinta Generación.
1.2 Programación Logica.
2. El lenguaje de programación PROLOG.
2.1 Hechos.
2.2 Variables.
2.3 Reglas.
2.4 Operadores.
3. Programación básica en PROLOG.
3.1 Un ejemplo sencillo.
3.2 Introduccion al PD-PROLOG.
3.3 La resolución de objetivos.
4. El mecanismo de control de PROLOG.
5. Programación avanzada.
5.1 Operadores especiales.
5.2 Estructuras de datos: las listas.
5.3 Recursividad.
5.4 Entrada/Salida.
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.
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:
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.
tiene(coche,ruedas).
X = ruedas.
instanciando la variable X con el objeto ruedas.
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.
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 esta "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.
(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.
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).
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:
X = 7
Una regla PROLOG puede ser esta:
densidad(X,Y) :- poblacion(X,P),
area(X,A), Y is P/A.
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'.
?-
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]
consult(fichero).
consult('fichero.ext').
consult('c:\ia\prolog\fichero').
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.]
Tiene como fin eliminar de la base de datos actual aquellos hechos
consultados de un fichero determinado. Su sintaxis es:
forget(fichero).
Este predicado nos devuelve al sistema operativo.
Una consulta tiene la misma forma que un hecho.
Consideremos la pregunta:
?-quiere_a(susana,pablo).
PROLOG buscará por toda la base de datos 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 datos se complican cuando estas están
compuestas por conjunciones ó bien intervienen reglas en su resolución.
Conviene, por lo tanto, conocer cual es el mecanismo de control del PROLOG,
con el fin de comprender el porqué de sus respuestas.
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 atras ó reevaluación (backtracking).
Razonamiento hacia atrás: Partiendo de un objetivo a probar, busca lasaserciones 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 datos en busca de un hecho que coincida con la cuestión planteada. Lo que halla es la reglapuede_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á:
(2) quiere_a(maria,Y).
De nuevo PROLOG recorre la base de datos. En este caso encuentra un hecho que coincide con el objetivo:
quiere_a(maria,enrique).
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 datos, 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:
quiere_a(maria,susana).
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 datos 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
quiere_a(maria,enrique).
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 datos, 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): yDe 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.]
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
mas avanzados.
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 er 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.
a :- b, c.
a :- not(b), d.
Equivale a:
a :- b, !, c.
a :- d.
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.
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]]
(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.
Su sintaxis es:
write('Hello world.').
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:
write(X).
El predicado nl fuerza un retorno de carro en la salida. Por ejemplo:write('linea 1'), nl, write('linea 2').
tiene como resultado:
linea 1
linea 2
Lee un valor del teclado. La lectura del comando read no finaliza hasta que se introduce un punto ".". Su sintaxis es:read(X).
Instancia la variable X con el valor leido del teclado.
read(ejemplo).
Se evalúa como cierta siempre que lo tecleado coincida con la constante entre paréntesis (en este caso 'ejemplo').