Penser en langage de tableaux

 (github.com/razetime)
2 points par GN⁺ 2024-01-15 | 1 commentaires | Partager sur WhatsApp
  • La programmation en K consiste à transférer vers des scripts du code expérimenté dans le REPL, en se concentrant sur la réduction continue de grands motifs impératifs en motifs de tableaux déclaratifs plus petits
  • Les scripts ngn/k s’exécutent ligne par ligne comme une saisie dans le REPL, et \\l file.k permet de charger dans le REPL des données et fonctions enregistrées
  • Reprendre tel quel l’algorithme de multiplication de matrices à triple boucle de Wikipedia conduit à de nombreuses variables globales, boucles imbriquées et mutations, ce qui va à l’encontre des points forts de K
  • Le processus d’amélioration passe par le fold +/, each avec ', eachright avec /:, eachleft avec \:, la suppression de la transposition, puis la conversion en forme tacite, pour se condenser de matmul: {x{+/x*y}\:y} à matmul: (+/*)\:
  • L’exemple de multiplication de matrices montre que la maîtrise de K consiste à répéter le processus de condensation du code pour transformer des procédures complexes en expressions de tableaux plus lisibles

Flux de développement K centré sur le REPL

  • Le code source complet est disponible sur GitHub dans matmul.k
  • En K, la programmation se fait majoritairement dans le REPL, ce qui facilite les expérimentations et améliorations rapides à partir du code précédent
  • La combinaison ngn/k et rlfe prend en charge l’historique avec les flèches haut/bas, ce qui suffit pour développer des programmes K plus conséquents
  • Il est naturel de tester d’abord les fonctions dans le REPL avant de les transférer dans le code réel
  • Le pretty-printing de ngn/k renvoie toujours des données K valides, ce qui permet de précalculer certaines valeurs pour accélérer le programme

Modèle d’exécution des scripts K

  • Un script K s’exécute comme s’il était saisi dans le REPL
    • chaque ligne est exécutée dans l’ordre
    • si une ligne ne se termine pas par un point-virgule, sa valeur de retour est affichée
  • Les scripts permettent des définitions sur plusieurs lignes pour améliorer la lisibilité
  • Pour utiliser dans le REPL des données et fonctions enregistrées, il faut exécuter \\l file.k
    • le fichier est exécuté
    • les données du fichier sont chargées
    • charger plusieurs fois le même fichier écrase les données précédentes
  • D’autres commandes sont disponibles dans l’aide du REPL accessible via \\

Réduire les motifs dans un langage de tableaux

  • K et la programmation par tableaux sont un processus de simplification continue des motifs
  • Même un grand motif difficile à manipuler peut être réduit d’au moins une manière vers une forme plus petite, déclarative et lisible
  • Une discussion connexe est détaillée dans Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17
  • Un point de départ fréquent consiste à vouloir traduire en K des algorithmes bien connus de GeeksforGeeks ou de Wikipedia
  • L’exemple utilise la multiplication de matrices

Quand on transpose directement une multiplication de matrices impérative

  • L’article Wikipedia Matrix multiplication algorithm remplit la matrice C avec trois boucles i, j, k et une accumulation sum
  • Le traduire directement en K amène à assigner de nombreuses valeurs globales comme A, B, n, m, p, C, i, j, k, sum
  • Ce code utilise K comme un langage impératif, ce qui correspond mal à sa conception
  • Le problème se ramène à trois points
    • trop d’assignations globales
    • plusieurs niveaux de boucles imbriquées subsistent
    • les mutations sont fréquentes

Réduire à partir de la boucle interne

  • La boucle la plus interne initialise sum à 0, itère sur k et accumule A[i;k]*B[k;j]
  • La première amélioration consiste à utiliser le fold / pour remplacer la somme par +/
    • la globale sum disparaît
    • on obtient une forme du type C[i;j]::+/...
  • Ensuite, en exploitant le fait que each avec ' renvoie un tableau, on peut utiliser directement la valeur de retour des boucles imbriquées sans modifier C
  • Après cette étape, il ne reste que trois boucles sans mutation, et les variables essentielles sont i, j, k

Processus d’élimination de k, j, i

  • Le rôle des trois variables est le suivant
    • i indexe chaque ligne de A
    • j indexe chaque colonne de B
    • k indexe chaque colonne de A et chaque ligne de B
  • k sert à faire correspondre chaque ligne de A avec chaque colonne de B, donc on peut supprimer l’indice intermédiaire et faire la correspondance directement
    • à cette étape, une boucle et m ne sont plus nécessaires
  • Pour supprimer j, il faut récupérer chaque colonne de B et l’associer à A[i]
    • on transpose B et on utilise eachright /: pour associer chaque élément
  • i peut être supprimé de la même manière
    • on utilise eachleft \: pour associer chaque ligne de A à chaque colonne de B
  • Après ce processus, on obtient la forme suivante sans variables globales
matmul: {x{+/x*y}/:\:+y}

Suppression de la transposition et forme tacite finale

  • La transposition + est coûteuse, on peut donc la supprimer
  • L’approche précédente est une méthode naïve qui multiplie chaque ligne de x par chaque colonne de y
  • À la place, si l’on aligne chaque ligne de B sur l’ensemble de A, on peut accomplir le même travail implicitement
matmul: {x{+/x*y}\:y}
  • Cette fonction peut être convertie en forme tacite en appliquant les règles du Chapter 3
  • Le résultat final est le suivant
matmul: (+/*)\:

Construire son intuition des langages de tableaux par la pratique

  • matmul: (+/*)\: se présente comme une fonction de multiplication de matrices idiomatique en K
  • Le processus de condensation peut sembler comporter beaucoup d’étapes au début
  • À mesure que l’on pratique K, la condensation du code devient plus simple et plus intuitive
  • La multiplication de matrices est une procédure simple qui s’accorde bien avec le support des tableaux en K
  • Les chapitres suivants traiteront d’algorithmes moins adaptés à K et de la manière de les aborder

À lire aussi

1 commentaires

 
GN⁺ 2024-01-15
Avis sur Hacker News

  • Ce qui m’a le plus convaincu du potentiel des langages de tableaux, en pratique, c’est une vidéo où Aaron Hsu explique comment il a développé le compilateur APL parallèle Co-dfns : https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
    Sur HN, sous le pseudo arcfide, il a aussi écrit plusieurs fois au sujet de la densité sémantique, en expliquant que le code APL est conçu pour permettre de voir, sur un seul écran et presque sans se déplacer, son fonctionnement, le contexte alentour et les dépendances : https://news.ycombinator.com/item?id=13571159
    L’idée est que, quand la concision devient telle que le nom d’un algorithme a à peu près la même longueur que l’algorithme lui-même une fois développé, on lit le code par idiomes comme on lirait des expressions en anglais, et il peut être plus rapide de modifier directement tous les usages visibles à l’écran plutôt que de créer une abstraction réutilisable

    • Je me demande aussi si les LLM, avec leur fenêtre de contexte limitée, pourraient mieux manipuler APL que d’autres langages
    • À mon avis, le fait qu’il faille écrire une explication aussi longue montre que le code est laid. Si les symboles avaient été choisis pour paraître moins disgracieux lorsqu’ils sont accolés, il n’aurait peut-être pas fallu passer 18 heures à convaincre les gens que le langage n’est pas mauvais

  • Si vous connaissez mal la programmation par tableaux, je recommande The Array Cast comme ressource d’introduction : https://www.arraycast.com/episodes/
    L’adresse RSS est https://www.arraycast.com/episodes?format=rss

    • J’ai écouté à peu près les 5 premiers épisodes de The Array Cast pour me laisser convaincre, mais je n’ai finalement pas adhéré. Les animateurs disaient que la notation concise des langages de tableaux et les symboles non ASCII deviennent acceptables une fois qu’on s’y habitue, et que leurs avantages valent cet effort, mais la plupart de ces avantages sont déjà familiers aujourd’hui via les fonctions d’ordre supérieur des langages mainstream
      map/filter/reduce existent déjà presque partout, et j’ai eu l’impression qu’ils passaient à côté du fait qu’on peut les utiliser sans apprendre un nouveau système de notation proche des idéogrammes
    • C’est comme ça que j’ai découvert BQN, mais je ne sais pas encore si je l’utiliserais dans un véritable environnement de production. Même si j’aime bien, à part R, NumPy ou Julia, la plupart des langages de tableaux restent déroutants, et si l’on s’enfonce dans APL, J ou BQN, j’ai l’impression qu’on s’éloigne soi-même des personnes susceptibles d’aider plus tard

  • Dans les années 70, j’ai découvert APL/APL2 sur des terminaux papier qui utilisaient réellement la surimpression, et j’ai immédiatement accroché ; mais plus tard, après avoir découvert la programmation fonctionnelle avec ML et Haskell, j’ai compris que ce que j’aimais vraiment dans APL, plus que les tableaux, c’était sa capacité de composition de fonctions
    Haskell est entièrement pur et son typage s’applique partout, ce qui le rend bien meilleur sur ce point ; je l’ai trouvé plus amusant et plus puissant qu’APL. J’ai créé beaucoup de petits et moyens projets, réalisé un prototype montrant qu’il était possible d’implémenter le parseur de LLVM Flang avec des parser combinators, et je résous chaque année Advent of Code en quelques centaines de lignes au total. Si vous aimez APL, Haskell vaut aussi la peine d’être essayé
    Aujourd’hui, l’aspect « notation comme outil de pensée » d’APL me semble surtout servir à rationaliser une concision excessive. C’est utile pour montrer la puissance de la composition, mais cela peut aussi nuire à la clarté

    • Sur ce sujet, je finis toujours par dire la même chose : depuis que je maîtrise assez bien le Haskell point-free, je touche très peu à J et K. Avec les foncteurs en plus, cela devient encore plus puissant que les trains de verbes ; <=< existe déjà, et avec l’équivalent de fmap, ça fonctionne vraiment très bien
      |||, +++, &&&, *** sont très bien aussi, et on peut créer soi-même des opérateurs UTF-8 pour obtenir quelque chose de plus court et plus élégant. Cela dit, dans le travail réel ou dans le code Haskell sérieux publié, il est rare de voir ce genre d’attention portée à l’économie de l’espace vertical à l’écran, ce qui est dommage
    • Ce serait bien de pouvoir voir un lien vers les sources Advent of Code

  • Je me demande comment les langages orientés tableaux traitent généralement des problèmes du type « trouver tous les nombres inférieurs à N pour lesquels le prédicat P est vrai ». Par exemple, trouver les nombres premiers inférieurs à 1000, ou les triplets pythagoriciens dont z est inférieur à 1 000 000
    Dans un langage impératif, on testerait le prédicat dans une boucle ; dans un langage fonctionnel, on utiliserait la récursion ou map/filter sur une liste paresseuse ; mais dans un langage orienté tableaux, je comprends qu’on crée généralement un tableau 1..N, qu’on applique le prédicat pour produire un tableau de masque, puis qu’on filtre le tableau d’origine avec ce masque
    Si N est très grand, comme un milliard, et que le prédicat est presque toujours faux, créer deux énormes tableaux temporaires — le tableau 1..N et le masque — semble très gaspilleur en mémoire et en ressources. Je me demande si les langages orientés tableaux ralentissent parce qu’ils créent sans cesse ce genre de tableaux temporaires, ou si les implémentations optimisent cela avec des techniques comme l’évaluation paresseuse

    • Oui, cela gaspille beaucoup de mémoire. Cela dit, la mémoire est bon marché, et si nécessaire on peut découper le calcul en blocs. En pratique, il est rare d’épuiser la mémoire, mais le blocage est utile pour rester dans des niveaux de cache plus bas
      Les langages scalaires, à l’inverse, traitent par défaut une valeur à la fois, et gaspillent donc le parallélisme potentiel que les langages orientés tableaux exploitent via des algorithmes SIMD. Là aussi, ce n’est pas perçu comme un gros problème surtout parce que l’état actuel nous est familier, et la solution est également le blocage
      En pratique, l’intérêt d’un langage orienté tableaux dépend du problème. Pour la grande majorité des usages pratiques, les performances n’ont aucune importance, et la réputation de k semble venir davantage de la rapidité de kdb comme base de données que du fait que les implémentations de k seraient elles-mêmes des langages rapides. Malgré tout, se concentrer sur des algorithmes élégants sur tableaux plutôt que sur des optimisations propres à chaque machine peut rendre les choses étonnamment rapides : https://mlochbaum.github.io/BQN/implementation/versusc.html
    • Il existe plusieurs contournements. L’évaluation paresseuse en est un, et Kap l’utilise : https://aplwiki.com/wiki/KAP
      Une autre méthode évidente consiste à fusionner les boucles de tout le corps pour éviter la création de tableaux temporaires. Une option plus simple consiste à découper les tableaux d’entrée et de sortie en chunks de quelques dizaines de Ko afin de limiter l’usage inutile de mémoire temporaire ; à ma connaissance, aucun langage orienté tableaux ne le fait automatiquement, et j’aimerais l’expérimenter un jour dans CBQN. L’utilisateur peut aussi le faire manuellement, et il faut effectivement le faire souvent pour maximiser les performances
    • L’intuition est globalement juste, mais en pratique c’est un problème rare. Dans la famille k, par exemple ngn/k, il existe une structure paresseuse qui traite !10000000, l’iota de 0 à dix millions, comme une simple plage, sans créer réellement un tableau de dix millions d’entiers
      Bien sûr, selon les opérateurs utilisés, un tel tableau peut finir par être créé. Il existe aussi des optimisations qui remplacent des motifs comme +|x, où l’on inverse x puis prend le premier élément, par une simple prise du dernier élément
    • On dirait que tu supposes que la création du tableau se produit littéralement. Rien n’empêche un langage orienté tableaux de traiter les données en interne par chunks. Même si on lui demande un tableau de dix milliards d’entiers, il peut éviter de le créer naïvement tel quel
    • Beaucoup de langages orientés tableaux ont effectivement ce problème. Plus précisément, le problème est que l’approche simple et intuitive a tendance à calculer beaucoup plus que nécessaire
      On peut bien sûr l’éviter en écrivant le code autrement, mais ces solutions peuvent être plus longues et moins élégantes. Le dialecte APL Kap sur lequel je travaille retarde les calculs jusqu’à ce que le résultat soit nécessaire, et gère plusieurs cas afin de permettre d’écrire le code de manière intuitive sans calculer les résultats qui seront jetés

  • Les plus grandes prises de conscience que j’ai eues en utilisant des langages orientés tableaux, en particulier k, sont les suivantes. Les verbes sont des algorithmes ; dans les langages impératifs et orientés objet, il faut souvent implémenter soi-même des algorithmes courants comme find, sort ou group
    Une suite de verbes ou d’adverbes est la forme de composition la plus directe que j’aie utilisée, et la composition devient facile et naturelle. Un programme cesse de ressembler à un ensemble d’instructions et d’expressions, et apparaît comme une composition d’algorithmes
    Traiter de manière cohérente les notions de domaine et de codomaine dans les tableaux, les maps et les fonctions simplifie les choix de conception ; et quand l’évaluation se fait de droite à gauche, on n’a pas besoin de faire sauter le regard partout en lisant le code
    Il devient possible, et préférable, d’envoyer le code vers les données plutôt que d’amener les données vers le code. La plupart des gros projets k, hors commentaires, tiennent dans le MTU réseau, c’est-à-dire 1540 octets. Parmi les bonus de k, les vues peuvent implémenter directement des relations fonctionnelles, et le chargement de code à chaud via l’interpréteur permet aussi des applications qui tournent « éternellement »

  • Mon impression personnelle, biaisée et limitée après avoir résolu des exercices en langage K pour préparer des entretiens d’embauche, est que le langage est volontairement obscur. C’est un bon langage pour les énigmes et les solutions astucieuses
    Mais, selon moi, ce qui apprend les langages orientés tableaux et la manière de penser en tableaux, c’est l’expérience de manipulation de tableaux NumPy en Python

    • Je suis curieux de savoir pour quel entretien c’était

  • Après avoir utilisé J pendant une cinquantaine d’heures, j’ai franchement eu l’impression que ce paradigme était beaucoup trop orienté dans une seule direction
    Je ne sais pas si penser tous les problèmes comme des imbrications de tableaux aide vraiment en tant qu’outil de pensée. Quand on peut créer librement des structures de données qui capturent bien le problème, la partie algorithmique peut s’en trouver grandement simplifiée
    Je pense qu’il faut être plus intelligent pour utiliser APL/J/K. Dans des langages plus flexibles, certaines approches immédiatement possibles sont souvent impossibles ici ; il faut transformer le problème, et cela peut demander beaucoup plus de réflexion

  • Cet exemple est basé sur K, mais il existe un autre langage orienté tableaux : J : http://jsoftware.com
    Dans J, on écrit par exemple dot =: +/ . *, P =: 2 3 4, Q =: 1 0 2, P dot Q, ce qui renvoie le produit scalaire 10 de P et Q

    • Le langage orienté tableaux d’origine est APL, et le produit scalaire peut s’écrire dot←+.×. Mais si la notation développée est aussi courte qu’un nom raisonnablement bref, il n’y a pas forcément besoin de lui donner un nom, d’autant qu’il peut aussi falloir mettre des espaces autour de ce nom
    • Je ne vois toujours pas bien quel avantage cela a par rapport à Haskell. On peut écrire dot = (sum.) . zipWith (*), p = [2, 3, 4], q = [1, 0, 2], puis p `dot` q
      À mes yeux, la seule différence est qu’on nomme sum et zipWith, et que le lifting ou les transformations de structure ne se produisent pas « comme par magie »
    • Dans KlongPy, le produit scalaire s’écrit dot::{+/x*y}. La forme est P::[2 3 4], Q::[1 0 2], dot(P;Q)

  • En voyant les exemples, je ne comprends pas ce que ça apporte. Est-ce que c’est plus performant d’une manière ou d’une autre ?
    La syntaxe de multiplication matricielle est plus courte, mais cela semble dû au fait qu’il faut garder en tête beaucoup de contexte implicite sur le fonctionnement du langage K.

    • Le fait d’être plus concis a une valeur en soi. C’est assez comparable si l’on considère que les mathématiques consistent de plus en plus à condenser davantage de concepts dans des définitions de plus haut niveau. Quand des concepts de plus haut niveau deviennent des primitives, on peut penser plus vite et construire des objets plus complexes.
    • Les performances peuvent être meilleures. Les ordinateurs sont très rapides pour parcourir des tableaux, surtout lorsqu’ils peuvent exploiter SIMD, mais ce n’est pas toute l’histoire.
      Cela vaut la peine d’essayer un langage de tableaux et de jouer avec jusqu’à comprendre le paradigme. Il arrive souvent que du code impératif s’exprime mieux dans un style tableau, et que de longues petites fonctions soient fortement simplifiées uniquement avec des opérations sur tableaux, ou en les combinant avec d’autres styles.
    • La verbosité a aussi un coût, et si l’on estime que seules les fonctions vraiment complexes ont le privilège d’être verbeuses, l’intérêt devient facile à voir.
      En Haskell, si l’on compare (+) <$> Just 1 <*> Just 2 et do x <- Just 1; y <- Just 2; Just (x + y), à ce niveau de complexité je préfère toujours la première forme. La seconde prend plus de place et donne l’impression qu’il se passe quelque chose de plus compliqué.
      Pour une opération plus complexe, plutôt que d’utiliser la seconde forme, j’aurais envie de la décomposer en petites fonctions afin qu’une variante de la première ait du sens. C’est un compromis qui remplace « une partie des débutants peut le lire rapidement » par « toute personne au-delà du niveau débutant peut le lire ».
      Je pense qu’optimiser pour « une partie des débutants peut le lire » offre des rendements très décroissants ; je vise plutôt une lisibilité pour « au-delà du niveau débutant », ou parfois « niveau intermédiaire et plus ».

  • Pour n’importe quel langage, il y a beaucoup de raisons de l’utiliser et beaucoup de raisons de ne pas l’utiliser. Mais l’essentiel n’est pas la notation courte, la clarté relative ni la capacité à compiler en code rapide : c’est de savoir si le programmeur qui arrive ensuite pourra réellement modifier et maintenir ce code pour un usage concret.
    Trop souvent, les programmeurs veulent montrer leurs compétences de leet, sans penser aux pauvres personnes qui devront ensuite reprendre leur code. Dans la pratique, beaucoup de code leet doit être jeté ou entièrement réécrit pour obtenir quelque chose de maintenable sur le long terme.
    Il m’a fallu longtemps pour comprendre cela, et depuis j’ai essayé d’écrire du code propre, simple et compréhensible, que d’autres puissent maintenir. Trop souvent, du code jetable se fige pour devenir l’infrastructure de base d’une organisation, puis devient incompréhensible pour la génération suivante.