% -*- coding: iso-8859-1-unix; -*- % cap02.tex % % Programación Lógica y Funcional % Álvaro Tasistro - Jorge Vidart % III E.B.A.I. (1988) % % maquetación LaTeX por César Ballardini % % Copyright (C) 1988 Álvaro Tasistro - Jorge Vidart. % % Permission is granted to copy, distribute and/or modify this document % under the terms of the GNU Free Documentation License, Version 1.2 or % any later version published by the Free Software Foundation; with no % Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A % copy of the license is included in the section entitled ``GNU Free % Documentation License'' % % $Id: cap02.tex,v 1.2 2003/08/13 04:28:01 cballard Exp $ % \chapter{Introducción a la programación en lógica} \label{cha:introduccionprogramacionlogica} % -------------------------------------------------------- \begin{abstract}\pagina{19} \label{sec:intprologresumen} En este capítulo se realiza una introducción a la programación en lógica. La presentación, que será informal, se basará en el concepto de relación matemática, y apelará a los conocimientos previos del lector en los aspectos de cálculo y evaluación para lenguajes tradicionales. El ejemplo que se usará, definir relaciones de parentezco familiar, constituye el caso clásico para presentar el tema. Se definirán las relaciones por enumeración, para luego, mediante el concepto de recursión, introducir relaciones más complejas. \end{abstract} En\pagina{20} la programación imperativa tradicional el usuario diseña sus algoritmos en términos de transiciones de estados de una máquina ficticia que corresponde al lenguaje que se esté utilizando. Así un programador Pascal utiliza los constructores del mismo (asignaciones, estructuras de control, etc.) para indicar a una supuesta máquina Pascal como van evolucionando sus estados a fin de alcanzar una situación final en la que puedan identificarse los resultados deseados. Desde otro punto de vista un programa tradicional puede interpretarse como una función, que a partir de un estado inicial de la máquina ya mencionada, define los valores que corresponden al estado final de la misma luego de la evolución del algoritmo. Por su parte un programa en lógica permite definir relaciones sobre ciertos dominios dados. Dicha definición puede realizarse por extensión, es decir enumerando todas las tuplas del producto cartesiano, o mediante una definición recursiva. Por ejemplo: \begin{verbatim} PADRE ( juan, raquel ). PADRE ( luis, jorge ). PADRE ( juan, mariana ). PADRE ( jorge, diego ). PADRE ( jorge, noel ). PADRE ( luis, ricardo ). \end{verbatim} \noindent corresponde a una definición parcial de una relación llamada \texttt{PADRE} tal que \texttt{PADRE} está contenida en el producto cartesiano \texttt{NOMBRES}$\times$\texttt{NOMBRES}, siendo \texttt{NOMBRES} un dominio que contiene nombres de personas. En la definición presentada se conviene en que el nombre que aparece en el primer argumento corresponde al padre de la persona cuyo nombre aparece en el segundo argumento. Se podría haber convenido la otra alternativa posible. Lo que es fundamental destacar es que cualquiera\pagina{21} sea la interpretación que se elija, la misma no aparecerá en el programa, ya que en él sólo presenta los elementos sintácticos del problema, dejando la semántica a la interpretación del usuario. Esta característica se pondrá en evidencia cuando en el capítulo siguiente se considere la ejecución de un programa en lógica como una derivación sintáctica en una teoría axiomática dada. Considerando entonces el programa el ejemplo como la definición de la relación \texttt{PADRE}, es posible ahora operar con la misma, lo que corresponderá a interrogar la relación. Las operaciones que se pueden realizar son las clásicas: restricciones (subconjuntos), proyecciones sobre dominios, ambas para definir nuevas relaciones, y preguntas de pertenencia. La forma de exresar dichas operaciones se realiza en programación en lógica mediante el uso de variables (que se notarán con letras mayúsculas), las que ubicadas en alguno, o varios, de los argumentos de la relación, indicarán la proyección deseada. Así por ejemplo, si se desea conocer cuáles son los hijos de Juan, dicha información corresponde a una relación unaria, que se obtiene de la relación inicial, restringiéndola para aquellas tuplas que tengan \texttt{juan} en el primer argumento, y proyectando luego por el segundo. Eso se expresa en programación lógica de la siguiente forma: \begin{verbatim} <- PADRE ( juan, X ). \end{verbatim} \noindent a lo que un sistema que implementa la programación en lógica respopnderá: \begin{verbatim} X = raquel. X = mariana. \end{verbatim} Esta respuesta corresponde a una una nueva relación, en este caso sobre un solo dominio, y lo que se presenta es la enumeración de las tuplas de la misma. Se pudiera también estar interesado en conocer quién es el padre de Ricardo, lo que se expresará, en forma simétrica a la anterior: \pagina{22}% \begin{verbatim} <- PADRE ( Y, ricardo ). \end{verbatim} \noindent obteniéndose como respuesta: \begin{verbatim} Y = luis. \end{verbatim} De las dos preguntas presentadas aparece una de las características más importantes de la programación en lógica. Debido a su aspecto relacional, no se introducen \emph{direcciones}, en el sentido clásico de datos y resultados. Un mismo programa, como el formado por el conjunto de las definiciones de la relación \texttt{PADRE}, permite conocer de quién es padre una persona (primer argumento como dato y segundo como resultado), como quién es el padre de una persona dada (segundo argumento como dato y primero como resultado). En la programación tradicional un cambio de dirección dato-resultado implicaría la reformulación del programa. Este aspecto de la reversibilidad de la programación en lógica, será presentado con más detalle en el capítulo~\ref{cha:interpretacionalgoritmica}. Puede observarse de los ejemplos vistos, que en cada interrogación, u operación, de la relación inicial, la presencia de constantes como argumentos indica una restricción de la relación, y la presencia de variables expresa el interés de realizar alguna proyección. Generalizando entonces, tenemos que: \begin{verbatim} <- PADRE ( luis, jorge ). \end{verbatim} \noindent corresponde a una restricción que da como resultado una sola tupla (en este caso estamos interrogando la pertenencia de la tupla en cuestión a la relación original). La pregunta: \begin{verbatim} <- PADRE ( X, Y ). \end{verbatim} \noindent corresponde a la proyección de la relación en todos sus dominios (en este caso el interés es en conocer todas las tuplas de la relación). Es\pagina{23} posible complementar la definición de la relación \texttt{PADRE}, con la definición de una nueva relación: \begin{verbatim} MADRE ( raquel, diego ). MADRE ( lucia, mariana ). MADRE ( raquel, noel ). MADRE ( carmen, ricardo ). MADRE ( carmen, jorge ). MADRE ( lucia, raquel ). MADRE ( mariana, alejandra ). MADRE ( mariana, german ). \end{verbatim} Las variables, que fueron utilizadas en las interrogaciones de las relaciones, permiten a su vez la definición de nuevas relaciones, en función de relaciones existentes. Si por ejemplo se desea definir la relación \texttt{ABUELO\_PATERNO}, en función de las relaciones presentadas, se puede escribir: \begin{verbatim} ABUELO_PATERNO(X,Y) <- PADRE(X,Z), PADRE(Z,Y). \end{verbatim} Esta cláusula puede leerse de la forma siguiente: \begin{quote} «una persona \texttt{X} es el abuelo paterno de una persona \texttt{Y}, si existe una tercera persona \texttt{Z} tal que \texttt{X} es el padre de esa \texttt{Z}, y esa misma persona \texttt{Z} es el padre de \texttt{Y}.» \end{quote} La nueva relación \texttt{ABUELO\_PATERNO}, puede ahora ser operada (o interrogada) como las relaciones definidas por extensión. De esta manera la pregunta: \begin{verbatim} <- ABUELO_PATERNO ( W, diego ). \end{verbatim} \noindent generará como respuesta: \begin{verbatim} W = luis. \end{verbatim} Para\pagina{24} obtener dicho resultado el sistema debió descubrir que existe una persona Jorge tal que \texttt{PADRE(jorge,diego)} está definida, para luego determinar que \texttt{PADRE(luis,jorge)} también lo está. Ese valor de \texttt{luis} es el que resuelve el problema, y por ello el sistema lo escribe como resultado. Es de hacer notar que las variables que aparecen en cada cláusula sólo tienen validez en la misma cláusula, es decir, utilizando nociones de los lenguajes de programación imperativa, que el alcance de una variable es la cláusula donde aparece. Es por ello que la \texttt{W} de la pregunta, se conectará con la \texttt{X} de la definición de la relación, mediante un mecanismo similar al pasaje de parámetros de los lenguajes tradicionales. Una nueva pregunta: \begin{verbatim} <- ABUELO_PATERNO ( W, R ). \end{verbatim} \noindent generará a su vez como respuesta: \begin{verbatim} W = luis, R = diego. W = luis, R = noel. \end{verbatim} Esta respuesta corresponde a la enumeración de toda la relación \texttt{ABUELO\_PATERNO}, en función de la información disponible; lógicamente que el agregado de nuevas tuplas a la relación \texttt{PADRE} inicial podrá modificar a \texttt{ABUELO\_PATERNO}. La pregunta \texttt{ABUELO\_PATERNO(W,diego)} corresponde a una restricción de la respuesta anterior. En forma similar a lo ya visto se puede definir una nuneva relación: \begin{verbatim} ABUELO_MATERNO(X,Y) <- PADRE(X,Z), MADRE(Z,Y). \end{verbatim} Un nuevo paso de generalización puede ser ahora dado. En base a las relaciones definidas hasta el presente es posible ahora incluir una nueva definición, que corresponda al concepto de abuelo en forma genérica.\pagina{25} El abuelo de una persona es el abuelo paterno o el abuelo materno. Esta situación se expresa en programación lógica de la forma siguiente: \begin{verbatim} ABUELO(X,Y) <- ABUELO_PATERNO(X,Y). ABUELO(X,Y) <- ABUELO_MATERNO(X,Y). \end{verbatim} \noindent donde al tener dos reglas para la definición de abuelo, estamos indicando que podemos utilizar una o la otra. Ante la pregunta: \begin{verbatim} <- ABUELO( X, noel ). \end{verbatim} \noindent el sistema responderá: \begin{verbatim} X = luis. X = juan. \end{verbatim} Para elaborar dicha respuesta, el sistema ha debido determinar mediante la relación \texttt{ABUELO\_PATERNO} el valor \texttt{X=luis}, y con la relación \texttt{ABUELO\_MATERNO} el valor \texttt{X=juan}. Con las herramientas ya vistas es posible continuar definiendo relaciones que correspondan a grados directos de parentesco, como por ejemplo: \begin{verbatim} HERMANO(X,Y) <- PADRE(Z,X), PADRE(Z,Y). HERMANO(X,Y) <- MADRE(Z,X), MADRE(Z,Y). TIO(X,Y) <- PADRE(Z,X), HERMANO(X,Z). TIO(X,Y) <- MADRE(Z,X), HERMANO(X,Z). PRIMO(X,Y) <- TIO(Z,X), PADRE(Z,Y). PRIMO(X,Y) <- TIO(Z,X), MADRE(Z,Y). \end{verbatim} \paragraph{Ejercicios}\pagina{26} \begin{enumerate} \item Escriba definiciones alternativas para la relación \texttt{TIO}. \item Determine porqué la relación \texttt{PRIMO} definida anteriormente no es equivalente a la siguiente: \begin{verbatim} PRIMO(X,Y) <- ABUELO(Z,X), ABUELO(Z,Y). \end{verbatim} \end{enumerate} En el trabajo con relaciones muy frecuentemente resulta necesario definir relaciones como clausuras transitivas de relaciones existentes. Por ejemplo, y siguiendo con las relaciones familiares que hemos planteado, puede interesar definir la relación \texttt{ANCESTRO}, que correspondería a la clausura de las relaciones \texttt{PADRE} y \texttt{MADRE} ya presentadas. La forma de escribirla sería la siguiente: \begin{verbatim} ANCESTRO(X,Y) <- PADRE(X,Y). ANCESTRO(X,Y) <- MADRE(X,Y). ANCESTRO(X,Y) <- PADRE(Z,Y), ANCESTRO(X,Z). ANCESTRO(X,Y) <- MADRE(Z,Y), ANCESTRO(X,Z). \end{verbatim} \noindent donde la tercera regla puede leerse como: \begin{quote} «una persona \texttt{X} es el ancestro de una persona \texttt{Y}, si existe una persona \texttt{Z}, tal que \texttt{Z} es el padre de \texttt{Y} y además \texttt{X} es ancestro de ese mismo \texttt{Z}» \end{quote} Puede observarse que de la descripción escrita en castellano en la frase anterior puede inducirse rápidamente la regla en programación en lógica correspondiente. Esto constituye otra de las características relevantes de la programación en lógica, que consiste en el alto nivel de expresión que ofrece. En general es posible \textit{pasar} con cierta facilidad de la especificación de un problema expresada en lenguaje natural, a una desscripción en programación en lógica. La\pagina{27} novedad que aparece en la definición anterior surge de la utilización de la recursión en la definición de la relación, lo que resulta totalmente natural al recordar que estamos definiendo una cláusula transitiva. La relación \texttt{ANCESTRO} definida puede ser operada en forma totalmente similar a las otras relaciones. Así por ejemplo si escribimos: \begin{verbatim} <- ANCESTRO( X, diego ). \end{verbatim} \noindent el sistema responderá: \begin{verbatim} X = luis. X = carmen. X = juan. X = lucia. \end{verbatim} \paragraph{Ejercicios} \begin{enumerate} \item Demuestre que la relación \texttt{ANCESTRO} definida, es equivalente a la siguiente: \begin{verbatim} ANCESTRO(X,Y) <- PADRE(X,Y). ANCESTRO(X,Y) <- MADRE(X,Y). ANCESTRO(X,Y) <- PADRE(X,Z), ANCESTRO(Z,Y). ANCESTRO(X,Y) <- MADRE(X,Z), ANCESTRO(Z,Y). \end{verbatim} \item ¿De qué manera cree usted que se manifiestan las diferencias entre la definición original de \texttt{ANCESTRO}, y la que aparece en 1.? \end{enumerate} En\pagina{28} los capítulos siguientes se presentan dos formas de interpretar el significado de los programas en lógica. Una primera visión proviene de la lógica matemática, y tiene un carácter más denotacional. La segunda introduce los aspectos operacionales que son la base de las implementaciones de programación en lógica. Una fuente de referencia para la escritura de estos capítulos la constituyó el excelente libro de Christopher John Hogger~\cite{Hog84}. % EOF cap02.tex %%% Local Variables: %%% mode: latex %%% TeX-master: "plyf" %%% End: