Consolidando conceptos de programación lógica

En esta clase vamos a consolidar los conceptos que vimos en la clase anterior. Primero, vamos a repasar y profundizar algunos de los conceptos que vimos en la clase anterior. Luego, vamos a profundizar en el ejercicio de definir las relaciones familiares, tal como lo planteamos en los ejercicios de la clase anterior. Para profundizar, vamos a usar algunas de las herramientas que nos ofrece prolog y SWIProlog en particular para observar cómo el intérprete de prolog trata de solucionar las preguntas que le planteamos, con una base de conocimiento dada.

Para empezar la clase, vamos a crear una base de conocimiento con una de las posibles soluciones al problema de definir relaciones familiares. Abran el editor de texto, creen un archivo y copien esta solución al problema. Después, ejecuten el intérprete de prolog, con el comando swipl en la terminal. Carguen en memoria la base de conocimiento sobre relaciones familiares, y empecemos.

Los programas en Prolog se componen de cláusulas de Horn que constituyen reglas del tipo “modus ponendo ponens”, es decir, “Si es verdad el antecedente, entonces es verdad el consecuente”. En prolog se escribe primero el consecuente y luego el antecedente. Por ejemplo, si quiero decir “Si llueve y no llevo paraguas, me empapo”, lo escribo así:

empapo(yo) :- llueve , not(llevo(yo,paraguas)).

El consecuente es la cabeza de la regla, y el antecedente es el cuerpo.

Una forma de entender las cláusulas de Horn es considerar que la cabeza de la regla es el objetivo que se quiere alcanzar, y en el cuerpo encontramos las condiciones o subobjetivos que tienen que cumplirse para alcanzar el objetivo de la cabeza.

Las consultas que hacemos al intérprete pueden entenderse como una pregunta sobre si un determinado objetivo es cierto. Por lo tanto, si preguntamos:

?- empapo(yo).

lo que estamos preguntando es si se dan las condiciones para que yo me empape, es decir, si son ciertos los subobjetivos que componen el cuerpo de alguna de las reglas que tienen 'empapo(yo)' en la cabeza.

El cuerpo de una regla puede ser una conjunción o disyunción de condiciones. Si queremos expresar conjunción de objetivos, los separamos con una coma (,), si queremos expresar disyunción, los separamos con un punto y coma (;). Podemos usar paréntesis para agrupar conjunciones y disyunciones de forma inambigua, ya que, como sabemos, tienen la misma precedencia. Por ejemplo, en el ejemplo de la familia, podemos definir el predicado hijo único de la siguiente forma:

hijoúnico(X) :- 
   ( hombre(X), mujer(X) ) , 
   not( hermano(_,X) ; hermana(_,X) ).

Los paréntesis nos están ayudando a agrupar las conjunciones y las disyunciones de forma que la regla diga exactamente lo que queremos que diga, y no cualquier otra cosa.

Recordemos que los hechos no son más que cláusulas de Horn con un true como antecedente. Por lo tanto, serán equivalentes:

llueve.

y

llueve :- true.

Recordemos que las reglas de prolog suelen estar expresadas con variables¹⁾. Las variables son huecos en los que podemos poner cualquier valor, siempre que mantengamos el mismo valor para una variable con el mismo nombre dentro de una misma regla. Por lo tanto, el valor de las variables va puede ser distinto en cada ejecución. Por ejemplo, en nuestro ejemplo de la familia, en la regla madre(X,Y) :- mujer(X), progenitor(X,Y)., las variables X e Y pueden tomar todos los siguientes valores:

X = pepa,
Y = 'lucía' ;
X = pepa,
Y = blanca ;
X = pepa,
Y = mario ;
X = 'lucía',
Y = rosa ;
X = 'lucía',
Y = alba ;
X = blanca,
Y = 'inés' ;
X = blanca,
Y = 'martín' ;
X = irene,
Y = 'matías'.

Podemos consultar estos valores preguntando madre(X,Y). al intérprete, y escribiendo ; después de cada respuesta, indicando así que queremos seguir viendo resultados. Si en lugar de escribir ; presionamos la tecla enter, el intérprete va a dejar de ofrecernos resultados, y sólo vamos a ver el primero.

A veces queremos comparar dos términos, ya sean constantes o variables a las cuales se ha asignado un valor. El mecanismo que determina si esos valores son iguales o no se llama unificación, y vimos un ejercicio en la clase anterior.

Los términos de prolog pueden ser simples (booleanos, números, constantes, variables) o complejos. Los términos complejos son funciones con argumentos, posiblemente con 0 argumentos. El número de argumentos de una función se conoce como aridad, y las funciones pueden llamarse unarias si tienen un argumento, binarias si tienen dos, ternarias si tienen tres, etc.

Las funciones (también llamadas predicados, porque son funciones cuyo resultado posible es true o false) se definen con su nombre y el número de argumentos que toman, por ejemplo:

llueve/0.
empapo/1.
madre/2.
pagar/3.

Dos funciones con el mismo nombre pero diferente número de argumentos se consideran distintas funciones. Por ejemplo, algunos de ustedes definieron madre/1 además de la función madre/2 que tenemos en la solución al problema de la familia. El predicado madre/1 sirve para saber si alguien es o no es madre, y se define así:

madre(X) :- mujer(X), progenitor(X,Y).

Muchas veces los programas fallan porque no estamos trabajando con el número correcto de argumentos de una función. Por esta razón, es muy importante fijarse en el número de argumentos de las funciones que nos aparecen en los mensajes de error o de aviso que genera prolog.

Cuando prolog trata de resolver una pregunta o objetivo, busca una cláusula de Horn que tenga ese objetivo en la cabeza, y sustituye el objetivo por el cuerpo de la cláusula. Entonces, los objetivos del intérprete pasan a ser cada una de las cláusulas del cuerpo. Por ejemplo, si preguntamos:

?- madre(pepa,blanca).

el intérprete encuentra la cláusula que tiene madre(X,Y) en la cabeza: madre(X,Y) :- mujer(X), progenitor(X,Y)., y sustituye por a nuestro objetivo inicial por los objetivos en el cuerpo de la regla.

mujer(pepa).
progenitor(pepa,blanca).

El intérprete repite esta procedimiento hasta que puede llegar a true para cada uno de los objetivos que tiene que resolver. ¿Cuándo sucede eso? Como podemos considerar que los hechos tienen un true como antecedente, al hacer la sustitución de la cabeza de una regla por su cuerpo, sustituimos un objetivo por un true, con lo cual llegamos a true para ese objetivo. En el ejemplo de madre(pepa,blanca)., los dos objetivos en que se desdobla el objetivo inicial se encuentran como hechos en nuestra base de conocimiento, por lo tanto el intérprete encuentra un true para todos sus objetivos.

Si alguno de los objetivos es falso o no se encuentra en la base de conocimiento, el intérprete no puede llegar a un true y el objetivo falla.

Pero a veces sucede que cuando hacemos una pregunta al intérprete, éste nos dá responde true, y, si le escribimos ; para que nos siga dando opciones, nos devuelve false. Este comportamiento sigue la misma lógica que si le pedimos al intérprete los posibles valores de una variable, y nos los devuelve todos. Para resolver un objetivo, el intérprete explora todas las posibles opciones, es decir, trata de resolver todas las cláusulas que tengan al objetivo en la cabeza, que puede ser más de una. Esta situación se puede entender como una disyunción: para satisfacer el objetivo, se puede hacer o bien satisfaciendo un subconjunto de objetivos (el cuerpo de una cláusula) o bien satisfaciendo otro subconjunto de objetivos (el cuerpo de otra cláusula). De hecho, es equivalente escribir dos cláusulas con la misma cabeza o escribir los cuerpos de esas dos cláusulas unidos por una disyunción en el cuerpo de una sola cláusula. Por ejemplo, serían equivalentes:

hasBroom(X) :- quidditchPlayer(X).
wizard(X) :- hasBroom(X), hasWand(X).
wizard(X) :- quidditchPlayer(X), hasWand(X).

y

hasBroom(X) :- quidditchPlayer(X).
wizard(X) :- ( hasBroom(X), hasWand(X) ) ;
             ( quidditchPlayer(X), hasWand(X) ).

Cada uno de estos puntos donde encontramos varias formas (o caminos) para que un predicado llegue a ser true o false se llaman punto de elección.

Cuando uno de los objetivos encontrados resulta ser falso, el intérprete vuelve para atrás hasta el punto de elección inmediatamente anterior, y busca otras reglas por las que sustituir el objetivo, y así hasta que agota todas las posibles reglas por las que sustituir el objetivo. El procedimiento de volver atrás se conoce como backtracking, y consiste en deshacer todo lo ejecutado, situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Como resultado, el intérprete nos ofrece todos los resultados a los que fue llegando en esta exploración de los caminos a los que le llevan los puntos de elección.

Todos los dialectos de prolog nos ofrecen diversas formas de inspeccionar el proceso de backtracking de una ejecución. En SWIProlog, tenemos una interfaz gráfica y una interfaz de texto. La interfaz gráfica se ejecuta de la siguiente manera:

?- guitracer.
% The graphical front-end will be used for subsequent tracing
true.

?- trace.
Unknown message: query(yes)
[trace] ?-

El intérprete está listo para mostrarnos gráficamente cómo va tratando de resolver nuestras preguntas. Si le hacemos cualquier pregunta, por ejemplo ?- madre(pepa,blanca). nos aparecerá la siguiente ventana:

En la ventana de arriba a la izquierda vemos cómo se va asignando valor a las variables en los diferentes pasos de la ejecución. En la ventana de arriba a la derecha vemos qué predicados se están evaluando en cada paso. En la ventana inferior vemos qué parte de la base de conocimiento se está aplicando en cada caso. Para ir avanzando en los pasos de la ejecución, hay que presionar el botón de la parte superior de la pantalla con el dibujo de una flecha que apunta a la derecha.

Si no podemos acceder a esta interfaz gráfica, podemos inspeccionar el progreso de la ejecución a través de la consola de texto del intérprete, con la instrucción trace:

?- trace.
Unknown message: query(yes)
[trace]  ?-

La palabra [trace] delante del prompt del intérprete nos indica que estamos en modo de traza, es decir, que el intérprete nos va a mostrar todos los pasos de la ejecución.

Para que el intérprete deje de mostrarnos los diferentes pasos de la ejecución, tenemos que decirle:

[trace]  ?- notrace.
true.

[debug]  ?- nodebug.
true.

?- 

Veamos un ejemplo de traza:

[trace]  ?- madre(pepa,blanca).
   Call: (7) madre(pepa, blanca) ? creep
   Call: (8) mujer(pepa) ? creep
   Exit: (8) mujer(pepa) ? creep
   Call: (8) progenitor(pepa, blanca) ? creep
   Exit: (8) progenitor(pepa, blanca) ? creep
   Exit: (7) madre(pepa, blanca) ? creep
true ;
   Redo: (8) progenitor(pepa, blanca) ? creep
   Fail: (7) madre(pepa, blanca) ? creep
false.

[debug]  ?- 

Cada línea nos muestra un paso en la ejecución de nuestra pregunta. El intérprete llama creep al hecho de pasar al siguiente paso en la ejecución. Veamos esta ejecución en detalle.

En primer lugar, se llama a la función madre(X,Y), lo cual se indica con la palabra clave Call: . Las variables toman el valor que le asignamos mediante la consulta: X=pepa, Y=blanca. Luego, se busca una regla que tenga madre(X,Y) en la cabeza, y se sustituye la cabeza por el cuerpo. En este caso, se encontró la regla madre(X,Y) :- mujer(X), progenitor(X,Y).. Se sustituyen las variables según está especificado en la consulta, X=pepa, Y=blanca.

Primero se evalúa el primer subobjetivo, mujer(pepa), llamando a la función mujer, en la línea Call: (8) mujer(pepa). Se encuentra un hecho que nos dice que esto es cierto, con lo cual el subobjetivo tiene éxito y sale, como se indica con la palabra clave Exit: , en la línea Exit: (8) mujer(pepa).

Después se evalúa el segundo subobjetivo, progenitor(pepa, blanca). También se encuentra un hecho que nos dice que esto es cierto, así que se sale de la evaluación de este predicado también con éxito.

Una vez que sabemos que son ciertas todas las condiciones necesarias para que sea cierto el predicado madre(pepa,blanca), podemos asegurar que el predicado es cierto, y por eso el intérprete nos devuelve un true.

Pero esta no es la única interpretación posible. Si escribimos ;, el intérprete vuelve atrás, aplica backtracking hasta algún punto de elección donde podría haber tomado una decisión distinta. Con la palabra clave Redo: nos indica qué subobjetivo va a rehacer, en este caso, progenitor(pepa, blanca). La evaluación de este subobjetivo resulta ahora falsa, y por lo tanto el objetivo general madre(pepa,blanca) también será falso. Así el intérprete nos lista todas las posibles soluciones a nuestra pregunta.

[trace]  ?- hermano(mario,blanca).
   Call: (7) hermano(mario, blanca) ? creep
   Call: (8) hombre(mario) ? creep
   Exit: (8) hombre(mario) ? creep
   Call: (8) progenitor(_L176, mario) ? creep
   Exit: (8) progenitor(pepa, mario) ? creep
   Call: (8) progenitor(pepa, blanca) ? creep
   Exit: (8) progenitor(pepa, blanca) ? creep
^  Call: (8) not(mario=blanca) ? creep
^  Exit: (8) not(mario=blanca) ? creep
   Exit: (7) hermano(mario, blanca) ? creep
true ;
   Redo: (8) progenitor(pepa, blanca) ? creep
   Redo: (8) progenitor(_L176, mario) ? creep
   Exit: (8) progenitor(armando, mario) ? creep
   Call: (8) progenitor(armando, blanca) ? creep
   Exit: (8) progenitor(armando, blanca) ? creep
^  Call: (8) not(mario=blanca) ? creep
^  Exit: (8) not(mario=blanca) ? creep
   Exit: (7) hermano(mario, blanca) ? creep
true ;
   Redo: (8) progenitor(armando, blanca) ? creep
   Redo: (8) progenitor(_L176, mario) ? creep
   Fail: (8) progenitor(_L176, mario) ? creep
   Fail: (7) hermano(mario, blanca) ? creep
false.

Aquí queremos saber si Mario es hermano de Blanca, para lo cual el intérprete llega de dos formas a un true y de una forma a un false. Algunos detalles interesantes de esta traza son el uso de nombres internos para las variables internas que aparecen en la regla de hermano: hermano(X,Y) :- hombre(X), progenitor(Z,X), progenitor(Z,Y), not(X=Y).. La variable Z no tiene un valor la primera vez que se llama a la función progenitor, porque no se le ha asignado un valor desde la consulta, y prolog le asigna un valor temporal _L176, que se sustituye por una constante en cuanto se encuentra algún hecho que se pueda unificar.

Por otro lado, notemos que las reglas en las que se involucra el predicado not/1 están marcadas con el símbolo ^, esto es así para llamar nuestra atención sobre esta parte de la ejecución, ya que el comportamiento del no en prolog es muy particular.

Para proponer una solución para un problema mediante un programa informático, es crucial hacer un buen análisis del problema. En el análisis trataremos de identificar cuáles son las componentes del problema y las relaciones entre ellas. Después, crearemos una solución teniendo en cuenta nuestro análisis.

Por la forma en que se maneja prolog, resulta muy directo escribir programas para cierto tipo de problemas, esencialmente, los que se pueden solucionar mediante la regla “modus ponens”. Pero, como en cualquier otra aproximación formal a los problemas, resulta básico hacer un buen análisis del problema antes de ponerse a programarlo.

En los ejercicios del día de hoy van a tener que proponer soluciones para algunos problemas que seguramente conocen bien. Si las soluciones que proponen no llegan a dar los resultados que esperaban, deben hacer dos cosas:

• leer bien atentamente los mensajes de error o de advertencia que les da el intérprete.
• usar las herramientas que hemos visto en la clase para observar cómo está funcionando el intérprete, seguramente de una forma distinta a como ustedes están pensando.

Traten de aportar soluciones para los siguientes problemas:

1. Partiendo del ejemplo de la familia, ¿cómo tenemos que ampliarlo para expresar la relación “suegra” o “cuñado”? ¿y “abuelo materno”? ¿o “hermano mayor”?
2. ¿Cómo sería un programa para recomendar amigos en una red social tipo facebook?
3. ¿Cómo podemos hacer un programa no muy largo que, dado un animal, nos diga si es ovíparo o vivíparo, si vive en la tierra, en el agua o en el aire, si come carne o vegetales, etc.? Traten de usar generalizaciones del tipo si es mamífero, entonces…. En esta aproximación, cómo tratarían excepciones como “delfín” o “guppi”?
4. Tenemos una lista de las conexiones por tren entre pares de ciudades, por ejemplo conectadas(Tarragona,Barcelona). . ¿Cómo sería un programa que nos ayudara a saber si podemos llegar de una ciudad a otra, es decir, si existe una lista de conexiones que nos lleve de una ciudad a otra, o bien eso es imposible? Primero, traten de hacer un programa que nos diga si podemos llegar de una ciudad a otra directamente o bien en dos o en tres pasos…