Unidad III - 1 - Paradigma funcional - Generalidades PDF

Preview

Summary

Unidad 3 generalidades...

Description

Programación Funcional Generalidades La programación funcional es sobre todo una forma distinta de programar la solución de un problema … ¿o de describirlo? Las funciones son el aspecto fundamental de este paradigma. En lugar de usar la iteración, se usa bastante la recursión apoyada en listas. Su característica más importante es la transparencia referencial, lo que ves es lo que obtienes (WYSIWYG); no depende del “estado” de la máquina. No hay variables ni asignaciones, sino la aplicación de funciones sobre el resultado de la aplicación de funciones, donde los argumentos son datos “normales” u otras funciones. Esto contrasta mucho con los lenguajes imperativos, cuyo código es difícil razonar, ya que consiguen su objetivo como el efecto colateral de las asignaciones entre lugares de memoria. En el paradigma funcional se dan definiciones casi matemáticas, en las que hay verdaderas igualdades, porque podemos sustituir libremente un lado de la igualdad por el otro, en todo el código (razonamiento ecuacional) sin cambiar el resultado del programa. Hay muchos lenguajes con inspiración funcional, cada uno con sus peculiaridades. El propio lenguaje de programación que se usa en el entorno de cálculo científico Mathematica, se caracteriza por un notable poder expresivo, utiliza y promueve las construcciones correspondientes al paradigma funcional, multiparadigma.

sin embargo,

permite

la programación

Haskell es un lenguaje funcional multiplataforma, de código abierto desarrollado por la comunidad, con varias implementaciones que compiten ayudándose entre sí. Hay un núcleo estable del lenguaje y muchas extensiones más o menos experimentales, que si dan resultado tienden a incorporarse en las versiones siguientes. Está orientado tanto al campo académico como a su uso en aplicaciones reales, y es una plataforma ideal para la experimentación y la investigación en aspectos avanzados de la computación. Uno de sus mayores ventajas es que se comprueba en tiempo de compilación la consistencia de tipos (comprobación estática), de manera que se reducen muchísimo los errores en tiempo de ejecución (comprobación dinámica). Entonces, ocurre un fenómeno muy curioso, que es una de las razones por las que el lenguaje “gusta”, si el código compila, lo más seguro es que ¡funcione bien! En los lenguajes imperativos, por muy estricta que sea, la comprobación estática no puede verificar que el orden de las sentencias sea el correcto. En cambio, como en la programación funcional no hay orden, la verificación de consistencia de tipos estática es mucho más fuerte. Paradigmas y Lenguajes

Pag. 82

Incluso ayuda cuando has entendido mal el algoritmo, porque eso a veces conduce a que los tipos del programa sean inconsistentes. Otra característica importante es el polimorfismo, es decir, el lenguaje está diseñado para que las funciones sean capaces de admitir todos los tipos de datos y que admitan las operaciones utilizadas. Por eso, si escribimos una función de ordenación, funcionará con cualquier tipo que admita comparaciones. Es como si estuviéramos programando con “templates” del C++, con la posibilidad de tratar realmente esas funciones polimórficas, pero con un verdadero control estático de consistencia de tipos. La sintaxis está orientada a la claridad del código, lo que permite que muchos algoritmos, sino todos, se expresen de forma muy concisa. Esa tremenda concisión y elegancia a veces hace pensar (especialmente a programadores expertos en otro tipo de lenguajes) que se trata de un pseudolenguaje para jugar. Sin embargo, el hecho que un algoritmo pueda escribirse de forma engañosamente simple no significa que no haya un control muy estricto sobre él. Un código sencillo que pasa todos los test de consistencia es improbable que sea incorrecto. Un mismo concepto de programación se puede expresar de muchas formas distintas, a gusto del programador, pero casi todo internamente se transforma en “lambda cálculo” con sistema de tipos. La evaluación no estricta (lazy) es otra de sus características, esto indica que las definiciones no se evalúan si no es estrictamente necesario para obtener el resultado final. Esto permite entrar en un mundo nuevo de técnicas de programación mucho más potentes y modulares. Por supuesto, no todas son ventajas. Se sabe que no es tan rápido, en algoritmos de procesamiento intensivo de datos como en los lenguajes imperativos, sin embargo, el precio que se paga por ascender en abstracción resulta en pérdida de eficiencia, a veces bastante apreciable. Sin embargo, no siempre lo más importante es el tiempo de ejecución. En resumen, las decisiones de diseño de este lenguaje no tienen como máxima prioridad aprovechar al máximo la potencia de cálculo del computador, sino ayudar al programador a escribir correctamente algoritmos cada vez más complejos. Aunque al final no se utilice a Haskell para implementar proyectos “reales”, muchos de los conceptos utilizados, pueden ayudarnos a programar mejor en cualquier otro lenguaje.

Paradigmas y Lenguajes

Pag. 83

 - cálculo Este es un lenguaje simple llamado “lambda calculo” (C), el cual permite la descripción de las funciones matemáticas y de sus propiedades. Fue introducido por Church en los años 30 como fundamento de la matemática (funciones y lógica) y constituye un modelo formal. El principal problema del C como lenguaje funcional es la libertad para combinar términos, ya que es un lenguaje sin tipos (type–free); una forma de restringir tal libertad es “C con tipos”, introducido también por Church (1934) y Curry (1941).

El cálculo lambda es universal porque cualquier función computable puede ser expresada y evaluada a través de él. Por lo tanto, es equivalente a las máquinas de Turing. Lambda expresiones Sintaxis Muchos lenguajes funcionales son a menudo descritos como un súper C o C extendido; de hecho, los programas funcionales puros deben poder ser traducidos a esta notación. EJEMPLO La expresión en lenguaje funcional x.2 * x (Interprétese matemáticamente como f(x) = 2x) y se escribe en C así: x.* 2 x (A la derecha del punto Notación polaca inversa) y denota una función de un solo argumento tal que al objeto x le asocia el objeto * 2 x. En el ejemplo anterior se observa que: • El símbolo  sirve para denotar funciones. • El punto (.) se usa para separar el argumento (o variable instanciable) del cuerpo de la función. • En el C se utiliza notación prefija. Las expresiones como las del ejemplo (x.2 * x) se llaman –abstracciones (para simplificar, A) y son un caso particular de –expresiones (para simplificar, E) o –términos.

Paradigmas y Lenguajes

Pag. 84

Memoization No se debe confundir con la memorización. En informática, memoization es una optimización técnica que se utiliza principalmente para acelerar los programas, cuando hay llamadas a funciones, con el fin de evitar la repetición de cálculos de los resultados para entradas previamente procesadas. Memoization también se ha utilizado con otros fines (distintos a la optimización de velocidad), como lo es el análisis de algoritmos que se adapten a la ambigüedad o la recursión por la izquierda en el polinomio tiempo y espacio. Aunque están relacionados con el almacenamiento en caché, memoization se refiere a un caso concreto de esta optimización, que la distingue de las formas de almacenamiento en caché como buffer o de reemplazo de páginas. En el contexto de la lógica en la programación de lenguajes, memoization también se conoce como presentación.

Etimología El término memoization fue acuñado por Donald Michie en 1968, y deriva del latín de la palabra memorando (para recordar), y por lo tanto el significado se refiere a los resultados de una función en algo para ser recordado. Por ello, memoization podría confundirse etimológicamente con memorización, sin embargo, “memoization” tiene un significado específico en la informática.

Información general Una función memoized recuerda los resultados correspondientes a un conjunto de entradas específicas. Las llamadas posteriores con entradas recordadas devolverán el resultado, en lugar de volver a calcular, eliminando el costo principal de una llamada con parámetros dados. Una función sólo puede ser memoized si es referencialmente transparente, es decir, sólo si llamar a la función tiene exactamente el mismo efecto que sustituir a esa llamada a la función con su valor de retorno. Memoization es un medio para reducir el costo en tiempo de ejecución de una función, a cambio del costo en espacio de almacenamiento. El análisis del costo tiempo/espacio tiene un nombre específico en la informática: la complejidad computacional. Todos los algoritmos tienen asociados una complejidad computacional en el tiempo (de ejecución) y en el espacio (de almacenamiento). Considere el siguiente pseudocódigo función para calcular el factorial de n: función factorial (n) si n es 0, entonces devuelve 1 sino factorial (n-1) fin si fin de la función

Paradigmas y Lenguajes

[es un entero no negativo] [0! = 1 ]

Pag. 85

Por cada número entero n tal que n ≥ 0, el resultado final de la función factorial es invariante, si se invoca como x = factorial (3), el resultado es tal que x siempre se le asigna el valor 6. Una versión no memoized de lo anterior, dada la naturaleza recursiva del algoritmo implicado, requeriría n + 1 invocaciones de factorial para llegar a un resultado, y cada uno de estas invocaciones, a su vez, tiene un costo asociado al tiempo que tarda la función para devolver el valor calculado. Dependiendo de la máquina, este costo podría ser la suma de: 1. 2. 3. 4. 5. 6.

El costo de crear el marco funcional de la pila de llamadas. El costo para comparar n a 0. El costo que restar 1 a n. El costo de establecer el marco de la pila de llamadas recursivas. (Igual que el anterior.) El costo para multiplicar el resultado de la llamada recursiva de factorial de n. El costo para almacenar el resultado de retorno de modo que pueda ser utilizado por el contexto de llamada.

En una aplicación no memoized, cada llamada de nivel superior a factorial incluye el costo acumulativo de los pasos 2 a 6 proporcional al valor inicial de n. Una versión memoized de factorial seria siguiente: función factorial (n es un entero no negativo) si n es 0, entonces devuelve 1 else si n se encuentra en tabla de llamadas regresar búsqueda-con valores de tabla-para-n sino x = factorial (n - 1) veces n [recurrentemente invoca fact n-1] fin si n en tabla fin si n es 0 return x fin de la función

En este ejemplo en particular, si factorial primero se invoca con 5 y, a continuación, invoca después con cualquier valor menor o igual a cinco, los valores de retorno también se han memoized, desde factorial se han llamado de forma recursiva con los valores 5, 4, 3, 2, 1 y 0, y los valores de retorno de cada de aquellos que han sido almacenados. Si se llama entonces con un número mayor que 5, tal como 7, sólo 2 llamadas recursivas se harán (7 y 6), ¡y el valor de 5! se han almacenado de la llamada anterior. De esta manera, memoization permite una función a ser más eficiente en el tiempo más a menudo se la llama, lo que resulta en general eventual acelerar.

Paradigmas y Lenguajes

Pag. 86

Evaluación perezosa o no estricta (Lazy evaluation) Los lenguajes funcionales pueden ser clasificados por el hecho de usar evaluación lazy o eager, conceptos que hacen referencia a cómo los argumentos de las funciones son procesados cuando una expresión está siendo evaluada. En la teoría de los lenguajes de programación, la evaluación perezosa, o Llamar-cuandonecesites es una estrategia de evaluación, que retrasa la evaluación de una expresión hasta que ese valor sea necesitado (evaluación no estricta) y evita las evaluaciones repetidas (intercambio). En la llamada-por-nombre (Llamada a una función en programación imperativa) en ciertas funciones, el intercambio puede aumentar exponencialmente el tiempo de ejecución, respecto de estrategias de evaluación no estrictas. Los beneficios de la evaluación perezosa incluyen: 

Incremento de performance por al evitar cálculos innecesarios y condiciones de error en la evaluación de expresiones compuestas.



La capacidad de construir potencialmente infinitas estructuras de datos.



La capacidad para definir el control de flujo (estructuras de control) como abstracciones, en lugar de sentencias.

La evaluación perezosa se combina a menudo con memoization. El valor de una función se calcula para ese parámetro o conjunto de parámetros, los resultados se almacenan en una tabla de consulta indexada por los valores de dichos parámetros; la próxima vez que se invoca la función, la tabla se consulta para determinar si el resultado de esa combinación de valores de parámetros está disponible. Si es así, se devuelve el resultado almacenado, sino la función se evalúa y se añade otra entrada a la tabla de búsqueda, para su eventual reutilización. La evaluación diferida puede conducir a la reducción de uso de memoria, ya que se crean los valores solo cuando son necesarios. Sin embargo, es difícil de combinar con las características imperativas, tales como el manejo de excepciones y de entrada / salida, ya que el orden de las operaciones no está determinado y por lo tanto, la evaluación diferida puede en este sentido presentar desaprovechamiento de espacio. Lo opuesto a la evaluación perezosa es la evaluación ansiosa (eager), a veces referida como evaluación estricta. La Evaluación impaciente o ansiosa, también conocida como evaluación estricta, que es la usada generalmente por defecto en la mayoría de lenguajes de programación. La evaluación perezosa o no estricta es utilizada, por defecto, en multitud de lenguajes funcionales puros, incluidos Miranda, Clean y Haskell.

Paradigmas y Lenguajes

Pag. 87...