Programmation : programmer avec moins que rien

• Cet article met en scène, de façon satirique, un candidat en entretien d’embauche qui tente d’implémenter le simple problème FizzBuzz à l’aide de combinateurs de fonctions pures fondés sur le lambda-calcul
• Le protagoniste commence en JavaScript, puis se met progressivement à définir les combinateurs S, K et I, reconstruisant lui-même les structures fondamentales du langage
• Il exprime ensuite les booléens, les nombres, les listes et les chaînes de caractères uniquement avec des combinateurs, puis implémente la récursion via le combinateur Y
• Il finit par compléter FizzBuzz dans un style entièrement point-free, mais le code s’étend jusqu’à devenir illisible pour les humains
• Le texte explore avec humour l’essence des langages de programmation et l’extrême de l’abstraction, tout en révélant l’autodérision propre à la culture développeur

---

Le début de l’entretien : FizzBuzz et les combinateurs

• L’histoire commence lorsque l’intervieweuse Dana demande au candidat de résoudre le problème FizzBuzz
  • Au lieu d’une boucle classique, le candidat commence par définir les combinateurs S et K pour résoudre le problème
  • Dana est perplexe, mais le candidat continue en disant que « ça y est presque »
• Le candidat définit ensuite divers combinateurs comme I, B, C, W, T et les utilise comme éléments de base d’un nouveau langage
  • Chaque combinateur implémente des concepts clés du lambda-calcul comme la composition de fonctions, l’échange d’arguments ou l’auto-application
  • Dans les commentaires du code apparaissent aussi des surnoms de combinateurs comme « Bluebird, Cardinal, Warbler, Thrush »

Définition des booléens et des nombres

• Le candidat construit une logique booléenne en définissant TRUE, FALSE et NOT uniquement avec des combinateurs
  • Quand Dana demande si c’est du « lambda-calcul », il répond que « le lambda-calcul est trop volumineux »
• Il définit ensuite ZERO, SUCC, PRED, IS_ZERO et construit ainsi un système numérique (Church numeral)
  • SUCC implémente le successeur, PRED le prédécesseur, et DECREMENT une décrémentation qui ne descend pas sous 0
  • Les nombres de ONE à TEN sont définis successivement

Récursion et combinateur Y

• Le candidat définit la fonction ADD, puis la transforme progressivement en forme point-free
  • Il définit ADD_MAKER, puis l’enveloppe dans le combinateur Y pour rendre la récursion possible
  • Dana fait remarquer que JavaScript permet déjà la récursion, mais le candidat répond que « bientôt, ce ne sera plus du JavaScript »
• Comme l’évaluation stricte (eager evaluation) de JavaScript provoque un stack overflow, le candidat exécute son code dans Skoobert, un interpréteur JS « lazy »
  • Le résultat affiche correctement 3

Arithmétique, listes et chaînes

• Le candidat implémente toutes les opérations arithmétiques, comme SUBTRACT, MULTIPLY, MOD, DIVIDE, sur une base de combinateurs
  • Chaque opération est construite en combinant récursivement IS_ZERO, PRED, SUCC, etc.
• Il définit ensuite CONS, FIRST, REST, EMPTY pour construire une structure de liste
  • Des opérations fonctionnelles d’ordre supérieur comme MAP, FOLD, RANGE, CONCAT sont elles aussi implémentées sous forme de combinateurs
• Pour afficher les listes comme des chaînes, il écrit les fonctions renderList et showLines
  • Dana semble alors avoir déjà abandonné et ne réagit plus

Construction des caractères et des chaînes

• Le candidat définit les codes de caractères de 1 à 9, puis par dizaines, à l’aide de combinateurs
  • Tout CHAR_A à CHAR_Z, ainsi que CHAR_0 à CHAR_9, est exprimé comme combinaison numérique
• Via la fonction ARRAY, il convertit des chaînes en listes et construit FIZZ, BUZZ, FIZZBUZZ
  • La fonction extractString permet de reconvertir la liste en vraie chaîne de caractères
  • La sortie console affiche "fizzbuzz"

Conversion des nombres en chaînes

• Il définit NUMBER_TO_DIGIT_LIST, qui transforme un nombre en liste de chiffres, puis NUMBER_TO_STRING, qui la convertit en chaîne
  • DIVIDE, MOD, TEN et d’autres éléments servent à séparer chaque chiffre
  • La liste DIGITS_NUMERAL sert à faire la correspondance entre chiffres et caractères numériques
• Grâce à ce processus, la conversion nombre → caractère → chaîne devient possible à l’intérieur d’un système entièrement fondé sur des combinateurs

L’achèvement de FizzBuzz

• Après avoir défini FIFTEEN et ONE_HUNDRED, il génère une liste de 1 à 100 avec MAP et RANGE
  • Pour chaque nombre, il vérifie s’il est multiple de 3, 5 ou 15 afin d’afficher "Fizz", "Buzz", "FizzBuzz" ou la représentation textuelle du nombre
  • Le résultat final est affiché avec showLines(extractString)(FIZZBUZZ_RESULT)
• Quand Dana lui demande s’il est enfin satisfait, le candidat supprime toutes les définitions de variables et réécrit le code avec de purs combinateurs uniquement
  • Le résultat est une énorme expression composée seulement de S et K, longue de plusieurs milliers de lignes

Conclusion et sens

• Le texte explore les composants fondamentaux des langages de programmation tout en satirisant la tendance des développeurs à compliquer à l’excès des problèmes simples
  • Le titre, « programmer avec moins que rien », symbolise la tentative de reconstruire un monde à partir des unités minimales du langage
• Cette œuvre est une forme de littérature technique qui déploie avec humour et narration une compréhension profonde de la programmation fonctionnelle, du lambda-calcul et de la logique des combinateurs
  • En même temps, elle met en scène avec ironie cet esprit développeur capable de transformer même FizzBuzz en expérience philosophique

[GN⁺]

Avis Hacker News

• Comme on dirait que pas mal de gens se demandent « mais qu’est-ce que c’est que ce truc ? », voilà l’idée principale derrière un combinator
  un combinator est une fonction qui ne modifie pas d’état global et ne capture aucune variable externe. Avec les mêmes arguments, elle produit toujours le même résultat et n’a aucun effet sur le reste du système
  En combinant ces fonctions pures, on obtient encore un autre combinator. Autrement dit, la composition de fonctions pures reste une fonction pure
  On peut écrire ce genre de fonctions facilement, même en assembleur ou en C. Par exemple, si on implémente directement S et K en x64, puis qu’on compile Common Lisp au-dessus avec une approche fondée sur les combinators, alors au final Lisp tourne sur deux fonctions assembleur seulement
  Les performances ne seraient pas terribles, mais si on crée quelques centaines de combinators inline pour les motifs les plus courants et qu’on leur donne un nom, on obtient une « machine » assez pratique
  Cette structure ressemble aussi à Forth quand on a peur de la mutation, à une bytecode VM, ou à un CPU où l’on appellerait les combinators des « instructions »
  Au fond, on peut voir les combinators comme une expression de l’informatique appliquée qui ignore autant que possible les détails d’implémentation. C’est pour ça qu’on peut dire que c’est plus simple que le lambda-calcul
  Si on implémente le lambda-calcul avec quelques combinators, puis qu’on empile Lisp par-dessus, la quantité de travail dépendant de la machine à faire tout en bas de la pile devient extrêmement réduite

  • J’ai l’impression qu’à un moment, une fonction s’est appelée elle-même et a reçu une seed round
  • J’avais fait quelque chose de similaire quand j’étais étudiant·e — pas Lisp, mais un petit langage qui s’étendait par macros en lambda-calcul — et le fait qu’on puisse tout implémenter avec seulement S et K m’avait vraiment sidéré. En même temps, son inefficacité m’avait tout autant surpris. Cela dit, plus l’ensemble d’instructions s’agrandit, plus la situation s’améliore
  • En théorie, oui, tout est possible, mais en pratique il faut choisir une base de calcul plus utile que la réécriture de graphes. À moins de vouloir explorer les limites de la calculabilité, on est presque au niveau du tour de salon. Et la représentation des nombres pose aussi problème. Il faut au minimum des entiers en complément à deux et des destructeurs efficaces pour que ce soit vraiment impressionnant
  • Je me demande s’il existe réellement un Lisp implémenté sur des combinators de cette façon. Si oui, ça aurait l’air assez amusant à porter

• let A = (x) => (y) => (z) => x(z)(y((w) => z))
  

  Il suffit de composer ça quelques fois

  let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
  let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
  

  « Je n’utiliserai jamais ce truc de lambda-calcul. C’est un langage beaucoup trop boursouflé. »
  Mais en réalité, la logique combinatoire est encore plus boursouflée. Il faut plus de bits pour exprimer le même programme
  Le lambda-calcul est au contraire l’un des langages les plus concis qui existent
  Même dans un langage strict comme JavaScript, on peut obtenir un comportement lazy en enveloppant les arguments dans des lambdas factices. Voir par exemple cet interpréteur JS de BLC
  Pour des articles liés, voir ce PDF et cet exemple de l’IOCCC

  • Ce qui est intéressant, c’est que les interpréteurs de lambda-calcul les plus rapides (comme uni.c) finissent par convertir les lambda-termes en logique combinatoire pour les évaluer. Ils utilisent simplement un ensemble de base plus large que S et K
  • Par « bloated language », on entend un langage avec beaucoup de fonctionnalités inutiles. Par exemple, le code C++ peut être plus court que du C tout en étant un langage bien plus complexe
  • En regardant ce bloc de code, j’ai l’impression que les sons qui me sortent de la bouche correspondent presque exactement à la liste des arguments
  • Je pense qu’il y a une erreur de parenthèses dans les définitions de K et S. La version corrigée est la suivante

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
    let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
    

    Et on peut rendre un langage strict lazy de cette manière

    let A = x => y => z => () => x()(z())(y()(w => z()));
    

  • On se demande forcément : « c’est quoi, ce w ? »

• « Vous connaissez FizzBuzz ? »
  « Bien sûr. La version code golf en 10 caractères, la version en 12 lignes qu’un junior peut comprendre, ou la version complètement absurde pour frimer avec un savoir ésotérique ? »

  • En voyant ça, j’ai implémenté le FizzBuzz le plus rapide en C64 BASIC. J’ai agréablement gaspillé ma matinée
    Lien vers le résultat

• L’explication de la logique combinatoire était vraiment superbe. Le style d’écriture m’a rappelé cette série

  • C’est moins une explication qu’une performance de démonstration. Mais c’était quand même assez marquant
  • On dirait clairement que c’était inspiré par cette série. Ça aurait été bien de citer le nom de l’auteur
  • Au Royaume-Uni, l’accès est bloqué à cause de l’Online Safety Act, ce qui est dommage

• Ça m’a rappelé ce billet que j’avais lu autrefois : « FizzBuzz in TensorFlow »
  Lien

  • Cette fois au moins, j’ai pu suivre le raisonnement, donc c’était appréciable

• Ce genre de cadre d’entretien de programmation me semble un peu à côté de la plaque
  Le but d’un entretien est de (1) vérifier les connaissances de programmation du candidat, et (2) voir si la culture de programmation de l’entreprise lui convient
  Par exemple, si on recrute pour un poste JavaScript et que quelqu’un est profondément absorbé par la logique combinatoire, il y a de fortes chances que ce ne soit pas un bon match culturel. Donc ce n’est pas absurde de l’écarter

  • Ça semble probablement faire référence à cette série, même si ce n’est pas explicitement indiqué dans le texte original
  • Parfois, on a l’impression que les commentateurs de HN sont des gens qui ont oublié de s’amuser
  • Mettre en avant la diversité de la programmation, d’accord, mais ce n’est qu’une manière parmi d’autres de recruter une expertise dans un écosystème donné. Le plus souvent, c’est un choix fait pour gérer du code legacy ou tirer parti d’un écosystème existant
  • Dire des choses comme « recalé si ton QI est bas », c’est amusant, mais avec assez d’argent on peut de toute façon s’adapter à n’importe quel style OOP/FP/FRP
  • En réalité, ce genre d’entretien idéal existe rarement. La plupart du temps, ce sont des intervieweurs frustrés qui imposent leur vision du monde. Le travail réel n’a presque rien à voir avec le contenu de l’entretien

• Il est temps de se souvenir de Moses Schönfinkel
  Il a inventé la logique combinatoire en 1920 alors qu’il était élève de Hilbert. De retour en Russie, il a souffert de troubles mentaux et est mort dans la pauvreté à Moscou. D’après Wikipédia, ses articles auraient été brûlés par ses voisins pour se chauffer

• Le dernier bloc de code est tellement gros qu’il provoque un défilement horizontal (166KB)
  S et K sont des fonctions curryfiées, qui ne prennent qu’un seul argument à la fois
  Pour plus de détails, voir cette réponse StackOverflow

  • Le plus drôle, c’est le moment où la coloration syntaxique abandonne pendant qu’on fait défiler

• J’adore les noms d’oiseaux comme « Bluebird, cardinal, warbler, thrush ». J’ai envie d’en faire une nouvelle convention de nommage
  « Barendregt. Church est beaucoup trop mainstream. »
  « Bientôt, ce ne sera même plus du JavaScript. »
  On dirait Douglas Adams en train d’enseigner SICP

  • Les noms d’oiseaux viennent de To Mock a Mockingbird de Smullyan. Il y a encore plus d’oiseaux dans le livre

• « Donc… c’est le Y combinator ? »
  « Exactement. Il en faut un pour faire de la récursion. »
  Fait amusant : il existe une infinité de combinateurs de point fixe. Autrement dit, on peut implémenter la récursion d’une infinité de façons sans utiliser le Y combinator