fml
Un piccolo linguaggio della famiglia ML implementato da zero in F#. Lexer, parser, sistema di tipi ed evaluator - una catena completa dal codice sorgente al risultato.
Un piccolo linguaggio della famiglia ML costruito da zero in F#: un lexer, un parser, un sistema di tipi e un valutatore - il percorso completo dal testo sorgente fino al risultato. La parte più difficile è il sistema di tipi.
Panoramica
fml è un piccolo linguaggio di programmazione della famiglia ML, costruito da zero in F#. Ha quattro anelli che insieme portano dal testo sorgente al risultato: un lexer, un parser, un sistema di tipi e un valutatore. Ognuno fa una cosa, ma il più interessante e il più difficile è il sistema di tipi.
Un linguaggio proprio è un progetto che insegna l'umiltà. Non è un solo problema ma un'intera sequenza in cui l'uscita di una fase è l'ingresso della successiva, e un errore in una fase iniziale torna con forza raddoppiata tre passi più tardi. Proprio per questo è un così buon esercizio di pensiero sui sistemi.
Il testo sorgente va tagliato in token, i token disposti in un albero, l'albero verificato dal punto di vista dei tipi, e infine eseguito. È una catena in cui non si può barare in nessuna fase, perché la successiva lo intercetta subito - o, peggio, non lo intercetta, e l'errore emerge solo alla fine come risultato incomprensibile.
Questa dipendenza tra le fasi è insieme la difficoltà e la bellezza del progetto. Ogni anello si può capire a sé, ma solo insieme formano qualcosa che esegue davvero un programma. Progettare i confini tra loro perché siano puliti è metà dell'opera.
Tipi che non devi scrivere
In un linguaggio della famiglia ML il sistema di tipi è la parte più interessante. Non devi scrivere i tipi a mano - il compilatore li deduce da come usi i valori. Scrivi una funzione ordinaria, e il linguaggio ricava da sé quale tipo ha e veglia che tu non la usi in modo incompatibile con esso.
Da nessuna parte in questo codice abbiamo scritto un solo tipo, eppure il linguaggio sa che map ha il tipo (a -> b) -> lista a -> lista b. Questa è l'inferenza di tipi - una delle cose più belle che si possano scrivere a mano, e allo stesso tempo una delle più impegnative.
Quattro fasi dal testo al risultato
Tutto il percorso si scompone in quattro passi dai ruoli chiaramente divisi. Il testo diventa token, i token un albero, l'albero riceve i tipi, e infine viene calcolato. Le incompatibilità di tipo emergono nella terza fase, prima dell'esecuzione, e non durante.
il testo sorgente diventa un flusso di token.
i token si dispongono in un albero sintattico.
ogni espressione riceve un tipo, e le incompatibilità emergono qui, non a runtime.
l'albero viene calcolato fino a un risultato.
La catena del compilatore
| Fase | Ingresso | Uscita |
|---|---|---|
| Lexer | testo sorgente | token |
| Parser | token | albero sintattico |
| Sistema di tipi | albero | albero tipizzato |
| Valutatore | albero | risultato |
Il risultato: un linguaggio ML scritto in un linguaggio ML
Ne esce un linguaggio piccolo ma completo che esegue davvero un programma - dal primo carattere in un file fino al risultato calcolato. F# era qui la scelta naturale, perché appartiene esso stesso alla famiglia ML, e scrivere un linguaggio ML in un linguaggio ML ha qualcosa di piacevolmente ricorsivo. È un progetto dopo il quale la parola "compilatore" smette di essere un'astrazione.
Altri progetti
Altri lavori della stessa categoria - scopri come affrontiamo sfide simili.
Hai un progetto simile?
Contattaci - il preventivo è gratuito e arriva entro un'ora.