% cap04.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: cap04.tex,v 1.1 2003/08/13 04:00:43 cballard Exp $ % \chapter{Interpretación algorítmica} \label{cha:interpretacionalgoritmica} % -------------------------------------------------------- \begin{abstract}\pagina{57} \label{sec:intalgresumen} La interpretación algorítmica de la programación en lógica, induce una semántica operacional, que sirve de base a las implementaciones existentes. Un programa en lógica se interpreta como un conjunto de definiciones de procedimientos. Sin embargo el modelo de activación y ejecución de los procedimientos aquí presentados, no corresponde al tradicional de los lenguajes imperativos. Por un lado los parámetros servirán para determinar cuál procedimiento activar. La ejecución corresponderá al recorrido de un espacio de computaciones posibles, ya que el modelo general de evaluación será no determinista. En este capítulo se analizarán todos estos aspectos y se culminará presentando las estrategias usuales de evaluación. \end{abstract} En\pagina{58} el capítulo anterior se presentó una interpretación lógica que permite entender el significado de los programas en lógica. Un programa representa la definición axiomática de una teoría formal, y una invocación a la ejecución del mismo se interpreta como una fórmula a ser demostrada como válida en dicha teoría. Dicha demostración se puede realizar mediante los mecanismos de derivación sintáctica, utilizando reglas de derivación que sean completas. En particular se presentó la regla de resolución de Robinson, que cumple con dicha propiedad, y se culminó el capítulo con un modelo para la aplicación de un paso inferencial. Sin embargo queda sin explicar una estrategia general de la prueba, que contemple los casos de imposibilidad de unificación, así como la selección de predicados y reglas del programa. En definitiva, es necesario definir un control global que especifique en cada punto de decisión cuál es el camino a seguir. La componente de control es una de las características más claras de la programación imperativa tradicional. La semántica operacional de los lenguajes de programación clásicos se basan en una máquina de estados, y cada constructor se define en términos de de la transición de estados que la ejecución del mismo produce. La evolución de la máquina de estados es la base del concepto de algoritmo. La dificultad que surge para utilizar el mismo enfoque en la programación en lógica proviene de que la máquina que naturalmente se necesitaría, sería no determinística, en el sentido en que se aplica en teoría de autómatas. La ejecución de un programa en lógica implica la existencia de una derivación sintáctica. El problema que se presenta es cómo hallar dicha derivación. De la metodología presentada en el capítulo anterior, surge que en el proceso de la prueba existen varios puntos donde es necesario realizar una decisión. En los ejemplos presentados las elecciones de objetivos y reglas se han hecho escogiendo la \emph{buena} alternativa. No se planteó, sin embargo, qué hacer en caso contrario. Lo que está faltando, entonces, es definir una componente de \emph{control} a la programación en lógica, que determine cómo proceder para\pagina{59} la ejecución total de un programa. Para expresar una visión de la programación que se fue imponiendo hace unos años, Wirth escribió un libro con un título muy sugestivo: \begin{center} Algoritmos + Estructuras de datos = Programas \end{center} \noindent donde se pretende poner en evidencia que un programa se obtiene a partir de la información estructurada a través del concepto de \emph{tipo} (que constituye una componente estática), combinada con un algortimo, donde aparece el control. Kowalski\cite{Kow79} por su parte escribió un artículo cuyo título, emulando al de Wirth, fue: \begin{center} Algoritmos = Lógica + Control \end{center} En este caso la componente estática proviene de la lógica, y si a ella se le agrega un mecanismo de control, entonces se obtienen los algoritmos. Es de hacer notar que en la parte que representa la lógica en la ecuación se incluyen tanto los datos como la especificación del problema a resolver. Este elemento es el que le da el carácter denotacional a la programación en lógica, y utilizando una terminología que ya ha sido presentada, es posible reformular la ecuación de Kowalski escribiendo: \begin{center} Algoritmos = \emph{Qué} + \emph{Cómo} \end{center} La interpretación algorítmica que se verá en este capítulo se concentrará en cómo iintroducir una componente de control a la programación en lógica. En esta interpretación los programas serán considerados como definiciones de \emph{procedimientos}, y la ejecución de los mismos se realizará siguiendo el modelo de invocación a rutinas de un lenguaje a la Pascal. Es por dicha razón que a la interpretación que aquí se llama algorítmica, se la llama también procedimental, que pretende ser una adaptación al castellano de la palabra inglesa «\eningles{\emph{procedural}}». El\pagina{60} auge actual de la programación en lógica, se inicia con los trabajos de A.~Colmerauer y Ph.~Roussel en la Universidad de Aix-Marsella II. Ellos crearon en 1973 el lenguaje PROLOG, inicialmente concebido para el tratamiento del lenguaje natural\cite{Col73}. El nombre PROLOG proviene de \emph{PROGgrammation en LOGique}, y una primera presentación del mismo apareció en\cite{Rou75}. Luego de implementaciones internas realizadas por Ph.~Roussel, el primer intérprete que tuvo difusión fue escrito por Battani y Meloni\cite{Bat73}. Dicho intérprete fue escrito en lenguaje FORTRAN, y ese hecho facilitó su instalación en diversas universidades y centros de investigación; ¿quién no disponía de un compilador FORTRAN en aquella época? (¡y aún hoy día!). Enormes paquetes de tarjetas perforadas con el intérprete se trasladaron por Europa, llegando a Inglaterra, Escocia, Hungría, Portugal, entre otros países. En~1976, uno de los autores de este trabajo, J.~Vidart, consiguió una copia que instaló en la Universidad Simón Bolívar, en Venezuela. Se formó así el primer grupo en Latinoamérica trabajando en PROLOG, y ese grupo se reforzó con la presencia durante cuatro años de Ph.~Roussel. PROLOG fue durante bastante tiempo un lenguaje de investigación, considerado por muchos como un juguete académico. Su utilización estaba poco generalizada, e incluso era muy poco conocido en los Estado Unidos de Norteamérica, donde se pensaba que para las aplicaciones de Inteligencia Artificial alcanzaba con el lenguaje LISP. Sin embargo, se habían producido avances muy importantes en la implementación de PROLOG, y el excelente trabajo de Warren\cite{War79} constituyó un aporte de capital importancia, al abandonar el terreno de los prototipos y disponer de eficiencia en el trabajo con el lenguaje. A nivel de la divulgación de PROLOG, el libro de Clocksin y Mellish\cite{Clo81} significó a su vez, un aporte relevante. No fue, sin embargo, hasta la aparición del proyecto de 5.ª generación de computadoras anunciado por el Japón, que PROLOG adquirió relevancia internacional, y pasó a ocupar el primer plano de la investigación y desarrollo de lenguajes para la inteligencia artificial. El proyecto japonés representó un verdadero impacto en el desarrollo de la\pagina{61} inteligencia artificial, y de la informática en general, tal vez no tanto por los objetivos planteados, sino por el cambio que manifestaba en la priorización de las herramientas informáticas. La programación de los años~\'{}90 sería simbólica y no numérica: las nuevas máquinas deben ser capaces de inferir, más que de calcular; la capacidad de esas máquinas se deberá medir en~LIPS (\emph{\eningles{logical inferences per second}}) y no en MIPS como actualmente. Desde el punto de vista de diseño, la máquina a que apunta el proyecto, tendría como lenguaje de máquina a alguna versión de PROLOG. A partir del anuncio japonés, PROLOG tuvo un desarrollo impresionante. Se multiplicaron las implementaciones, y aparecieron compiladores muy eficientes. Las desventajas iniciales respecto a las implementaciones de lenguajes como LISP, se han ido reduciendo, y actualmente la decisión de elegir entre PROLOG y LISP para una aplicación de inteligencia artificial, no pasa necesariamente por la eficiencia de los programas que se construyen. No sólo se han desarrollado implementaciones para máquinas de tamaño importante, sino que existen múltiples versiones para micro computadores. La aparición del TURBO-PROLOG (MR) de Borland a un precio muy accesible, contribuyó a la difución masiva del lenguaje, si bien introduce algunas modificaciones a lo que puede llamarse el PROLOG tradicional. No solamente el desarrollo consistió en implementaciones cada vez más eficientes, sino que además se ha ido generando una serie de lenguajes derivados del PROLOG inicial, donde se ha ido incorporando mejoras. Esencialmente las modificaciones conciernen a las primitivas de control, y a mecanismos de modularización para facilitar la construcción de sistemas de tamaño importante. Para poder utilizar alguna versión de PROLOG como lenguaje de base para el proyecto de 5.ª generación, resultaba imprescindible disponer de primitivas explícitas para el manejo de la concurrencia. Los lenguajes Concurrent PROLOG y GHC (\emph{\eningles{Guarded Horn Clauses}}) proveen mecanismos para expresar que ciertas operaciones pueden ejecutarse en paralelo. % -------------------------------------------------------- \section{Procedimientos y programación en lógica} \label{sec:procedimientosyprogramacionlogica} La\pagina{62} interpretación algorítmica de la programación en lógica se basa en el concepto de procedimiento de los lenguajes imperativos tradicionales. Un programa será la definición de un conjunto de procedimientos, y una invocación de ejecución será precisamente la invocación de un procedimiento. El control general corresponderá, entonces, a la ejecución de procedimientos, que serán activados mediante una invocación, y que al terminar devolverán el control al procedimiento invocante. El pasaje de parámetros adquirirá un papel más importante que en el sentido tradicional, ya que de la adecuación de los parámetros reales y formales (que es lo que corresponde al concepto de unificación ya visto) dependerá si un cierto procedimiento es susceptible de ser invocado o no. La diferencia esencial entre el concepto de procedimientos que serán presentados en lo que sigue, y el símil de los lenguajes imperativos, radica en el aspecto no determinístico de la programación en lógica. En un lenguaje como Pascal, el orden en que se van a ejecutar las instrucciones del programa está dado explícitamente por el usuario. Una invocación a un procedimiento implica que cuando deba ejecutarse la misma, el control será transferido al procedimiento, que se identifica sin ambigüedades en la misma invocación. En cambio en programación en lógica, una invocación puede provocar la activación de más de un procedimiento. Cada uno de ellos implica un camino de ejecución posible. Habiendo tomado una decisión de cuál camino escoger es posible que el camino seleccionado no produzca una solución, en el sentido del fracaso del proceso inferencial que se vio en el capítulo anterior. Dicho problema no implica que no exista una solución en los otros caminos que fueron descartados, por lo que se hace necesario volver al punto de decisión y escoger otra alternativa. Por otro lado, podría suceder que se obtenga una solución en la primera decisión, pero al estar evaluando relaciones, es posible que existan más soluciones por los otros caminos. También en este caso es necesario volver al punto de decisión y explorar todas las alternativas posibles. Las implementaciones de programación en lógica deben contemplar las alternativas expuestas\pagina{63}, y utilizan el mecanismo de \emph{backtracking} para resolverlo. % -------------------------------------------------------- \section{Definición de procedimientos} \label{sec:definicionprocedimientos} Un programa en lógica está formado por un conjunto de reglas, o cláusulas, de acuerdo a la sintaxis vista en el capítulo anterior. Dichas reglas son de dos tipos: $$ \begin{array}{llll} A & \leftarrow & . & \mathrm{(I)} \\ A & \leftarrow & B_1, \ldots, B_m & \mathrm{(II)} \end{array} $$ Cada regla de un programa se interpretará como la definición de un procedimiento. De acuerdo a la tradición de la programación imperativa toda definición está compuesta de un encabezamiento y un cuerpo. El predicado que aparece a la izquierda del símbolo «$\leftarrow$» será el encabezamiento, y los predicados que aparecen a la derecha de dicho símbolo constituirán el cuerpo del procedimiento. Los argumentos que pueda contener el predicado del encabezamiento serán los parámetros formales. Los predicados que aparecen en el cuerpo representan invocaciones a otros procedimientos, que serán ejecutadas durante la evaluación del procedimiento. El orden en que aparecen los predicados en el cuerpo no necesariamente indica la secuencia en la que se harán las invocaciones. Si la regla es de tipo (I), entonces el procedimiento tiene cuerpo vacío, y la evaluación del mismo se reduce a un retorno de control. Si se considera nuevamente el programa para la concatenación de listas: \begin{verbatim} CONCAT ( [] , X, X ) <- . CONCAT ( [X.L], Y, [X.Z] ) <- CONCAT ( L, Y, X ). \end{verbatim} \noindent el mismo está formado por la definición de dos procedimientos. El primero tiene cuerpo vacío, mientras que el segundo al ser activado producirá una invocación recursiva. % -------------------------------------------------------- \section{Invocación de procedimientos} \label{sec:invocacionprocedimientos} Tal\pagina{64} como se planteó en la sintaxis una invocación de ejecución de un programa tendrá la forma: \begin{verbatim} <- A. \end{verbatim} En la interpretación algorítmica dicha cláusula representa una invocación de procedimiento. Un requerimiento de evaluación del programa del ejemplo sería: \begin{verbatim} <- CONCAT ( [a.[]] , [b.[]] , Z ). \end{verbatim} La semántica de la activación de un procedimiento en un lenguaje estilo ALGOL, indica que una invocación es sustituída por el cuerpo del procedimiento, luego de haber realizado la transferencia de parámetros. En el caso de la programación en lógica el proceso es similar, salvo en lo que concierne a los parámetros. Éstos, debido al proceso de unificación visto en el capítulo anterior, forman parte del mecanismo de selección del procedimiento a activar. Aún cuando haya coincidencia de nombres entre el predicado de la invocación y el de la cabeza de una definición, si no existe unificación de argumentos, entonces el procedimiento es descartado. En caso que la unificación tenga éxito, se procede al reemplazo del predicado de la invocación por el cuerpo del predicado, y se aplica dicho unificador al conjunto de predicados que representan invocaciones pendientes. \paragraph{Ejemplo} Sea el programa: \begin{verbatim} P <- R, S, T. (1) R <- M, N. (2) S <- M. (3) T <- . (4) M <- . (5) N <- . (6) \end{verbatim} \noindent y\pagina{65} la cláusula de invocación: \begin{verbatim} <- P. \end{verbatim} \noindent que representa una invocación al procedimiento \texttt{P}. A los efectos de mostrar la evaluación del programa se considerará al conjunto $Q$ que contendrá los nombres de los procedimientos a ser invocados. En la terminología de la interpretación lógica vista en el capítulo anterior, $Q$ constituye el conjunto de objetivos a ser demostrados. Inicialmente: $$ Q = \{ P \} $$ La evolución de los valores de $Q$ a lo largo de la ejecución sería: $$ \begin{array}{llll} Q & = & \{ P \} & \\ Q & = & \{ R, S, T \} & \mbox{por invocación al procedimiento (1)}\\ Q & = & \{ M, N, S, T \} & \mbox{por invocación al procedimiento (2)}\\ Q & = & \{ N, S, T \} & \mbox{por invocación al procedimiento (5)}\\ Q & = & \{ S, T \} & \mbox{por invocación al procedimiento (6)}\\ Q & = & \{ M, T \} & \mbox{por invocación al procedimiento (3)}\\ Q & = & \{ T \} & \mbox{por invocación al procedimiento (5)}\\ Q & = & \{ \, \} & \mbox{por invocación al procedimiento (4)} \end{array} $$ Al llegar a una situación donde el conjunto $Q$ sea vacío, no habrá más procedimientos para invocar, y concluye la ejecución. Ya se ha mencionado que el orden en que aparecen los predicados en el cuerpo de un procedimiento no debe significar, en principio, que con dicho orden los procedimientos serán invocados. Ello implica que al ir construyendo el conjunto $Q$ del ejemplo, en cada paso cuaquiera de los predicados que aparecen son suceptibles de ser invocados. En el caso del ejemplo, cualquiera que sea la elección en cada paso, se obtiene la finalización satisfactoria de la ejecución. Supóngase ahora que se modifica el programa anterior, agregándose la cláusula: \pagina{66}% \begin{verbatim} N <- F. (7) \end{verbatim} El programa sigue siendo válido, y la ejecución presentada continúa siendo un camino posible en la medida que al invocar el procedimiento \texttt{N} se opte por la definición (6). Sin embargo, si la decisión hubiera recaído en la definición (7), la ejecución hubiese podido continuar, pero se llegaría a un estado representado por: $$ Q = \{ F \} $$ \noindent de terminación anormal, al no disponerse de definiciones del procedimiento \texttt{F}. De lo presentado en el ejemplo puede concluirse lo siguiente: \begin{enumerate} \item Pueden existir múltiples caminos que conduzcan a una terminación exitosa de la ejecución de un programa. \item Pueden existir caminos que conduzcan a una terminación anormal de la ejecución. \end{enumerate} Además, dado un programa y una invocación, puede suceder que tanto 1. como 2. sean ciertos. Esto significa que la decisión de escoger un predicado para ser activado puede tener capital importancia para obtener una ejecución que culmine exitosamente. Habiendo presentado en forma general el problema de la invocación de procedimientos se analizará a continuación el papel que juegan las variables en la selección del procedimiento a activar. Se considera nuevamente el programa para la concatenación de listas: \begin{verbatim} CONCAT ( [ ] , X, X ) <- . (1) CONCAT ( [X.L], Y, [X.Z] ) <- CONCAT ( L, Y, X ). (2) \end{verbatim} La invocación: \begin{verbatim} CONCAT ( [a.[]], [b.[]], W ). \end{verbatim} \noindent producirá\pagina{67} una ejecución que se presenta como evolución del conjunto $Q$: $$ \begin{array}{llll} Q & = & \{ \mathtt{CONCAT([a.[]],[b.[]],W)} \}\\ Q & = & \{ \mathtt{CONCAT([],[b.[]],Z)} \} & \mbox{por proc. (2) con unif. = \texttt{W:=[a.Z]}}\\ Q & = & \{ \, \} & \mbox{por proc. (1) con unif. = \texttt{Z:=[b.[]]}} \end{array} $$ Es decir que la ejecución culmina exitosamente, y en el transcurso de la misma se han definido unificadores que van precisando el valor pedido de \texttt{W}. El resultado obtenido es: \begin{verbatim} W = [a.[b.[]]] \end{verbatim} En el desarrollo de la ejecución no han habido, en este caso, puntos de decisión. Si bien el programa tiene tiene dos procedimientos con el mismo nombre, \texttt{CONCAT}, ha sido el proceso de unificación de parámetros el que ha descartado alternativas durante la ejecución. % -------------------------------------------------------- \section{Intérprete no determinista} \label{sec:interpretenodeterminista} A partir de lo planteado en la sección anterior, puede concluirse que un programa en lógica implica un no determinismo en su evaluación, que se evidencia por los puntos de decisión que aparecen en el transcurso de una ejecución. Parece natural que para explicar el comportamiento de un evaluador de programas en lógica, se utilice un lenguaje que tenga primitivas de no determinismo. En esta sección se presentarán dichas primitivas, y se describirá una máquina no determinista como semántica operacional para describir la evaluación de programas en lógica. Sea $P$ el conjunto de procedimientos que conforman un programa. Se dispone además de las funciones: \begin{verbatim} cabeza : procedimientos -> predicados \end{verbatim} \noindent cuya\pagina{68} semántica es que dado un procedimiento devuelve el predicado del encabezamiento del mismo, y \begin{verbatim} cuerpo : procedimientos -> conjunto de predicados \end{verbatim} \noindent que devuelve los predicados del cuerpo del procedimiento que recibe como argumento. Sea $Q$ el conjunto de invocaciones de procedimientos. Inicialmente contendrá el (los) predicado(s) dado(s) por el usuario al solicitar una ejecución. Se dispone de un procedimiento: $$ \mbox{\texttt{unif ( P1, P2, éxito, }}\theta \mbox{\texttt{ )}} $$ \noindent que intenta resolver los predicados \texttt{P1} y \texttt{P2}. Si lo consigue devuelve en $\theta$ el unificador más general, y asigna el valor verdadero a \texttt{éxito}. Si la unificación no es posible, \texttt{éxito} toma el valor falso. Finalmente se tiene la función \texttt{sust}: $$ \begin{array}{l} \mbox{\texttt{sust : conjunto de predicados }} \times \mbox{\texttt{unificador -> conjunto de predicados}} \end{array} $$ \noindent cuya función es aplicar el unificador al conjunto de predicados y devolver el conjunto así obtenido. El constructor no determinista que se usará es: \begin{verbatim} elegir : conjunto => elemento del conjunto \end{verbatim} \noindent y cuya función es escoger arbitrariamente un elemento de un conjunto. Se utiliza el símbolo «\texttt{=>}» para expresar el no determinismo de la «función». Una forma de entender el comportamiento de \texttt{elegir} es escribir su significado mediante primitivas más básicas de no determinismo. Supóngase que a los conjuntos los representamos como sucesiones, y se dispone\pagina{69} del constructor de programas «\texttt{O}». Si \texttt{P1} y \texttt{P2} son dos programas, entonces \texttt{P1 O P2} es un nuevo programa cuya ejecución será la ejecución de \texttt{P1}, o la ejecución de \texttt{P2}, siendo la decisión entre ambas alternativas arbitraria. Con estos elementos se puede definir la función \texttt{elegir}: \begin{verbatim} elegir ( sucesión ) := si la sucesión tiene un solo elemento entonces devolver ese elemento sino ( devolver primer elemento de la sucesión O elegir ( sucesión sin el primer elemento ) ) \end{verbatim} Con todo lo definido, es posible presentar la máquina no determinista para la evaluación de programas en lógica. \paragraph{Máquina no determinista}\revisar{sustituir los @ por $\theta$} \begin{verbatim} sea Q un conjunto de predicados, P un conjunto de procedimientos; sea q un predicado, p un procedimiento, éxito un lógico, @ una sustitución; comienzo Q := { predicado dado por el usuario }; mientras Q no sea vacío hacer q := elegir(Q); p := elegir(P); unif( cabeza(p), q, éxito, @ ); si éxito entonces Q := sust( Q-q+cuerpo(p), @ ); fin fin \end{verbatim} % -------------------------------------------------------- \section{Estrategias de evaluación} \label{sec:estrategiasevaluacion} Una\pagina{70} descripción no determinista como la presentada, representa una especificación formal de la evaluación de programas en lógica, interpretada como invocaciones de procedimientos. Cada punto de no determinismo de la descripción determina un conjunto de posibles caminos de computación. Una implementación de programación en lógica, que será necesariamente determinista, deberá recorrer cada uno de esos caminos, y realizar las evaluaciones corresspondientes. De esta forma se podrá encontrar la o las soluciones a la invocación del programa. El siguiente ejemplo, extraído de\cite{Hog84} ilustra lo anterior. Sea el programa: \begin{verbatim} CONSEC ( X, Y, [X.[Y.Z]] ) <- . (1) CONSEC ( X, Y, [W.Z] ) <- CONSEC ( X, Y, Z ). (2) \end{verbatim} El primero y el segundo de los argumentos, son elementos que deben ser consecutivos en la lista que aparece en el tercero. Como se trata de listas se puede utilizar la notación para las mismas que ya fue presentada y cuya estructura [1.[2.[5.[]]]] se escribe (1 2 5). Sea la invocación: \begin{verbatim} <- CONSEC ( 2, Z, (2 3 2 4) ). \end{verbatim} En este caso la invocación puede activar tanto el procedimiento (1) como el (2). Si se escoge el primero, se inicia una computación que culmina con un resultado de: \begin{verbatim} Z := 3 \end{verbatim} Si por el contrario la decisión hubiera recaído en el procedimiento (2), entonces otra computación se hubiera realizado y el nuevo conjunto de objetivos sería: \pagina{71}% $$ Q = \{ \mbox{\texttt{CONSEC ( 2, Z, (3 2 4) )}} \} $$ Sólo el procedimiento (2) satisface este objetivo, por lo que se obtiene: $$ Q = \{ \mbox{\texttt{CONSEC ( 2, Z, (2 4) )}} \} $$ Se presenta una nueva disyuntiva ya que ambos procedimientos pueden ser activados. Si se opta por el (1), la computación finaliza satisfactoriamente dando como resultado: \begin{verbatim} Z := 4 \end{verbatim} En cambio si se escoge el procedimiento (2), la computación sería: $$ \begin{array}{lll} Q & = & \{ \mbox{\texttt{CONSEC ( 2, Z, (4) )}} \}\\ Q & = & \{ \mbox{\texttt{CONSEC ( 2, Z, () )}} \} \end{array} $$ El último predicado no representa ninguna invocación posible. La misma no puede ser satisfecha por los procedimientos del programa. Se ha llegado a una situación de terminación no satisfactoria sin resultados: \begin{verbatim} [ ] \end{verbatim} En el ejemplo se evidencian los distintos caminos de computación posibles, y la forma en que pueden obtenerse las diferentes soluciones de la ejecución de un programa. Al conjunto de todos los caminos de evaluación se le llama espacio de computación. Un intérprete de programas en lógica debe considerar dicho espacio, y recorrerlo mediante una estrategia definida. Una forma de representar ese espacio es mediante un árbol cuyos nodos son los valores del conjunto $Q$ de invocaciones a ser ejecutadas. Los descendientes de un nodo representan las distintas alternativas de evaluación del mismo. Las hojas del árbol que correspondan al valor \emph{vacío} para $Q$ significarán una culminación exitosa de una evaluación, y\pagina{72} se representarán por «\texttt{[ ]}». En caso que se termine sin posibilidad de resolver una invocación, o sea en la culminación insatisfactoria, se denotará con«\texttt{[X]}». Si se considera el ejemplo anterior y la invocación considerada, el espacio de computación puede representarse de la siguiente manera: \begin{verbatim} * CONSEC(2, Z, (2 3 2 4)) / \ / \ [ ] * CONSEC(2, Z, (3 2 4)) | | * CONSEC(2, Z, (2 4)) / \ / \ [ ] * CONSEC(2, Z, (4)) | | * CONSEC(2, Z, ()) | | [X] \end{verbatim} Todas las computaciones que han sido presentadas son finitas en el sentido que culminan, satisfactoriamente o no. Pueden existir, sin embargo, casos de caminos de computación infinitos, como sería el caso si al programa del ejemplo se lo invocara con: \begin{verbatim} <- CONSEC ( 1, 2, Z ). \end{verbatim} Un espacio con computaciones infinitas implica un árbol de profundidad infinita. En\pagina{73} el ejemplo presentado cada nodo contenía un solo predicado. Sin embargo, en el caso general pueden ser más de uno, y entonces la decisión a tomar no es solamente cuál procedimiento activar, sino también cuál invocación elegir. Este hecho no hace sino poner en evidencia los dos puntos de no determinismo de la máquina presentada en la sección anterior. Un intérprete de programación en lógica tendrá definido internamente el orden en que irá recorriendo el espacio de computación, es decir el orden en que irá escogiendo invocaciones y procedimientos. Esto implica que una vez escogido un camino, será necesario retornar al punto de la decisión para buscar una nueva alternativa. Cabe señalar que todos los caminos deben ser iniciados con el mismo estado de las variables. El retorno no solamente necesita de un posicionamiento de control en el punto de decisión, sino que además se deben restaurar los valores que tenían las variables al iniciar la alternativa anterior. Al mecanismo para realizar tal proceso se le denomina \emph{\eningles{backtracking}}. Las implementaciones de PROLOG y de sus lenguajes derivados poseen una estrategia generalmente aceptada de decisión, que se basa en el orden establecido por el usuario al escribir sus programas. \paragraph{Elección de invocaciones.} Se considera al conjunto $Q$ de invocaciones como una secuencia y el mecanismo de elección implica el recorrido de la misma. Esta estrategia produce un tipo de recorrido del árbol que se conoce como \emph{\eningles{depth first}} (primero en profundidad). En cada nodo se analiza primero, totalmente, el subárbol engendrado por un descendiente antes de considerar a los hermanos del mismo. En conocimiento de este ordenamiento, el usuario puede guiar la evaluación de sus programas, determinando el orden con que escribe los predicados en el cuerpo de los procedimientos. \paragraph{Elección de procedimientos.}\pagina{74} Se utiliza el orden en que el usuario escribió las definiciones de procedimientos. En este sentido se sigue la tradición de los lenguajes imperativos. Bajo esta estrategia la evaluación del programa \texttt{CONSEC}, visto anteriormente, recorrería el árbol de izquierda a derecha, y las soluciones se las daría al usuario en el orden \texttt{Z := 3} y \texttt{Z := 4}. Si en cambio se intercambiaran las definiciones de los procedimientos, la misma invocación produciría un recorrido del mismo árbol de derecha a izquierda, encontrando primero la culminación insatisfactoria para luego dar las soluciones en el orden \texttt{Z := 4} y \texttt{Z := 3}. Con el objeto de ofrecer al usuario la posibilidad de alterar el árbol del espacio de computación, y así obtener mayor eficiencia en la ejecución de sus programas, el lenguaje PROLOG dispone de un operador de control explícito. Normalmente se le escribee con el símbolo «\texttt{/}» y se le denomina \textbf{cut}. Sintácticamente cumple la función de un predicado sin parámetros que sólo puede aparecer en el cuerpo de un predicado. Su función es \emph{podar} el árbol de computación, eliminando todas las alternativas pendientes desde que el procedimiento que contiene al «\texttt{/}» fue invocado. Si la primera regla del programa \texttt{CONSEC} se escribiera: \begin{verbatim} CONSEC ( X, Y, [X.[Y.Z]] ) <- / . \end{verbatim} \noindent la ejecución terminaría luego de encontrar la solución \texttt{Z := 3}. El operador «\texttt{/}» no tiene interpretación lógica y su explicación algorítmica no es simple. Es por ello que a su utilización en programación lógica se la compara con el uso del \texttt{GO TO} en la programación tradicional. Es indudable que permite construir programas más eficientes (como el \texttt{GO TO}), pero oscurece la comprensión de los programas y es fuente de errores durante la modificación de los mismos. % -------------------------------------------------------- \section{Tratamiento de la negación} \label{sec:tratamientonegacion} Durante\pagina{75} el diseño de un programa en lógica, algunas veces resulta necesario expresar la negación de algunos hechos. A pesar de que la negación existe en la lógica tradicional, ella no aparece en la programación en lógica. Esta carencia puede ser remediada de diferentes formas. Dado un predicado \texttt{P} puede definierse un nuevo predicado, llamado por ejemplo \texttt{NO\_P}, el que deberá ser verdadero cada vez que \texttt{P} sea falso. Para construir el nuevo predicado se utilizarán predicados predefinidos del sistema, que expresan la negación a un nivel básico, como por ejemplo la desigualdad de átomos. Otra alternativa surge de la utilización del operador «\texttt{/}» interpretando un fallo para derivar un predicado, como la negación del mismo. Así por ejemplo, si se desea definir un predicado para negar a \texttt{P}, y se dispone de un predicado predefinido \texttt{FAIL} que fracasa siempre, se puede escribir: \begin{verbatim} NO_P <- P , / , FAIL. NO_P <- . \end{verbatim} Si la activación de \texttt{P} tiene éxito, entonces se \emph{atraviesa} el operador «\texttt{/}», y la invocación a \texttt{FAIL} produce un fallo de \texttt{NO\_P}. Por eel contrario, si la activación de \texttt{P} falla, entonces se activa el segundo procedimiento, que es una aserción, y \texttt{NO\_P} tiene éxito. Este mecanismo, si bien puede ser de utilidad, no representa la implementación general de la negación. Si los predicados tienen variables, el fracaso de \texttt{NO\_P} en el primer caso se produce para una cierta instanciación de las variables, mientras que el éxito de \texttt{NO\_P} resultante de utilizar el segundo procedimiento, se obtiene para cualquier valor de las mismas. Con\pagina{76} el objeto de clarificar el uso de la negación, ciertos lenguajes como IC-PROLOG, proveen la facilidad de un operaador de \emph{cuasi-negación} que se implementa interpretando la negación como un fallo, de acuerdo a la llamada asunción del mundo cerrado. % -------------------------------------------------------- \section*{Problemas} \label{sec:intalgproblemas} \begin{enumerate} \item Evaluar \texttt{PREFIX([a,b,c], X)} con el programa construído para el problema 3.2\revisar{referencia al problema}. \item Definir un predicado \texttt{HANOI(N, A, B, C, Movim)} que resuelva el problema de las torres de Hanoi, con \texttt{N} discos, pasándolos de \texttt{A} a \texttt{B} usando \texttt{C} como auxiliar y siendo \texttt{Movim} la secuencia de movimientos realizada. \item Escribir un programa para resolver el siguiente \emph{rompecabezas lógico}: \begin{itemize} \item Hay cinco casas, habitadas por hombres de diferentes nacionalidades, con diferentes mascotas, que suelen tomar diferentes bebidas y fuman distintas marcas de cigarrillos. \item El inglés vive en la casa roja. \item El español es dueño del perro. \item En la casa verde se toma café. \item El ucraniano toma té. \item La casa verde está a la derecha de la casa marfil. \item El que fuma Winston tiene ardillas. \item En la casa amarilla se fuma Camel. \item En la casa del medio se toma leche. \item El noruego vive en la casa que está más a la izquierda. \item El que fuma Chesterfield vive en la casa de al lado del dueño del zorro. \item Al lado de donde está el caballo se fuma Camel. \item El que fuma Lucky Strike toma jugo de naranja. \item El japonés fuma Parliament. \item El noruego vive al lado de la casa azul. \end{itemize} ¿Quién\pagina{77} es dueño de la cebra? ¿Quién toma agua? \item Escribir un programa lógico para resolver el problema de las \emph{ocho reinas}. Esto es determinar las formas en que pueden colocarse ocho reinas en un tablero de ajedrez de modo que no se amenacen mutuamente. \item Escribir un programa en lógica para resolver el siguiente problema. Tres misioneros y tres caníbales están en la orilla izquierda de un río. Hay un bote para cruzar el río, con capacidad a lo sumo para dos personas. Todos deben cruzar el río. Si en algún momento en alguna orilla quedan más misioneros que caníbales, éstos serán convertidos por aquellos. Encontrar modos de transportar los misioneros y caníbales a través del río sin exponer ningún caníbal al peligro de la conversión. \end{enumerate} % EOF cap04.tex %%% Local Variables: %%% mode: latex %%% TeX-master: "plyf" %%% End: