Devenir plus intelligent en lisant le code C d'Arthur Whitney (2024)

• Analyse d’un interpréteur du langage K en C de 50 lignes conçu par Arthur Whitney, avec une tentative de décoder son style de programmation singulier
• Le code contient de nombreuses structures expérimentales inhabituelles dans du C classique, comme une syntaxe compacte fondée sur des macros, des extensions C non standard et l’usage d’arguments implicites
• L’auteur interprète lui-même le sens de chaque macro et fonction, tout en explorant la philosophie des langages de la famille APL ainsi que les forces et limites de la densité du code
• Parmi les points forts du code : sa brièveté et sa forte expressivité structurelle ; parmi ses faiblesses : la syntaxe non standard et la baisse de lisibilité
• En conclusion, ce code est présenté moins comme un exemple de « comment écrire court » que comme une démonstration de l’importance d’écrire du code après avoir entièrement compris le problème

---

Arthur Whitney et son code

• Arthur Whitney est un informaticien qui a conçu les langages A, K et Q ainsi que les bases de données kdb et Shakti
  • kdb est une base de données de séries temporelles ultra-rapide utilisée dans la finance, et Shakti en est une version plus rapide encore, pensée pour traiter des jeux de données de l’ordre de mille milliards de lignes
• Ses langages sont des langages orientés tableaux fortement influencés par APL, qui privilégient la concision et l’expressivité mathématique
• L’article ne se concentre pas sur les applications financières, mais sur l’analyse du style très particulier du code C écrit par Whitney

Structure de l’interpréteur K de 50 lignes

• Le dépôt public ksimple contient un interpréteur C d’environ 50 lignes que Whitney a écrit en quelques jours
• Le cœur du code se compose de deux fichiers, a.h et a.c, et se distingue par des définitions de fonctions abrégées via des macros ainsi qu’une structure qui traite des pointeurs comme des entiers
• La construction typedef char*s,c; définit s comme un pointeur de chaîne et c comme un type caractère
• s Q=(s)128; est un exemple de pointeur utilisé comme un entier ; dans tout le code, Q sert de valeur spéciale représentant un état d’erreur
• On y trouve de nombreuses extensions GCC, comme les statement expressions de la forme ({e;}) et l’opérateur ?:

Sens des principales macros et fonctions

• #define _(e...) ({e;}) : macro qui regroupe plusieurs instructions en une seule expression
• #define i(n,e) : forme abrégée de boucle, qui permet d’exprimer une boucle for sur une seule ligne
• #define Q(e) et assimilées sont des macros de gestion d’erreurs ; Qr, Qd et Qz renvoient respectivement des erreurs de rank, domain et not-yet-implemented
• Les macros _s, _i, f, F simplifient les déclarations de fonctions et utilisent implicitement les arguments x et a
• ax, ix, nx et autres sont des macros de test de type et d’indexation ; ax détermine si x est un atome (atom)
• f(w,write(1,ax?&x:x,ax?1:strlen(x));x) est une fonction d’affichage : si la valeur est atomique, elle s’affiche comme un caractère ; si c’est un vecteur, comme une chaîne

Fonctionnement de l’interpréteur

• La fonction m(x) gère l’allocation mémoire et la création de pointeurs contenant aussi des informations de longueur ; la longueur maximale d’un vecteur est de 255 octets
• La macro g(a,v) unifie le traitement des opérations sur atomes et vecteurs ; des fonctions comme not, sub, At et _A sont définies à partir d’elle
• La macro G(f,o) permet la génération automatique de fonctions d’opérateurs binaires et prend en charge des opérations comme <, ==, +, *, &, |
• cat, rev, cnt, Tak sont des fonctions de manipulation de vecteurs ; rev utilise la fonction ind pour générer des index inversés
• La fonction e() est un évaluateur récursif qui lit la chaîne de droite à gauche et traite les variables à un caractère, nombres et opérateurs
• main() prend l’entrée, l’évalue via e(), puis affiche le résultat dans une boucle de type REPL

Évaluation du style de code

• Avantages
  • Un ensemble compact d’opérations primitives construit avec des macros composables
  • Une faible longueur de code qui permet de voir toute la logique d’un seul coup d’œil, sans faire défiler l’écran
  • Une expression très dense qui compresse la structure logique du programme
• Inconvénients
  • Un traitement typé peu sémantique qui utilise char* comme s’il s’agissait d’un entier
  • Une lisibilité réduite à cause de l’usage direct des codes ASCII, de ternaires complexes et d’une syntaxe non standard
  • Les arguments implicites et les noms de variables très courts rendent l’intention difficile à saisir
• Éléments neutres
  • La syntaxe spécifique à GCC (?:, statement expression) est intéressante, mais réduit la portabilité
  • L’usage d’arguments implicites peut être utile dans un petit programme, mais devenir source de confusion à grande échelle
  • Les noms courts peuvent être efficaces une fois assimilés, mais transmettent mal le sens

Conclusion et enseignements

• Ce code ne montre pas simplement « comment écrire court », mais une façon d’écrire après avoir complètement compris le problème
• Le code de Whitney prend la forme d’un modèle mathématique déjà achevé transposé en code, autrement dit d’un résultat où la pensée s’exprime directement dans le programme
• L’auteur y voit aussi une remise en question de sa propre habitude à résoudre le problème à l’intérieur même du code
  et insiste désormais sur l’importance de la modélisation conceptuelle et de la clarification de la pensée avant l’écriture
• Au final, cette expérience est présentée comme un exercice pour entraîner la capacité à lire du code et explorer l’équilibre entre densité du code et clarté de la pensée

Idées d’expérimentations futures

• Suggestions d’extension de l’interpréteur :
  • prise en charge de vecteurs en virgule flottante
  • gestion de plus de 255 éléments
  • nombres et noms de variables à plusieurs chiffres ou caractères
  • littéraux de tableau et ignorance des espaces
  • ajout de gestion mémoire et d’affichage des erreurs
  • compléter les fonctions non implémentées
• De telles extensions pourraient devenir une expérience pour faire évoluer ce style de code à la Whitney vers un langage réellement utilisable, tout en en préservant l’esprit

[GN⁺]

Avis Hacker News

• Les macros de ce code servent à compresser les opérations communes J’ai lu J Incunabulum avant de regarder ce code, et pour des programmeurs à l’aise en C qui commenceraient la lecture au milieu, les définitions de macros du début peuvent être déroutantes Comme les macros s’empilent les unes sur les autres, le code gravit rapidement l’échelle de l’abstraction J’aime particulièrement la macro Iterate (i), qui réduit une boucle verbeuse à une seule lettre Si ce code très dense est difficile à lire, c’est parce qu’il crée des dizaines d’abstractions en quelques lignes et les utilise aussitôt Il faut donc le lire lentement, une lettre à la fois Ayant travaillé sur de grandes bases de code composées de centaines de fichiers minces, je trouve au contraire cette compressibilité extrême assez rafraîchissante

  • J’ai eu une impression similaire en lisant Incunabulum, mais en remplaçant les noms de variables par des emojis, c’est devenu bien plus facile à comprendre Comme on peut le voir dans l’image du code en version emoji, une partie du problème ne vient pas seulement de la densité d’information, mais aussi de la forme des caractères (orthographe) Les langages modernes empêchent d’utiliser des symboles ou des emojis dans les identifiants, mais avec une telle distinction visuelle, ce serait bien plus lisible En outre, la plupart des éditeurs utilisent une coloration syntaxique par type, mais une coloration fondée sur les tokens (une couleur propre à chaque identifiant) est souvent plus utile Le “hashed syntax highlighting” de Sublime Text en est un exemple Avec ce changement, la structure du code est devenue évidente d’un seul coup d’œil
  • On dirait que les développeurs préfèrent au contraire les énormes bases de code Moi, j’aime les structures où l’on peut chercher directement avec grep *.[ch] sans sous-répertoires Les projets Java, en particulier, ont trop de petits fichiers au contenu maigre, ce qui complique la recherche Avec un IDE, ce serait peut-être mieux, mais je n’en utilise pas Dans une interview, Whitney disait vouloir faire tenir tout le code sur une seule page, et que son “IDE” était la console Windows et Notepad

• Pour comprendre le code C d’Arthur Whitney, il faut d’abord apprendre un langage de la famille APL Sinon, cela ressemble simplement à un style C bizarre Whitney essaie d’écrire du C comme de l’APL Le style sans espaces, avec des noms d’une lettre et des fonctions sur une seule ligne, est le même en APL Cela ressemble à un programmeur Pascal qui ferait des choses comme #define begin {, sauf que Whitney est bien plus original

  • Même du point de vue d’un utilisateur d’APL, cela paraît étrange Le langage K créé par Whitney emploie ce style, mais les fonctions sur une seule ligne étaient impossibles dans l’APL traditionnel Les macros, l’opérateur ternaire ou les noms de variables implicites n’existent pas en APL L’essence d’APL, ce sont les opérations sur tableaux immuables, et le style C de Whitney ne suit pas vraiment cette philosophie
  • À propos de « ça ressemble à un programmeur Pascal passé au C qui fait #define begin { », quelqu’un plaisante : « Ah, comme Stephen Bourne. »
  • Au début, cela ressemblait à un langage fonctionnel, puis cela a vite rappelé l’horreur du préprocesseur C
  • L’introduction de l’article explique déjà que « le C de Whitney est inspiré de l’APL » C’est une remarque sur le fait qu’il y a beaucoup de commentaires qui ne font que résumer l’article
  • Apprendre J semble aussi une bonne idée C’est plus accessible que l’APL, et cela utilise des symboles saisissables sur un clavier ordinaire

• En cherchant Shakti, j’ai vu que le lien Wikipedia redirigeait vers k.nyc, où la page ne contient que la seule lettre “k” En regardant la source, il n’y avait vraiment que `k

` On dirait une version HTML du minimalisme à la Whitney — tout ce qui n’est pas nécessaire est supprimé, avec l’impression de laisser le compilateur gérer implicitement le reste

• k

• Quel que soit le jugement qu’on porte sur le style de code de Whitney, ce billet de blog est une excellente analyse Pour un texte écrit en 8 heures, il a de la profondeur, et la conclusion m’a particulièrement marqué Lien vers l’original

• Cela rappelle la tentative de Stephen Bourne de faire du C un langage proche d’Algol Les exemples de mac.h et de expand.c dégagent une sensibilité similaire

• Il existe des “best practices” dans tous les domaines, mais elles ne fonctionnent bien que dans les cas moyens Dans certaines situations, il vaut mieux faire exactement l’inverse Au final, la sagesse collective doit servir de valeur par défaut, mais dès qu’on commence à réfléchir par soi-même, on en voit les limites

  • C’est pour cela que je n’aime pas l’expression “best practice” En réalité, ce n’est qu’un compromis moyen C’est un échange où l’on sacrifie l’efficacité et les performances pour gagner en maintenabilité et en cohérence
  • Construire un bon produit et la lisibilité ou courbe d’apprentissage d’une base de code sont deux choses distinctes Le fait que l’une soit réussie n’implique pas automatiquement l’autre

• J’ai apprécié qu’on adopte un point de vue équilibré sans se montrer agressif envers le code C’était une lecture agréable, et j’ai l’intention d’y revenir plus tard

• Je me demandais si ce style de code relevait d’un paradigme particulier J’ai très rarement vu ce genre de code dans des projets réels, à part des exceptions comme les “business card ray tracer” Le code source du langage J créé par Whitney a lui aussi un style extrêmement compressé

  • Oui, c’est le style de code propre à Whitney Il l’emploie de façon cohérente dans ses interpréteurs de langages de tableaux, et il est connu pour faire tenir des implémentations entières en quelques pages Il existe aussi un lien vers un méta-commentaire rassemblant des discussions HN sur le sujet
  • À « je n’ai jamais vu ce genre de code en vrai », quelqu’un répond : « Vous avez eu de la chance. » Ce n’est plus vraiment du C, mais une sorte de DSL interne construit au-dessus du C Le C n’est que la première cible de compilation
  • Cela ressemble à des langages de la famille APL comme J ou K Ils utilisent des symboles non ASCII et permettent de faire tenir énormément d’information sur une page grâce à une densité extrême Une fois habitué, cela a aussi l’avantage de réduire le nombre de couches d’abstraction
  • Il existe aussi une vidéo sur co-dfns réalisée dans une approche similaire Ce n’est pas du C, mais c’est écrit dans un style comparable, à forte densité
  • Sur le ton de la plaisanterie, quelqu’un appelle cela de l’“OCC (Obfuscated C Code)”

• Quand on voit les définitions de macros suivantes

  #define _(e...) ({e;})
  #define x(a,e...) _(s x=a;e)
  #define $(a,b) if(a)b;else
  #define i(n,e) {int $n=n;int i=0;for(;i