Programación genética con ruby, lisp y java
Últimamente he tenido que trabajar en una implementación de juguete de un algoritmo de programación genética, uno de los miembros más jóvenes de la familia de métodos de computación evolutiva, de la que también forman parte otros formalismos más conocidos como los algoritmos genéticos o las estrategias evolutivas.
La idea es sencilla y a la vez increíblemente sugerente, crear algoritmos que sean capaces de generar otros programas con la capacidad de autogenerarse, siguiendo los mecanismos que rigen la evolución de los organismos biológicos.
El pionero en este campo, John Koza (http://www.genetic-programming.com/johnkoza.html), se refiere a un programa genético como una máquina de invención con capacidades generales y, de hecho, ya ha patentado algunas cosillas producidas por un cluster beowulf con 1000 PC con el que pasa el rato en Stanford.
En mi implementación de juguete el programa no es más que una secuencia operaciones aritméticas básicas (+, -, *, /) sobre un pequeño conjunto de símbolos terminales (|R U {x}) con los que se generan programas que deben aproximar la función 'f(x) = x**2+x+1'.
El algoritmo debía ser capaz de manipular la propia representación del programa, el código, como si fuese un tipo de datos más, para generar nuevas sentencias mediante los operadores evolutivos básicos: recombinación y mutación. Además, se debía, evaluar el código generado, también en tiempo de ejecución, para evaluar el fitness de ese individuo de cara a su selección como padre para la recombinación.
Otras implementaciones de métodos evolutivos, las había realizado en Java, lenguaje en el que ya había construido un pequeño framework para llevar a cabo este tipo de computación. Sin embargo estaba claro que en para este tipo de algoritmos, Java presentaba graves deficiencias, la más importante de las cuales era que debería modelar el dominio del código que debe generar el programa genético en Java: una interfaz función, implementada por clases funcion+, funcion-... con un atributo aridad que indicase cuantos argumentos podían recibir y que pudiese almacenar otros objetos función o símbolos terminales. Además, estos objetos función debían ser capaces de computar la función que modelaban de tal forma que la función + llamase al operador + de java sobre el resultado de sus argumentos.
Esta forma de abordar el problema, hace muy difícil extender este enfoque, ya que, por ejemplo, para cada nueva función que se quisiese soportar, habría que crear la correspondiente clase.
Al final lo que sale a relucir, es la falta de capacidades para realizar metaprogramación y la carencia de dinamismo que acusa Java. La opción ideal sería poder tener soporte para generar código Java usando técnicas de metaprogramación para, posteriormente, evaluarlas dinámicamente.
Esto nos lleva a la segunda opción que consideré, la que en mi opinión mejor se adapta a este tipo de problemas: usar Lisp. Cualquier dialecto de Lisp no sólo soporta estas capacidades de metaprogramación y capacidad de evaluación dinámica, sino que permite manipular el propio código como cualquier estructura de datos del programa, en realidad la única estructura de datos de Lisp, las listas de s-expressions.
En lisp es trivial generar código del tipo: (+ x (/ 1 (+ 2 (* x x)))) y evaluarlas dinámicamente, pero es que además la manipulación del propio código Lisp no presenta ninguna diferencia respecto al resto de tipos de datos del programa (car, cdr, cons, list, list-ref...), con los que implementar los operadores evolutivos.
La pregunta es, ¿qué tal encaja Ruby en este tipo de problemas?. Ruby
tiene (casi) las mismas capacidades dinámicas de Lisp y unas impresionantes capacidades de metaprogramación.
A pesar de todo esto, Ruby se encuentra igual de limitado que Java frente a Lisp, a la hora de generar el código que se debe evaluar dinámicamente. Al final, el código de Ruby son cadenas de caracteres que hay que generar y modificar usando las funciones de manipulación de cadenas que ofrece el lenguaje. Esto supone una gran carencia frente a la potencia que el uso de listas como código y datos, ofrece Lisp, sobre todo en dominios de aplicación como el que estamos tratando, además de vedar el acceso, al menos parcialmente, a algunas de las capacidades más potentes de Lisp, como por ejemplo, las macros.
Con todo lo anterior, la implementación Ruby realizada ha resultado bastante concisa y elegante. Pero no he podido evitar tener que escribir algo de código 'boiler-plate' para construir una clase que modela, de manera abstracta, una función del lenguaje Ruby. Los objetos de esta clase son capaces de transformarse en código Ruby con una llamada to_code y de evaluarse mediante una llamada do_eval. Gracias a las capacidades dinámicas de ruby, añadir soporte para nuevas funciones es algo trivial, pero aún así, las carencias de Ruby frente a Lisp han salido a relucir en muchos aspectos, un ejemplo más: frente a la uniformidad en la notación de Lisp, la función es el primer elemento de la lista, el resto son argumentos, Ruby mezcla la notación prefija e infija, con lo que el modelo de función genérica debe guardar información adicional relacionada con la notación de la función.
En definitiva, que Ruby está a años luz de Java es una realidad, (frente a las 10-13 horas que me había llevad escribir software similar en Java, esta implementación estaba terminada en 3-4 horas), pero a pesar de ello, Ruby no puede igualar las capacidades de un lenguaje de programación con 50 años de antigüedad.
Reflexionando sobre esto, parece que la evolución de las tendencias en el uso de lenguajes de programación nos está acercando poco a poco a lenguajes con características cada vez más similares a las de Lisp, ¿quién sabe si dentro de unos años llegaremos al punto del que partimos hace 50?. Por cierto, curiosamente, el único framework comercial para realizar programación genética que he encontrado está escrito en Java.
