Les articles qui ont changé ma façon de voir les langages de programmation
(bernsteinbear.com)- Présentation de divers articles, travaux de recherche et vidéos qui ont profondément changé ma vision des langages de programmation et des compilateurs
- Des ressources qui ont considérablement élargi ma compréhension de sujets pratiques comme l’implémentation du GC, la conception d’optimiseurs, l’allocation de registres et les moteurs d’expressions régulières
- Des structures et algorithmes concrets comme Z3, les domaines abstraits, la forme SSA et les E-Graphs y sont expliqués simplement, avec de vrais exemples de code
- Chaque ressource présente des concepts complexes de manière concise, extensible et facile à comprendre
Présentation d’articles qui ont transformé ma compréhension des langages de programmation et des compilateurs
- Il m’arrive parfois de tomber sur des articles, billets de blog ou vidéos sur les langages de programmation et les compilateurs qui changent complètement ma manière de penser ces sujets
- Pour certains textes, leur impact est si fort que je ne me souviens même plus de ce que je pensais avant de les lire
- Voici une présentation de quelques-unes de ces ressources (sans ordre particulier)
GC, optimiseurs, domaines abstraits et allocation de registres
- a simple semi-space collector d’Andy Wingo montre très bien comment passer de la théorie à la pratique pour les concepts de ramasse-miettes Cheney / par copie / compactant
- Le cœur de l’implémentation du GC dans le texte est très concis, extensible et peut se comprendre en une demi-journée
- L’article Implementing a Toy Optimizer de CF Bolz-Tereick provoque un vrai changement de perspective sur l’approche par rewrite d’instructions dans un optimiseur
- Au lieu d’un simple rechercher-remplacer, il met l’accent sur l’usage de forwarding pointers et introduit l’idée de union-find
- Toute la série sur ce toy optimizer apporte, article après article, des idées nouvelles et intéressantes
- L’article A Knownbits Abstract Domain for the Toy Optimizer, Correctly présente à la fois un nouveau domaine abstrait et une manière d’utiliser Z3
- Il montre non seulement comment Z3 est utilisé pour diverses preuves sur des opérations numériques, mais aussi comment il peut servir de moteur de vérification de code Python
- Il introduit l’idée que, si Z3 ne trouve pas de contre-exemple, on obtient une garantie de correction du code
- Dans Cranelift, Part 3: Correctness in Register Allocation, Chris Fallin explique une méthode qui prouve directement la validité de l’allocation de registres pour chaque entrée
- En production, on obtient soit une allocation correcte, soit un crash significatif
- L’article introduit aussi une approche qui explore l’espace des états et détecte les bugs via des techniques de fuzzing
Parsing, interpréteurs, JIT et structures abstraites
- Regular Expression Matching: the Virtual Machine Approach de Russ Cox présente l’implémentation d’un moteur d’expressions régulières en environ 50 lignes de code facile à lire
- Au passage, le texte explique aussi clairement les principes des coroutines, fibres, ordonnanceurs, etc.
- micrograd d’Andrej Karpathy est un exemple d’implémentation ultra-minimale permettant de faire fonctionner un réseau de neurones sans bibliothèque externe, utile pour acquérir les structures et principes de base du machine learning
- How I implement SSA form de Fil Pizlo présente une nouvelle manière d’améliorer la structure union-find
- Dans la transformation SSA, les pointeurs supplémentaires sont gérés via un Identity tag interne aux objets
- Le texte ouvre aussi d’autres pistes de réflexion, comme la forme Phi/Upsilon ou les effets heap de style TBAA
- Speculation in JavaScriptCore de Fil Pizlo traite en détail de diverses méthodes d’implémentation d’optimiseurs dans JavaScriptCore
- À chaque relecture, on en retire de nouveaux enseignements
Conception de compilateurs, parseurs, structures d’IR et E-Graphs
- Dans sa présentation Modernizing Compiler Design for Carbon Toolchain (vers la 29e minute), Chandler Carruth explique comment définir un objectif de temps de compilation extrêmement ambitieux et concevoir l’architecture d’ensemble
- À partir d’environ la 40e minute, il détaille la structure couche par couche
- A Python Interpreter Written in Python d’Allison Kaptur aide à comprendre facilement le fonctionnement interne de l’interpréteur de bytecode de CPython
- Parsing expressions by precedence climbing d’Eli Bendersky présente la méthode de parsing Precedence Climbing, plus facile à comprendre et moins lourde à développer qu’un parseur récursif descendant traditionnel
- Ruby JIT Challenge de Takashi Kokubun montre la génération de code et une nouvelle méthode d’allocation de registres (
stack foldingà la compilation) - [An Incremental Approach to Compiler Construction (PDF)(https://bernsteinbear.com/assets/img/11-ghuloum.pdf) d’Abdulaziz Ghuloum explique une méthode d’implémentation en passe unique qui permet de comprendre d’un seul coup l’architecture classique des compilateurs multi-étapes
- Il adopte une approche qui ajoute progressivement chaque fonctionnalité de bout en bout
- Lessons from Writing a Compiler de Fernando Borretti explique la stratégie d’implémentation d’un compilateur en la formulant de manière claire
- L’article egg: Fast and extensible equality saturation change en profondeur la manière de penser les optimiseurs et l’ordre des passes
- Il propose de construire un hypergraphe compressé contenant toutes les versions possibles d’une expression, puis de choisir la meilleure
- Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations de Chris Fallin montre que les e-graphs fonctionnent aussi efficacement dans un compilateur industriel réel
- Acyclic Egraphs and Smart Constructors de Phil Zucker explore la structure des e-graphs acycliques et l’usage de smart constructors
- C’est un texte difficile à comprendre au départ, mais qui devient de plus en plus clair avec le temps
Stockage des AST, interprétation dynamique massivement parallèle et autres sujets
- ce commentaire Reddit de Bob Nystrom et Flattening ASTs d’Adrian Sampson
- montrent comment stocker un AST de façon compacte, presque comme du bytecode,
- et ont lancé une réflexion plus large sur le fait qu’en stockant ainsi les nœuds d’IR, on peut aussi permettre une interprétation massive, parallèle et sans verrou
- Les remarques de Cliff Click sur la vitesse d’allocation des buffers ont également influencé cette manière de penser
1 commentaires
Avis Hacker News
J’aime beaucoup ce billet. J’ai fait pas mal de recherche en informatique récemment, mais parmi les choses mentionnées ici, il y en a encore que je n’avais jamais rencontrées. J’aimerais présenter quelques articles que j’adore mais qui ne figurent pas ici : « Open, Extensible Object Models » de Ian Piumarta traite d’un système méta-objet orienté objet minimal qui donne un maximum de liberté au programmeur ; en gros, seule l’opération d’envoi de messages est définie, et tout le reste peut être modifié à l’exécution. On a l’impression d’une version pratique de « Art of the Metaobject Protocol ». « Scripting: Higher-Level Programming for the 21st Century » de John Ousterhout traite de la dichotomie entre langages de programmation système et langages de script. On rêve toujours d’un langage multiparadigme parfait qui permette de tout faire à la fois rapidement et avec productivité, mais il vaut souvent mieux combiner un langage système compilé, rapide et complexe avec un frontend interprété, pratique et flexible. En réalité, dans bien des cas, C et Tcl suffisent déjà ensemble. C’est une lecture indispensable pour quiconque crée des langages de programmation. Project Oberon de Niklaus Wirth est un exemple d’implémentation d’un système informatique complet, de l’interface utilisateur haut niveau jusqu’au noyau, au compilateur et à une architecture CPU proche du RISC. Il a plaidé avec force pour le « lean software » et l’a réellement mis en pratique. À une époque comme la nôtre, envahie par l’enfer des dépendances et l’abstraction excessive, c’est un artisanat perdu
J’aime vraiment beaucoup ce billet. Des textes sur les langages de programmation ont changé ma manière de voir la programmation elle-même. Je repense souvent à une citation de TAPL (Types and Programming Languages) sur la « sécurité » : un langage sûr est un langage qui empêche le programmeur de se tirer une balle dans le pied et qui protège ses abstractions. Autrement dit, ce qui compte, c’est la capacité du langage à garantir l’intégrité des abstractions qu’il fournit et des abstractions de plus haut niveau que le programmeur construit lui-même. Par exemple, s’il existe une abstraction de tableau, elle ne devrait pouvoir être modifiée que lorsqu’on la met à jour explicitement, et elle ne devrait pas non plus pouvoir altérer par erreur d’autres structures de données
À propos d’habitudes de développement intéressantes… Aaron Hsu, connu pour APL, écrit son code à la plume de manière calligraphique pour mettre de l’ordre dans ses idées. Moi, de façon similaire, je clarifie ma pensée en griffonnant au stylo-bille bon marché des sortes d’organigrammes d’objets Python. C’est une sorte d’UML low cost
Moi aussi, quand je m’attaque aux problèmes les plus difficiles, je finis par chercher un stylo-plume. J’ai l’impression qu’écrire avec un stylo-plume me fait entrer dans un espace mental complètement différent. Les limites d’édition encouragent une pensée plus cohérente et linéaire, mais le fait de pouvoir passer librement de l’anglais au code, aux maths ou aux diagrammes ouvre la créativité
Le lien entre écriture manuscrite et amélioration de la mémoire est effectivement démontré. Prendre des notes sur ordinateur, c’est à peu près comme laisser des empreintes digitales sur le manche. J’espère que la technologie OCR deviendra assez bonne pour permettre de tout enregistrer et rechercher même en ne notant les choses qu’à la main
Je recommande vivement de regarder les conférences de Rich Hickey, surtout les premières. Moi aussi, après en avoir vu, ma manière de voir la programmation elle-même a complètement changé
Pour moi, avec « Programming Perl » de Larry Wall, ce sont les conférences de Rich Hickey qui ont eu le plus d’influence
J’ai presque envie de plaisanter en disant de passer « Simple made easy », parce que tous les intervenants de conférence le citent depuis dix ans au point que c’en est devenu un cliché. Personnellement, je préfère « Hammock driven development », mais c’est moins facile à recommander en entreprise
C’est dommage qu’Abdulaziz se soit fait discret après son retour au Koweït. Il était stagiaire sur la VM Maxine en 2009 et c’était quelqu’un de vraiment bien. Cet article est une vraie pépite
Il y a eu récemment un bon billet sur un interpréteur basé sur des closures pour accélérer les interpréteurs. J’ai essayé cette technique pour créer un petit interpréteur brainfuck, et c’était plutôt rapide. Je n’aurai probablement jamais l’occasion de l’utiliser ailleurs, mais c’était instructif comme expérience
J’aimerais voir paraître ce genre de texte sur des langages plus haut niveau comme JavaScript ou .NET. Cet auteur est très intelligent, mais il travaille à un niveau plus bas (ou plus haut ?) que la plupart des utilisateurs
Les autres billets de son blog sont eux aussi vraiment excellents
À propos de micrograd : je me demande s’il existe plus de documentation que le simple code source du dépôt Github
Je dis ça parce que j’apprécie cette personne, mais les textes ici ne portent pas vraiment sur les PL (langages de programmation) en eux-mêmes ; ils parlent presque tous de compilateurs, à part le garbage collector. J’aime aussi les compilateurs, bien sûr, mais c’est un autre sujet que les PL