TypeScript est étonnamment convenable aussi pour implémenter des compilateurs

 (matklad.github.io)
8 points par GN⁺ 2023-08-20 | 1 commentaires | Partager sur WhatsApp
  • Les langages d’implémentation des outils de type compilateur se répartissaient traditionnellement entre OCaml et C++, mais pour de petites expérimentations de langage, TypeScript devient une option légère, utilisable comme un langage de la famille ML
  • Rust combine les avantages de ML et de C++, et offre même du multithreading sûr, mais comme il faut modéliser la disposition physique des données, il peut devenir pesant pour de petits prototypes
  • Deno permet de démarrer rapidement des expérimentations de langage en TypeScript grâce à son binaire unique, son linting et son formatage intégrés, l’absence d’étape de compilation, son task runner et son mode watch
  • L’exemple de type checker combine AST générique, unions étiquetées, visitor et transformation bottom-up pour convertir Expr<void> en Expr<Type>, et place TypeError comme valeur de type afin de réduire les erreurs en cascade
  • Grâce à l’autocomplétion, à un système de types flexible et à des caractéristiques d’exécution qui permettent de basculer vers une approche dynamique quand nécessaire, TypeScript peut être productif comme outil pour bidouiller de petits langages

Le paysage traditionnel du choix du langage d’implémentation

  • Lorsqu’on crée un outil de type compilateur, le choix du langage d’implémentation suit généralement deux grandes tendances
  • Pour les travaux davantage centrés sur l’implémentation et devant être prêts pour la production, C++ est souvent choisi
    • LLVM, clang, v8 et HotSpot reposent tous sur C++
  • Rust a été directement influencé par ML et C++, combine les avantages des deux langages et apporte aussi ses propres atouts, comme le multithreading sûr
    • Mais, sur le spectre, il penche davantage du côté de la préparation à la production
    • Son système de build qui « fonctionne tout simplement » aide aussi au prototypage, mais il s’accompagne d’une complexité supplémentaire : il faut modéliser la disposition physique des données

Les avantages de l’approche par index en Rust et son coût pour du petit code

  • Quand on écrit un compilateur en Rust, le conseil courant consiste à éviter les pointeurs et à utiliser des index
  • Les index ont plusieurs avantages dans de grandes bases de code
    • Ils permettent de placer les tables latérales dans les modules concernés, ce qui réduit le couplage
    • Un index est un u32 et favorise une disposition struct-of-arrays, avantageuse pour les performances
    • Ils sont faciles à sérialiser ou à connecter à un framework de compilation incrémentale, ce qui rend la stratégie de calcul plus flexible
  • Mais dans une programmation à petite échelle, l’approche par index elle-même devient fastidieuse, et cette charge peut être rédhibitoire dans des expérimentations de loisir
  • OCaml conserve une impression un peu datée, et dans ce contexte, la question est de savoir si TypeScript peut servir d’alternative équivalente à ML

Deno et TypeScript offrent un environnement d’expérimentation rapide

  • L’environnement de départ utilisé est deno
    • Il offre une expérience prête à l’emploi permettant d’utiliser TypeScript directement
    • Dans OCaml, c’est un point douloureux ; Rust fait mieux qu’OCaml ou C++, mais Deno offre une expérience encore plus simple que Rust
  • L’expérience de développement avec Deno convient bien au petit hacking PLT
    • C’est un binaire unique
    • Le linting et le formatage sont intégrés
    • Il n’y a pas d’étape de compilation séparée
    • Un task runner intégré et un mode watch sont disponibles
  • TypeScript lui-même fournit un système de types suffisamment flexible, avec une syntaxe légère

Les patterns TypeScript vus à travers un petit type checker

  • L’AST commence par des expressions dotées d’informations de position dans le fichier
    • Location possède file, line et column
    • En TypeScript, les chaînes sont simplement des string et les nombres simplement des number, donc il n’est pas nécessaire de se demander s’il faut distinguer usize et u32
  • Les expressions séparent la position et le kind, puis généralisent ensuite les données associées sous la forme Expr<T>
    • Juste après le parsing, une expression possède des données void
    • Une expression traitée par le type checker possède des données Type
    • La fonction d’inférence de type reçoit un ast.Expr<void> et renvoie un ast.Expr<Type>
  • TypeScript n’ajoutant pas automatiquement de comportement à l’exécution, il faut ajouter soi-même des informations de type runtime pour faire du matching sur les types union
    • Des champs comme tag: "binary" et tag: "if" jouent ce rôle
    • tag: "binary" signifie qu’à l’exécution, cette valeur ne peut être que la chaîne "binary"
  • Les littéraux booléens et les littéraux entiers ayant quasiment la même forme, ils sont abstraits en ExprLiteral<T, V, Tag>
    • ExprBool<T> est ExprLiteral<T, boolean, "bool">
    • ExprInt<T> est ExprLiteral<T, number, "int">
  • Les valeurs de type sont séparées en TypeBool et TypeInt, et des valeurs singletons du même nom sont aussi fournies
    • TypeScript efface complètement les types, si bien que les noms liés aux types et ceux liés aux valeurs existent dans des espaces de noms séparés
    • Cette propriété permet de définir un type et une valeur avec le même nom

Visitor, transformation, type d’erreur et desugaring

  • Le switch de TypeScript étant une instruction et non une expression, un visitor est défini afin de traiter confortablement les kinds d’expression
    • Les méthodes bool, int, binary et if traitent chacune le kind correspondant
    • L’autocomplétion de l’éditeur aide à écrire les case du switch et l’implémentation du visitor
  • transform<U, V> est une fonction de parcours généralisée qui transforme un Expr<U> en Expr<V>
    • La transformation s’exécute bottom-up
    • Lorsqu’un nœud interne est visité, ses sous-expressions ont déjà été transformées ; le type du visitor devient donc Visitor<V, V> et non Visitor<U, V>
  • En tirant parti du fait que TypeScript est un langage à typage dynamique à l’exécution, on peut aussi construire un parcours plus général avec Object.keys
    • Même dans ce cas, on peut conserver une signature de fonction statique
    • Ce n’est pas indispensable dans l’exemple, mais il reste possible de basculer vers une approche dynamique si nécessaire
  • Les erreurs de type ne sont pas accumulées dans un tableau par effet de bord, mais représentées par le type TypeError
    • Type devient TypeBool | TypeInt | TypeError
    • TypeError possède tag: "Error", location et message
    • type_equal renvoie true si l’un des deux côtés est Error, afin d’éviter les échecs en cascade
  • Le type checker final vérifie les expressions binary et if
    • Une expression binary renvoie l’erreur "binary expression operands have different types" si les types des opérandes gauche et droit diffèrent
    • Une expression if renvoie l’erreur "if condition is not a boolean" si la condition n’est pas un booléen
    • Si les types des branches then et else diffèrent, elle renvoie l’erreur "if branches have different types"
  • Le résultat demande une certaine quantité de typage, mais l’autocomplétion compense largement ; on a peu l’impression de se battre avec le langage, qui épouse naturellement la forme du problème
  • Les raisons pour lesquelles TypeScript est productif comme outil pour bidouiller de petits langages se résument en trois points
    • Deno est un runtime de scripting petit, fermé, puissant et optimisé pour un workflow de développement efficace
    • Les outils TypeScript rendent l’IDE utile et productif, et Deno évite toute configuration
    • Le langage est puissant à la fois à l’exécution et à la compilation ; il permet des représentations assez sophistiquées par les types, tout en autorisant un repli vers une approche dynamique si nécessaire
  • Une idée supplémentaire consiste à désucrer de manière type-safe beaucoup de sucre syntaxique
    • Expr et ExprKind ne sont pas paramétrés sur les données associées, mais récursivement sur l’ensemble de ExprKind
    • ExprKindCore représente l’ensemble des expressions de base
    • ExprKindSugar contient soit des expressions de base, soit des expressions pouvant être désucrées en expressions de base
    • desugar(expr: ExprSugar): ExprCore réduit une expression avec sucre syntaxique en expression cœur
    • desugar_one(expr: ExprKindSugar<ExprCore>): ExprKindCore<ExprCore> effectue une transformation d’un seul niveau lorsque les sous-expressions ont déjà été désucrées

À lire aussi

1 commentaires

 
GN⁺ 2023-08-20
Avis de Hacker News

  • TypeScript est globalement un excellent langage, et le fait qu’une fonction soit un objet pouvant avoir des propriétés/méthodes est sous-estimé.
    On peut exécuter un tableau de fonctions comme des commandes puis y ajouter plus tard des descriptions comme help, ou ajouter de l’état via des closures/l’application partielle, sans définir prématurément des classes comme Command.
    Dans l’orienté objet, donner des noms trop tôt crée souvent beaucoup de frictions, et il semble plus naturel de passer les valeurs nécessaires à une fonction que d’avoir une structure du type VideoCompressor#compress().

    • Plus exactement, c’est davantage une fonctionnalité de JavaScript que de TypeScript.
      Les autres langages qui prennent en charge des objets se comportant comme des fonctions sont répertoriés ici : https://en.wikipedia.org/wiki/Function_object
    • En Go, on peut aussi attacher des méthodes à des fonctions, et en fait quasiment à n’importe quel type.
      Comme les handlers de net/http, une structure peut implémenter une méthode serve, ou une fonction handler peut s’appeler elle-même pour satisfaire une interface.
      En Clojure, on peut traiter cela de façon similaire en attachant des métadonnées à une var de fonction, et comme c’est du Lisp, les macros permettent de faire presque n’importe quoi.
      De plus, les canaux CSP de core/async séparent l’exécution et la communication, ce qui évite le problème de « couleur » des fonctions avec callbacks/promesses/async/await, et les commandes peuvent se comporter comme des producteurs envoyant leurs résultats vers un canal.
    • On peut obtenir un effet similaire avec les interfaces à méthode unique de Java.
      Quel que soit le nom de la méthode, elles peuvent être utilisées dans un contexte fonctionnel, sans avoir à référencer le nom concret de la méthode.
      En revanche, je n’aime pas trop qu’une fonction possède des propriétés, embarque de l’état, et puisse changer de comportement même appelée avec les mêmes arguments. À mon avis, l’un des grands avantages de la programmation fonctionnelle est justement de s’éloigner de l’état à la manière de l’orienté objet.
    • Python va bien dans ce sens, puisque tout y est objet.
    • En C#, on peut exprimer quelque chose de similaire avec Func pour les fonctions qui renvoient une valeur, et Action pour celles qui n’en renvoient pas.
      Les expressions lambda de JavaScript ressemblent beaucoup à celles de C#, et les signatures de fonctions de TypeScript et C# sont assez proches.
      Il existe aussi un petit dépôt qui montre les similarités entre JavaScript, TypeScript et C# : https://github.com/CharlieDigital/js-ts-csharp
      Capture d’écran montrant la même logique côte à côte en JS/TS/C# : https://github.com/CharlieDigital/js-ts-csharp/blob/main/js-...

  • Ce n’est pas si surprenant. TypeScript est, au fond, un autre langage qui a intégré, non sans peine, une bonne partie des fonctionnalités de la famille ML.
    L’absence de vrai pattern matching le rend moins pratique qu’OCaml, mais comparé à des langages comme C#, Swift, Dart ou Kotlin, il reste tout à fait correct.

    • C’est une comparaison faite à un niveau trop élevé. En pratique, le ressenti est assez différent.
      TypeScript a un système de types puissant, mais sa bibliothèque standard de base et le langage lui-même laissent à désirer, et il n’a ni pattern matching ni expression switch.
      Dart a un modèle objet fermé, avec moins de liberté dynamique, un système de types et des expressions plus faibles, et quasiment pas d’outils de métaprogrammation, ce qui oblige à s’appuyer sur du boilerplate à la Java et des générateurs de code.
      C# est, parmi les langages cités, celui qui se rapproche le plus des fonctionnalités ML, mais contrairement à TypeScript il n’a pas de types somme, ce qui rend beaucoup de choses plus fastidieuses.
    • Dans un compilateur pédagogique de style Pascal-C que j’avais autrefois écrit en Haskell, les combinateurs de parseurs permettaient d’exprimer directement la grammaire en code, d’une façon proche de BNF.
      Par exemple, on pouvait combiner un parseur reconnaissant { ... } avec d’autres parseurs, et définir une instruction comme étant soit du contrôle de flux, soit une déclaration, soit une affectation.
      Le traitement des listes et le pattern matching à la ML étaient très expressifs pour manipuler la représentation intermédiaire.
    • Quand j’ai besoin de pattern matching en TypeScript, j’aime bien utiliser cette bibliothèque : https://github.com/gvergnaud/ts-pattern
    • Il est difficile de dire que TypeScript a repris la plupart des fonctionnalités de ML.
      Même dans l’article, comme switch n’est pas une expression, il fallait contourner le problème avec le patron visiteur, et la prise en charge des itérateurs en JavaScript est étrangement insuffisante.
      .map() existe, mais ne fonctionne que sur les tableaux, et ne peut pas s’appliquer directement aux itérateurs génériques.
    • Quand on utilise TypeScript et kotlin-js, les deux langages paraissent assez proches.
      Il y a beaucoup de différences, mais la transition n’est pas difficile, et même si je préfère personnellement Kotlin, je peux utiliser les deux.
      Je me demande ce que donnerait TypeScript s’il s’affranchissait de la compatibilité JavaScript pour compiler vers WASM. Kotlin est en train d’ajouter un compilateur WASM et dispose déjà d’un transpileur JS ; le même code se charge en WASM de façon plus compacte et plus rapide.
      Le JavaScript des navigateurs n’est pas une bonne cible de compilation, et comme de plus en plus de nouveaux projets démarrent directement en TypeScript, l’argument selon lequel il faut faciliter la migration depuis le JavaScript existant devient lui aussi de moins en moins fort.

  • Quand on passe de Rust à TypeScript et inversement, l’absence de fonctionnalités comme les énumérations taguées saute vraiment aux yeux.
    La proposition d’énumérations ADT semble à l’arrêt ; je me demande s’il existe d’autres efforts en ce sens : https://github.com/Jack-Works/proposal-enum/discussions/19

    • Pour des usages similaires, je trouve que les unions discriminées fonctionnent plutôt bien

  • Le système de types de TypeScript est intéressant, mais on se demande à quel point le compilateur serait plus rapide s’il était écrit dans un langage compilé
    Bien sûr, cela suppose fortement qu’il s’agisse d’une « bonne implémentation »

    • swc et esbuild ne sont pas de bons points de comparaison. Une grande partie du gain de vitesse vient du fait qu’ils suppriment la syntaxe propre à TypeScript pour générer du JavaScript
      tsc n’est vraiment lent qu’au premier lancement, et avec le flag incremental ou un mode de surveillance --transpile-only, le temps de compilation descend généralement sous les 100 ms, ce qui rend la différence ressentie avec SWC ou ESBuild presque inexistante
    • L’équipe TypeScript a répondu à ce sujet : https://twitter.com/drosenwasser/status/1260723846534979584
      L’idée est que si la vérification de types d’un programme de taille moyenne prend 20 secondes, ce n’est généralement pas parce que c’est du JS, mais parce que les types provoquent une explosion combinatoire
      D’autres runtimes peuvent apporter des gains en parallélisme ou en temps de démarrage, mais ils disent ne pas avoir vu de benchmark centré CPU justifiant une accélération globale d’un facteur 20
    • Le système de types est amusant tant qu’on ne commence pas à exploiter les génériques au maximum
      Puis, après avoir passé toute une journée à déboguer 5 lignes de logique de types, on se demande comment on en est arrivé là
    • Plus besoin de se contenter d’imaginer : https://github.com/dudykr/stc
      C’est un projet écrit en Rust par l’un des principaux développeurs de SWC : SWC compile TS en JS, et STC vérifie les types TS
    • Les performances récentes du compilateur TypeScript se sont beaucoup améliorées
      Le futur isolated declaration mode pourrait réduire les temps de compilation jusqu’à 75 % : https://github.com/microsoft/TypeScript/pull/53463#issuecomm...

  • Pour quelqu’un qui commence tout juste à apprendre les compilateurs, je recommande ce livre : https://keleshev.com/compiling-to-assembly-from-scratch/
    L’auteur y construit un compilateur vers l’assembleur ARM 32 bits à partir d’un sous-ensemble de TypeScript, et explique que le code ressemble presque à du pseudo-code, ce qui le rend très accessible

    • Je recommande aussi vivement Crafting Interpreters : https://craftinginterpreters.com/
      Le livre est divisé en deux parties : la première construit un interpréteur de langage en Java, la seconde compile le même langage en bytecode puis implémente une machine virtuelle de bytecode en C
      Chaque ligne de code de l’implémentation est référencée dans le livre

  • Pour éviter le patron visiteur, on peut utiliser un switch façon IIFE avec une fonction utilitaire run
    Il suffit d’écrire un switch dans une fonction immédiatement invoquée et de laisser le type de retour être inféré

    • J’ai écrit un article sur ce pattern : https://maxgreenwald.me/blog/do-more-with-run
    • En réalité, même ça n’est pas nécessaire : il suffit d’appeler immédiatement une fonction pour que le type de retour soit inféré
      Si les () à la fin vous dérangent et que vous voulez éviter l’IIFE, vous pouvez définir la fonction séparément puis l’appeler

  • J’écris actuellement un compilateur en TypeScript, et je suis d’accord pour dire que ce n’est pas aussi mauvais qu’on pourrait le croire
    Au début, j’avais commencé avec Deno comme l’auteur, mais j’ai fini par passer à Bun ; malgré quelques aspérités, j’en suis plus satisfait que de Deno, et c’est très rapide
    Pour un frontend standard de générateur de parseur, Ohm-js est assez agréable : https://ohmjs.org/
    Le compilateur officiel tsc est trop énorme pour que je recommande de le lire ; pour voir comment tsc fonctionne, mini-typescript est préférable : https://github.com/sandersn/mini-typescript/
    La branche centi-typescript est particulièrement utile : https://github.com/sandersn/mini-typescript/tree/centi-types...
    J’ai hâte que le GC et l’accès au DOM soient possibles dans WASM

    • Je suis curieux de savoir ce qui t’a poussé à passer à Bun

  • Je pensais que TypeScript aurait un surcoût supplémentaire à cause des interfaces, c’est donc surprenant
    Je me demande si cela peut s’appliquer à d’autres domaines, par exemple si ce serait aussi adapté au parsing de langages

    • À l’exécution, le coût des interfaces est de 0
      Elles disparaissent complètement pendant la compilation

  • Le résultat n’est pas très surprenant. Le compilateur TypeScript lui-même est écrit en TypeScript
    En tant que ML, TypeScript est déjà éprouvé au quotidien dans des environnements de production lourds

  • J’ai déjà écrit un compilateur en C#, et ce qui semble particulier ici, ce sont surtout les types union
    Personnellement, j’ai choisi d’éviter la verbosité du patron visiteur, et j’attends une fonctionnalité d’énumérations fermées pour avoir une vérification d’exhaustivité à la compilation

    • Quand on utilise un langage sans types union ni enums à la Rust, cette fonctionnalité manque beaucoup
      Les alternatives sont généralement maladroites. Soit on crée une classe représentant un type somme avec N propriétés nullable et on s’appuie sur une condition documentée du type « exactement une seule est non-null », soit on fait hériter plusieurs classes d’une classe commune ; dans les deux cas, cela paraît lourd
      Pour créer plusieurs types union qui se recoupent, les deux approches exigent soit de la duplication, soit des combinaisons astucieuses