Ciencias de la Computación FAMAF

Este año vamos a ver aproximaciones distintas a la programación declarativa: programación lógica (en prolog) y programación funcional (en haskell). Este tipo de programación tiene varias diferencias con la programación imperativa que quizás muchos de ustedes conozcan (C, C++, Visual Basic, Perl).

En el paradigma de la programación declarativa, lo que hace el programador es explicar cómo son las cosas, a diferencia de la programación imperativa, donde uno dice qué cosas hacer, es decir, dá órdenes. Vamos a ver que en prolog o haskell no damos órdenes, sino que describimos las cosas que nos interesan, y luego le pedimos al intérprete que nos responda preguntas sobre la información que le hemos proporcionado.

El interés de la programación declarativa radica en el hecho de que podemos obtener mucha más información de la que hemos declarado inicialmente, ya que los intérpretes son capaces de hacer inferencia de conocimiento mediante reglas, o instanciar reglas generales en casos particulares. Veamos algunos ejemplos, que luego vamos a implementar como ejercicios.

En prolog podemos describir una familia declarando únicamente las relaciones entre padres e hijos y el sexo de cada miembro de la familia, y luego con reglas que describen cada relación familiar (padre, madre, primo, tío) en función de estas dos únicas fuentes de conocimiento.

También podemos describir las conexiones que existen entre ciudades, de a pares únicamente, y ahí determinar si existe algún camino que conecte un par de ciudades cualquiera. Incluso se puede determinar cuál es el camino más corto de todos los posibles, si es que hay más de uno.

Algunas cosas para las que no es razonable usar prolog: para gestión de archivos, tratamiento masivo de datos, manipulación de texto mediante expresiones regulares, entre otros.

Empezamos con la programación lógica (en prolog). Hay varios dialectos de prolog, nosotros vamos a usar SWIProlog. En las computadoras del laboratorio ya está instalado, pero si lo quieren tener en su casa, tendrán que bajárselo e instalarlo. Existen versiones para linux, windows, windows de 64 bits, mac sobre intel y mac sobre power pc.

Lo primero que vamos a hacer es conseguirnos un editor de texto que nos ayude a escribir programas. Si alguien programa habitualmente en un editor o entorno de programación en concreto, que siga usando ese (emacs, vi, eclipse). Sino, podemos empezar usando editores livianos y no propietarios. En linux, podemos usar kate, en windows podemos usar un editor específico para SWIprolog o cualquier otra cosa que os guste (incluyendo NotePad). A partir de ahora vamos a trabajar solamente en linux, los que trabajen en Windows, sigan las instrucciones específicas para windows que encontrarán en SWIProlog.

Lo segundo que vamos a hacer es ejecutar prolog. Para eso vamos a una terminal y escribimos swipl, lo que nos lleva al entorno de prolog:

computador:~ usuario$ swipl
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.64)
Copyright (c) 1990-2008 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- 

El símbolo ?- nos indica que el intérprete de prolog está preparado y esperando nuestras órdenes. En el caso de prolog, las órdenes serán preguntas que le vamos a hacer y el intérprete nos va a responder. Las preguntas tienen forma de predicados.

El intérprete solamente contesta a cosas que sepa. Si nosotros no le proporcionamos ningún conocimiento extra, el intérprete sólo sabe algunas propiedades sobre números, por ejemplo, le podemos preguntar lo siguiente:

?- 5 is 2+3.
true.

?-

Pero si le queremos preguntar otra para, antes tenemos que proporcionarle el conocimiento que necesita. Para proporcionarle ese conocimiento, lo que hacemos es editar un archivo con el editor que queramos usar (kate, notepad, cualquiera). En ese archivo escribimos el conocimiento que queramos proporcionar al intérprete, en forma de hechos y reglas. Una vez que tenemos el conocimiento escrito, guardamos el archivo mediante el menú de archivo del editor, vamos al intérprete, cargamos el archivo en la memoria, y ahí podemos empezar a preguntar por el conocimiento que cargamos.

Cuando ya no queremos preguntar nada más al intérprete, cerramos el intérprete diciéndole halt.

?- halt.
computador:~ usuario$ 

Para proporcionar el conocimiento al intérprete, el proceso más habitual es escribir este conocimiento en un archivo, y luego darle el archivo al intérprete para que lo cargue en su memoria. Después, el intérprete va a tener el conocimiento en la memoria y podremos preguntarle sobre ese conocimiento.

Vamos a proporcionarle a nuestro intérprete algo de conocimiento. Prendemos nuestro editor y escribimos algo de conocimiento. Por ejemplo, vamos a declarar un par de hechos: que Sócrates es un hombre y que Sócrates es mortal. Lo escribimos como predicados, de la siguiente forma:

mortal(sócrates).
hombre(sócrates).

NOTA: Fíjense que no usamos mayúsculas, ya que las mayúsculas están reservadas para las variables.

Guardamos el archivo con un nombre cualquiera y la extensión .pl, por ejemplo, ejemplo1.pl.

Ahora cargamos el archivo en la memoria del intérprete:

?- ['ejemplo1.pl'].
% ejemplo1.pl compiled 0.00 sec, 0 bytes
true.

?-

El intérprete está listo para que le preguntemos cosas sobre la mortalidad de Sócrates y su hombría, de la siguiente forma:

?- mortal(sócrates).
true.

?- 

Cuando terminamos de preguntar, el intérprete queda listo para una nueva consulta.

Es importante darse cuenta de que el intérprete nos va a decir que es falso todo aquello que no tenga cargado en la memoria, incluso si es algo que es verdad. Por ejemplo:

?- hombre(platón).
false.

?-

Podemos añadir información para que el intérprete tenga más conocimiento cargado en memoria editando el archivo ejemplo1.pl. Por ejemplo, añadimos las siguientes líneas:

hombre(platón).
hombre(aristóteles).

Ahora le podemos preguntar al intérprete, que nos dirá:

?- hombre(platón).
false.

?-

Por qué sucede esto? Porque no cargamos el conocimiento en memoria! Primero hay que guardar el archivo con el conocimiento, cargarlo a la memoria del intérprete y después preguntar.

?- ['ejemplo.pl'].
% ejemplo.pl compiled 0.00 sec, 584 bytes
true.

?- hombre(platón).
true.

?- 

Finalmente, y no menos importante, fíjense que todas las aserciones en prolog terminan en un punto. Si no terminan en un punto, el intérprete se queda esperando hasta que le ponemos el punto:

?- hombre(platón)
|    .
true.

?- 

Ahora bien, si queremos añadir el conocimiento de que Platón y Aristóteles también son mortales, tendremos que declararlo en una aserción para cada caso? No podemos hacer algo más general? Sí, podemos usar reglas y variables. Podemos decir algo así como “si alguien es un hombre, ese alguien es mortal”, o mejor todavía, “si un X es hombre, entonces ese X es mortal”, escrito de la siguiente forma:

mortal(X) :- hombre(X).

Esto es una regla de prolog, lo que se conoce formalmente como cláusula de Horn. Las cláusulas de Horn son muy parecidas a las implicaturas lógicas. A la derecha de la cláusula encontramos el consecuente de una implicación, a la derecha encontramos las condiciones para que se dé el consecuente. Por ejemplo, si queremos decir “si llueve, me resfrío” lo escribiremos así:

resfrío(yo) :- llueve.

Recién hemos introducido el uso de variables. Hasta ahora sólo habíamos usado constantes, que se escriben siempre en minúscula y pueden ser atómicas o complejas. Ejemplos de constantes atómicas (también llamados “átomos”) serían sócrates, platón, aristóteles, yo o llueve. Constantes complejas serían los predicados como hombre(), mortal(). Son complejas porque su significado está compuesto de más de una parte, por ejemplo hombre(sócrates). Por el momento hemos visto constantes con solamente un argumento, pero el número de argumentos es arbitrario. Así, podemos decir cosas como ama(pedro,maría). o paga(empleador,empleado,sueldo).

Las variables se escriben siempre empezando por mayúscula (por ejemplo, X, Equis o Variable, pero nunca x, equis o variable) y son simplemente huecos donde podemos poner cualquier cosa. Eso sí, con una restricción: si en una regla ponemos una cosa en una variable que se llama, por ejemplo, X, tenemos que poner la misma cosa siempre que aparezca la variable X en la misma regla. Es decir, dentro de una misma regla no podemos poner una cosa en un lugar donde aparece X y otra cosa en otro lugar donde aparece X. La única excepción a esta regla es la variable comodín _, que es un súper hueco: puede sustituirse por cualquier cosa, y esas cosas pueden ser distintas dentro de una misma regla.

Al mecanismo por el que sustituimos una variable por un valor, con algunas restricciones, se le llama unificación. La unificación es un mecanismo que se usa en muchos lenguajes de programación. En concreto en prolog, sigue las siguientes normas:

1. una variable a la cual no se ha asignado todavía ningún valor se puede unificar con un átomo, un término o otra variable a la cual no se ha asignado valor. En muchos dialectos de prolog y en lógica de primer orden, una variable no se puede unificar con un término que la contiene.
2. dos átomos sólo se pueden unificar si son idénticos.
3. un término se puede unificar con otro término si la función que los contiene es la misma, tiene la misma cantidad de argumentos y los argumentos se pueden unificar entre ellos (fíjense que esto es un procedimiento recursivo, ya que puede ser que los argumentos sean términos y que el procedimiento para unificación de términos tenga que aplicarse también a ellos).

Supongamos que estamos trabajando con el siguiente conjunto de hechos (o base de conocimiento):

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

Cómo responde prolog a las siguientes preguntas?

• wizard(ron).
• witch(ron).
• wizard(hermione).
• witch(hermione).
• wizard(harry).

Y ahora, introduzcamos algún cambio:

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

Qué efectos tiene este cambio? Por qué?

El intérprete nos va a avisar cuando haya algún error o bien alguna cosa que le parece extraña en el archivo. Es importante leer los mensajes que nos dá el intérprete para interpretar qué está pasando en cada momento. Muchas veces se trata de cosas sin importancia:

?- ['ejemplo.pl'].
Warning: /Users/la/fen/introalg09/taller/prolog/ejemplo.pl:6:
	Clauses of wizard/1 are not together in the source-file
Warning: /Users/la/fen/introalg09/taller/prolog/ejemplo.pl:7:
	Clauses of hasBroom/1 are not together in the source-file
% ejemplo.pl compiled 0.00 sec, 0 bytes
true.

?-

En este caso, lo único que nos dice el intérprete es que las aserciones que hacen referencia a wizard no están todas juntas en el archivo “ejemplo.pl”. Nos avisa porque cree que es más elegante tener todas las referencias a un mismo predicado juntas en la base de conocimiento, para que la base de conocimiento sea más ordenada.

Warning: /Users/la/fen/introalg09/taller/prolog/ejemplo.pl:2:
	Redefined static procedure wizard/1
Warning: /Users/la/fen/introalg09/taller/prolog/ejemplo.pl:3:
	Redefined static procedure hasWand/1

Acá el intérprete se queja porque había espacio en blanco delante del predicado, de la siguiente forma:

      wizard(ron).
hasWand(ron).

Algunas veces el intérprete se queja porque no le hemos definido los predicados que pretendemos usar, eso sí es grave, ya que no se puede realizar la interpretación, y por eso el intérprete nos lo marca como ERROR:

?- witch(hermione).
ERROR: toplevel: Undefined procedure: witch/1 (DWIM could not correct goal)
?- 

?- wizard(harry).
ERROR: wizard/1: Undefined procedure: hasWand/1

A veces le exigimos operaciones demasiado complicadas al intérprete, la máquina no tiene suficiente capacidad y nos quedamos sin recursos, por ejemplo:

?- caballero(a).
ERROR: Out of local stack

Para salir de esta situación, el intérprete nos dá el siguiente mensaje:

Action (h for help) ? 

Si presionamos la tecla 'h', nos aparecen diferentes opciones:

Action (h for help) ? Options:
a:                 abort      b:                 break
c:                 continue   e:                 exit
g:                 goals      t:                 trace
h (?):             help
Action (h for help) ? 

Si presionamos la tecla 'a', salimos de la ejecución, si presionamos la tecla 'e', salimos del intérprete.

El próximo día vamos a ver un poco más qué pasa con la opción 't', que nos permite ver los pasos por los que va pasando el intérprete. También vamos a entrar un poco más en detalle en funciones complejas, y vamos a ver más sistemáticamente las cuestiones de aridad de las funciones, que en prolog se expresan con barra y número: 'hasWand/1', 'a/0', etc.

1. Digan cuáles de estas expresiones unifican y cuáles no (de la página sobre unificación de la wikipedia):
   • A = A
   • A = B, B = abc
   • abc = B, B = A
   • abc = abc
   • abc = xyz
   • f(A) = f(B)
   • f(A) = g(B)
   • f(A) = f(B, C)
   • f(g(A)) = f(B)
   • f(g(A), A) = f(B, xyz)
   • A = f(A)
   • A = abc, xyz = X, A = X
2. Implementen una regla que diga “cuando llueve, me resfrío”. Fíjense que para que el intérprete conteste true a la pregunta “yo me resfrío?”, el antecedente de la implicación tiene que ser cierto…
3. Ahora un ratito de reflexión (sólo 10-15 mins, luego pasen al siguiente ejercicio). Recuerdan a los caballeros y pícaros? Traten de formalizar las oraciones que hablan de ellos y vean qué pasa. Vean qué cosas tienen que formalizar para la máquina, vean si anda, vean si la máquina puede lidiar con tanta complejidad…
4. Expresen en reglas las relaciones entre los miembros de la familia que describimos aquí mediante hechos:

mujer(pepa).
mujer(lucía).
mujer(blanca).
mujer(rosa).
mujer(alba).
mujer(inés).
mujer(irene).
hombre(armando).
hombre(julián).
hombre(esteban).
hombre(mario).
hombre(alejandro).
hombre(martín).
hombre(matías).
progenitor(pepa,lucía).
progenitor(pepa,blanca).
progenitor(pepa,mario).
progenitor(lucía,rosa).
progenitor(lucía,alba).
progenitor(blanca,inés).
progenitor(blanca,martín).
progenitor(irene,matías).
progenitor(armando,lucía).
progenitor(armando,blanca).
progenitor(armando,mario).
progenitor(julián,rosa).
progenitor(julián,alba).
progenitor(alejandro,inés).
progenitor(alejandro,martín).
progenitor(mario,matías).

Escriban reglas para expresar las relaciones padre, madre, abuelo, abuela, hermano, hermana, tío, tía, primo, prima y también hijo único.

El libro Learn Prolog Now!, de Patrick Blackburn, Johan Bos and Kristina Striegnitz tiene un montón de ejercicios muy bien explicados para practicar. Yo les recomiendo:

• en la primera tanda de ejercicios, el 1.4 y 1.5
• en la segunda tanda de ejercicios, todos!