LISP vs. C++

Uno de estos días necesitaba un intérprete de LISP para probar algunos procedimientos bastante simples. Pero resulta que mi conexión a Internet estaba en un mal momento, y por esto el gestor de paquetes decía que instalar el intérprete que tenía disponible iba a requerir más de 50 minutos de descarga. Fue ahí cuando pensé: "puedo escribir mi propio intérprete en menos de 50 minutos". Así que abrí el ZinjaI y lo intenté. 40 minutos y 160 lineas de código C++ después tenía un intérprete para lo mínimo necesario de LISP para los ejercicios que quería probar.

Este post no se trata de comparar las ventajas y desventajas de un lenguaje frente al otro (el título es engañoso). Se trata de responder a preguntas más razonables tales como: "¿cómo entra todo un lenguaje en solo 160 lineas?", "¿cómo se te ocurre ponerte a escribir algo así?", "¿no tenías nada mejor que hacer?", etc.

Voy a empezar por la última: me encantan este tipo de "ejercicios" de programación; me divierten y siempre aprendo algo de la experiencia. Luego, para el "¿cómo se me ocurre?", lo que pasó es que estaba leyendo por primera vez el maravilloso "Structure and Interpretation of Computer Programs" de Abelson y Sussman, libro que toma a LISP como lenguaje principal para el desarrollo de los conceptos, y que dicen todo programador serio debería leer alguna vez en su vida. Y llegué a los primeros ejercicios. Había leído y escuchado mucho sobre LISP y otros lenguajes similares (ya les hablé de estos autores y del paradigma funcional), pero en realidad nunca había hecho práctica (nunca antes toqué un intérprete de LISP). Así que quería resolverlos y probarlos antes de seguir, como para asegurarme de que iba bien.

¿Y qué mejor forma tiene uno de asegurarse de que entiende algo que implementándolo? Dicen que solo sabés algo cuando podes explicárselo a otro. ¿Qué mejor que explicárselo a un compilador? Nadie más estricto y quisquilloso. En fin, alcanzaran o no los 50 minutos, parecía un ejercicio combinado de C++ y LISP muy interesante.

Funciones básicas resueltas en 40 minutos: aplicación de

 operadores, expresiones anidadas, definiciones de "variables"...

Y llegando a la primer y más interesante pregunta, "¿cómo entra en 160 lines/40 minutos?", el principal responsable es el propio LISP. Una de las cosas más maravillosas que tiene este lenguaje es que permite hacer construcciones increíblemente complejas a partir de un conjunto muy muy básico de reglas. En esencia todo es una lista, y los elementos de una lista pueden ser cualquier cosa: constantes, operadores, procedimientos del usuario, más listas, etc. La gracia está en que todo se trata por igual. Es decir, que en el corazón del intérprete, un operador predefinido, una variable, y un procedimiento del usuario son más o menos la misma cosa. No hay trato especial para nadie, y por eso en este mundo son todos ciudadanos de primera clase (funciones incluidas).

Entonces, para interpretarlo necesito: 1) parsear una lista que viene en un string, y 2) darle un significado a cada elemento de la misma. Para lo primero, use la clase std::stringstream, que ya separa por espacios de por si, por lo que solo tuve que hacer un pequeño preproceso para separar los paréntesis, y una pequeña lógica para detectar el anidamiento. Como resultado de unas 25 lines de código sale una lista de cadenas ya cortadas (std::list<std::string>). Para lo segundo, hay un par de funciones que toman esas listas y actúan en consecuencia.

En LISP, siempre el primer elemento de la lista dice cual es el operador/procedimiento que hay que aplicar, y lo que quedan son argumentos. Si lo que hay que evaluar es una lista, uso entonces el primer elemento como clave para un mapa, y el mapa me devuelve la función asociada al procedimiento (std::map<std::string,std::function<...>>). Solo tengo que ejecutar esa función. Si la entrada no era una lista, puede haber sido una variable, o una constante. Las variables serán para mi como procedimientos que no reciben nada, así que el tratamiento es casi igual. Definir esta pequeña casuística y despachar la lista de argumentos a quien corresponda lleva una 15 lineas con control de errores incluido.

 Llegando a la hora ya funcionaba la definición de nuevos procedimientos, 

y el anidamiento de definiciones conocido como "block-structure"

La función a ejecutar puede ser cualquier cosa que tome una lista y un ambiente (el scope, con las cosas previamente declaradas) y retorne un string. Uso lambdas para absolutamente todo. Cargo los operadores built-in (esto incluye "define", "lambda" y hasta los condicionales "if" y "cond") de mi LISP con lambdas (C++) ad-hoc en el main (esta es la parte más grande del código), genero lambdas que simplemente retornan un valor para representar variables, y más lambdas que invocan a estas funciones para los procedimientos del usuario (estas lambdas capturan por copia las listas con sus definiciones, entonces el mecanismo de resolución es recursivo).

Lo que más tuve que depurar y corregir es el indentado de la linea de comandos (son unas 25 lineas más de código solo para I/O). En cualquier caso, finalmente armé un intérprete suficientemente bueno como para resolver todos los ejercicios de la primer parte del libro. La descarga del verdadero (una versión de scheme) finalmente finalizó y pude comparar y corroborar que los resultados coinciden. Los detalle negativos importantes son: que mi intérprete es muy muy poco eficiente, en varios niveles, principalmente porque hace copias que podrían evitarse en la gestión de los scopes, y porque no es capaz de convertir funciones recursivas en iterativas (en los casos de tail-recursion), que es una de las grandes magias que hacen los lenguajes funcionales.

Con una hora más de trabajo pulí unos cuantos detalles, y agregué comentarios, llegando a las más de 200 lineas casi finales. Durante el resto de la semana fui encontrando y corrigiendo otros "pequeños" bugs. Si tienen curiosidad, pueden descargar aquí la versión actual. Tiempo atrás esto me habría llevado 10 días y 5000 lineas de código. Pero C++11 cambió el panorama y con ello la forma de programar, no solo brindando nuevas herramientas, sino también abriendo la puerta a nuevas técnicas de diseño.

Con un poco más de trabajo y depuración soporta también pasar funciones

como argumentos y definirlas al vuelo (lambdas)

Como reflexión final, no deja de sorprenderme nunca lo ridículamente simples y a la vez poderosas que son las muy pocas reglas de LISP. Y estamos hablando de un lenguaje con casi 70 años!!! C++, en cuando a simpleza es todo lo contrario: tiene miles de reglas con millones de casos particulares cada una, que parecen hacerse más grandes y más complejas con cada versión. Sin embargo, aún así, y gracias a esta evolución, me permite resolver problemas rápidamente y expresar soluciones complejas de formas bastante compactas. Ningún lenguaje es la bala de plata, pero estos dos definitivamente son de los más interesantes.

Este post continúa en Lisp vs. C++ (fe de erratas), donde hay además un link a una versión corregida del intérprete.