fml
Eine kleine Sprache aus der ML-Familie, von Grund auf in F# implementiert. Lexer, Parser, Typsystem und Evaluator - eine komplette Kette vom Quellcode bis zum Ergebnis.
Eine kleine Sprache der ML-Familie, von Grund auf in F# gebaut: ein Lexer, ein Parser, ein Typsystem und ein Evaluator - der volle Weg vom Quelltext bis zum Ergebnis. Der schwerste Teil ist das Typsystem.
Überblick
fml ist eine kleine Programmiersprache der ML-Familie, von Grund auf in F# gebaut. Sie hat vier Glieder, die zusammen vom Quelltext zum Ergebnis führen: einen Lexer, einen Parser, ein Typsystem und einen Evaluator. Jedes tut eine Sache, aber das interessanteste und schwerste ist das Typsystem.
Eine eigene Sprache ist ein Projekt, das Demut lehrt. Es ist nicht ein Problem, sondern eine ganze Folge, in der die Ausgabe einer Stufe die Eingabe der nächsten ist und ein Fehler in einer frühen Stufe drei Schritte später mit doppelter Wucht zurückkommt. Genau deshalb ist es eine so gute Übung im Denken über Systeme.
Der Quelltext muss in Token zerschnitten, die Token zu einem Baum geordnet, der Baum auf Typen geprüft und am Ende ausgeführt werden. Es ist eine Kette, in der man auf keiner Stufe schummeln kann, weil die nächste es sofort abfängt - oder, schlimmer, nicht abfängt, und der Fehler erst am Ende als unverständliches Ergebnis auftaucht.
Diese Abhängigkeit der Stufen ist zugleich die Schwierigkeit und die Schönheit des Projekts. Jedes Glied lässt sich einzeln verstehen, aber erst zusammen ergeben sie etwas, das ein Programm wirklich ausführt. Die Grenzen zwischen ihnen so zu entwerfen, dass sie sauber sind, ist die halbe Miete.
Typen, die man nicht schreiben muss
In einer Sprache der ML-Familie ist das Typsystem der interessanteste Teil. Sie müssen Typen nicht von Hand schreiben - der Compiler leitet sie daraus ab, wie Sie Werte verwenden. Sie schreiben eine gewöhnliche Funktion, und die Sprache findet selbst heraus, welchen Typ sie hat, und sorgt dafür, dass Sie sie nie im Widerspruch dazu verwenden.
Nirgends in diesem Code haben wir auch nur einen einzigen Typ geschrieben, und dennoch weiß die Sprache, dass map den Typ (a -> b) -> Liste a -> Liste b hat. Das ist Typinferenz - eines der schönsten Dinge, die man von Hand schreiben kann, und zugleich eines der anspruchsvollsten.
Vier Stufen vom Text zum Ergebnis
Der ganze Weg zerfällt in vier Schritte mit klar geteilten Rollen. Text wird zu Token, Token zu einem Baum, der Baum bekommt Typen, und am Ende wird er berechnet. Typunstimmigkeiten tauchen in der dritten Stufe auf, noch vor dem Ausführen, und nicht während des Laufs.
der Quelltext wird zu einem Strom von Token.
die Token ordnen sich zu einem Syntaxbaum.
jeder Ausdruck bekommt einen Typ, und Unstimmigkeiten tauchen hier auf, nicht zur Laufzeit.
der Baum wird zu einem Ergebnis berechnet.
Die Compilerkette
| Stufe | Eingabe | Ausgabe |
|---|---|---|
| Lexer | Quelltext | Token |
| Parser | Token | Syntaxbaum |
| Typsystem | Baum | typisierter Baum |
| Evaluator | Baum | Ergebnis |
Das Ergebnis: eine ML-Sprache, geschrieben in einer ML-Sprache
Heraus kommt eine kleine, aber vollständige Sprache, die ein Programm wirklich ausführt - vom ersten Zeichen in einer Datei bis zum berechneten Ergebnis. F# war hier die natürliche Wahl, weil es selbst zur ML-Familie gehört, und eine ML-Sprache in einer ML-Sprache zu schreiben hat etwas angenehm Rekursives. Es ist ein Projekt, nach dem das Wort "Compiler" aufhört, eine Abstraktion zu sein.
Weitere Projekte
Weitere Projekte aus derselben Kategorie - sehen Sie, wie wir ähnliche Herausforderungen angehen.
Haben Sie ein ähnliches Projekt?
Melden Sie sich - ein Angebot ist kostenlos und kommt innerhalb einer Stunde.