Programación imperativa vs declarativa I

En general, que el futuro de la programación será (casi seguro) programación declarativa, es algo que difícilmente puede negarse. Ya sólo la gestión eficiente del flujo de eventos en una sencilla aplicación de escritorio puede dar algún que otro quebradero de cabeza y si nuestros procesos consumen algo de procesador, hacerlo eficiente para diversas condiciones (pocas o muchas CPU, memoria, …) requiere paciencia y talento (una buena paralización no es “poner una tarea en cada núcleo”), aderecemos el plato con flujos sincronizados de datos a través de la red y disco y ya tenemos el “comerecursos” perfecto.

Parece que la programación imperativa es cada vez más costosa, mientras que la programación declarativa nos atrae cada vez más con sus cantos de sirena. Si te apetece, pensemos sobre ello en nuestra “programación imperativa vs declarativa” particular.

Los costes de la programación imperativa

Desde hace mucho tiempo me pregunto cómo es posible que en mi 8088 a 12 MHz con 512Kbytes de RAM las aplicaciones corrieran maravillosamente (había aplicaciones muy buenas, de editores de texto, suites ofimáticas más que aceptables y fue esa época [hasta el 386] mi época dorada de los videojuegos). Hoy en día es evidente que los ordenadores hacen muchas más cosas (eg. la memoria de vídeo que tienen que gestionar es ahora 1920×1080×32 / 640×200×2 = 259.2 veces más que antes), pero la capacidad de cálculo se ha multiplicado en muchas más veces; por ejemplo, la calidad de las arquitecturas ahora es muchísimo mejor (a igual velocidad de reloj, los procesadores actuales son decenas y centenas de veces más eficientes), tienen tamaños de palabra 8 veces mayores (de 8bits a 64bits), los compiladores generan código muchísimo más optimizado sobre algoritmos más sofisticados (que antes no existían) y aún sin tener todo ésto en cuenta, ahora la cantidad de proceso es 2×2500 MHz / 1×12MHz = 417 veces más, pero es que resulta ¡que la CPU no renderiza, pues hay otra GPU sólo para eso!. ¿Porqué entonces mi ordenador (¡para ver una simple página web!) no va raudo como el rayo?, ¿por dónde se está yendo esa capacidad de cálculo de mi ordenador?.

La respuesta la tenemos en “la complejidad combinada”, dicho rápidamente sería como que: “la complejidad total resultante, es mucho mayor que la suma de la complejidad de las partes”. Por ejemplo, si tenemos que hacer un programa, solemos dividir grosso modo, la funcionalidad total del programa en pequeñas partes que vamos resolviendo individualmente. Así, resolvemos eficientemente las pequeñas partes, pero al combinarlas, obtenemos soluciones ineficientes.

Por un lado, nosotros no somos capaces de abarcar una visión global pero precisa simultáneamente del sistema y por otro, el compilador no puede ayudarnos a suplir este problema. Así, todo problema (medianamente complejo) que nosotros no seamos capaces de resolver, la programación imperativa tampoco lo conseguirá.

Voy a poner un ejemplo, supongamos que tenemos las siguientes funciones en C ¿qué haría el compilador?:

Vamos a desgranar la estrategia obvia y la estrategia óptima que ha logrado el compilador (GCC 4.7.1). Primero el ensamblador resultante:

Empecemos:

• mod4 se resuelve “tontamente” realizando una división, pero alguien ha dicho al compilador que el resto de dividir entre 4 en base 2, son precisamente los dos bits menos significativos. Es muchísimo más económico (en términos de tiempo de procesador) hacer una operación and que una división.

• div4, de forma similar, alguien ha dicho al compilador que dividir por 4 en base dos es desplazar los bits a la derecha ignorando los 2 menos significativos.

• divX, ¿pero que pasa si el divisor tiene un valor desconocido? (al compilar), pues que no se puede optimizar.

• divX4, vaya, alguien ha dicho al compilador que expanda las funciones a ver si puede optimizarlas inline y aquí le ha funcionado.

• sumDiv5, ¿y si llamamos a la función no optimizada un número constante de veces?, otra vez, alguien ha dicho al compilador que puede desenrollar el bucle, aplicando el cuerpo interno del mismo inline y realizando las optimizaciones cuando se pueda (sólo dos divisiones reales cuando en el código se han indicado cinco).

• distributiva, ¿que pasa aquí?, ¿porqué no ha reducido un cálculo tan sencillo?, no ha sido capaz de reducir ese código a: “un incremento, dos multiplicaciones y un desplazamiento de un único bit ((PN(N+1))>>1)”. Hay que reconocer, que ha reducido elegantemente la multiplicación por una serie (P, P+P, P+P+P, …). Quien arguya que puede haber desbordamientos, éstos se pueden predecir fácilmente (y bifurcar en el peor de los casos). Es decir, si N=1000 resulta que se realizarán 1000 saltos (con sus 3000 sumas). ¡Pero todo se reduce a 4 sencillas instrucciones!. Nosotros no hemos sabido resolver el problema (por eso hemos iterado), pero el compilador tampoco (no ha sabido reducir nuestro código).

“Entonces, ¿hemos solucionado el problema?”, siento decirlo, pero no. “¿Y si vamos acumulando sabiduría optimizadora?” (le decimos más cosas al compilador), pues tampoco, porque el número de combinaciones en las estrategias resultantes crece a una velocidad gigantesca, de hecho, sólo con el código escrito actualmente cabrían hacer muchísimas optimizaciones más de las que son capaces los compiladores actualmente.

Los problemas que tienen los compiladores (de lenguajes imperativos) son realmente tres:

• Primero, los compiladores (actuales, claro) no son capaces de inferir (deducir, adivinar, pensar, …) una optimización que no haya sido explícitamente programada previamente. Por tanto, nunca pueden mejorar el algoritmo indicado por el programador, en todo caso, lo hacen más rápido (si ya, en sí es una mejora, pero el algoritmo sigue siendo el mismo), por ejemplo, reemplazando una forma de dividir por otra. Vaya, que si un programador escribe un mal algoritmo, seguirá siendo malo tras compilar (con instrucciones superoptimizadas, eso sí, pero malo).

• Segundo, aunque el programador escriba un algoritmo óptimo, los compiladores actualmente no pueden obtener el conjunto mínimo de instrucciones que corresponden con el programa escrito. Ésto es así, porque los compiladores sólo saben optimizar lo que se les ha dicho explícitamente que optimicen.

• Tercero (y el más importante), el código que escribe un programador hoy, está escrito en el contexto actual, mañana, lo más probable, es que quede obsoleto. Con obsoleto, me refiero a que mañana, si se quiere que ese programa saque ventaja de las nuevas mejoras (técnicas, en algoritmos, hardware, …), habrá que recodificarlo, que reprogramarlo, y ningún compilador lo hará por ti (no te confundas, si tienes un programa que usa una librería y la librería es optimizada, tu programa va más rápido precisamente porque se ha recodificado la librería, tu programa sigue siendo igual de bueno o malo que antes).

Resumiendo, nada de lo que hacen actualmente los compiladores sirve para minimizar la creciente “complejidad combinada” en nuestros sistemas. Es decir, si quieres un algoritmo, un programa, un sistema eficientes… cúrratelo, pero además, si quieres que tu programa sea eficiente mañana, cúrratelo mañana otra vez. Además, no puedes esperar que el compilador detecte tus ineficiencias, por tanto, si quieres un código eficiente… cúrratelo dos veces.

NOTA: en cuatro párrafos es imposible analizar y cubrir todos los aspectos y contraejemplos que pueden ponerse, el escribir una inteligente jerarquía de objetos sólo hace que tu código dure más tiempo, hablar de una función obvia (y aburrida) que se va a usar hoy y dentro de dos siglos (eg. la media aritmética) no quiere decir que el problema que planteo sea sostenible indefinidamente en el resto de programas y para todas las tecnologías futuras, etc…

Por poner algún ejemplo más, ¿cuantos de tus programas podrían correr sin recodificar bajo CUDA?, si mañana sacan la primera computadora cuántica (no, esa no, la de verdad) ¿crees que tu código podrá correr eficientemente en ella?, Intel está estudiando procesadores de uso general con cientos o miles de cores ¿aprovecharían tus algoritmos esa potencia?, etc…

Programación declarativa

Creo que podemos decir que es célebre la frase que describe a la programación declarativa: “di qué quieres, pero no cómo lo quieres”.

En última instancia por tanto, el objetivo último de la programación declarativa sería “plantear el problema coloquialmente (posiblemente libre de ambigüedades) y obtener la solución automáticamente”. No vamos a ser tan ambiciosos y espero que sepas entender el contexto (real y actual) sobre el que se hace la comparativa.

Una vez hemos definido la programación declarativa, pactemos que no vamos a retorcer el lenguaje para llegar a absurdos como: “yo en C le digo que quiero un bucle, no cómo lo quiero” y cosas similares. Es cierto que entre la programación imperativa y la declarativa existe una suave y alargada gama de grises. Al fin y al cabo, intento ceñirme a situaciones prácticas y los ejemplos declarativos que pondré a continuación, están limitados por la capacidad tecnológica (y teórica) actual.

En la práctica, sea el lenguaje que sea, un lenguaje es imperativo respecto de los problemas que no sabe resolver por él mismo. Y será declarativo, respecto de los problemas que sí sabe resolver por sí mismo. La medida entre uno y otro, nos dirá si se trata de un lenguaje imperativo o declarativo.

SQL (Structured Query Language)

No se me ocurre otro lenguaje declarativo más conocido, usado y prolífico que SQL. Si bien debemos reconocer que el problema que resuelve está bien definido y acotado (lo cual hace que sea más fácil resolverlo que si ésto no ocurriera), el producto resultante (SQL) es una auténtica joya. Sus profundas raíces, que parten de las lógicas formales, han nutrido un poderoso árbol cuyos frutos seguimos disfrutando hoy en día (y sin visos de ser reemplazado; no, NoSQL no lo sustituye). Te animo a que leas (ver referencias) sobre los orígenes de tan magnánimo lenguaje.

Siguiendo la definición dada anteriormente, SQL es imperativo respecto los problemas que especifican qué se quiere hacer con los datos, pero es declarativo respecto cómo recuperar esos mismos datos. Es decir, SQL no sabe (no provee formas de) decidir por sí mismo si tiene que combinar la tabla A con la B, pero una vez se lo hemos dicho (“combina la tabla A con la B”), sabe hacer el resto de forma muy eficiente.

(No entremos a discutir si SQL es o no un lenguaje al uso, pero piensa, que cualquier proceso puede reducirse a una concatenación finita de sentencias SQL).

Veamos un ejemplo con SQL y las implicaciones respecto el tema que nos ocupa:

En Solveet propusieron un problema que simplificaré por múltiples motivos: “nos dan una lista de canciones, de ellas sabemos que pueden ser de los 70, de los 80 o de los 90 y la duración. Nos dan un portacedés y en cada hoja caben tres cederrones. Nos piden que rellenemos el portacedés de tal forma, que en cada hoja haya un cederrón de los 70, de los 80 y de los 90, que la duración de las canciones sea decreciente (para que al final de la fiesta sean lo más cortas posibles) y que haya hojas con cederrones suficientes para poner música durante un tiempo prefijado (pero no hay que llenar más hojas de las necesarias, no vamos a llevar más peso del que haga falta)”.

En SQL, una posible solución sería la siguiente:

No es complicado lo que se está haciendo: se divide la lista en tres conjuntos (70, 80 y 90), con sus canciones enumerados desde la más larga a la más corta, y se identifican los elementos que tienen el mismo ordinal. Para obtener sólo los tripletes que nos interesan, sólo recuperamos aquellos cuyo tiempo acumulado (desde el más largo hasta él mismo) alcanza el tiempo total de la fiesta.

De todos modos, lo interesante, es que nosotros hemos indicado al sistema, con sentencias SQL, cómo queremos combinar los datos, pero no cómo recuperarlos. No le hemos dicho si tiene que paralelar tal o cual parte, no le hemos dicho si tiene que leer los datos en un orden u otro, si tiene que iterar tal o cual archivo, etc…

El resultado, es que (sin ninguna preparación o análisis previo) el motor de bases de datos a generado el siguiente plan de consulta:

No importa si no ves bien que hace exactamente el plan, lo importante, es que ha conseguido seis flujos de trabajo que pueden realizarse en paralelo desde el primer instante.

Pero más importante todavía, es que:

• Aunque la consulta la hubiéramos escrito de otra forma, si implica la misma recuperación de datos, obtendríamos el mismo plan de consulta óptimo.

• Si las condiciones de ejecución de la consulta cambian (número muy grande de registros, interbloqueos, más o menos procesadores, etc…) sin modificar la consulta (el “qué queremos obtener”) el motor puede obtener un nuevo plan óptimo de consulta (el “cómo hacerlo”).

• Si mañana se descubren algoritmos o teorías nuevas que permiten combinar los datos con mayor eficiencia, el nivel de abstracción de la consulta escrita, permite introducirlas en el motor de base de datos de forma transparente.

• Si mañana se descubren propiedades físicas o hardware que permitan manipular los datos con mayor eficiencia, el nivel de abstracción de la consulta es lo suficientemente elevado para que pueda evaluarse en ese nuevo hardware.

(NOTA: SQL no es infalible, en determinadas ocasiones es preciso replantear las consultas de diferente forma para que “se de cuenta” de que otro plan de ejecución es posible o bien indicarle mediante “consejos” cómo debe acceder a determinados datos. Sin embargo, en la mayoría de los casos, las implementaciones de SQL son lo suficientemente buenas para obtener resultados muy eficientes que, de otro modo, nos obligaría a pensar en términos de los procesos subyacentes: lectura en disco, paralización, etc… SQL no es perfecto, pero es la leche).

La programación declarativa, hoy

Sin duda SQL es un logro impresionante, podemos pensar en conjuntos de datos sin importar los mecanismos subyacentes (eg. es frecuente separar los conjuntos abstractos de datos en diferentes conjuntos físicos de archivos para paralelar el acceso a disco, un mayor número de ejes [discos] permite paralelar las lecturas y escrituras en disco). Pero su área de aplicación es realmente limitada, un lenguaje de propósito general (y SQL no lo es) debe tener la suficiente flexibilidad para expresar una gran variedad de problemas.

“¿Qué lenguajes declarativos están disponibles?, ¿en que medida son útiles en la práctica?, etc…”.

Seguro que estás pensando en la programación funcional y, efectivamente, la programación funcional es la programación declarativa de propósito general más conocida (hay otras), sin embargo, para poder tener una visión más amplia de la situación actual, sus problemas y sus posibles soluciones, antes debemos detenernos en dos paradas más:

• Cálculo simbólico.

• Demostración automática de teoremas.

En el siguiente post, comentaremos estas dos técnicas que se complementan y nos darán una idea del tipo de problemas a los que se enfrenta una útil aplicación práctica de la programación declarativa.

En Genbeta Dev | Diferencias entre paradigmas de programación.
Más información | SQL, Relational algebra, Tuple relational calculus.
Más información | Symbolic calculation, Demostración automática de teoremas.