Durante los últimos 6 meses, he estado trabajando en un lenguaje de programación llamado Pinecone. No lo llamaría maduro todavía, pero ya tiene suficientes características funcionando para ser utilizable, como:
- variables
- funciones
- estructuras definidas por el usuario
Si está interesado en él, consulte la página de destino de Pinecone o su repositorio de GitHub.
No soy un experto Cuando comencé este proyecto, no tenía ni idea de lo que estaba haciendo y todavía no lo hago. No tomé clases sobre creación de lenguajes, solo leí un poco sobre ello en línea y no seguí muchos de los consejos que me dieron.
Y, sin embargo, todavía hice un lenguaje completamente nuevo. Y funciona. Entonces debo estar haciendo algo bien.
En esta publicación, me sumergiré bajo el capó y le mostraré la canalización que Pinecone (y otros lenguajes de programación) usan para convertir el código fuente en magia.
También mencionaré algunas de las compensaciones que he tenido y por qué tomé las decisiones que tomé.
Este no es de ninguna manera un tutorial completo sobre cómo escribir un lenguaje de programación, pero es un buen punto de partida si tiene curiosidad sobre el desarrollo del lenguaje.
Empezando
“No tengo ni idea de por dónde empezaría” es algo que escucho mucho cuando les digo a otros desarrolladores que estoy escribiendo un lenguaje. En caso de que esa sea su reacción, ahora analizaré algunas decisiones iniciales que se toman y los pasos que se toman al comenzar cualquier nuevo idioma.
Compilado vs interpretado
Hay dos tipos principales de lenguajes: compilados e interpretados:
- Un compilador averigua todo lo que hace un programa, lo convierte en "código de máquina" (un formato que la computadora puede ejecutar muy rápido) y luego lo guarda para ejecutarlo más tarde.
- Un intérprete recorre el código fuente línea por línea, averiguando lo que está haciendo a medida que avanza.
Técnicamente, cualquier idioma podría compilarse o interpretarse, pero uno u otro suele tener más sentido para un idioma específico. Generalmente, la interpretación tiende a ser más flexible, mientras que la compilación tiende a tener un mayor rendimiento. Pero esto es solo una parte de la superficie de un tema muy complejo.
Valoro mucho el rendimiento, y vi una falta de lenguajes de programación que sean tanto de alto rendimiento como orientados a la simplicidad, así que decidí compilar para Pinecone.
Esta fue una decisión importante que tomar desde el principio, porque muchas decisiones de diseño de lenguaje se ven afectadas por ella (por ejemplo, la escritura estática es un gran beneficio para los lenguajes compilados, pero no tanto para los interpretados).
A pesar de que Pinecone se diseñó teniendo en cuenta la compilación, tiene un intérprete completamente funcional que fue la única forma de ejecutarlo durante un tiempo. Hay varias razones para esto, que explicaré más adelante.
Elegir un idioma
Sé que es un poco meta, pero un lenguaje de programación es en sí mismo un programa y, por lo tanto, debes escribirlo en un lenguaje. Elegí C ++ por su rendimiento y gran conjunto de funciones. Además, disfruto mucho trabajando en C ++.
Si está escribiendo un lenguaje interpretado, tiene mucho sentido escribirlo en uno compilado (como C, C ++ o Swift) porque la actuación perdida en el lenguaje de su intérprete y el intérprete que está interpretando a su intérprete se agravará.
Si planea compilar, un lenguaje más lento (como Python o JavaScript) es más aceptable. El tiempo de compilación puede ser malo, pero en mi opinión, eso no es tan importante como un mal tiempo de ejecución.
Diseño de alto nivel
Un lenguaje de programación generalmente está estructurado como una tubería. Es decir, tiene varias etapas. Cada etapa tiene datos formateados de una manera específica y bien definida. También tiene funciones para transformar datos de cada etapa a la siguiente.
La primera etapa es una cadena que contiene todo el archivo fuente de entrada. La etapa final es algo que se puede ejecutar. Todo esto quedará claro a medida que avancemos por el oleoducto Pinecone paso a paso.
Lexing
El primer paso en la mayoría de los lenguajes de programación es lexing o tokenización. 'Lex' es la abreviatura de análisis léxico, una palabra muy elegante para dividir un montón de texto en tokens. La palabra 'tokenizer' tiene mucho más sentido, pero 'lexer' es tan divertido de decir que la uso de todos modos.
Tokens
Un token es una pequeña unidad de un idioma. Un token puede ser un nombre de función o variable (también conocido como identificador), un operador o un número.
Tarea del Lexer
Se supone que el lexer debe tomar una cadena que contenga un archivo completo de código fuente y escupir una lista que contenga cada token.
Las etapas futuras de la canalización no harán referencia al código fuente original, por lo que el lexer debe producir toda la información que necesitan. La razón de este formato de canalización relativamente estricto es que el lexer puede realizar tareas como eliminar comentarios o detectar si algo es un número o un identificador. Desea mantener esa lógica encerrada dentro del lexer, para no tener que pensar en estas reglas al escribir el resto del lenguaje y poder cambiar este tipo de sintaxis en un solo lugar.
Flexionar
El día que comencé con el idioma, lo primero que escribí fue un simple lexer. Poco después, comencé a aprender sobre herramientas que supuestamente harían el lexing más simple y con menos errores.
La herramienta predominante es Flex, un programa que genera lexers. Le da un archivo que tiene una sintaxis especial para describir la gramática del idioma. A partir de eso, genera un programa en C que lexiza una cadena y produce la salida deseada.
Mi decisión
Opté por mantener el lexer que escribí por el momento. Al final, no vi beneficios significativos de usar Flex, al menos no lo suficiente como para justificar agregar una dependencia y complicar el proceso de compilación.
Mi lexer tiene solo unos pocos cientos de líneas y rara vez me da problemas. Rolling my own lexer también me da más flexibilidad, como la capacidad de agregar un operador al idioma sin editar varios archivos.
Analizando
La segunda etapa de la canalización es el analizador. El analizador convierte una lista de tokens en un árbol de nodos. Un árbol utilizado para almacenar este tipo de datos se conoce como árbol de sintaxis abstracta o AST. Al menos en Pinecone, el AST no tiene información sobre tipos o qué identificadores son cuáles. Son simplemente tokens estructurados.
Deberes del analizador
El analizador agrega estructura a la lista ordenada de tokens que produce el lexer. Para detener las ambigüedades, el analizador debe tener en cuenta los paréntesis y el orden de las operaciones. Simplemente analizar los operadores no es muy difícil, pero a medida que se agregan más construcciones de lenguaje, el análisis puede volverse muy complejo.
Bisonte
Una vez más, hubo que tomar una decisión sobre la participación de una biblioteca de terceros. La biblioteca de análisis predominante es Bison. Bison funciona muy parecido a Flex. Usted escribe un archivo en un formato personalizado que almacena la información gramatical, luego Bison lo usa para generar un programa en C que hará su análisis. No elegí usar Bison.
Por qué lo personalizado es mejor
Con el lexer, la decisión de usar mi propio código fue bastante obvia. Un lexer es un programa tan trivial que no escribir el mío se sentía casi tan tonto como no escribir mi propio "pad izquierdo".
Con el analizador, es un asunto diferente. Mi analizador Pinecone tiene actualmente 750 líneas de longitud y he escrito tres de ellas porque las dos primeras eran basura.
Originalmente tomé mi decisión por varias razones, y aunque no ha ido del todo bien, la mayoría de ellas son ciertas. Los principales son los siguientes:
- Minimice el cambio de contexto en el flujo de trabajo: el cambio de contexto entre C ++ y Pinecone es suficientemente malo sin incluir la gramática de Bison
- Mantenga la compilación simple: cada vez que cambie la gramática, Bison debe ejecutarse antes de la compilación. Esto se puede automatizar, pero se vuelve un problema al cambiar entre sistemas de compilación.
- Me gusta construir cosas interesantes: no hice Pinecone porque pensé que sería fácil, así que ¿por qué delegaría un papel central cuando podía hacerlo yo mismo? Un analizador personalizado puede no ser trivial, pero es completamente factible.
Al principio no estaba completamente seguro de si estaba yendo por un camino viable, pero lo que Walter Bright (un desarrollador de una versión inicial de C ++ y el creador del lenguaje D) me dio confianza en el tema:
"Algo más controvertido, no me molestaría en perder el tiempo con generadores lexer o parser y otros llamados" compiladores de compiladores ". Son una pérdida de tiempo. Escribir un lexer y parser es un pequeño porcentaje del trabajo de escribir un compilador. El uso de un generador tomará tanto tiempo como escribir uno a mano y lo vinculará con el generador (lo cual es importante cuando se traslada el compilador a una nueva plataforma). Y los generadores también tienen la desafortunada reputación de emitir pésimos mensajes de error ".Árbol de acción
Ahora hemos dejado el área de los términos universales comunes, o al menos ya no sé cuáles son los términos. Según tengo entendido, lo que llamo el "árbol de acción" es más parecido al IR de LLVM (representación intermedia).
Existe una diferencia sutil pero muy significativa entre el árbol de acciones y el árbol de sintaxis abstracta. Me tomó bastante tiempo darme cuenta de que incluso debería haber una diferencia entre ellos (lo que contribuyó a la necesidad de reescribir el analizador).
Árbol de acción vs AST
En pocas palabras, el árbol de acción es el AST con contexto. Ese contexto es información como qué tipo devuelve una función, o que dos lugares en los que se usa una variable de hecho usan la misma variable. Debido a que necesita descubrir y recordar todo este contexto, el código que genera el árbol de acción necesita muchas tablas de búsqueda de espacios de nombres y otras cosas.
Ejecución del árbol de acciones
Una vez que tenemos el árbol de acciones, ejecutar el código es fácil. Cada nodo de acción tiene una función 'ejecutar' que toma alguna entrada, hace lo que la acción debería (incluyendo posiblemente llamar a la acción secundaria) y devuelve la salida de la acción. Este es el intérprete en acción.
Opciones de compilación
"¡Pero espera!" Te escucho decir: "¿No se supone que Pinecone se compilará?" Sí lo es. Pero compilar es más difícil que interpretar. Hay algunos enfoques posibles.
Construye mi propio compilador
Esto me pareció una buena idea al principio. Me encanta hacer cosas yo mismo, y he estado ansioso por encontrar una excusa para mejorar en el montaje.
Desafortunadamente, escribir un compilador portátil no es tan fácil como escribir un código de máquina para cada elemento del lenguaje. Debido a la cantidad de arquitecturas y sistemas operativos, no es práctico para cualquier persona escribir un backend compilador multiplataforma.
Incluso los equipos detrás de Swift, Rust y Clang no quieren molestarse con todo por su cuenta, por lo que todos usan ...
LLVM
LLVM es una colección de herramientas de compilación. Básicamente es una biblioteca que convertirá su lenguaje en un binario ejecutable compilado. Parecía la elección perfecta, así que salté de inmediato. Lamentablemente, no comprobé la profundidad del agua e inmediatamente me ahogué.
LLVM, aunque no es un lenguaje ensamblador difícil, es una biblioteca gigantesca y compleja. No es imposible de usar, y tienen buenos tutoriales, pero me di cuenta de que tendría que practicar un poco antes de estar listo para implementar completamente un compilador Pinecone con él.
Transpilar
Quería una especie de Pinecone compilado y lo quería rápido, así que recurrí a un método que sabía que podía hacer funcionar: transpilar.
Escribí un transpilador Pinecone a C ++ y agregué la capacidad de compilar automáticamente la fuente de salida con GCC. Esto funciona actualmente para casi todos los programas Pinecone (aunque hay algunos casos extremos que lo rompen). No es una solución particularmente portátil o escalable, pero funciona por el momento.
Futuro
Suponiendo que continúe desarrollando Pinecone, tarde o temprano obtendrá soporte de compilación LLVM. Sospecho que no importa cuánto trabaje en él, el transpilador nunca será completamente estable y los beneficios de LLVM son numerosos. Es solo una cuestión de cuándo tengo tiempo para hacer algunos proyectos de muestra en LLVM y aprender a usarlos.
Hasta entonces, el intérprete es excelente para programas triviales y la transpilación de C ++ funciona para la mayoría de las cosas que necesitan más rendimiento.
Conclusión
Espero haber hecho que los lenguajes de programación sean un poco menos misteriosos para ti. Si quieres hacer uno tú mismo, te lo recomiendo. Hay un montón de detalles de implementación que resolver, pero el esquema aquí debería ser suficiente para comenzar.
Aquí está mi consejo de alto nivel para comenzar (recuerde, realmente no sé lo que estoy haciendo, así que tómelo con un grano de sal):
- Si tiene dudas, vaya interpretado. Los lenguajes interpretados son generalmente más fáciles de diseñar, construir y aprender. No te estoy disuadiendo de escribir uno compilado si sabes que eso es lo que quieres hacer, pero si estás indeciso, iría interpretado.
- Cuando se trata de lexers y analizadores, haga lo que quiera. Hay argumentos válidos a favor y en contra de escribir el suyo. Al final, si piensa en su diseño e implementa todo de una manera sensata, realmente no importa.
- Aprenda de la tubería con la que terminé. Se realizaron muchas pruebas y errores en el diseño de la tubería que tengo ahora. He intentado eliminar los AST, los AST que se convierten en árboles de acciones en su lugar y otras ideas terribles. Esta canalización funciona, así que no la cambie a menos que tenga una idea realmente buena.
- Si no tiene el tiempo o la motivación para implementar un lenguaje complejo de propósito general, intente implementar un lenguaje esotérico como Brainfuck. Estos intérpretes pueden ser tan cortos como unos pocos cientos de líneas.
Lamento muy poco en lo que respecta al desarrollo de Pinecone. Tomé una serie de malas decisiones en el camino, pero he reescrito la mayor parte del código afectado por tales errores.
En este momento, Pinecone se encuentra en un estado lo suficientemente bueno como para que funcione bien y se pueda mejorar fácilmente. Escribir Pinecone ha sido una experiencia muy educativa y agradable para mí, y apenas está comenzando.