fml
Un pequeño lenguaje de la familia ML implementado desde cero en F#. Lexer, parser, sistema de tipos y evaluador - una cadena completa desde el código fuente hasta el resultado.
Un pequeño lenguaje de la familia ML construido desde cero en F#: un lexer, un analizador, un sistema de tipos y un evaluador - el camino completo del texto fuente hasta el resultado. La parte más difícil es el sistema de tipos.
Descripción general
fml es un pequeño lenguaje de programación de la familia ML, construido desde cero en F#. Tiene cuatro eslabones que juntos llevan del texto fuente al resultado: un lexer, un analizador, un sistema de tipos y un evaluador. Cada uno hace una cosa, pero el más interesante y el más difícil es el sistema de tipos.
Un lenguaje propio es un proyecto que enseña humildad. No es un solo problema sino toda una secuencia en la que la salida de una etapa es la entrada de la siguiente, y un error en una etapa temprana vuelve con fuerza doblada tres pasos después. Por eso mismo es un ejercicio tan bueno de pensar en sistemas.
El texto fuente hay que cortarlo en tokens, ordenar los tokens en un árbol, comprobar el árbol desde el punto de vista de los tipos, y al final ejecutarlo. Es una cadena en la que no se puede hacer trampa en ninguna etapa, porque la siguiente lo atrapa de inmediato - o, peor, no lo atrapa, y el error solo surge al final como un resultado incomprensible.
Esa dependencia entre etapas es a la vez la dificultad y la belleza del proyecto. Cada eslabón se entiende por separado, pero solo juntos forman algo que ejecuta de verdad un programa. Diseñar las fronteras entre ellos para que sean limpias es la mitad del éxito.
Tipos que no tienes que escribir
En un lenguaje de la familia ML el sistema de tipos es la parte más interesante. No tienes que escribir los tipos a mano - el compilador los infiere de cómo usas los valores. Escribes una función ordinaria, y el lenguaje descubre por sí mismo qué tipo tiene y vela por que nunca la uses en contradicción con él.
En ningún lugar de este código escribimos un solo tipo, y aun así el lenguaje sabe que map tiene el tipo (a -> b) -> lista a -> lista b. Eso es la inferencia de tipos - una de las cosas más bellas que se pueden escribir a mano, y a la vez una de las más exigentes.
Cuatro etapas del texto al resultado
Todo el camino se descompone en cuatro pasos con roles claramente divididos. El texto se vuelve tokens, los tokens un árbol, el árbol recibe tipos, y al final se calcula. Las incompatibilidades de tipo surgen en la tercera etapa, antes de ejecutar, y no durante.
el texto fuente se vuelve un flujo de tokens.
los tokens se ordenan en un árbol sintáctico.
cada expresión recibe un tipo, y las incompatibilidades surgen aquí, no en tiempo de ejecución.
el árbol se calcula hasta un resultado.
La cadena del compilador
| Etapa | Entrada | Salida |
|---|---|---|
| Lexer | texto fuente | tokens |
| Analizador | tokens | árbol sintáctico |
| Sistema de tipos | árbol | árbol tipado |
| Evaluador | árbol | resultado |
El resultado: un lenguaje ML escrito en un lenguaje ML
Lo que sale es un lenguaje pequeño pero completo que ejecuta de verdad un programa - del primer carácter en un archivo hasta el resultado calculado. F# fue aquí la elección natural, porque pertenece él mismo a la familia ML, y escribir un lenguaje ML en un lenguaje ML tiene algo agradablemente recursivo. Es un proyecto tras el cual la palabra "compilador" deja de ser una abstracción.
Más proyectos
Más trabajos de la misma categoría - mira cómo abordamos retos parecidos.
¿Tiene un proyecto similar?
Escríbenos - el presupuesto es gratuito y llega en una hora.