Diferencias

Muestra las diferencias entre dos versiones de la página.

--- introalg:taller09_1 [2009/03/21 12:55] – laura
+++ introalg:taller09_1 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 1: / Línea 1: @@
+=====Introducción a la Programación Lógica=====
+====Qué es la programación declarativa?====
 Este año vamos a ver aproximaciones distintas a la [[http://es.wikipedia.org/wiki/Programaci%C3%B3n_declarativa|programación declarativa]]: [[http://es.wikipedia.org/wiki/Programaci%C3%B3n_L%C3%B3gica|programación lógica]] (en [[http://es.wikipedia.org/wiki/Prolog|prolog]]) y [[http://es.wikipedia.org/wiki/Programaci%C3%B3n_funcional|programación funcional]] (en [[http://es.wikipedia.org/wiki/Haskell|haskell]]). Este tipo de programación tiene varias diferencias con la [[http://es.wikipedia.org/wiki/Programaci%C3%B3n_imperativa|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.
+====Iniciando prolog====
 Empezamos con la [[http://es.wikipedia.org/wiki/Programaci%C3%B3n_L%C3%B3gica|programación lógica]] (en [[http://es.wikipedia.org/wiki/Prolog|prolog]]). Hay varios dialectos de prolog, nosotros vamos a usar [[http://www.swi-prolog.org/|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 [[http://www.swi-prolog.org/download/stable/bin/pl-5.6.64-339.i586.rpm|linux]], [[http://www.swi-prolog.org/download/stable/bin/w32pl5664.exe|windows]], [[http://www.swi-prolog.org/download/stable/bin/w64pl5664.exe|windows de 64 bits]], [[http://www.swi-prolog.org/download/stable/bin/swi-prolog-5.6.64-leopard-intel.mpkg.zip|mac sobre intel]] y [[http://www.swi-prolog.org/download/stable/bin/swi-prolog-5.6.64-leopard-powerpc.mpkg.zip|mac sobre power pc]].
@@ Línea 20: / Línea 37: @@
 </code>
-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. Pero para poder preguntar algo, antes tenemos que conseguir que nuestro intérprete sepa algo. Cuando recién lo llamamos, el intérprete no sabe casi nada, así que tenemos que proporcionarle el conocimiento que necesita para poder contestarnos preguntas.
+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:
+<code>
+?- 5 is 2+3.
+true.
+?-
+</code>
+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.''
+<code>
+?- halt.
+computador:~ usuario$
+</code>
+====Incorporando conocimiento: hechos====
 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 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:
 <code>
 mortal(sócrates).
 hombre(sócrates).
 </code>
+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''.
@@ Línea 59: / Línea 97: @@
 </code>
-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 sigguientes líneas:
+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:
 <code>
 hombre(platón).
@@ Línea 84: / Línea 122: @@
 ?-
 </code>
+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:
+<code>
+?- hombre(platón)
+|    .
+true.
+?-
+</code>
+====Inferencia de conocimiento: reglas====
 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:
@@ Línea 94: / Línea 144: @@
 </code>
-Además, 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 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)''.
+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 en mayúscula 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. Al mecanismo por el que sustituimos una variable por un valor, con algunas restricciones, se le llama **unificación**.
+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.
-La unificación es un mecanismo que se usa en muchos lenguajes de programación. En concreto en prolog, sigue las siguientes normas:
+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:
    - 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.
@@ Línea 104: / Línea 154: @@
    - 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).
-Finalmente, y no menos importante, fíjense que todas las aserciones en prolog terminan en un punto.
+===Pensando un poco más sobre variables y unificación===
-Cuando ya no queremos preguntar nada más al intérprete, le decimos ''halt.''
+Supongamos que estamos trabajando con el siguiente conjunto de hechos (o base de conocimiento):
+<code>
+    wizard(ron).
+    hasWand(ron).
+    hasBroom(ron).
+    quidditchPlayer(harry).
+    wizard(X) :- hasBroom(X),hasWand(X).
+    hasBroom(X) :- quidditchPlayer(X).
+</code>
+Cómo responde prolog a las siguientes preguntas?
+  * wizard(ron).
+  * witch(ron).
+  * wizard(hermione).
+  * witch(hermione).
+  * wizard(harry).
+Y ahora, introduzcamos algún cambio:
+<code>
+  wizard(X) :- hasBroom(X),hasWand(_).
+</code>
+Qué efectos tiene este cambio? Por qué?
+====Desconocimiento: mensajes de alerta y de error====
+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:
+<code>
+?- ['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.
+?-
+</code>
+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.
+<code>
+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
+</code>
+Acá el intérprete se queja porque había espacio en blanco delante del predicado, de la siguiente forma:
+<code>
+      wizard(ron).
+hasWand(ron).
+</code>
+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:
+<code>
+?- witch(hermione).
+ERROR: toplevel: Undefined procedure: witch/1 (DWIM could not correct goal)
+?-
+</code>
+<code>
+?- wizard(harry).
+ERROR: wizard/1: Undefined procedure: hasWand/1
+</code>
+A veces le exigimos operaciones demasiado complicadas al intérprete, la máquina no tiene suficiente capacidad y nos quedamos sin recursos, por ejemplo:
+<code>
+?- caballero(a).
+ERROR: Out of local stack
+</code>
+Para salir de esta situación, el intérprete nos dá el siguiente mensaje:
+<code>
+Action (h for help) ?
+</code>
+Si presionamos la tecla 'h', nos aparecen diferentes opciones:
+<code>
+Action (h for help) ? Options:
+a:                 abort      b:                 break
+c:                 continue   e:                 exit
+g:                 goals      t:                 trace
+h (?):             help
+Action (h for help) ?
+</code>
+Si presionamos la tecla 'a', salimos de la ejecución, si presionamos la tecla 'e', salimos del intérprete.
-Escribir conocimiento es declarar, de ahí programación declarativa TODO
+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.
 ====Ejercicios====
-  - Expresen los miembros de una familia.
   - Digan cuáles de estas expresiones unifican y cuáles no (de la página sobre [[http://en.wikipedia.org/wiki/Unification|unificación]] de la wikipedia):
     * A = A
@@ Línea 126: / Línea 255: @@
     * A = f(A)
     * A = abc, xyz = X, A = X
+  - 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...
+  - 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...
+  - Expresen en reglas las relaciones entre los miembros de la familia que describimos aquí mediante hechos:
+<code>
+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).
+</code>
+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 [[http://www.learnprolognow.org/|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 [[http://cs.union.edu/~striegnk/learn-prolog-now/html/node13.html#sec.l1.exercises|primera tanda de ejercicios]], el 1.4 y 1.5
+  * en la [[http://cs.union.edu/~striegnk/learn-prolog-now/html/node21.html#sec.l2.exercises|segunda tanda de ejercicios]], todos!