Las estrategias que se siguen para resolver el problema de la programación imperativa (dado un código, conseguir que la máquina lo ejecute eficientemente) son radicalmente distintas (y mucho más sencillas) que las estrategias que se siguen para resolver el problema de la programación declarativa (en general, mucho más complejas). Pero el producto resultante, también es radicalmente diferente.
Para entender cual es el problema al trabajar con lenguajes declarativos y sus soluciones eficientes, vamos a comentar el problema del cálculo simbólico, de hecho, el primero podría considerarse un caso concreto del segundo.
Si te parece esotérico (o muy complejo) que los programas de cálculo simbólico resuelvan complejas ecuaciones emulando a los mejores matemáticos (como ves en la imagen), aquí vamos a programar, con matemáticas muy básicas, una auténtica calculadora simbólica, comparando la estrategia y el producto resultante con soluciones imperativas.
NOTA: en el anterior artículo no supe transmitir de forma clara la gran diferencia cualitativa existente entre la programación imperativa y la programación declarativa. Dividiré el post que pensaba escribir (cálculo simbólico y demostración automática de teoremas) en dos, para intentar aclarar la cuestión. Siento tener que utilizar algunas veces simplificaciones y eufemismos (como cuando digo “algoritmo imperativo”), sólo pretendo picar la curiosidad del lector, no escribir la teoría por volúmenes (que la hay mucha y muchísimo mejor de lo que la pueda explicar yo). Espero que seas comprensivo con mis limitaciones.
NOTA: aprovecho también para hacer una aclaración importante, en toda la serie hablo de las virtudes de la programación declarativa como si hoy ya estuvieran completamente disponibles. El estado del arte de los lenguajes declarativos es más que precario y difícilmente “usables” en la práctica como yo los expongo (aunque los avances son notables). Mi intención es llamar la atención sobre este paradigma como la necesaria evolución del desarrollo de software. Al final de la serie, pretendo concretar el marco práctico actual disponible (eg. Haskell).
Estrategia imperativa, estrategia declarativa
En primer lugar, dejemos claros dos aspectos muy diferentes al comparar los dos paradigmas:
- El punto de vista del programador que utiliza un paradigma y no tiene porqué saber nada de como funciona el compilador (o lo que sea que procesa su código).
- El punto de vista del programador que construye un compilador (imperativo o declarativo) y los problemas a los que se enfrenta.
En la programación imperativa, lo difícil es para el programador [1], pues escribir código eficiente (en C, Java, Go, Python, etc…) requiere que el programador escriba un buen algoritmo, si lo escribe malo, el compilador no le va a ayudar. Por otro lado, para el programador [2], hacer un compilador para un lenguaje imperativo es realmente sencillo, pues sólo tiene que transformar cada sentencia del lenguaje imperativo (for, while, if, etc…) en su contrapartida en el otro lenguaje imperativo. Si, si, es muy fácil, es una práctica habitual que mandan (o deberían mandar) a los alumnos de informática. Obviamente, es cuando queremos generar un código eficiente que la cosa se complica, porque no se puede y lo más que consiguen es hacer optimizaciones puntuales y precarias (eg. la división por cuatro que comentábamos en el anterior post).
Con la programación declarativa ocurre precisamente lo contrario, el programador [1] lo tiene muy fácil, porque da igual si escribe un algoritmo desastroso (eg. itera de 1 a n = 1020 para sumar esos números ¡tardando más de mil años con un procesador a 3GHz!) porque el “compilador declarativo” sabrá (dentro de su ámbito) reducir el problema a la solución óptima (en el ejemplo, a n (n + 1) / 2, menos de un nanosegundo).
Es el programador [2] con la programación declarativa quien lo tiene muy complicado, porque debe ser capaz de construir un compilador que, de alguna forma, sintetice (absorba, conozca, …) toda la información contenida en su ámbito de aplicación (ahora veremos un ejemplo). Es decir, no sólo tiene que identificar los elementos del lenguaje y transformarlos (que también), sino que debe sintetizar todas las interrelaciones existentes y saberlas manipular para obtener el resultado óptimo.
En el ejemplo anterior, hemos escrito el siguiente programa “dame la suma de los números de 1 a n”; así escrito, es claramente un lenguaje declarativo (porque no decimos cómo debe obtener la suma), pero un lenguaje declarativo debe ser algo más (o debería serlo, sino, nos servirá de poco), debe ser capaz de generar (idealmente) la mejor solución para ese problema.
Despejando la X
Para concretar las ideas comentadas, voy a poner un ejemplo de un sistema real de cálculo simbólico. Para hacerlo muy sencillo usaremos únicamente matemáticas de 2º de ESO, por lo tanto, tampoco pretendamos un sistema muy potente. De todos modos, creo que es suficiente para comprender el alcance y esencia de los sistemas de cálculo simbólico.
El problema y ámbito del sistema propuesto
Para no tener que explicar ni comparar otras técnicas que no vienen al caso (eg. cálculo numérico), te pido que imagines el problema como lo ven los alumnos de 2º de la ESO, no pienses en términos de algoritmos. Mi intención, es que imagines todas las capacidades y destrezas que se requieren para resolver el problema que nos ocupa.
Nuestro sistema de cálculo simbólico, debe ser capaz de “despejar la incógnita en una ecuación de primer grado”. Ni más, ni menos. Veamos algunos ejemplos:
Ten en cuenta, que nuestro sistema debe resolver de forma eficiente cualquier ecuación de primer grado. No sólo las que empiecen en 7, no sólo las que por divisor tengan al 4, no sólo “aproximadamente”, no sólo aquella que tiene “pocos paréntesis”, etc… debe resolver eficientemente, cualquier ecuación de primer grado.
Veamos las soluciones a estos dos ejemplos:
Si, no vale como solución indicar 2,625 o -12,727272… y muchísimo menos serviría 2,624095 o -12,727194 (cuya respuesta es la que daría un “algoritmo imperativo”).
Lo importante ahora, es que veamos que, si resolvemos el problema, para nuestro sistema “no habrá misterios” en cuanto a despejar la x en ecuaciones de primer grado. Lo hará perfectamente, y lo hará bien.
Cálculo simbólico
Permiteme que hoy no escriba código, lo escribiré “de viva voz” y confío que sabrás imaginar mentalmente el programa resultante. Los motivos son dos: por un lado, el programa resultante es demasiado simple y por otro, hacen falta dos librerías que son demasiado conocidas como para escribirlas nosotros (que podríamos sin mucha dificultad, pero no es el caso que nos ocupa).
Bien, supongamos que disponemos por un lado de un tipo de dato llamado Racional. Los números racionales son muy conocidos y también se dan en la ESO. Crear este tipo de dato es un ejercicio sencillo pero interesante si queremos practicar la sobrecarga de operadores.
Supongamos también que disponemos de una función que, usando como números el tipo Racional, nos evalúa una ecuación de primer grado, exactamente lo que en JavaScript sería:
function Eval(P, x) {return eval(”(function(x) {return “ + P + “})(” + x + “)”)}
sólo que usando el tipo Racional.
Pues bien, si disponemos de estos dos conocidísimos ingredientes, nuestro algoritmo para resolver simbólicamente nuestro problema es:
Eval(P, 0) / (Eval(P, 0) – Eval(P, 1))
Si, lo se, no impresiona mucho, pero realiza perfectamente su cometido, no hay mejor solución.
(Si quieres ver soluciones completas a este problema, puedes verlas en Solveet).
El poder real del cálculo simbólico
Espero haber transmitido el poder real del cálculo simbólico, las soluciones (cuando se consiguen), son completas, totales, son algoritmos de Dios.
En su ámbito, las soluciones encontradas (y enormemente complejas) de cálculo simbólico son poderosísimas. Encuentran a diario soluciones eficientes (eg. con el menor número de operaciones necesarias) que de otro modo (eg. con cálculo numérico) tardaría horas.
Nuestro humilde ejemplo no es tan poderoso, pero permite a un compilador imperativo reducir el número de operaciones si el programador es torpe y no ha simplificado un polinomio de primer grado en su programa (si, GCC 4.7.1 simplifica las expresiones y consigue reducirlas a una constante ¡gracias al cálculo simbólico!).
Sin embargo, los lenguajes imperativos no pueden aprovecharse de otras reducciones (como la de la serie que he puesto al principio) porque el lenguaje no lo permite (lo embrolla todo como una bobina de hilo desmadejada), cuando son muy habituales en Mathematica, Maxima, Scientific Notebook, etc…
En la próxima, comentaremos el complemento perfecto para obtener un lenguaje declarativo ideal: la demostración automática de teoremas (y sí, construiremos nuestro propio “demostrador de teoremas”).
En Genbeta Dev | Programación imperativa vs declarativa I.
Más información | Symbolic computation, Mathematica, Maxima, Scientific Notebook.
Más información | Ecuación de primer grado en Solveet.