% -*- coding: iso-8859-1-unix; -*- % cap06.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$ % \chapter{Lenguajes funcionales} \label{cha:lenguajesfuncionales} % -------------------------------------------------------- \begin{abstract}\pagina{97} La idea central del capítulo es desarrollar, a partir del lenguaje usado en el caso de estudio, una estructura sintáctica y una interpretación informal de los lenguajes funcionales, identificando las facilidades de modularización que proveen. Se presta especial atención a aquellas que no existen en los tradicionales lenguajes imperativos, (en particular, el concepto de función de orden superior), señalándose que constituyen la principal diferencia entre ambos esquemas y, por lo tanto, un aporte relevante del paradigma funcional al desarrollo de los lenguajes de programación. En este análisis se siguen ideas de~\cite{bac78}, \cite{hug84} y \cite{abe85}. \end{abstract} % -------------------------------------------------------- \section{La estructura de los lenguajes funcionales} \label{sec:estructuralenguajesfuncionales} Véase\pagina{98} la expresión que define la función \texttt{dimension}: \begin{verbatim} dimension :- (f, datom) if Atómica?(f) then datom(f) else if Suma-o-Resta?(f) then DimAd( dimension( PrimerOperando(f), datom ), dimension( SegundoOperando(f), datom ) ) else if Producto?(f) then DimProd( dimension( PrimerOperando(f), datom ), dimension( SegundoOperando(f), datom ) ) else DimCoc( dimension( PrimerOperando(f), datom ), dimension( SegundoOperando(f), datom ) ) \end{verbatim} Interesa examinar la forma de las expresiones que ocurren a la derecha del símbolo \texttt{:-}. Véase que: \begin{itemize} \item La expresión principal denota la definición de una función y tiene la siguiente estructura: \begin{verbatim} ( "variable", "variable", ... , "variable" ) "expresión" \end{verbatim} \noindent donde las variables son los argumentos nominales y la expresión definen la construcción de la imagen de éstas en la función. \item Aparecen aplicaciones de funciones definidas, en el ejemplo, bajo dos formas: \begin{verbatim} "nombre" ("expresión", "expresión", ... , "expresión" ) "variable" ("expresión", "expresión", ... , "expresión" ) \end{verbatim} \noindent donde las expresiones entre paréntesis se llamarán argumentos efectivos de la aplicación y se hace notar que pueden ser, como en algunos casos del ejemplo, a su vez expresiones complejas y no necesariamente sólo variables. \end{itemize} Lo\pagina{99} anterior sugiere cierta similitud en el comportamiento de los nombres y las variables. En particular, ambos pueden denotar funciones que son aplicables a un conjunto de argumentos. Esta similitud es aún más amplia, puesto que ambos pueden denotar también resultados de aplicaciones de funciones. Esto es claro para las variables, como en el caso de \texttt{f}, que, en general denota el resultado de la aplicación de un constructor de fórmulas. Sucede lo mismo para los nombres. Aunque no hayan sido usados con ese sentido en nuestro caso de estudio, podrían darse, por ejemplo, definiciones como: \begin{verbatim} 1 :- sucesor(cero) 2 :- sucesor(sucesor(cero)) ... \end{verbatim} \noindent que asociarían la representación corriente (con dígitos) a las expresiones dadas por la definición inductiva de los naturales con los constructores \texttt{cero} y \texttt{sucesor}. De hecho, el uso de nombres es el mecanismo a través del cual una expresión arbitrariamente compleja puede ser referenciada sin necesidad de mostrar su estructura interna. Es, por tanto, una facilidad de abstracción en la formulación de expresiones. La diferencia entre nombre y variable reside en que éste representa una expresión sobre cuya forma no se hacen hipótesis, es decir, ". Cada nombre está asociado, por el contrario, a una expresión específica. Estas consideraciones iluminan aspectos parciales de la estructura y el sentido de las expresiones usadas (a la derecha de \texttt{:-}): \begin{itemize} \item El propósito de estas es, claramente, expresar definiciones y aplicaciones de funciones. \item Dos casos particulares que sirven a ese objetivo ya han sido identificados. Éstos autorizan a escribir:\pagina{100} \begin{verbatim} ::= | \end{verbatim} \noindent que se lee: \emph{expresión} es una \emph{variable} o bien un \emph{nombre}. \end{itemize} A partir de estas expresiones primitivas pueden formarse otras más complejas, que, como éstas, se interpretan como definiciones y aplicaciones de funciones. La definición del conjunto de estas expresiones, se completa usando inducción de una manera informal: \begin{verbatim} ::= | | ( ,..., ) | ( ,..., ) \end{verbatim} Se definen expresiones atómicas (\emph{variables} y \emph{nombres}) y otras compuestas que se llamarán \emph{abstracciones funcionales} y \emph{aplicaciones}. Nótese que la denominación \emph{abstracción funcional} se asocia a las expresiones que definen funciones. Esto no esun mero refinamiento de la terminología. Efectivamente, considérese una expresión sencilla como: \begin{verbatim} 4 + 2 \end{verbatim} Usando la abstracción funcional puede construirse una expresión de la cual la anterior sea un \emph{caso particular}, haciendo, por ejemplo: \begin{verbatim} (x) 4 + x \end{verbatim} La nueva expresión da una forma más general, de la cual pueden obtenerse, por aplicaciones convenientes, la expresión original además de otras. El cambio de constantes por argumentos es una técnica de generalización corriente también en la práctica de la programación. Este concepto resultará de utilidad más adelante. Es\pagina{101} interesante analizar con más cuidado la sintaxis dada, tratando de determinar el tipo de construcciones que ella autoriza. En particular, considérese el caso en que se desea definir una función. Corresponde a una expresión de la forma de \emph{abstracción funcional}: \begin{verbatim} ( , ... , ) \end{verbatim} En particular, es, obviamente, admisible que contenga un único argumento nominal, como en: \begin{verbatim} (g) \end{verbatim} Ahora \emph{} puede ser reemplazada por cualquiera de sus formas válidas. Su significado será, de acuerdo a lo dicho, denotar el correspondiente de \texttt{g} en la función que se está definiendo. Una de las posibilidades admitidas es que \emph{} sea reemplazada por otra abstracción funcional. Esto debe interpretarse como que el resultado de una función puede, a su vez, ser otra función. Por ejemplo: \begin{verbatim} (g) (x) \end{verbatim} Ahora está dicho que la imagen de \texttt{g} será una cierta función de \texttt{x}. Está por darse, todavía, la definición de esta última. En particular, \texttt{g} también puede ser considerada como una función, a su vez. Esto no es una novedad, puesto que una variable denota en principio una expresión genérica y, de hecho, así se usó \texttt{datom} en \texttt{dimensión}. Entonces puede entenderse: \begin{verbatim} (g) (x) g (g (x)) \end{verbatim} La función definida sobre \texttt{g} le hace corresponder otra función que dado otro argumento \texttt{x}, aplica \texttt{g} a éste dos veces (\emph{twice}, en inglés). Ahora\pagina{102} es posible asociar un nombre a esta función: \begin{verbatim} twice :- (g) (x).g (g (x)) \end{verbatim} \noindent y calcular la imagen en \texttt{twice} de una función conocida, por ejemplo la raíz cuadrada (\texttt{sqrt}): \begin{verbatim} twice (sqrt) :- (x) sqrt (sqrt (x)) \end{verbatim} \noindent donde aparece claro que la aplicación de \texttt{twice} a una función es otra función. Ésta puede aplicarse, a su vez, a un cierto valor, como en: \begin{verbatim} twice (sqrt) (16) \end{verbatim} \noindent cuyo resultado, salvo error u omisión, debería ser \texttt{2}. Varias conclusiones deben obtenerse: \begin{itemize} \item Los argumentos y resultados de funciones son, en general, otras funciones, las cuales pueden aplicarse, a su vez, a otros argumentos. Así ocurre con \texttt{g}, argumento de \texttt{twice}, que aparece aplicada en la expresión que define a ésta y también con \texttt{twice(g)} que, a su vez, se aplica a otro argumento numérico. El tipo de función que este lenguaje maneja es llamado \emph{"} (en inglés \emph{high order functions}) para denotar el hecho de que sus argumentos y resultados son, a la vez, funciones. \item Nótese la forma de la expresión: \begin{verbatim} twice (sqrt) (16) \end{verbatim} \noindent que denota la composición de dos aplicaciones, que deben entenderse realizadas de izquierda a derecha. La primera devuelve una función, como ya se vió, la cual es aplicada al argumento efectivo \texttt{16}. Esto es diferente, aunque similar, a: \begin{verbatim} twice (sqrt, 16) \end{verbatim} En\pagina{103} el caso, la última expresión denotaría la aplicación de \texttt{twice} a dos argumentos. Sin embargo, su definición sólo admite uno. Para hacer consistente tal aplicación, la definición de \texttt{twice} debió haber sido: \begin{verbatim} twice :- (g, x) g (g (x)) \end{verbatim} \noindent que también es válida. Esto muestra que toda función de más de un argumento puede expresarse en términos de funciones de orden superior de un argumento. La transformación es muy sencilla: % GUARDA @@@ trasnformar en una figura con \caption \begin{verbatim} ( x1, ... , xN ) (definición con N argumentos) \end{verbatim} \noindent puede reescribirse como: % GUARDA @@@ trasnformar en una figura con \caption \begin{verbatim} (x1), (x2), ... , (xN) (función de orden superior de 1 argumento) \end{verbatim} Para mayor ejemplo, la suma de enteros podría verse como: \begin{verbatim} suma :- (x) (y) x + y \end{verbatim} \noindent es decir, una función de un argumento, que asocia a éste otra función de un argumento, que, a su vez, asocia a este último su suma con el primero. Para fijar ideas, piénsese en la expresión \texttt{suma (x)} como la función que aplicada a cualquier valor, le suma a éste la cantidad \texttt{x}. \end{itemize} % @@@ dónde termina el itemize en el libro? Lo anterior permite simplificar la estructura de las expresiones del lenguaje: en la formulación de la forma general de las abstracciones funcionales y aplicaciones no es necesario denotar una cantidad indeterminada de argumentos. Apenas uno es suficiente para todos los casos: \begin{verbatim} :- | | ( ) | ( ) \end{verbatim} Estas\pagina{104} expresiones pueden interpretarse usando un único concepto: el de función. Éstas pueden aplicarse entre sí y servir para definir a otras con plena libertad. Así lo autoriza la sintaxis. El lector atento podrá argumentar que esta libertad es excesiva y posiblemente la crítica sea aceptable. En efecto, hay expresiones permitidas cuyo sentido es oscuro, si no existente. Véase por ejemplo: \begin{verbatim} 5 (8) \end{verbatim} \noindent que es un caso de aplicación donde función y argumento efectivo son nombres, pero que carece de sentido puesto que el primero no admite ser aplicado a ningún argumento, y también: \begin{verbatim} sucesor (sucesor) \end{verbatim} \noindent donde el argumento efectivo no es un natural, como debiera esperarse. El problema es importante, y constituye la principal motivación para la introducción del concepto de \emph{tipo} en los lenguajes. Por supuesto, existen lenguajes funcionales con tipos, aunque no serán tratados en este desarrollo. Como consecuencia, la formación de expresiones con sentido exigirá la aplicación de una disciplina (no formalizada) adicional a las reglas de sintaxis de los lenguajes que se definan. Sin embargo, la generalidad de la construcción de expresiones del lenguaje tiene importantes ventajas. En particular, si se reinterpreta el término \emph{función} como \emph{programa} se tendrá entonces que, en estos lenguajes, los programas pueden ser, con toda generalidad, argumentos de otros programas y pueden producir, también, otros programas como resultado. Esta caracterización es, efectivamente, adecuada y se justificará plenamente en la siguiente sección, donde quedará de manifiesto su utilidad. % -------------------------------------------------------- \section{La importancia de los lenguajes funcionales} \label{sec:importancialenguajesfuncionales} Se\pagina{105} considerará un caso en que las ideas dadas al final de la sección anterior pueden aplicarse con resultados apreciables. El caso se desarrolla en~\cite{Hug84}: Se trata del problema de realizar la suma de todos los elementos de una lista. También las listas, como las fórmulas y los lenguajes, pueden definirse inductivamente: \begin{itemize} \item Hay una lista primitiva, llamada \texttt{Vacía}. Intuitivamente, representa una lista sin elementos. \item Hay un constructor de listas, que llamaremos \texttt{Cons}. Aplicado a un elemento y una lista, devuelve otra lista. \end{itemize} Intuitivamente, si \texttt{l} es la lista: % GUARDA @@@ trasnformar en una figura \begin{verbatim} < x1, x2, ... , xN > \end{verbatim} \noindent \texttt{Cons ( x0, l )} es la lista % GUARDA @@@ trasnformar en una figura \begin{verbatim} < x0, x1, x2, ... , xN > \end{verbatim} De este modo, las listas no vacías pueden pensarse como compuestas de un elemento (su cabeza) y otra lista (su cola). Se supondrá que pueden aplicarse sobre listas las funciones: \begin{itemize} \item \texttt{Vacía?}: que denota \texttt{Verdadero} si es aplicada a la lista \texttt{Vacía}, y \texttt{Falso} en caso contrario. \item \texttt{Cabeza} y \texttt{Resto}: que son selectores para listas no vacías, devolviendo, respectivamente, cabeza y cola. \end{itemize} Ahora puede definirse la función en cuestión, siguiendo un esquema recursivo: \begin{verbatim} List_suma :- (l) if Vacía? (l) then 0 else Cabeza (l) + List_suma (Resto (l) ) \end{verbatim} \noindent es\pagina{106} decir, se define la imagen de la lista primitiva (\texttt{Vacía}) y luego se enuncia la regla para calcular la imagen de una lista compuesta en función de su cabeza y de la imagen de su cola. El esquema sería idéntico si se quisiera definir el producto de todos los objetos de la lista, en lugar de la suma. Las modificaciones a introducir se marcan en la siguiente figura: \begin{verbatim} 1 List_suma :- (l) if Vacía? (l) / then [0] <---+ else Cabeza (l) [+] List_suma (Resto (l) ) ^ | * \end{verbatim} Esto muestra un patrón recursivo, general para el tratamiento de listas, que está siendo aplicado a las partes entre corchetes.% en el original % dice "recuadradas". Con este enfoque se está sugiriendo una partición del problema que produciría un módulo de aplicación general, representando el patrón citado. Este módulo puede definirse como una función: \begin{verbatim} reduce :- (f) (b) (l) if Vacía? (l) then b else f (Cabeza (l)) (reduce (f) (b) (Resto (l))) \end{verbatim} \noindent donde se ha hecho abstracción, a partir de la expresión de \texttt{List\_suma}, de: \begin{itemize} \item la función a aplicar (representada ahora por el argumento nominal \texttt{f}) \item el resultado para el caso base de la inducción (representado ahora por \texttt{b}) \end{itemize} En\pagina{107} términos de la jerg clásica podría decirse que se ha construído un módulo que representa una \emph{forma general de tratamiento de listas} que, combinada con funciones adecuadas, construye una variedad de \emph{programas} concretos. Efectivamente, los anteriores \emph{programas} de suma y producto de elementos de una lista son ahora resultados de aplicaciones convenientes de este módulo más general: \begin{verbatim} List_suma :- reduce (+) (0) List_product :- reduce (*) (1) \end{verbatim} \noindent que, como puede verse, a partir de la definición de \texttt{reduce}, son, como antes, funciones, cada una de un argumento, que se espera represente una lista. De igual modo podrán construirse módulos similares para tratar otras clases de objetos, lo que equivale a decir que pueden definirse constructores de programas adaptados a cada aplicación particular. Para esto es básico el concepto de \emph{orden superior}, que autoriza a realizar abstracciones sobre funciones, es decir a que éstas sean representadas por variables que son argumentos de otras funciones. Esta propiedad es un atributo esencial de los lenguajes funcionales. En el caso general de los lenguajes imperativos hay, por ejemplo, una sustancial diferencia conceptual entre los programas y sus argumentos. Estos últimos (los llamados \emph{datos}) denotan direcciones de una memoria con valores asociados mientras que los programas representan una transformación de, precisamente, tal asociación entre direcciones y valores. En los lenguajes en que esta heterogeneidad de significado entre los programas y sus argumentos se mantiene estrictamente, el concepto de orden superior no puede ser incorporado: una variable que sea argumento de un programa sólo puede representar una dirección de memoria que aquel eventualmente habrá de afectar y, por lo tanto, no otro programa. Como\pagina{108} consecuencia, las formas en que los programas pueden combinarse en estos lenguajes quedan restringidas a la aplicación de un conjunto preestablecido de constructores (las estructuras de control) sobre programas fijos (ya sea referenciados por un nombre o por una estructura expresa), lo cual limita la posibilidad de desarrollar módulos de aplicación general. Las \emph{formas generales de tratamiento de objetos} como \texttt{reduce} pueden tratarse, en todo caso, como \emph{esquemas de programas}, pero tal \emph{esquema} no es un elemento del lenguaje y cada programa debe reproducir, en su construcción, la estructura del mismo. Esta concepción, debida a la semántica particular de programas y datos, es tomada del modelo de cálculo en que estos lenguajes se fundamentan que corresponde al \emph{cálculo por efecto} de los computadores Von~{}Neumann. En el esquema funcional, por el contrario, todas las expresiones denotan un valor, representando tanto el concepto de \emph{dato} como el de función o \emph{programa}. La diferencia es apenas una cuestión de interpretación: \begin{itemize} \item Lo que usualmente se llama \emph{dato} es una expresión que no admite ser aplicada a ningún argumento, es decir, está \emph{completamente evaluada}. \item Las funciones, por su parte, esperan ser aplicadas a una cierta cantidad de argumentos para ser \emph{completamente evaluadas}. \end{itemize} Según esta interpretación, no hay más diferencias entre un entero y la función \texttt{+} (de dos argumentos) que entre ésta y, por ejemplo, \texttt{List\_suma} (que admite un solo argumento). Todos son casos particulares del concepto sintáctico de expresión, interpretado como valor y los constructores de expresiones (aplicación y abstracción funcional) deberían interpretarse simplemente como operadores cuyo resultado es una expresión \emph{más evaluada} (en el caso de la aplicación) o \emph{menos evaluada} (en el de la abstracción funcional) que sus operandos. Otras consecuencias interesantes de esta uniformidad conceptual entre \emph{datos} y \emph{programas} pueden ilustrarse con otro ejemplo. Considérese\pagina{109} el problema de definir funciones para representar las operaciones clásicas sobre conjuntos: unión, intersección, pertenencia de un elemento a un conjunto. Se supondrá, además, que los conjuntos a manejar son definidos por comprensión, es decir, por una propiedad que deben cumplir sus elementos, los cuales supondremos, para fijar ideas, que son, en todos los casos, números naturales. Con esta idea, tales conjuntos pueden representarse por medio de funciones que, aplicadas a un elemento, devuelven \texttt{Verdadero} si éste tiene la propiedad que define al conjunto, y \texttt{Falso} en caso contrario. Por ejemplo, la función \begin{verbatim} Pares :- (x) (x / 2) = 0 \end{verbatim} \noindent define el conjunto de los pares, si se asume que \texttt{=} representa el predicado de igualdad en los naturales y, análogamente puede interpretarse: \begin{verbatim} Menores_que_10 :- (x) x < 10 \end{verbatim} De este modo, los \emph{datos} del problema (conjuntos) están siendo representados por funciones que pueden ser calculadas aplicándolas a argumentos (los que se llamarían \emph{programas} en la concepción tradicional) y no como estructuras localizadas en una memoria. Ahora las operaciones clásicas sobre estos conjuntos pueden recibir representaciones muy sencillas: \begin{itemize} \item La pertenencia de un elemento a un conjunto se resuelve, eimplemente, aplicando la función que representa a este último al elemento en cuestión: \begin{verbatim} Member :- (x,c) c(x) \end{verbatim} \noindent donde \texttt{c} representa un conjunto y \texttt{x} el elemento cuya pertenencia a \texttt{c} se quiere verificar. La forma de esta función se justifica, simplemente, por la representación elegida para los conjuntos. \item La\pagina{110} unión de dos conjuntos \texttt{c1} y \texttt{c2} es otro conjunto cuyos elementos se caracterizan por satisfacer la propiedad que define a \texttt{c1} o la que define a \texttt{c2}. De aquí, entonces, la definición: \begin{verbatim} Unión :- (c1, c2) (x) c1 (x) or c2 (x) \end{verbatim} \noindent donde \texttt{or} representa la disyunción lógica. Nótese que \texttt{Unión} se define como función de dos argumentos (\texttt{c1} y \texttt{c2}) \end{itemize} \faltatodavia \begin{verbatim} \end{verbatim} % EOF cap06.tex %%% Local Variables: %%% mode: latex %%% TeX-master: "plyf" %%% End: