TypeScript ist überraschend brauchbar – sogar für Compiler-Implementierungen

 (matklad.github.io)
8 Punkte von GN⁺ 2023-08-20 | 1 Kommentare | Auf WhatsApp teilen
  • Die Implementierungssprache für compilerartige Werkzeuge war traditionell zwischen OCaml und C++ aufgeteilt, aber für kleine Sprachexperimente kann TypeScript eine leichtgewichtige Option sein, ähnlich wie eine ML-Familiensprache.
  • Rust kombiniert die Stärken von ML und C++ und bietet sogar sicheres Multithreading, doch weil man das physische Layout der Daten modellieren muss, kann es für kleine Prototypen zu aufwendig sein.
  • Deno ermöglicht mit Single Binary, integriertem Linting und Formatting, ohne Kompilierungsschritt sowie mit Task Runner und Watch-Modus einen schnellen Start für TypeScript-Sprachexperimente.
  • Der Beispiel-Typechecker kombiniert generische ASTs, Tagged Unions, Visitor und Bottom-up-Transformationen, um Expr<void> in Expr<Type> zu verwandeln, und verwendet TypeError als Typwert, um Kaskadenfehler zu reduzieren.
  • TypeScript kann dank Autovervollständigung, flexiblem Typsystem und Laufzeiteigenschaften, die bei Bedarf dynamische Ansätze erlauben, ein produktives Werkzeug für kleine Sprach-Hacks sein.

Die bisherige Lage bei der Wahl der Implementierungssprache

  • Beim Bau compilerartiger Werkzeuge gibt es bei der Wahl der Implementierungssprache grob zwei Strömungen.
  • Für implementierungsorientierte Arbeiten mit Bedarf an Produktionsreife wird häufig C++ gewählt.
    • LLVM, clang, v8 und HotSpot basieren alle auf C++.
  • Rust ist direkt von ML und C++ beeinflusst, kombiniert die Stärken beider Sprachen und bringt zusätzlich eigene Vorteile wie sicheres Multithreading mit.
    • Im Spektrum ist es allerdings stärker in Richtung Produktionsreife geneigt.
    • Ein Build-System, das „einfach funktioniert“, hilft zwar auch beim Prototyping, bringt aber die zusätzliche Komplexität mit sich, das physische Layout der Daten modellieren zu müssen.

Die Vorteile des Rust-Index-Ansatzes und die Last für kleinen Code

  • Ein häufiger Rat beim Schreiben von Compilern in Rust ist, Pointer zu vermeiden und stattdessen Indizes zu verwenden.
  • Indizes haben in großen Codebasen mehrere Vorteile.
    • Side Tables können im zugehörigen Modul bleiben, was die Kopplung senkt.
    • Indizes sind u32 und fördern ein Struct-of-Arrays-Layout, was der Performance zugutekommt.
    • Sie lassen sich leicht serialisieren oder an Frameworks für inkrementelles Kompilieren anbinden, wodurch die Berechnungsstrategie flexibler wird.
  • Bei kleineren Programmeinheiten wird der Index-Ansatz selbst jedoch umständlich, und bei Hobby-Experimenten kann diese Last entscheidend sein.
  • OCaml wirkt ein wenig altmodisch, und in diesem Kontext wird geprüft, ob TypeScript als eine Art ML-Alternative dienen kann.

Deno und TypeScript als Umgebung für schnelle Experimente

  • Als Startumgebung wird deno verwendet.
    • Es bietet eine Out-of-the-box-Erfahrung, bei der TypeScript sofort nutzbar ist.
    • In OCaml ist genau dieser Punkt oft schmerzhaft, und Rust ist hier zwar besser als OCaml oder C++, aber Deno liefert noch eine einfachere Erfahrung als Rust.
  • Das Entwicklererlebnis mit Deno passt gut zu kleinen PLT-Hacks.
    • Es ist ein Single Binary.
    • Linting und Formatting sind eingebaut.
    • Es gibt keinen separaten Kompilierungsschritt.
    • Es gibt einen integrierten Task Runner und einen Watch-Modus.
  • TypeScript selbst bietet ein Typsystem, das ausreichend flexibel ist und zugleich eine geringe syntaktische Hürde hat.

TypeScript-Muster im kleinen Typechecker-Beispiel

  • Der AST beginnt mit Ausdrücken, die Positionsinformationen aus der Datei enthalten.
    • Location enthält file, line und column.
    • In TypeScript sind Zeichenketten einfach string und Zahlen einfach number, sodass man nicht über Unterscheidungen wie usize und u32 nachdenken muss.
  • Ausdrücke trennen Position und Kind und verallgemeinern die zugehörigen Daten später in der Form Expr<T>.
    • Direkt nach dem Parsen haben Ausdrücke Daten vom Typ void.
    • Vom Typechecker verarbeitete Ausdrücke haben Daten vom Typ Type.
    • Die Typinferenzfunktion nimmt ast.Expr<void> entgegen und gibt ast.Expr<Type> zurück.
  • TypeScript fügt Laufzeitverhalten nicht automatisch hinzu, daher muss man für das Matching auf Union-Typen selbst Laufzeit-Typinformationen einbauen.
    • Felder wie tag: "binary" und tag: "if" übernehmen diese Rolle.
    • tag: "binary" bedeutet zur Laufzeit, dass der Wert nur die Zeichenkette "binary" sein kann.
  • Boolean-Literale und Integer-Literale haben fast dieselbe Form und werden daher als ExprLiteral<T, V, Tag> abstrahiert.
    • ExprBool<T> ist ExprLiteral<T, boolean, "bool">.
    • ExprInt<T> ist ExprLiteral<T, number, "int">.
  • Typwerte sind in TypeBool und TypeInt aufgeteilt, Singleton-Werte werden unter denselben Namen ebenfalls bereitgestellt.
    • TypeScript löscht Typen vollständig, deshalb existieren typbezogene und wertbezogene Namen in getrennten Namespaces.
    • Diese Eigenschaft erlaubt es, Typen und Werte mit demselben Namen zu definieren.

Visitor, Transformation, Fehlertypen und Desugaring

  • Da switch in TypeScript kein Ausdruck, sondern eine Anweisung ist, wird zur bequemen Verarbeitung der Ausdrucksarten ein Visitor definiert.
    • Die Methoden bool, int, binary und if verarbeiten jeweils das entsprechende Kind.
    • Die Autovervollständigung des Editors hilft sowohl bei switch-Cases als auch bei der Visitor-Implementierung.
  • transform<U, V> ist eine verallgemeinerte Traversierungsfunktion, die Expr<U> in Expr<V> umwandelt.
    • Die Transformation läuft bottom-up ab.
    • Beim Besuch innerer Knoten sind die Unterausdrücke bereits transformiert, daher hat der Visitor den Typ Visitor<V, V> und nicht Visitor<U, V>.
  • Weil TypeScript auch eine dynamisch typisierte Sprache ist, könnte man mit Object.keys eine allgemeinere Traversierung bauen.
    • Dabei kann die statische Funktionssignatur trotzdem erhalten bleiben.
    • Im Beispiel ist das nicht unbedingt nötig, aber bei Bedarf gibt es die Möglichkeit, in einen dynamischen Ansatz auszuweichen.
  • Typfehler werden nicht als Seiteneffekt in einem Array gesammelt, sondern als Typ TypeError dargestellt.
    • Type wird zu TypeBool | TypeInt | TypeError.
    • TypeError besitzt tag: "Error", location und message.
    • type_equal gibt true zurück, wenn eine der beiden Seiten Error ist, und verhindert so Kaskadenfehler.
  • Der finale Typechecker prüft binary- und if-Ausdrücke.
    • Bei einem binary-Ausdruck wird bei unterschiedlichen Typen der linken und rechten Operanden der Fehler "binary expression operands have different types" zurückgegeben.
    • Bei einem if-Ausdruck wird der Fehler "if condition is not a boolean" zurückgegeben, wenn die Bedingung kein Boolean ist.
    • Unterscheiden sich die Typen von then- und else-Branch, wird "if branches have different types" zurückgegeben.
  • Das Ergebnis erfordert zwar ein gewisses Maß an Typannotationen, doch die Autovervollständigung gleicht viel davon aus, das Gefühl eines Kampfs mit der Sprache ist geringer, und es passt sich natürlich an die Problemform an.
  • Warum TypeScript als Werkzeug für kleine Sprach-Hacks produktiv sein kann, wird in drei Punkten zusammengefasst.
    • Deno ist eine kleine, geschlossene, leistungsfähige und auf einen effektiven Entwicklungs-Workflow optimierte Scripting Runtime.
    • Die TypeScript-Tooling ist dank nützlicher IDE-Unterstützung produktiv, und mit Deno ist keine Konfiguration nötig.
    • Die Sprache ist sowohl zur Laufzeit als auch zur Compile-Zeit mächtig, erlaubt recht ausgefeilte Ausdrücke über Typen und bietet dennoch die Möglichkeit, bei Bedarf dynamisch vorzugehen.
  • Als weitere Idee ist auch ein typsicheres Desugaring vieler Sprachzucker-Konstrukte möglich.
    • Expr und ExprKind werden nicht über zugehörige Daten, sondern rekursiv über das gesamte ExprKind parametrisiert.
    • ExprKindCore steht für die Menge der Kernausdrücke.
    • ExprKindSugar enthält entweder Kernausdrücke oder Ausdrücke, die sich in Kernausdrücke desugaren lassen.
    • desugar(expr: ExprSugar): ExprCore reduziert Ausdrucksformen mit Sprachzucker auf Kernausdrücke.
    • desugar_one(expr: ExprKindSugar<ExprCore>): ExprKindCore<ExprCore> führt eine einzelne Transformation aus, wenn die Unterausdrücke bereits desugart wurden.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-08-20
Meinungen auf Hacker News

  • TypeScript ist insgesamt eine hervorragende Sprache, und es wird unterschätzt, dass Funktionen Objekte sind, die Properties/Methoden haben können.
    Man kann ein Array von Funktionen wie Befehle ausführen und später Beschreibungen wie help anhängen, oder über Closures/Partial Application Zustand hinzufügen, sodass man nicht vorschnell Klassen wie Command definieren muss.
    In der Objektorientierung sorgt es oft für Konflikte, Dingen zu früh Namen zu geben; natürlicher sei es, die benötigten Werte an eine Funktion zu übergeben, statt Strukturen wie VideoCompressor#compress() zu verwenden.

    • Genau genommen ist das eher eine JavaScript- als eine TypeScript-Funktion.
      Andere Sprachen, die Objekte unterstützen, die sich wie Funktionen verhalten, sind unter https://en.wikipedia.org/wiki/Function_object zusammengefasst.
    • In Go kann man auch Funktionen Methoden hinzufügen, tatsächlich ist das praktisch bei jedem Typ möglich.
      Wie bei den Handlern in net/http kann eine Struct eine serve-Methode implementieren, oder eine Handler-Funktion kann sich selbst aufrufen und so ein Interface erfüllen.
      In Clojure kann man ähnlich vorgehen, indem man an ein Funktions-var Metadaten hängt; und da es Lisp ist, ist mit Makros fast alles möglich.
      Außerdem trennen die CSP-Channels aus core/async Ausführung und Kommunikation und helfen so, das Problem der Funktionsfarben wie bei Callbacks/Promises/async/await zu vermeiden; Befehle können sich dabei wie Producer verhalten, die Ergebnisse in Channels senden.
    • Mit Javas Single-Method-Interfaces lässt sich ein ähnlicher Effekt erzielen.
      Unabhängig vom Methodennamen kann man sie in einem Funktionskontext verwenden, ohne auf den konkreten Methodennamen verweisen zu müssen.
      Allerdings bevorzuge ich es nicht, wenn eine Funktion Properties besitzt, Zustand in sich trägt und ihr Verhalten sich trotz Aufruf mit denselben Argumenten ändern kann. Ein großer Vorteil funktionaler Programmierung liegt meiner Ansicht nach darin, sich von objektorientiertem Zustand zu lösen.
    • Python unterstützt diese Richtung gut, weil dort alles ein Objekt ist.
    • Auch in C# lässt sich Ähnliches ausdrücken: Funktionen mit Rückgabewert als Func, Funktionen ohne Rückgabewert als Action.
      Die Lambda-Ausdrücke von JavaScript ähneln denen von C# ziemlich stark, und auch die Funktionssignaturen von TypeScript und C# sind recht ähnlich.
      Es gibt auch ein kleines Repository, das die Ähnlichkeiten zwischen JavaScript, TypeScript und C# zeigt: https://github.com/CharlieDigital/js-ts-csharp
      Screenshot, der dieselbe Logik nebeneinander in JS/TS/C# zeigt: https://github.com/CharlieDigital/js-ts-csharp/blob/main/js-...

  • So überraschend ist das nicht. TypeScript ist letztlich auch nur eine weitere Sprache, die viele Funktionen aus der ML-Familie mühsam übernommen hat.
    Weil echtes Pattern Matching fehlt, ist sie unbequemer als OCaml, aber verglichen mit Sprachen wie C#, Swift, Dart oder Kotlin liegt sie durchaus im Rahmen.

    • Das ist ein Vergleich auf zu hoher Ebene. Das tatsächliche Nutzungsgefühl ist ziemlich anders.
      TypeScript hat zwar ein starkes Typsystem, aber die zugrunde liegende Standardbibliothek und die Sprache selbst sind enttäuschend; Pattern Matching/Switch-Expressions fehlen.
      Dart hat ein geschlossenes Objektmodell, bietet also weniger dynamische Freiheit, Typsystem und Expressions sind schwächer, und es gibt kaum Metaprogramming-Fähigkeiten, sodass man sich auf Java-artigen Boilerplate und Codegeneratoren stützen muss.
      C# kommt von den genannten Sprachen den ML-Funktionen am nächsten, aber im Gegensatz zu TypeScript fehlen Sum Types, wodurch vieles umständlicher wird.
    • In einem früheren, mit Haskell gebauten Pascal-C-artigen Lern-Compiler ermöglichten Parser-Kombinatoren, die Grammatik direkt im Code ähnlich wie BNF auszudrücken.
      Zum Beispiel kann man einen Parser, der { ... } erkennt, mit anderen Parsern kombinieren, und eine Anweisung kann als eines von Kontrollfluss/Deklaration/Zuweisung definiert werden.
      ML-artige Listenverarbeitung und Pattern Matching waren beim Umgang mit Zwischenrepräsentationen sehr ausdrucksstark.
    • Wenn ich in TypeScript Pattern Matching brauche, nutze ich gern diese Bibliothek: https://github.com/gvergnaud/ts-pattern
    • Es ist schwer zu sagen, dass TypeScript den Großteil der ML-Funktionen übernommen hat.
      Auch im Artikel musste man auf das Visitor Pattern ausweichen, weil switch keine Expression ist, und die Iterator-Unterstützung von JavaScript ist merkwürdig unzureichend.
      .map() gibt es zwar, aber es funktioniert nur auf Arrays und lässt sich nicht direkt auf allgemeine Iteratoren anwenden.
    • Wenn man TypeScript und kotlin-js verwendet, fühlen sich die beiden Sprachen ziemlich ähnlich an.
      Es gibt viele Unterschiede, aber der Wechsel ist nicht schwierig; persönlich bevorzuge ich Kotlin, kann aber beide verwenden.
      Ich frage mich, wie es wäre, wenn TypeScript sich von der JavaScript-Kompatibilität lösen und nach WASM kompilieren würde. Kotlin fügt gerade einen WASM-Compiler hinzu und hat bereits einen JS-Transpiler; derselbe Code ist in WASM kleiner und lädt schneller.
      Browser-JavaScript ist kein gutes Compile Target, und da neue Projekte immer häufiger von Anfang an mit TypeScript starten, wird auch das Argument, man müsse leicht von bestehendem JavaScript migrieren können, zunehmend schwächer.

  • Wenn man zwischen Rust und TypeScript wechselt, sieht man sehr deutlich, wie sehr Funktionen wie Tagged Enums fehlen.
    Der Vorschlag für ADT-Enums scheint stehengeblieben zu sein; ich frage mich, ob es andere Bemühungen gibt: https://github.com/Jack-Works/proposal-enum/discussions/19

    • Für ähnliche Zwecke funktionieren Discriminated Unions meiner Ansicht nach ziemlich gut

  • Das Typsystem von TypeScript ist interessant, aber man fragt sich, wie viel schneller es wäre, wenn der Compiler in einer kompilierten Sprache geschrieben wäre
    Dafür braucht es natürlich die große Voraussetzung einer „guten Implementierung“

    • swc und esbuild sind keine guten Vergleichsmaßstäbe. Ein erheblicher Teil des Geschwindigkeitsgewinns kommt daher, dass TypeScript-spezifische Syntax entfernt und JavaScript erzeugt wird
      tsc ist vor allem nur beim ersten Lauf langsam; mit dem incremental-Flag oder einem Watch-Modus mit --transpile-only sinkt die Kompilierzeit meist unter 100 ms, sodass sich zu SWC oder ESBuild kaum noch ein spürbarer Unterschied ergibt
    • Es gibt eine Antwort des TypeScript-Teams: https://twitter.com/drosenwasser/status/1260723846534979584
      Wenn die Typprüfung eines mittelgroßen Programms 20 Sekunden dauert, liegt das meist nicht daran, dass es JS ist, sondern daran, dass die Typen eine kombinatorische Explosion verursachen
      Andere Runtimes könnten bei Parallelität oder Startzeit Vorteile bringen, aber CPU-zentrierte Benchmarks, die eine insgesamt 20-fache Beschleunigung stützen, habe man nicht gesehen
    • Das Typsystem macht Spaß, bis man Generics wirklich maximal ausreizt
      Und nachdem man dann einen ganzen Tag lang 5 Zeilen Typ-Logik debuggt hat, fragt man sich, wie man überhaupt so weit gekommen ist
    • Man muss es sich nicht mehr nur vorstellen: https://github.com/dudykr/stc
      Ein in Rust geschriebenes Projekt eines der Hauptentwickler von SWC; SWC kompiliert TS zu JS und STC prüft TS-Typen
    • Die Performance des TypeScript-Compilers hat sich in letzter Zeit stark verbessert
      Der kommende isolated declaration mode soll die Kompilierzeit um bis zu 75 % reduzieren können: https://github.com/microsoft/TypeScript/pull/53463#issuecomm...

  • Wer gerade erst anfängt, Compiler zu lernen, dem empfehle ich dieses Buch: https://keleshev.com/compiling-to-assembly-from-scratch/
    Der Autor baut darin einen Compiler von einer TypeScript-Teilmenge zu 32-Bit-ARM-Assembly und erklärt, dass es fast wie Pseudocode wirkt und dadurch gut zugänglich ist

    • Crafting Interpreters ist ebenfalls sehr zu empfehlen: https://craftinginterpreters.com/
      Das Buch ist in zwei Teile gegliedert: Im ersten wird in Java ein Interpreter für eine Sprache gebaut, im zweiten wird dieselbe Sprache zu Bytecode kompiliert und anschließend in C eine Bytecode-VM implementiert
      Jede Codezeile der Implementierung wird im Buch referenziert

  • Wenn man das Visitor Pattern vermeiden will, kann man mit einer run-Utility-Funktion einen IIFE-artigen switch verwenden
    Man schreibt also ein switch in eine sofort ausgeführte Funktion und lässt den Rückgabetyp ableiten

    • Ich habe einmal über dieses Pattern geschrieben: https://maxgreenwald.me/blog/do-more-with-run
    • Eigentlich braucht man nicht einmal das; wenn man einfach eine Funktion sofort aufruft, wird der Rückgabetyp abgeleitet
      Wenn man IIFEs wegen des abschließenden () vermeiden möchte, kann man die Funktion separat definieren und dann aufrufen

  • Ich schreibe gerade einen Compiler in TypeScript und stimme zu, dass es besser ist als erwartet
    Anfangs habe ich wie der Autor mit Deno angefangen, bin aber letztlich zu Bun gewechselt; trotz einiger rauer Kanten gefällt es mir besser als Deno und ist sehr schnell
    Als Frontend mit Standard-Parsergenerator ist Ohm-js ziemlich angenehm: https://ohmjs.org/
    Der offizielle tsc-Compiler ist viel zu groß, daher würde ich ihn nicht zum Lesen empfehlen; um zu sehen, wie tsc funktioniert, ist mini-typescript besser: https://github.com/sandersn/mini-typescript/
    Besonders der Branch centi-typescript ist hilfreich: https://github.com/sandersn/mini-typescript/tree/centi-types...
    Ich freue mich darauf, dass in WASM GC und DOM-Zugriff möglich werden

    • Mich würde interessieren, warum der Wechsel zu Bun erfolgte

  • Ich hätte wegen der Interfaces bei TypeScript mehr zusätzlichen Overhead erwartet, das ist überraschend
    Da fragt man sich, ob sich das auch auf andere Bereiche übertragen lässt, etwa ob es auch für Sprachparsing taugt

    • Zur Laufzeit ist der Overhead von Interfaces 0
      Sie verschwinden beim Kompilieren vollständig

  • Das Ergebnis ist nicht allzu überraschend. Schließlich ist der TypeScript-Compiler selbst in TypeScript geschrieben
    TypeScript als ML wird bereits täglich in schweren Produktionsumgebungen erprobt

  • Ich habe einmal einen Compiler in C# geschrieben; was hier besonders wirkt, sind eigentlich nur die Union Types
    Persönlich habe ich mich entschieden, die Ausführlichkeit des Visitor Patterns zu vermeiden, und warte auf geschlossene Enums, um zur Kompilierzeit Vollständigkeitsprüfungen zu bekommen

    • Wenn man eine Sprache ohne Union Types oder Rust-artige Enums verwendet, vermisst man diese Funktion sehr
      Die üblichen Alternativen sind unbeholfen: Entweder hat man in einer Klasse zur Darstellung eines Summentyps N nullable Properties und verlässt sich auf die dokumentierte Bedingung „immer genau eines ist non-null“, oder man lässt mehrere Klassen von einer gemeinsamen Klasse erben; beides fühlt sich schwergewichtig an
      Wenn man mehrere überlappende Union Types erstellen will, braucht man bei beiden Ansätzen Duplikation oder clevere Kombinationen