PDF de programación - La Programación Funcional: Un Poderoso Paradigma

La Programación Funcional: Un Poderoso Paradigma


Cuadernos de la Facultad n. 3, 2008

Gustavo Ramiro Rivadera 1

[email protected]


Resumen

El presente artículo pretende introducir al lector en el paradigma
de la programación funcional, utilizando el lenguaje Haskell, un lenguaje
funcional puro, de propósito general, que incluye muchas de las últimas
innovaciones en el desarrollo de los lenguajes de programación
funcionales.


Palabras Claves: programación funcional, paradigma funcional,
abstracción de datos, funciones de orden superior, evaluación
perezosa, transparencia referencial, tipos de datos

1. Introducción

formé parte de un proyecto de

Hace ya bastante tiempo, cuando cursaba mis últimos años en la
investigación en
Universidad,
arquitecturas de computadoras. En este proyecto analizábamos y
clasificábamos todas los posibles tipos de arquitecturas existentes,
desde las comunes y ubicuas PC a las lejanas (para nosotros)
supercomputadoras paralelas. En ese proyecto, a la par de descubrir
que no todas las computadoras eran PC, y que no todas tenían un solo
procesador y del mismo tipo, me di cuenta asimismo que los lenguajes
de programación que utilizaban tampoco eran similares. Claro que ya
había aprendido el omnipresente Pascal, algo de C, C++, y la nueva ola
de los lenguajes orientados y basados en objetos, pero lo que me llamó
la atención, no fueron las variaciones sobre estos últimos lenguajes,

1 Ingeniero en Computación, desarrollador independiente de software, docente de las Cátedras de
Modelos y Simulación, Análisis Estratégico de Datos y Bases de Datos III, en la Facultad de
Ingeniería e Informática, UCASAL. Actualmente cursa la Maestría en Ingeniería del Software en el
Instituto Tecnológico de Buenos Aires (ITBA).


63

Rivadera: La Programación Funcional
sino otros radicalmente distintos, diseñados muchas veces en forma
especial para máquinas específicas. Para comenzar, estos lenguajes no
ordenaban sus computaciones (instrucciones) en forma secuencial, sino
que el orden estaba dado por, en el caso particular de los funcionales,
la aplicación de funciones a otras funciones, resultando por tanto,
innecesaria la existencia de variables. Finalmente, este proyecto me
llevó a investigar sobre los diferentes paradigmas de programación.

Un paradigma de programación es una forma específica de
realizar las computaciones. Un lenguaje de programación siempre sigue
un paradigma o una mezcla de varios; por ejemplo el paradigma
procedimental es seguido por la mayoría de los lenguajes actuales,
tales como JAVA, Pascal y C++. También podemos encontrar lenguajes
con la influencia de dos paradigmas, por ejemplo el antes mencionado
C++, que tiene su origen procedimental y al cual se le ha agregado el
paradigma orientado a objetos.

El paradigma del que trata este artículo se denomina funcional,

programación funcional o FP.

2. Orígenes

Los orígenes de la programación funcional pueden rastrearse al
matemático Alonzo Church, que trabajaba en la Universidad de
Princeton, y, al igual que otros matemáticos de allí, estaba interesado
en la matemática abstracta, particularmente en el poder computacional
de ciertas máquinas abstractas. Las preguntas que se hacía eran por
ejemplo: si dispusiésemos de máquinas de un ilimitado poder de
cómputo, ¿qué tipos de problemas se podrían solucionar?, o ¿se
pueden resolver todos los problemas?

Para contestar este tipo de preguntas, Church desarrolló un
lenguaje abstracto, denominado Cálculo Lambda, que el cual sólo
realizaba evaluación de expresiones usando
funciones como
mecanismo de cómputo. Este lenguaje abstracto no tenía en cuenta
limitaciones concretas de implementación de ningún tipo.

Al mismo tiempo que Church, otro matemático, Alan Turing,
desarrolló una máquina abstracta para intentar resolver el mismo
tiempo de problemas planteados por Church. Después se demostró que
ambos enfoques son equivalentes.

64

Cuadernos de la Facultad n. 3, 2008
Las primeras computadoras digitales se construyeron siguiendo un
esquema de arquitectura denominado de Von Neumann, que es
básicamente una implementación de la máquina de Turing a una
máquina real. Esta máquina forzó de alguna manera el lenguaje en el
cual se escriben sus programas,
justamente el paradigma
procedimental, el cual, como menciona Backus en un muy famoso
artículo que escribió al recibir el premio Turing en 1978 (Backus 1978),
tiene tantísimos defectos, que muchos programadores padecemos aun
hoy.

La programación funcional se aparta de esta concepción de
máquina, y trata de ajustarse más a la forma de resolver el problema,
que a las construcciones del lenguaje necesarias para cumplir con la
ejecución en esta máquina. Por ejemplo, un condicionamiento de la
máquina de Von-Neumann es la memoria, por lo cual los programas
procedimentales poseen variables. Sin embargo en la programación
funcional pura, las variables no son necesarias, ya que no se considera
a la memoria necesaria, pudiéndose entender un programa como una
evaluación continua de
la
programación funcional posee un estilo de computación que sigue la
evaluación de funciones matemáticas y evita los estados intermedios y
la modificación de datos durante la misma.

funciones. Es decir,

funciones sobre

Hoy en día existen diversos lenguajes funcionales. Se podría
considerar como uno de los primeros lenguajes funcionales al LISP, que
actualmente sigue en uso, sobre todo en áreas de la inteligencia
artificial. También un pionero de este paradigma es APL desarrollado en
los años 60 (Iverson 1962). El linaje funcional se enriqueció en los años
70, con el aporte de Robin Milner de la Universidad de Edimburgo al
crear el lenguaje ML. Éste se subdividió posteriormente en varios
dialectos tales como Objective Caml y Standard ML. A fines de los años
80, a partir de un comité, se creó el lenguaje Haskell, en un intento de
reunir varias ideas dispersas en los diferentes lenguajes funcionales (un
intento de estandarizar el paradigma). Este año Microsoft Research ha
incluido un nuevo lenguaje (funcional), denominado F#, a su plataforma
.NET.

La Figura 1 compara gráficamente ambos paradigmas.



65

Rivadera: La Programación Funcional



Modelo imperativo (de Labra 1998)

Modelo Funcional (de Labra 1998)



Figura 1. Comparación entre los modelos imperativo y funcional (Labra 98).

3. Qué es la programación funcional

En este breve artículo, intentaré explicar la utilidad y potencia de la
programación funcional, por medio de pequeños ejemplos, para
comprender más rápidamente esta filosofía de programación.

Dado el nombre del paradigma, sabemos básicamente que lo
central en el mismo es la idea de función, que podríamos decir es
análoga a lo que conocemos de funciones de la matemática. Por
ejemplo, podemos escribir en el lenguaje funcional Haskell:


Factorial :: int -> int
factorial 0 = 1
factorial n = n * factorial (n-1)

Es decir, la última es una función sencilla, parecida a la que conocemos
de las matemáticas de la secundaria, que permite calcular el factorial de
un número entero (ver definición de la función factorial más abajo).

66

Cuadernos de la Facultad n. 3, 2008
Comparemos esa línea de código de Haskell con la siguiente en un
lenguaje como C#:


unsigned factorial (unsigned n)
{
int product = 1; // valor inicial
while (n > 1)
{
product *= n--; // acumulador
}
return product; // resultado
}
Este ejemplo es muy sencillo y los dos fragmentos de código son
muy parecidos. Sin embargo, la definición de Haskell es mucho más
cercana a la matemática:


0! =
n! =
La pregunta que nos hacemos ahora, es si podemos construir
programas complejos usando simplemente funciones. Esta pregunta se
puede contestar fácilmente si describimos las características principales
de este tipo de lenguajes. A modo de ejemplo de introducción, veamos
como se escribiría el programa de ordenamiento QuickSort en Haskell:
quicksort [] = []
quicksort (x:xs) = (quicksort [ y | y <- xs, y <= x ])
++ [x] ++
(quicksort [ z | z <- xs, z > x ])

1
n * (n - 1)!

En este caso, conseguimos un programa muy sencillo y corto, que
basa su potencia en la habilidad de Haskell de manipular listas ([ ]) y
especificar funciones recursivas. Quicksort se define recursivamente, a
partir de la misma definición matemática del algoritmo. Este algoritmo
utiliza una estrategia de divide y conquista (divide and conquer), la cual
divide a una lista en dos sublistas, la primera con elementos menores o
iguales que uno dado, denominado pivot, y la segunda con elementos
mayores. En la primera línea del cuerpo (línea 2), se define la primera
sublista, en la segunda línea el pivot, y la tercera línea la tercera
sublista. El operador predefinido ++ concatena dos listas. Cada llamada
recursiva a QuickSort en el cuerpo especifica que se concatenará el
nuevo elemento (y o z) a la lista de argumento siempre y cuando se
cumpla con la condición de más a la derecha (ej. y <= x).



67

Rivadera: La Programación Funcional

Comparemos ahora nuestro sencillo programa funcional con uno

en un lenguaje procedimental, tal como C (Wikipedia 2008):

//Programa Quicksort en C
void quicksort(int* array, int left, int right)
{
i