Friday, November 23, 2007

Sobre Monadas, monoides y afines

Brian Beckman ofrece un vídeo orientado a los programadores donde explica que es una monada:

http://channel9.msdn.com/ShowPost.aspx?PostID=358968#358968

Otra serie de vídeos interesantes sobre el tópico, aunque mas orientados hacia la parte matemática pueden verse en el canal de YouTube "The Catsters".

Tuesday, July 31, 2007

Como no aprender sobre recursividad

A mediados de los 80s descubrí el fascinante mundo de la recursión gracias al lenguaje LOGO. LOGO es un lipsoide con excelente soporte gráfico, por lo que nada mas natural que combinar gráficos y recursión para generar fractales como el copo de nieve. Desgraciadamente la fuente de la que aprendí no era muy buena es ese tópico en particular. Los ingredientes en una función recursiva son:
  • Un segmento de código que evite la recursión infinita
  • Un segmento de código que haga el trabajo
  • Un segmento de código que reinvoque la función
Con esta receta me encaminé a implementar mis propias funciones recursivas como la curva de Hilbert. Pasar de la teoría a la práctica es bastante difícil, sobre todo cuando no se tiene computador, mucho menos una versión de LOGO a la mano. Así que tenía que hacer los algoritmos en papel, hacer una corrida en frío, ejecutándolos con lápiz y escuadra. Pero la mayor dificultad estaba en dar con el algoritmo recursivo correcto, básicamente por ensayo y error.

Cuando pasé de los gráficos a las estructuras de datos, la vieja receta aprendida se mostró igualmente ineficiente. La recursión era para mí un arte y no una ciencia. Eso hasta que fui enseñado correctamente, gracias a un libro de Paul Graham.

La belleza de las funciones recursivas se muestra en todo su esplendor con las estructuras de datos recursivas. Cuando se define una estructura de datos recursiva se da una receta para crear nuevos valores en base a valores previos. Por ejemplo, para definir una lista en Haskell:

data Lista a = Nulo | Cons a (Lista a)


Esta expresión dice que una lista de un tipo "a" es o bien el elemento especial "Nulo" o la unión ("Cons") de un elemento de tipo "a" con una lista de tipo "a" (desde luego, Haskell ya tiene definido su propio tipo para las listas, con una notación mas suscinta. Sin embargo, para fines didácticos esta definición es mas conveniente).

Aquí es donde se evidencia el poder de las funciones recursivas. Para definir una función recursiva sobre el tipo de datos Lista a, solo hay que considerar que se debe hacer para cada una de las partes que conforman su definición. Donde aparezca "Lista a" cabe esperarse que haya un llamado recursivo. Por ejemplo, para obtener la longitud de una lista:

longitud Nulo = 0
longitud Cons a b = 1 + longitud b

Es esta simetría entre la forma de la estructura de datos y la función recursiva lo que facilita el trabajo al programador.

Monday, July 2, 2007

Haskell como herramienta para los matematicos

Una interesante página en el sitio de haskell resume las ventajas que ofrece un lenguaje funcional fuertemente tipificado para el aprendizaje, estudio y juego con la matemática.

Otros lenguajes, como Qi, pueden ofrecer estas mismas ventajas con el añadido de ser derivados de Lisp y por lo tanto, conceptualmente mas austeros.

Wednesday, June 20, 2007

Python 3000

Recientemente, Guido van Rossum concretó mas detalles sobre el futuro Python 3000:

http://www.artima.com/weblogs/viewpost.jsp?thread=208549

Es de particular relevancia:
  • El Viejo sistema de Clases desaparecerá.
  • Mayor coherencia en la librería estándar.
  • La compatibilidad con versiones previas no es un objetivo.
Python ha seguido una evolución interesante, pasando a ser un "verdadero" lenguaje orientado a objetos al tiempo que ha visto incrementado el rango de funcionalidades que ofrece "out of the box". Sin embargo, su inicio modesto y la colaboración de centenares de personas en la elaboración de las librerías, de alguna forma ha causado que el lenguaje haya dejado de ser tan simple y elegante como lo era en un principio.

La mayor (tal vez la única?) envidia que sienten los pythonistas ante, digamos, Java, es que sus librerías lucen estandarizadas. Esto en el sentido que todas cumplen con una convención de nombres y denominaciones que facilita su aprendizaje (podemos criticar todo lo que queramos el diseño, sentido o necesidad de muchas librerías de Java, pero al menos son consistentes en sus APIs).

Esta es una excelente oportunidad para que este magnifico lenguaje, que ya ha sentido las tensiones entre el crecimiento y la elegancia, recobre la consistencia interna que a tantos de nosotros enamoró.

Monday, May 28, 2007

La Perfecta Maquina Virtual

La idea de una maquina virtual no es nueva. Antes que C#, antes que Java, incluso antes que el microprocesador, ya habían maquinas virtuales operando en los "mini" computadores de la época.

De hecho, el término "maquina virtual" se ha ampliado haciéndose cada vez mas difuso. Al principio, las maquinas virtuales implicaban un soporte de hardware que permitía que varios sistemas operativos corrieran independientemente en un equipo.

Las maquinas virtuales al estilo Java y .Net son las que han traído el concepto al foco de atención de la mayoría de los programadores en los tiempos recientes. Este tipo de maquinas virtuales son "computadores implementados en software" que corren sobre el sistema operativo anfitrión y que se usan para ejecutar las aplicaciones.

Otro enfoque es el del sistema operativo. La idea es que, dado que la principal función del sistema operativo es hacer una abstracción del hardware sobre el que este corre, el propio sistema operativo constituye una maquina virtual. De hecho, muchas veces los núcleos de los sistemas operativos son llamados maquinas virtuales.

Y es aquí donde viene la atractiva idea de Lina. Si una maquina virtual puede ser tanto una aplicación como el núcleo de un sistema operativo, por que no aprovechar uno de los sistemas operativos libres mas populares y exitosos del mundo? Ese es el concepto tras OpenLina: correr el núcleo de linux sobre windows, OSX y el propio Linux. Las librerías de soporte mapearan llamadas estándar de lina a servicios del sistema anfitrión. Las aplicaciones de lina podrán correr así en cualquier plataforma. Si bien esto es poco mas o menos lo que hace Java, por ejemplo, la novedad esta en que la maquina virtual de lina (el núcleo de linux) es una pieza de software muy madura y excelentemente soportada y con librerías estandarizadas.

Monday, May 7, 2007

Diversión con Monadas

Para el programdor en Haskell, pocos conceptos son tan dificiles de aprehender como las monadas. Existen infinidad de tutoriales sobre el tema y al parecer estos no son suficientes. Su origen en la teoría de tipos y su nombre atemorizante intimidan, al punto que uno de los pilares de Haskell ha comentado que tal vez deban rebaustizarse como las monadas con el titulo de las "cosas difusas y calidas" (warm fuzzy things) con el objeto de hacerlas mas amistosas.

Hay dos elementos que contribuyen a la confusión del recien llegado con las monadas. El primero tiene que ver con su uso especifico para contener los efectos colaterales, es decir la programación no funcional, en particular el sistema de entrada/salida. Esto deja al recien iniciado preguntandose si monadas es sinonimo de I/O.

El segundo elemento que contribuye a la confusión inicial es un menejo del tema desligado de las implicaciones practicas. En Haskell una monada es una clase. Para convertir un tipo dado en una monada hay que implementar las funciones definidas en dicha clase y dichas funciones deben cumplir ciertas de reglas. Un importante conjunto de librerías de Haskell implementan monadas. Todo eso muy bien, pero ¿por que dichas librerías son implementadas así y no otras? ¿Cuando debería un programador desarrollar sus propias monadas?¿Como implemento mi monada?¿Como garantizar que las monadas creadas cumplan con dichas reglas?¿Que pasa si no cumplen con las mismas? Esas son preguntas mas interesantes.

La mejor forma de aprender el significado de las monadas es entender cuando tú como programador deberias implementar una solución basada en monadas. Una vez entendido esto, resulta fácil entender las librerías y saber por que el sistema de I/O de Haskell y el código que produce efectos colaterales es implementado de esa forma. En ese sentido, no hay mejor tutorial que "Tu pudiste haber inventado las monadas! (y tal vez ya lo hiciste)" por sigfpe.

La idea de sigfpe es simple abordar las monadas desde un punto de vista utilitario. ¿Para que sirven?. ¿Que problema resuelven?. Él hace un trabajo insuperable, por lo que aquí me limitare a reexpresar la conclusión a la que llega:

Desde el punto de vista del programador, las monadas son la extensión natural a los functores. Como ya vimos los functores son una forma de mapear las funciones que operan sobre tipos "simples" a funciones que operan sobre tipos "compuestos".
Lo que las monadas permiten es componer funciones cuyo dominio es el tipo "simple" y su rango es el tipo "compuesto" entre si. Sencillo, no?

Eso es todo lo que significa el operador "bind" de la clase Monad:
(>>=) :: m a -> (a -> m b) -> m b
El programador ha desarrollado bastante tiempo creando funciones que toman argumentos simples y devuelven argumentos complejos, como por ejemplo a -> m b, b -> m c y ahora desea combinar esas funciones. Pero como la primera devuelve un valor compuesto (m b) y la segunda requiere un valor simple (b), necesita alguna forma de "sacar" (b) de (m b) para introducirla en la segunda función. Eso responde todas las preguntas planteadas sobre las monadas, como se vera a continuación.


Cuando debería un programdor desarrollar sus propias monadas?

Cuando desarrolla su propio tipo "compuesto" y necesita componer funciones del tipo "simple" hacia el tipo "compuesto".


Por que ciertas librerías en Haskell estan implementadas como monadas?

Porque dichas librerías implican tipos "compuestos" y funciones que devuelven este tipo de valores y que es útil componer. Así por ejemplo, la librería IO no trabaja diretamente sobre enteros, reales y caracteres sino sobre tipos derivados {tipos que contienen de forma oculta el estado del universo y que podriamos sentirnos tentados a representar como (entero, mundo), (real, mundo) y (caracter, mundo)}.
Una revision a las librerías que son implementadas como monadas arroja esa constante: tipos compuestos involucrados (a veces habilmente ocultos) y funciones sobre ellos que es conveniente componer.


¿Como implemento mi monada?

Al crear el tipo compuesto; al necesitar componer las fuciones el programador ya sabe como implementar la monada. Sin un ejemplo en esta pagina puede sonar bastante abstracto, pero el tutorial de sigfpe ofrece suficientes ejemplos y ejercicios. Basta decir que la naturaleza misma del tipo compuesto y su uso deseado sirve para definir la monada.


¿Como garantizar que las monadas creadas cumplan con las reglas de las monadas?

Uno de los temores del programador recien iniciado a las monadas y que las aprendió por su definición es temer que su implementación de una monada sea invalida. Esto ocurre cuando se trata de imponer el concepto no bien internalizado de una monada sobre un problema. En el momento en que el programador se da cuenta que implementar una monada es implementar la composicion entre funciones de una forma que tenga sentido para el tipo "compuesto", el temor a implementar incorrectamente una monada desaparece.


¿Pero que pasa si mi monada no cumplen con la leyes?

Esa situación es perfectamente posible y tiene un término técnico que la describe, se le denomina bug. una monada que no cumple con sus leyes es, desde luego, inútil. Pero ello significa simplemente que tú como progrmador cometiste un error en la función que crea un valor "compuesto" a partir de un valor "simple", o que la función de composición no esta correctamente definida. Es un bug como cualquier otro, no hay nada místico en ello.


Wednesday, April 11, 2007

Sobre los Tipos de Datos Algebraicos y la Abstracción

Desde el comienzo de la computación electrónica ha habido dos campos en el desarrollo de los lenguajes de programación: los que buscan velocidad y los que buscan expresividad. Los primeros se caracterizan por su poco nivel de abstracción. Las características del equipo donde corren son visibles al programador y este, en su trabajo, debe preocuparse por ellos. El ejemplo clásico es el lenguaje C.

El otro tipo de lenguajes, representados por scheme, lisp, haskell y varios lenguajes de scripts, busca la abstracción. El programador debe preocuparse por expresar el problema en los términos mas cercanos al mismo, sin hacer consideraciones o concesiones a la plataforma.

Para alcanzar tan loable objetivo, pocas herramientas son tan útiles como los Tipos de Datos Algebraicos o ADT, por sus siglas en ingles. La idea de los tipos algebraicos es permitirle al programador definir nuevos valores primitivos y a partir de ellos generar nuevos tipos, combinando los valores, bien sea por medio de la unión de conjuntos o su producto.

Un ejemplo permitirá mostrar el valor de los ADT como medio de abstracción, comparando la solución a un problema en C, Haskell y, por diversion, BASIC.

Si bien BASIC sería bajo los estándares actuales un lenguaje de script, y por lo tanto mas abstracto, me referiré en cambio a las primeras versiones de BASIC, antes de Visual Basic o Turbo BASIC; un lenguaje mas cercano a la idea original, para correr en una maquina con menores recursos. Hablemos del BASIC que corría en un equipo como el Commode 64 o el Sinclair ZX Spectrum.

El problema en cuestión es extremadamente simple: representar un mazo de cartas. Cada carta tiene una pinta que puede ser corazón, pica, diamante o trébol y un "numero" que puede ser los números del 2 al 10, las letras "A", "J", "Q" o "K".

En un lenguaje de programación contemporáneo una carta podría ser representada por un registro o un objeto, de acuerdo al paradigma para el cual el lenguaje este optimizado. En el BASIC que tengo en mente, conceptos como registros y objetos son términos muy avanzados. Como se representa un registro en tal BASIC? Fácil: con variables separadas, siendo responsabilidad del programador mantener en su cabeza la asociación entre tales variables. Así la J de trébol podría representarse como:
10 c1p = 4
20 c1n = 11
El 10 y el 20 son los "números de linea". Cada linea del programa debía tener un numero, el cual era usado como medio para acceder a la misma por los primitivos editores que era menester hacer caber en 8KB de memoria o menos.

Sin embargo esta solución es suboptima. Los números mágicos 4 y 11 son una mala señal. En un lenguaje cuyos únicos tipos son los números reales, los arreglos y las cadenas de caracteres es poco lo que se puede hacer, mas allá de representar las pintas y los "numeros" especiales de las cartas con constantes:
10 c1p = 4
20 c1n = 11
10 CPCORAZON = 0
20 CPPICA = 1
30 CPDIAMANTE = 2
40 CPTREBOL = 3
50 CNA = 1
60 CNJ = 11
70 CNQ = 12
80 CNK = 13
...
500 c1p = CPTREBOL
510 c1n = CNJ

Mencione que la mayoría de los BASIC de esa época eran insensibles a las mayúsculas y minúsculas y que tenían un limite en el tamaño del nombre de las variables?

Ahora, para representar a un mazo de cartas, se necesita un arreglo... mejor dicho dos arreglos. De nuevo, hay que mantener separados las pintas de los números y hacer la asociación mental durante la escritura del programa.
590 rem el comando dim crea un arreglo
600 dim mp(52)
610 dim mn(52)
Para inicializar los arreglos, es útil el hecho de que la representación elegida para las pintas y los "números" son ambas numéricas, y como cada carta es diferente puede establecerse una correspondencia entre los naturales y estas:
700 for x = 0 to 51
705 rem cada 13 cartas cambia la pinta
710 mp(x) = int(x/13)
720 mn(x) = (x mod 13) + 1
730 next x
La solución en BASIC es engorrosa. Parte del problema no esta reflejado directamente en el programa, sino que debe ser sobreentendido, en particular la necesidad de usar arreglos diferentes para una sola entidad, o la representación numérica de entes como la pinta y el "numero" de la carta.

La solución en C es mas avanzada. El C nos ofrece ENUMs que es una forma básica de representar tipos de datos no númericos.
enum pinta {Corazon, Pica, Diamante, Trebol};
enum numero {As, Dos, Tres, Cuatro, Cinco,
Seis, Siete, Ocho, Nueve, Diez,
Jack, Queen, King};
Tambien permite definir estructuras (registros), con lo que se solventa el problema de mas de una variable para un solo ente.
struct { enum pinta pinta;
enum numero numero; } carta;
Una solución mucho mas elegante que la elaborada en BASIC, pero no mucho mas abstracta. Un enum es poco mas o menos que un conjunto de constantes con valores enteros creados automáticamente. En nuestro caso, Corazon es solo una forma de decir 0 y Trebol es 3. De hecho, una variable declarada como enum puede contener cualquier valor entero, mas allá de los cuatro valores permitidos.

Una estructura tiene también una representación de bajo nivel que puede ser accedida por el programador. Para un compilador especifico el "numero" de una carta puede estar almacenado cuatro bytes después de su pinta, por lo que obteniendo la dirección de esta, se puede modificar aquella.

En resumen, se ha ganado algo de abstracción, pero solo en la forma. Si el programador se compromete a no efectuar ninguna operación sobre las estructuras básicas subyacentes, es probable que todo le salga bien...

Veamos ahora la solución en Haskell, el único de los lenguajes mencionados en este articulo que tiene ADT. Primero creamos un nuevo tipo de datos algebraico para la pinta y el "numero" de la carta:
data Pinta = Corazon | Pica | Diamante | Trebol
data Numero = As | Dos | Tres | Cuatro | Cinco
| Seis | Siete | Ocho | Nueve | Diez
| Jack | Queen | King

Y luego creamos otro tipo algebraico con el producto cartesiano de los dos antes definidos:
data Carta = Carta Numero Pinta

Igual a lo expresado en C? Solo superficialmente. Pinta es un nuevo tipo de datos, no un entero. Su representación interna por el compilador es desconocida. Tal vez sería una buena adivinanza suponer que es representado por un entero de un byte. Pero adivinar sería fútil, ya que el saberlo es irrelevante: la única forma de operar sobre un tipo algebraico es con las operaciones explícitamente definidas por el programador. Lo mismo ocurre con el tipo Carta. Si, de seguro durante la compilación nuestro tipo algebraico se convierte en una estructura equivalente a la del C, pero eso es un asunto entre el compilador y la CPU. Para el programador es un ítem único e indivisible.

También esta el aspecto sicológico. En el caso del C el programador esta definiendo un layout de memoria y unas constantes enteras. En Haskell, el programador esta declarando que una carta es representada por un "numero" y una pinta, y que la pinta puede tomar solo estos valores y que un "numero" en este contexto son tales otros.

Este aspecto sicológico es un subproducto de la mayor capacidad de abstracción del lenguaje, y es una de las mas importantes contribuciones para el programador.

Friday, March 16, 2007

Saber decir "No"

Que hace a un lenguaje diferente de otro? En el caso particular de los lenguajes de script imperativos, es cada vez mas amplia la lista de características compartidas: las estructuras de control "estructuradas", las listas, los diccionarios, las funciones como ciudadanos de primera clase...

Y sin embargo, programar en Ruby sigue siendo diferente a programar en TCL; programar en python tiene un sabor distinto a hacerlo en perl. Entonces, cual es la diferencia? La raíz en la diferenciación de los lenguajes esta en su filosofía, la idea que guía a sus desarrolladores a decidir que características entran en el lenguaje y como lo hacen.

Paul Graham tiene un articulo interesante al respecto en donde lista los lenguajes de acuerdo al problema que pretenden resolver. Esta puede ser una primera guía sobre la filosofía de los desarrolladores.

En el caso de python, su mantra esta explicado en el 'import this' (pruebe importar el modulo this en un interprete en python). Los dos preceptos fundamentales en el python son la legibilidad y la simplicidad. El lenguaje procura no interponerse en el camino del programador, de manera que el pueda expresar de forma clara sus intensiones. Para ello es fundamental ser sucinto en los conceptos. Por esta razon el punto 13 del zen de python es: "Debe haber una forma obvia de hacerlo --y preferiblemente solo una".

Así, lo que distingue al python es que su filtro para nuevas caracteristicas es: ayuda la característica a expresar los algoritmos de forma mas clara? mas concisa? menos redundante? Y ello lo ha logrado -sorprendentemente, para algunos- sabiendo decir "no" a ciertas funcionalidades.

Después de todo, expresividad no es poder decir una cosa de mil maneras distintas; es poder decir cualquier cosa, al menos de una manera.

Thursday, February 8, 2007

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.

Wednesday, February 7, 2007

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...

Sunday, February 4, 2007

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.

Thursday, January 25, 2007

Alternativa al C: O'Caml

Cuando se habla de alternativas al C, la mayoría de personas piensa en C++, Objective C o Java. Un candidato mas digno, aunque menos conocido es el lenguaje D. Todas estas opciones tienen algo en común: son lenguajes de computación que sigue el paradigma imperativo.

Los lenguajes imperativos se caracterizan por los siguientes elementos:
  • Son dependientes del estado de la computación: Los resultados de los computos dependen de un conjunto de valores almacenados durante la ejecución del programa y que son mutables
  • El flujo de control debe ser totalmente especificado
  • El orden de ejecución debe ser totalmente especificado
Estas características hacen que los lenguajes imperativos puedan ser traducidos mas directa y eficientemente a lenguaje maquina, pero al costo de forzar en el programador la especificación de la solución a un mayor nivel de detalle. Por eso, cuando se busca velocidad, la mayoría de los programadores están predispuestos a buscar lenguajes imperativos. O al menos así solía ser


Bienvenidos a O'Caml

Los lenguajes funcionales por su parte, ofrecen ciertas ventajas al programador:
  • No dependen del estado: Esto elimina un conjunto de errores y permite que el código sea mas auditable (de hecho el código puede ser demostrado correcto, en el sentido matemático del término)
  • Composición de programas: Pequeños segmentos de programas pueden ser combinados de manera sencilla, permitiendo la generación de código complejo expresado sucintamente
  • El flujo de control y/o el orden de ejecución no necesita ser indicado explícitamente
O'Caml es una interesante encarnación de los lenguajes funcionales. Ofrece todas las ventajas descritas (con la excepción del orden de ejecución, el cual sigue siendo explicito). Además, permite programar en otros paradigmas como el imperativo o el orientado a objetos. Agreguesele a ello su robusto sistemas de tipos, el cual permite detectar muchos errores en tiempo de compilación y generar un código super-optimizado.

Adicionalmente, O'Caml parece haberse trazado una meta poco común para los lenguajes funcionales: competir en el terreno de los lenguajes imperativos. Así, O'Caml ofrece librerías para la programación bajo UNIX, depuradores, profilers...

Esto hace del O'Caml uno de los lenguajes mas interesantes y rápidos del vecindario [1], apto incluso para la programación de bajo nivel. De hecho, mientras escribía la entrada respectiva al lenguaje de programación D, para familiarizarme con el, decidí implementar el programa supervise de Dan Berstein. Pues, para mi sorpresa resultó mas directo hacerlo en O'Caml que en D, debido al mejor soporte de las librerías del sistema (el D es facílmente extensible también; no se trata de una crítica al lenguaje D, sino un reconocimiento a las librerías estándares de O'Caml)


[1] Si, si. Son micro-benchmarks. Si, si. Estas pruebas no representan el uso real de los lenguajes in the wild, y todas las advertencias de costumbre cuando se habla de benchmarks. Pero... mientras no haya una forma científica de comparar los lenguajes, una prueba justa es al menos un indicativo a considerar.

Friday, January 19, 2007

Que viene despues de "C"?: "D"

Habiendo establecido que el lenguaje C es una opción cada vez menos atractiva para la programación de sistemas, cabe preguntar: cual es la alternativa? Existen varias, entre ellas:
  • C++
  • D
  • OCaml
  • SML
La opción mas obvia, el C++ es la menos interesante. Dado que el C++ es una extensión del C cuyo objetivo era mantener la compatibilidad con el mismo a nivel de código fuente, presenta las mismas debilidades. C++ es decepcionante en muchos aspectos. No va lo suficientemente lejos en su intención renovadora. Ofrece programación orientada a objetos y templates, pero no hace ningún esfuerzo por eliminar las debilidades del C. No agrega recolección de basura y su sintaxis es perversamente compleja. Pese a todo ello el C++ conquisto parte del mercado del C.


Por que?

Precisamente debido a su bajo perfil pudo el C++ colarse en el mercado. Casi puedo escuchar el razonamiento de los primeros gerentes en adoptarlo en sus proyectos: "Quieres cambiarlo todo para que nada cambie? Quieres mantenerte a la moda sin arriesgar un ápice? C++ es para ti". Sumele a ello la inercia de la interacción con librerías y código heredado, el temor al reentrenamiento, y tendremos un panorama en el que el el heredero de C debía provenir de su mismo linaje.
Desde luego, también estaban los programadores que deseaban probar el paradigma de la programación orientada a objetos y no conocían nada mejor. Como podrían conocer otra cosa? Quien les hablaría de otros paradigmas, como la programación funcional o implementaciones mas radicales y puras como Smalltalk?


En donde nos deja todo esto?

Existen otros lenguajes no emparentados directamente con el C que permiten la programación de sistemas y ofrecen una velocidad igual o superior. En efecto, el C, el lenguaje mas veloz de la cuadra, el hasta hace poco imbatible líder en rendimiento, se ha visto superado por otros contenedores, los cuales ofrecen además mejoras en otras áreas.


D


Sobre las alternativas en el paradigma funcional (OCaml y SML) hablaré en otra ocasión. Centremonos en el mas clásico D. El lenguaje D es a la programación de sistemas lo que Java es a la programación de aplicaciones generales: la satisfacción a la promesa incumplida por C++ de un mejor C.

D no pretende ser compatible a nivel de código fuente con C. Sin embargo, si ofrece compatibilidad a nivel binario. Esta característica clave ya lo separa del montón. Para que un lenguaje de alto rendimiento aspire tener algún éxito, debe necesariamente poder interoperar con las librerías heredadas. Muchos lenguajes conceptualmente mas interesantes que el C han fracasado por el problema del huevo y la gallina (o es el programador y la librería?): El lenguaje es interesante pero no se usa para el desarrollo porque no tiene suficientes librerías, las cuales no son escritas porque no hay suficientes programadores trabajando en el lenguaje porque... no tiene suficientes librerías.

D ha escapado graciosamente a este circulo vicioso al no reinventar la rueda. Las estructuras de datos entre C y D son compatibles. Además, D usa la misma ABI que C. Esto significa que, dado un binario, no hay forma de distinguir si proviene de código fuente escrito en C o en D.

Pero D ofrece mucho mas que compatibilidad binaria:
  • Recolección de basura con capacidad de ser desactivada, permitiendo el manejo manual de la memoria.
  • Programación orientada a objetos.
  • Eliminación de las arbitrariedades e inconsistencias del C.
  • ...manteniendo una sintaxis semejante.
  • Eliminación del preprocesador de texto.
  • Un poderoso sistema de tipos.
  • Las mas importantes estructuras de datos están predefinidas en el lenguaje.
  • Implementación en software libre.
En definitiva, en la clase de lenguajes imperativos destinados a la programación de sistemas o aplicaciones, ya existe una alternativa viable a C/C++. Solo el miedo irracional a nuevas alternativas mantendrá al C en su posición actual.

Monday, January 15, 2007

Migración a Blogger

He migrado todas las entradas del blog a un nuevo proveedor, http://www2.blogger.com/. Por esta razón todos los post previos a este tienen la misma fecha.

El mal C

No deja de resultar paradójico que las características que hacen que un lenguaje triunfe suelen ser las mismas que ocasionan que este deje de ser una alternativa viable. Esta aparente paradoja se entiende cuando se analizan los cambios en el entorno: mientras un lenguaje sigue siendo básicamente el mismo conforme pasa el tiempo, el poder de computo, la memoria y el tipo de problemas evolucionan continuamente.

En una entrada anterior comente que hizo grande al C. Ahora comentare por que el C es cada vez menos una opción valida en un conjunto cada vez mas grande de problemas.
Las principales características que evidencian la edad del C son:

  • Sin colección de memoria
  • Sistema de tipos débil
  • Muy de bajo nivel
  • Pobre especificación

La falta de un recolector de memoria, la cual es una atractiva característica en la programación de sistemas es una pesadilla en casi cualquier otro ámbito. Con excepciones limitadas a cierto tipo de problemas, el ser humano no es mejor administrando la memoria que el compilador. Esta simple verdad es difícil de aceptar por los miembros de la vieja escuela, incluso cuando ellos mismos confían rutinariamente en el compilador para optimizar su código.

El sistemas de tipo del C es otra de esas características que son una bendición/maldición. En el momento de su diseño, el sistema de tipos del C era elogiable: lo suficientemente simple para ser implementado sucintamente, lo suficientemente poderoso para generar código optimizado, lo suficientemente flexible para competir con el ensamblador. Eso fue entonces. Ahora existen sistemas de tipos mas poderosos que permitir expresar los problemas de manera mas clara y ahorrar lineas de código. Estos mismos sistemas, al ser mas estrictos, permiten hacer mas y mejores optimizaciones, por lo cual el C ya no es el lenguaje mas rápido del oeste (véase el lenguaje D, Ocaml o SML).

Otro aspecto que ha cambiado en el ecosistema, es que con el aumento en la velocidad de los procesadores y su memoria, muchas tareas privilegian el tiempo de programación sobre el tiempo de ejecución. Esto hace que el C sea un lenguaje de muy bajo nivel. La administración de sistemas, la cual se hacia antes con C, se hace ahora con bash, perl o python. El desarrollo de aplicaciones web es dominada por lenguajes interpretados. Incluso el uso de lenguajes mas flexibles ha llegado al escritorio de la mano de java/C#-mono/tcl-tk/python.

El ultimo punto, la pobre especificación del C tiene que ver con el hecho que el lenguaje, en aras de permitirle al implementador obtener la máxima eficiencia en la plataforma de destino, se negó a regular de manera completa el comportamiento del lenguaje. Aunque admito que este seria un problema aun mas grave de no haber sido superado por la incompatibilidad entre librerías en el mundo UNIX…

El buen C

Con mas de treinta años de existencia, el lenguaje C aun es uno de los mas usados para escribir las aplicaciones con las que el usuario final se relaciona. Virtualmente todos los sistemas operativos de uso masivo son escritos en el, al igual que muchas aplicaciones en las que la velocidad es critica.

Si bien las costuras del lenguaje tienen tiempo siendo evidentes, hoy quiero escribir de las características que hicieron al C atractivo durante este periodo. En otro momento escribiré sobre los elementos que lo hacen hoy día, a mi modo de ver, dispensable.

En la época en la que el C fue desarrollado los recursos del sistema eran sumamente escasos para los estándares actuales. Los costosos minicomputadores median su memoria en Kilobytes en vez de gigabytes y la programación en ensamblador aun era común.

Bajo estas condiciones el C hizo lo mejor que pudo:

  • Permitir expresiones aritméticas y lógicas en alto nivel, siguiendo la tradición de los lenguajes imperativos que lo precedieron.
  • Permitir el manejo de la memoria con una flexibilidad comparable al del lenguaje ensamblador.
  • Usar un sistema de tipos que permite la generación de código optimizado.
  • Dejar el manejo de memoria al programador.

Estas características le valieron al C el ser considerado el lenguaje de “alto-bajo nivel”: lo suficientemente alto como para que no fuera tedioso escribir código para el procesamiento de datos y lo suficientemente bajo para sustituir al ensamblador el 99.9% de las veces. Sumesele a ello que fue el lenguaje utilizado para escribir el sistema operativo UNIX y se tiene una combinación ganadora.

La razón por la que el lenguaje C se ha mantenido saludable durante estas décadas (además de la inercia causada por el volumen de librerías a su disposición) es que durante todo este tiempo no ha habido alternativas creíbles e interoperables que permitan hacer programación de sistemas. El controlar ese nicho ha mantenido la preponderancia del C en la escritura de sistemas operativos y librerías de soporte.

Tal situación podría estar por cambiar, aunque eso es motivo para otro post.

Hacia el Sistema Operativo del siglo XXI

Hay muchos conceptos interesantes en el desarrollo de sistemas operativos. Buena parte de ellos son diseños totalmente nuevos. Si bien el desarrollo desde cero ofrece el terreno óptimo para la innovación, experiencias del pasado sugiere (el computador personal, MSDOS, ethernet…) que la evolución de los sistemas actuales tiene mayores probabilidades de éxito.

En este orden de ideas, cuales son las áreas en las que Linux necesita evolucionar para hacerse mas flexible y coherente? He aquí algunas posibilidades:

  • Una nueva jerarquía en el filesystem: La jerarquía de directorios de linux, si bien es mas coherente que la de Windows, aun tiene mucho espacio para mejorar. Otros Unixes ya han comenzado el proceso, desde NeXT, hasta Mac OSX. Un ejemplo interesante dentro del mundo del Linux es Gobolinux.
  • Paquetes para aplicaciones: Los sistemas de paquetes dependen de la jerarquía actual en el sistema de archivos, lo cual tiene sus inconvenientes: esparcen los archivos de una apelación entre varios directorios y tienen dificultades con múltiples versiones de librerías.
  • Un nuevo sistema de archivos: En particular uno que permita asociar propiedades a los archivos. La mas reciente versión de ReiserFS podría permitirlo a través de plugins.
  • Nuevos mecanismos de seguridad: La seguridad de UNIX basada en usuario-grupo-otros ya esta mostrando su edad. Si bien es suficiente para muchos entornos, en la actualidad ya hay varias opciones con distintos grados de utilidad.

Estos cambios son superficiales y pueden implementarse en nuevas distribuciones sin tocar el núcleo. Hay otras mas ambiciosas, las cuales requieren abandonar Linux tal y como lo conocemos. En futuros artículos comentare algunos de esos cambios.

Uno en particular, es abandonar el mantra de UNIX “todo es un archivo”. Es cierto, esa concepción fue una de sus grandes fortalezas, y tal vez la mas influyente. Sin embargo, la vieja conseja nunca fue del todo cierta. Comenzando con la división entre dispositivos de bloque y de carácter. Adicionalmente, las infames llamadas ioctl también conocidas como todo-lo-que-no-cabe-en-la-interface-de-archivos-va-acá. Un paso adelante seria el reconocimiento que todo no es un archivo y adoptar un enfoque mas liberal. En vez de tener una jerarquía de archivos, el sistema seria un espacio de nombres de objetos.

Sustituir “archivos” por “objetos” puede sonar cosmético, pero elimina la necesidad de ioctl, homogeniza los conceptos y permite al SO adaptarse a necesidades cambiantes. Desarrollare el concepto en próximo artículos.


Por que calcular es mejor que esquematizar?

En http://www.cs.kent.ac.uk/people/staff/dat/miranda/wadler87.pdf se puede encontrar el paper de Philip WadlerWhy calculating is better than scheming”. Este paper compara lenguajes de la familia lisp/scheme con lenguajes tipo miranda/haskell en el contexto del excelente libro de Abelson y SussmanStructure and Interpretation of Computer Programs” (SICP).

El paper analiza temas aun no resueltos en el área como:

  • Definición de tipos
  • Notación prefija vs. infija
  • Las virtudes del sistema de macros de lisp

Su conclusión? Que la notación infija, la posibilidad de declarar tipos de datos, el uso de tipos de datos algebraicos y el emparejamiento de patrones hacen que la intención del programador sea expresada de manera mas clara y concisa; que la identidad entre código y datos en lisp puede ser un importante factor de confusión para los programadores noveles (y los no tanto); que la evaluación perezosa ofrece una elegante homogenización de los lenguajes que la poseen.

En definitiva, lisp no sale muy bien parado en el análisis de Wadler. Tal vez ello le condujo al desarrollo de Haskell

Sobre Strong Typed

Strong Typed es un blog dedicado al estudio de la ciencia de la computación, programación y sistemas operativos. Otros temas afines, en lo tocante a matemática también tienen cabida acá.