Las virtudes de la programción funcional
Ernesto Hernandez-Novich
emhn at telcel.net.ve
Mon Nov 25 13:53:10 CST 2002
Hoy es un buen día para hackear.
Casi cualquiera que dice "saber programar", probablemente ha adquirido
toda su experiencia utilizando el paradigma Imperativo (también conocido
como Procedural), en el cual se indica al computador exactamente todos
los pasos que debe realizar para cumplir determinada tarea, además de
estar basado en "efectos laterales", es decir la posibilidad de mantener
un estado (variables globales) y sabiendo que cada acción que ejecuta el
computador depende de ese estado y puede modificarlo. No hay nada malo
en conocer solamente ese paradigma, pero si hay mucho muy bueno en los
demás paradigmas que los hacen superiores en varios aspectos, y a la vez
brindan al programador maneras novedosas de enfrentar problemas de
programación. No es mi intención discutir aquí los cuatro paradigmas
fundamentales (Imperativo, Objetivo u "Orientado a Objetos", Funcional y
Lógico Declarativo); el interesado debe referirse a libros de texto
cualesquiera en el ámbito de Lenguajes de Programación.
Mi intención con esta nota (y las dos que le seguirán) es ilustrar como
el paradigma Funcional es _muchísimo_ más expresivo que el Imperativo,
mucho más conciso, facilita la demostración de correctitud de los
programas y permite hacer cosas que con el paradigma Imperativo
simplemente no se pueden [1]. Perl es uno de los pocos lenguajes de
programación Turing-completos que incluye _tres_ paradigmas
simultánea y complementariamente [2]. Lo único que hace falta es
agregar nuevas formas de pensar para aprovecharlos.
En este primer artículo, trataré de cubrir los aspectos prácticos de la
programación funcional en el "día a día". Hay un sólo aspecto teórico
que es importante mantener presente: en la programción funcional pura
_no_ existen las variables globales. Es decir, cuando uno plantea la
solución a un problema, lo hace combinando aplicaciones de funciones que
reciben N argumentos y producen M resultados, pero no hay _nada_
compartido entre las funciones ni mecanismo alguno de comunicación entre
ellas (salvo el pasaje de parámetros y la captura de valores de
retorno). Desde el punto de vista del diseño de programas, eso implica
que se utiliza la metodología Top-Down. Si se trabaja en un lenguaje
puramente funcional como Scheme, ML o Haskell, no hay otra forma de hacer
las cosas; Perl es un caso excepcional, porque si permite mezclar ambos
paradigmas.
Lo primero que uno debe aprender cuando trabaja funcionalmente es que
todo se logra aplicando funciones. El que está acostumbrado a la
programación Imperativa piensa
sub foo {
...
return ($bar);
}
($ret1,$ret2,$ret3) = foo(arg1,arg2,arg,3)
y se siente feliz. Sin embargo esto es lo mínimo que un lenguaje
funcional debe soportar (aplicación de funciones). Tomemos un ejemplo
clásico: se tiene una lista de longitud _desconocida_ a priori y se
desea operar un cálculo específico sobre cada elemento de la lista, para
obtener una nueva lista con los resultados. "¡Fácil!"
@nueva = ();
for ($i = 0; $i < @original; $i++) {
$valor = operar-sobre($original[$i]);
push(@nueva,$valor);
}
es la solución clásica imperativa y "cabeza cuadrada" [3]:
1. Crear una lista nueva.
2. Determinar el largo de la lista, y con otra variable
iterar desde cero hasta allí.
3. Usar otra variable para operar sobre el original.
4. Crear la nueva lista agregando al final los nuevos valores
Algo un poco mejor sería hacer
foreach $elemento (@original) {
operar-sobre($elemento)
}
como foreach es una implementación parcial de un operador funcional (un
"iterador" para ser precisos) no es necesario calcular la longitud de la
lista... sin embargo no es un operador puro porque se basa precisamente
en un "efecto lateral": $elemento se convierte en una referencia al
valor original en la lista, de modo que estoy trabajando "en el sitio" [4].
Para ser completamente funcionales, lo que deseamos es expresar
"aplica la función operar-sobre() sobre cada elemento de la lista y
genera una nueva lista", de la forma más sucinta posible.
@nueva = map { operar_sobre($_) } @original
Eso es todo. Si se utiliza el módulo Benchmark para comparar las
velocidades se puede apreciar la vergüenza que pasa el programador
Imperativo por desconocer la técnica Funcional [5].
#!/usr/bin/perl -w
use Benchmark;
sub operar {
my $x = shift;
return $x * 2;
}
timethese(20000, {
imperativo => 'my @lista = (1..100);
my @nueva = ();
for (my $i = 0; $i < $#lista; $i++) {
push(@nueva,operar($lista[$i]));
}',
mediocamino => 'my @lista = (1..100);
my @nueva = ();
foreach (@lista) {
push(@nueva,operar($_));
}',
funcional => 'my @lista = (1..100);
my @nueva = map { operar($_) } @lista;'
});
Es decir, se ejecutó 20000 veces cada proceso trabajando con listas
de 100 elementos. Saquen sus conclusiones en cuanto a claridad y
velocidad (edité los resultados, pero pruébenlo en sus máquinas):
Benchmark: timing 20000 iterations of funcional, imperativo, mediocamino...
imperativo: 42 wallclock secs
mediocamino: 31 wallclock secs
funcional: 25 wallclock secs
Así que con el estilo funcional soy 60% más rápido que con el
imperativo, y hay que fumar algo peor que crack para negar que el
funcional es más claro y conciso.
Ahora bien, utilizar map solamente para hacer ciclos implícitos como el
que he presentado, aunque es un avance para el programador, no llega a
ser tan efectivo como podría serlo. Supongan que tienen una lista
de _referencias_ a "cosas" (hashes de listas de hashes de ..., no
importa) que representan elementos comparables, i.e. tienen una lista
de referencias a datos de clientes. Digamos que la lista apunta a un
hash que tiene una clave 'montos' que es una referencia a una lista
de tres elementos, y resulta que ustedes tienen que ordenar la lista
de clientes según cada uno de esos campos, i.e. tienen
( ... clientes ..., * .... ) <=== Ordenar esto según
| valor en A, B y/o C
|
+-----> { nombre => ...,
cedula => ...,
montos => [ A, B, C ]
...
}
Los Imperativos ya están diciendo algún improperio. Yo les presento
lo siguiente:
@clientes = ( ... el mamotreto antes visto ... );
for my $i (0..2) {
$ordenada[$i] = [ map { $_->[1] }
sort { $a->[0] <=> $b->[0] }
map { [ $_->{montos}->[$i], $_ ] } @clientes ];
}
y en $ordenada[$i] tienen una referencia a una lista que es @clientes
ordenada por el campo $i-ésimo de la lista de montos. Así de simple.
¿Aún están pensando como hacerlo imperativo?
Uno de los secretos para comprender el paradigma funcional es
desplazarse "de adentro afuera":
map { [ $_->{montos}->[$i], $_ ] } @clientes
Esto toma la lista de clientes y le aplica la función entre llaves. Esa
función devuelve una referencia a una lista que tiene dos elementos:
el valor del campo $i-ésimo de la clave 'montos' del cliente, y una
referencia al cliente original. Entonces, map me devolverá una lista
de pares ($i-ésimo monto, referencia al cliente).
sort { $a->[0] <=> $b->[0] } (...)
Esto se aplica a la lista que salió del map. Por lo tanto ordena la
lista de pares en orden ascendente por el 0-ésimo elemento del par,
es decir, el monto. Entonces sort me devolverá la lista de pares
ordenada según el monto.
map { $_->[1] }
Esto se aplica a la lista que salió del sort. Por lo tanto, genera una
nueva lista que tiene las referencias a los clientes originales; como la
lista que salió del sort ya tiene el orden que me interesa...
$ordenada[$i] = [ map/sort/map ]
... tomo la referencia a esa lista. Y listo. ¿Aún tratan de pensar como
hacerlo de forma Imperativa? [6] Incidentalmente, la técnica
map/sort/map que he descrito se conoce en el argot Perl como "maniobra
Schwartziana" porque fue descubierta por Randal Schwartz; existe una
técnica similar map/grep/map que no tiene nombre.
El último tópico a cubrir en esta introducción es lo que dá el nombre
al paradigma funcional: las funciones. ¿Qué puede ser manipulado como
_dato_ en un lenguaje Imperativo? "Bueno, los números, las cadenas,
apuntadores a números y cadenas, estructuras de datos. ¿Por?". En
el paradigma Funcional, se pueden manipular las _funciones_ [7].
Seguramente, no les resultará extraño ver algo como
sub cuadrado {
my $x = shift;
return ($x * $x);
}
print cuadrado(4);
"¡Duh! Una función que retorna el cuadrado de un numero. ¡Gran cosa!"
Al igual que en los lenguajes Imperativos, los lenguajes Funcionales
permiten definir funciones como ésta; nada del otro mundo. Sin embargo,
en los lenguajes Funcionales se pueden definir funciones anónimas, que
se usan con una referencia, en Perl, por ejemplo
my $funcion = sub { my $x = shift; return ($x * $x); }
y $funcion ahora tendrá una _referencia_ a una función. De modo que
puedo aprovecharla haciendo
print $funcion->(4)
que quiere decir "sigue la referencia a la función con los siguientes
argumentos". Si no le ven la utilidad inmediatamente para crear
callbacks en interfaces gráficas, o para hacer un despachador de
rutinas... no han programado mucho que se diga. Pero aún así,
aparentemente no es muy útil...
Si una función puede manipularse igual que cualquier objeto, ¿será
posible escribir una función que _retorne_ una función? Por supuesto, y
eso es el corazón de la programación Funcional. Continuando con el
ejemplo, es trivial darse cuenta que
sub retornafuncion {
return sub { my $x = shift; return ($x * $x); }
}
my $cuadrado = retornafuncion();
print $cuadrado->(4)
hace lo mismo que los programas anteriores. "¡Gran cosa!".
Ahora tienen que escribir funciones para generar secuencias. Digamos que
necesitan una secuencia para números de transacción, otra secuencia para
números de clientes, y así, necesitan tener varias secuencias que
comiencen por números diferentes. Es más, durante la vida del programa
les van a pedir que agreguen secuencias. La solución Imperativa gira por
tener varias variables globales y una rutina para manipular cada una,
etc. etc. etc. Horriblemente confuso y difícil de mantener.
Comencemos por escribir una función que dado un valor inicial, genere una
función que cuenta a partir de ese valor inicial:
sub generador {
my $n = shift;
return sub { return $n++; };
}
Y la uso de la siguiente manera:
my $secuencia_cliente = generador(1000);
my $secuencia_producto = generador(2000);
print $secuencia_cliente->(), "\n", # 1000
$secuencia_producto->(), "\n", # 2000
$secuencia_producto->(), "\n", # 2001
$secuencia_producto->(), "\n", # 2002
$secuencia_cliente->(), "\n"; # 1001
Es decir, llamo a la rutina con 1000, y me devuelve una rutina que
sabe contar desde 1000 y "acordarse" de mantener esa secuencia. Luego
llamo a la rutina con 2000, y me devuelve una rutina que sabe contar
desde 2000 y "acordarse" de mantener esa secuencia.
Lo que ocurre en generador es que cuando se construye la rutina anónima
que va a ser retornada, el lenguaje se "dá cuenta" que cuando sea
invocada debe "recordar" el valor que tenía $n. Entonces la rutina
recién construida lleva consigo copias de las variables léxicas (locales
definidas con my) para poder calcular en el mismo ambiente en el que fue
definida. [8] Es decir, durante la ejecución del programa hay "dos $n";
una es la que se utilizó cuando se llamó a generador(1000) y se "guarda"
junto con la rutina construida, y otra es la que se utilizó cuando se
llamó a generador(2000) y se "guarda" junto con esa rutina. Son
independientes entre sí, y cada vez que se llame a la rutina particular,
su "$n" privado será modificado apropiadamente.
¿Puede ser que yo esté fumando lumpias? Por supuesto. Puedo tener
clausuras que _compartan_ ambiente, i.e. una misma "$n" vista por dos (o
más) clausuras al mismo tiempo. Voy a usar un ejemplo que no es
"práctico" pero que ilustra el poder del paradigma; quiero tener dos
contadores, "más-p" y "más-q" que hagan lo que su nombre dice
(contar de p en p y de q en q) pero a partir del valor que dejó el contador
anterior... es decir si p es cuatro, q es siete y el valor inicial es 42,
entonces
mascuatro --> 46
massiete --> 53
massiete --> 60
mascuatro --> 64
Lo escribimos así
sub droga {
my ($p,$q,$n) = @_;
my $c1 = sub { return $n += $p; };
my $c2 = sub { return $n += $q; };
return ($c1,$c2);
}
my ($mascuatro,$massiete) = droga(4,7,42);
my ($mastrece,$masquince) = droga(13,15,-4);
print $mascuatro->(),"\n", # 46
$mastrece->(), "\n", # 9
$massiete->(), "\n", # 53
$massiete->(), "\n", # 60
$masquince->(), "\n", # 24
$mascuatro->(), "\n"; # 64
Se generan _cuatro_ rutinas anónimas. Dos de ellas comparten un $n
que comienza con 42 y al cual le suman 4 y/o 7 según sean llamadas.
Las otras dos comparten otro $n que comienza con -4 y al cual le
suman 13 o 15 según sean llamadas.
Finalmente, otro de los elementos del paradigma es la recursión. La
recursión es matemáticamente natural para expresar cálculos, y el caso
clásico del factorial no debería necesitar explicación. Usualmente los
lenguajes Imperativos tienen la habilidad de utilizar recursión, pero
los programadores la evitan por el famoso "stack overflow" producto de
anidar muchas llamadas recursivas: ese es un problema de la
implementación imperativa y no de la recursión per sé.
Así, el factorial recursivo sería
sub fac {
my $n = shift;
return ($n > 0) ? fac($n - 1) : 1;
}
Queda como ejercicio para el lector escribir una función que
retorne una función recursiva.
El paradigma Funcional es bastante más expresivo que el Imperativo, además
que enseña maneras alternas más eficientes y claras de resolver problemas
de cómputo. Soy firme creyente que un programador que nunca ha estado
expuesto a la programación Funcional siempre va a estar varios escalafones
por debajo de un programador que si lo ha estado. Siento que lenguajes
100% funcionales como Scheme, ML o Haskell son muy "duros" de aprender
pero deberían ser obligatorios en la enseñanza de programación. En la
vida real, un lenguaje como Perl que representa una mezcla de ambos
paradigmas es una herramienta invaluable.
Comparando con otros lenguajes:
- C/C++ soporta apuntadores a rutinas, pero no soporta clausuras. Uno
podría implementar el map, pero es bastante engorroso el manejo de
memoria. Así mismo, si quisieran implementar clausuras tendrían que
definir quizás una clase genérica para el callback y luego
especializarla en cada clausura. IMNSHO eso es basura.
- Python tiene clausuras débiles: solamente se acuerda de las variables
en su entorno local [9].
- Java no ofrece apuntadores a rutinas, mucho menos clausuras. No
existe map y solamente se podría simular con un iterador.
- PHP es a la programación funcional lo que Basic es a la estructurada.
En la segunda nota, voy a explorar la Jerarquía de Funciones de Kleene
para demostrar que todo aquello que se pueda computar se puede
hacer _solamente_ con el cero, el sucesor y dos operadores funcionales.
Para eso, programaré de manera 100% funcional (sin ciclos, sin variables
globales y sin efectos laterales), cinco funciones primitivas
(denominadas primitivas recursivas) y de allí sacaremos suma, resta,
multiplicación, factorial, división, etc.
[1] Traten de hacer los ejemplos en otro lenguaje que no sea Perl, por
ejemplo Java, Python, PHP e incluso C o C++ y verán como
desilusionan en su capacidad expresiva.
[2] Imperativo, Objetivo y Funcional. Pueden usarse los tres al mismo
tiempo o cualesquiera combinaciones de ellos a la vez. El paradigma
Lógico Declarativo viene en Perl 6.
[3] Pueden argumentar que en lugar de usar @lista en contexto escalar
use length, que no necesito crear la lista nueva, etc. Ese no es
el punto; el punto es que el lenguaje les obliga a explicar todo.
[4] Si, podría usarse $_ y no definir $elemento, pero lo hago por
claridad solamente. Optimízenlo todo lo que quieran y verán que
aún así el funcional es superior.
[5] Todo fue probado en un PIII 550Mhz con 128Mb de RAM que además
está corriendo SETI at Home ;-)
[6] Cuando lo implementen, comparen la velocidad. Nuevamente la
programación funcional será superior.
[7] Se dice que las funciones son "objetos de primer orden".
[8] Se denomina "ambiente léxico" y las funciones anónimas que "llevan"
ambiente consigo son denominadas "clausuras".
[9] Eso se llama "shallow binding". Si se tiene
{ my $x; { my $y; { my $z; sub { ... } } }
en Python solamente se puede llevar $x, en Perl se lleva $x, $y y
$z. Se puede simular en Python con algunas artimañas. IMNSHO
eso también es basura porque el entorno de ejecución debería
ser suficientemente inteligente para llevarse todo.
--
Ernesto Hernández-Novich - Running Linux 2.4.19 i686 - Unix: Live free or die!
Geek by nature, Linux by choice, Debian of course.
If you can't apt-get it, it isn't useful or doesn't exist.
GPG Key Fingerprint = 438C 49A2 A8C7 E7D7 1500 C507 96D6 A3D6 2F4C 85E3
------------------------------------------------------------------------
Enviar e-mail a <majordomo at pm.org> colocando en el cuerpo:
"UNSUBSCRIBE caracas-pm-list" para desuscribirse.
"INFO caracas-pm-list" para conocer las reglas de etiqueta.
------------------------------------------------------------------------
More information about the caracas-pm
mailing list