Diversión con functores

Despues de programar durante algún tiempo, es común encontrarse repitiendo una y otra vez las mismas soluciones, con ligeras variantes. Es esta ha originado todas las innovaciones en el campo, desde la creación de subrutinas hasta los macros.

Una de estas situaciones se presenta cuando se tiene una funcion que convierte datos del tipo A al tipo B y se la desea transformar en una nueva función que opere sobre un tipo derivado de A para convertirlo en un tipo derivado (en una manera equivalente) de B.

La definición de functores es:

Dadas dos categorías C y D, un functor F de C a D es un mapeo que:

• Asocia a cada elemento X de C un elemento F(X) de D
• Asocia a cada funcion f: X -> Y de C otra F(f): F(X) -> F(Y)

De manera tal que

• F(IDx) = ID(Fx)
• F(f o g) = F(f) o F(g)

Desde el punto de vista programatico, un functor esta formado por dos funciones: la primera convierte tipos "simple" en tipos "complejos" y la segunda convierte funciones cuyo dominio y rango son tipos "simples" a otras funciones, en algún sentido equivalentes, pero cuyo dominio y rango son tipos "complejos". De esta forma, si has programado una función que convierta manzanas en compotas, aplicando un functor tienes automaticamente una funcion que convierta cajas de manzanas en cajas de compotas o camiones de manzanas en camiones de compotas.

Un ejemplo practico es el functor cuyo rango son las listas. La categoría C sería el conjunto de todos los tipos que son susceptibles de ser contenidos dentro de listas (enteros, reales, complejos, caracteres, incluso listas, ...). La categoría D esta formada por las listas de los tipos en la categoría C (listas de enteros, listas de reales, listas de complejos, listas de caracteres, listas de listas, ...).

Para definir dicho functor, necesitamos una función que convierta elementos de los tipos en C a elementos en los tipos en D. En este caso la función es simple, solo necesita crear una lista con ese unico elemeto. El otro elemento necesario es una función que convierta una funcion del tipo X -> Y en una funcion del tipo [X] -> [Y]. En Haskell esta función se denomina map, y su definición es:

map [] f = []
map x:xs = (f x) : (map xs)

Eso es todo. Al definir map, se ha solucionado de una vez por todas el problema de mapear funciones hacia la categoría de las listas. Desde luego, cada categoría distinta requiere un mapeo distinto. Normalmente la primera parte del mapeo es el constructor de tipos y la segunda recibe como nombre genérico "fmap".

La belleza de la programación funcional en lenguajes como Haskell es la simplicidad con la que se implementan conceptos como los functores. Lengajes imperativos como Java poseen todo lo necesario para crear functores: funciones que mapean tipos a otros tipos (generics en el lenguaje de java), funciones como ciudadanos de primera clase (en java, clases) e interfaces. Sin embargo, su implementación es mucho mas verbosa.

El olor de la sangre

Recientemente he estado implementando un protocolo de comunicación para un dispositivo embebido. Dada la naturaleza de la plataforma, el lenguaje de programación elegido fue C.

Así que comencé a programar: a preocuparme por el manejo de memoria, a acceder a los elementos de un arreglo a través de índices que yo mismo me veía obligado a incrementar, a codificar mis estructuras de datos utilizando números en vez tipos de datos algebraicos.

Conforme iba retrocediendo en la escala evolutiva de los lenguajes me ocurrió algo curioso... algo solo comparable a la involución que sufrieron los protagonistas de "El señor de las moscas". A medida que me acercaba cada vez mas al ensamblador despertaba en mi algo atabico, casi salvaje... Programar la maquina desnuda, sin la ayuda de poderosos conceptos fue una experiencia intoxicante... casi lo mismo que debían sentir nuestros ancestros al cazar bisontes solo con piedras y flechas... al percibir el olor de la sangre de la presa cazada...

Desde luego, la aplicación era lo suficientemente pequeña como para que el lado oscuro del c no se mostrara. De haber sido mas grande la aplicación, los problemas con el manejo de memoria, el tedio de la escritura de código boilerplate, la molestia de tener a cada paso que indicar lo obvio me habría frustrado. Al igual que un citadino transportado a los albores de nuestra especie se habría aburrido esperando por la presa, hambriento, exasperado por los mosquitos y molesto por las inclemencias del tiempo.

Es que el olor de la sangre llama, pero no tanto...

Un abreboca al poder de la programación funcional

Una de las razones por la cual la programación funcional es considerada poderosa es por la facilidad con la que se puede derivar nuevo código a partir del ya existente. Por ejemplo, una de las tareas mas comunes durante el desarrollo de programas es operar sobre una colección de datos, bien sea para generar una nueva colección, modificar la ya existente o generar una estructura nueva derivada de esta.

Así, si quisieramos la sumatoria de los valores en un arreglo numérico el código (en python) seria:

suma = 0
for x in arreglo :
suma += x

Para elevar al cuadrado los componentes de un arreglo, la solución que implementaría un programador de C escribiendo python seria:

for i in len(arreglo) :
arreglo[i] = arreglo[i]**2

(python tienen una forma mas elegante de lograrlo, pero es precisamente una forma "prestada" de lenguajes con paradigmas diferentes al imperativo).

Estos códigos son representativos de las soluciones imperativas: crear un bucle que recorra el arreglo, operando sobre cada elemento para generar el resultado deseado. Un programador de C o Java con algunos años de experiencia habrá escrito lineas semejantes a esas un millar de veces. El problema esta en que precisamente la tarea es tan común que forma un patrón ideal para ser resumido.

Ahora, como podría aislarse esa solución en un lenguaje como C o Java, de manera que el programador solo tuviera que escribir la parte del problema que cambia (el suma +=x o el arreglo[i] = arreglo[i]**2)? Dado que la estructura semántica del C y el java están fijadas y no lo permiten directamente, la única posibilidad seria por medio de una librería. La librería implementaría la parte común (el bucle) y recibiría como parámetro un elemento (un objeto en Java o un apuntador a una función en C) que contenga el pedazo de programa que varía.

Y he allí el problema. Declarar una función en C es mas trabajo que escribir el bucle directamente. Definir una clase en Java que implemente el comportamiento deseado, instanciarla y pasar el objeto a la librería no es una opción: es una penitencia.

La mayoría de los lenguajes funcionales por otra parte permiten la creación de funciones con un costo mínimo para el programador, razón por la cual hacer una librería con los tipos mas comunes de bucles no solo es viable, sino la forma natural de proceder.

El primer caso mostrado, la suma de los valores en un arreglo, es de hecho un caso particular de un tipo de bucles llamado fold (también llamado reduce). Este caso se caracteriza por dos elementos: un valor a ser devuelto en caso que el arreglo sea de longitud cero, y una función que tome dos valores y devuelve uno, la cual es usada para "reducir" el arreglo. En nuestro caso, el valor a ser devuelto en caso que el arreglo este vació es cero y la función que reduce el arreglo es la suma.

Así, expresar ese bucle en python de forma funcional seria

reduce(real.__add__, arreglo, 0.0)


En Haskell, uno de los lenguajes mas elegantes, seria

foldr (+) 0.0 arreglo

En ambos casos el significado es el mismo: si el arreglo esta vació, devuelve 0.0, sino suma sus elementos. Si bien este programa puede resultar de mas difícil lectura (sobre todo debido a la costumbre imperativa), también ofrece algunas ventajas:

• Es mas conciso
• No usa variables temporales
• Puede ser manipulado programaticamente

El ultimo punto tendrá un impacto gigante en la forma en que programamos en los años venideros. Dado que la función fold aisla las partes que varían en un bucle y homogeniza la estructura, es mas amistosa desde el punto de vista matemático. Si todos los bucles son expresados con fold y otras pocas estructuras semejantes, el código puede ser transformado por un compilador inteligente siguiendo una serie de teoremas, obteniendo un código super-optimizado.