PDF de programación - 5.-Programación funcional

5.-PROGRAMACIÓҭ FUҭCIOҭAL.

Historia

Sus orígenes provienen del Cálculo Lambda (o λ-cálculo), una teoría matemática elaborada
por Alonzo Church como apoyo a sus estudios sobre computabilidad.

Los programas escritos en un lenguaje funcional están constituidos únicamente por
definiciones de funciones, entendiendo éstas no como subprogramas clásicos de un
lenguaje imperativo, sino como funciones puramente matemáticas, en las que se verifican
ciertas propiedades como la transparencia referencial.



Otras características propias de estos lenguajes son la no existencia de asignaciones de
variables y la falta de construcciones estructuradas como la secuencia o la iteración (lo que
obliga en la práctica a que todas las repeticiones de instrucciones se lleven a cabo por medio
de funciones recursivas).


¿Qué es la Programación Funcional?
C, Java, Pascal, Ada, etc.. son lenguajes imperativos. Son “imperativos” en el sentido de
que consisten en una secuencia de comandos que son ejecutados uno tras otro estrictamente.

Un programa funcional es una expresión simple que es ejecutada por evaluación de la
expresión. La cuestión está en QUÉ va a ser computado, no en CÓMO va a serlo.

Otro lenguaje muy conocido, casi funcional es el lenguaje de consultas estándar de bases de
datos, SQL. Una consulta SQL es una expresión con proyecciones, selecciones y uniones.
Una consulta dice qué rela-ción se debe computar sin decir cómo debe computarse.
Además, la consulta puede ser evaluada en cualquier orden que sea conveniente

Modelo Funcional

El modelo funcional, tiene como objetivo la utilización de funciones matemáticas puras sin
efectos.

El esquema del modelo funcional es similar al de una calculadora. Se establece una sesión
interactiva entre sistema y usuario: el usuario introduce una expresión inicial y el sistema
la evalúa mediante un proceso de reducción. En este procesos se utilizan las definiciones
de funciones realizadas por el progra- mador hasta obtener un valor no reducible.

El valor que devuelve una función está únicamente determinado por el valor de sus
argumentos consi- guiendo que una misma expresión tenga siempre el mismo valor.

Es más sencillo demostrar la corrección de los programas ya que se cumplen propiedades
matemáticas tradicionales como la propiedad conmutativa, asociativa, etc.

El programador se encarga de definir un conjunto de funciones sin preocuparse de los
métodos de eva-luación que posteriormente utilice el sistema. Estas funciones no tienen
efectos laterales y no dependen de una arquitectura concreta.



Este modelo promueve la utilización de una serie de características como las funciones de
orden superior, los sistemas de inferencia de tipos, el polimorfismo, la evaluación pere- zosa,
etc.



Funciones de orden superior

Un lenguaje utiliza funciones de orden superior cuando permite que las funciones sean
tratadas como valores de 1ª clase, permitiendo que sean almacenadas en estructuras de
datos, que sean pasadas como argumentos de funciones y que sean devueltas como
resultados.

La utilización de funciones de orden superior proporciona una mayor flexibilidad al
programador, siendo una de las características mas sobresalientes de los lenguajes
funcionales.



quad :: Int -> Int
quad x = x * x

impar :: Int -> Bool
impar x

| (x `mod` 2) == 1
| otherwise

map :: (t -> u) -> [t] -> [u]
map f [] = []
map f (a:x) = f a : map f x

= True
= False

map quad [1,2,3,4] = [1,4,9,16]
map impar [1,2,3,4] = [True, False, True, False]

Sistemas de Inferencia de Tipos y Polimorfismo

Muchos lenguajes funcionales han adoptado un sistema de inferencia de tipos que consiste
en:

El programador no está obligado a declarar el tipo de las expresiones.
El compilador contiene un algoritmo que infiere el tipo de las expresiones.
Si el programador declara el tipo de alguna expresión, el sistema chequea que el

tipo declarado coincide con el tipo inferido.


Los sistemas de inferencia de tipos permiten una mayor seguridad evitando errores de tipo
en tiempo de ejecución y una mayor eficiencia, evitando realizar comprobaciones de tipos
en tiempo de ejecución.

Los sistemas de inferencia de tipos aumentan su flexibilidad mediante la utilización de
polimorfismo.

El polimorfismo permite que el tipo de una función dependa de un parámetro. Por
ejemplo, si se define una función que calcule la longitud de una lista, una posible
definición sería:



long ls = if vacia(L) then 0

else 1 + long(cola (L))

long :: [x] → Integer

El sistema de inferencia de tipos inferiría el tipo: long::[x] → Integer, indicando que
tiene como argu- mento una lista de elementos de un tipo a cualquiera y que devuelve un
entero.

En un lenguaje sin polimorfismo sería necesario definir una función long para cada tipo de
lista que nece- sitase. El polimorfismo permite una mayor reutilización de código ya que no
es necesario repetir algorit- mos para estructuras similares.



Evaluación Perezosa

Los lenguajes tradicionales, evalúan todos los argumentos de una función antes de conocer
si estos serán utilizados.
Por ejemplo:

f (x:Integer; y:Integer):Integer
begin

return (x+3);

end;



g (x:Integer):Integer
begin
(* bucle infinito *)
while true do

x:=x
end;


-- Programa Principal
begin

write

(f(4,g(5)));

end;

Con el sistema de evaluación tradicional, el programador no devolvería nada, puesto que al
intentar eva- luar g(5) el sistema entraría en un bucle infinito. Dicha técnica de evaluación
se conoce como evaluación impaciente porque evalúa todos los argumentos de una función
antes de conocer si son necesarios.

Por otra parte, en ciertos lenguajes funcionales se utiliza evaluación perezosa que consiste
en no evaluar un argumento hasta que no se necesita. En el ejemplo anterior, si se utilizase
evaluación perezosa, el sistema escribiría 7.

¿Qué tienen de bueno los lenguajes funcionales?

Estos son algunas de las características más importantes de los lenguajes funcionales.



Examinemos algunos de los beneficios de la programación funcional:

1. Programas cortos. La brevedad de los programas funcionales hace que sean

mucho más con- cisos que su copia imperativa.



2. Facilidad de comprensión de los programas funcionales. Deberíamos ser
capaces de en- tender el programa sin ningún conocimiento previo del Haskell. No
podemos decir lo mismo de un programa en C. Nos lleva bastante tiempo
comprenderlo y, cuando lo hemos entendido, es muy fácil cometer un pequeño
fallo y tener un programa incorrecto.

3. No hay ficheros “core”. La mayoría de los lenguajes funcionales y Haskell en
particular son fuertemente tipados y eliminan una gran cantidad de clases que se
crean en tiempo de compila- ción con las que se pueden cometer errores. O sea,
fuertemente tipados significa que no hay fi- cheros “core”. No hay posibilidad de
tratar un puntero como un entero o un entero como un pun-tero nulo.

4. Reutilización de código. Los tipos fuertes están, por supuesto, disponibles en
muchos lengua- jes imperativos como Ada o Pascal. Sin embargo el sistema de tipos
de Haskell es mucho menos restrictivo que, por ejemplo el de Pascal porque usa
polimorfismo. Por ejemplo, el algoritmo Quicksort se puede implementar de la
misma manera en Haskell para listas de enteros, de carac- teres, listas de listas...
mientras que la versión en C es sólo para arrays de enteros.

5. Plegado. Los lenguajes funcionales no estrictos tienen otra característica, la
evaluación perezo- sa. Los lenguajes funcionales no estrictos llevan exactamente
esta clase de evaluación. Las es-tructuras de datos son evaluadas justo en el
momento en el que se necesita una respuesta y puede que haya parte de estas
estructuras que no se evalúen

6. Abstracciones potentes. Generalmente, los lenguajes funcionales ofrecen nuevas
formas para encapsular abstracciones. Una abstracción permite definir un objeto
cuyo trabajo interno está oculto. Por ejemplo, un procedimiento en C es una
abstracción. Las abstracciones son la clave para construir programas con módulos y
de fácil mantenimiento. Son tan importantes que la pre- gunta para todo nuevo
lenguaje es: “¿De qué mecanismos de abstracción dispone?”.Un mecanismo de
abstracción muy potente que está disponible en los lenguajes funcionales son las
funciones de alto orden. En Haskell una función es un “ciudadano de primera
clase”: pueden pasarse tranquilamente a otras funciones, ser devueltas como el
resultado de otra función, ser incluidas en una estructura de datos, etc. Esto nos
quiere decir que el buen uso de estas funcio- nes de alto orden puede mejorar
sustancialmente la estructura y modularidad de muchos pro- gramas.

7. Manejo de direcciones de memoria. Muchos programas sofisticados necesitan
asignar me- moria dinámica desde una pila. En C, esto se hace con una llamada a
“malloc”, seguida de un código para inicializar la memoria. El programador es el
responsable de liberar memoria cuando ya no se necesite más. Esto produce,
muchas veces, errores del tipo “dangling-pointer” (punteros colgados).

Cada lenguaje funcional libera al programador del manejo de este almacenamiento.
La memoria es asignado e inicializado implícitamente y es recogido por el
recolector de basura.

La tecnología de asignación del store y la recolección de basur