Penser en langage de tableaux

Penser en langage K

• La programmation en K se fait principalement via un REPL.
• rlwrap de ngn/k permet de parcourir l’historique avec les touches fléchées, ce qui est utile pour développer de gros programmes.
• Les fonctions sont testées dans le REPL avant d’être transférées dans le code réel.
• Le pretty-print de ngn/k renvoie toujours des données K valides et peut être précalculé pour accélérer le programme.
• Les scripts K s’exécutent comme s’ils étaient saisis dans le REPL, et la valeur de retour de chaque ligne est affichée sauf si elle se termine par un point-virgule.
• Les scripts autorisent des définitions sur plusieurs lignes, ce qui améliore la lisibilité.
• Pour enregistrer son travail dans un script et l’utiliser dans le REPL, on peut exécuter le fichier et charger les données avec \lfile.k.
• On peut recharger plusieurs fois un fichier dans le REPL pour écraser les données précédentes.
• L’aide du REPL, accessible via \, contient diverses commandes utiles.

Simplification de la programmation par tableaux

• La programmation par tableaux est un processus continu de simplification de motifs complexes en motifs plus petits, déclaratifs et plus faciles à lire.
• La manière de simplifier des motifs complexes est discutée en détail dans « Patterns and Antipatterns in APL: Breaking Out of the Beginner's Plateau - Aaron Hsu - Dyalog '17 ».

Transformation en K de la multiplication de matrices

• Il est possible de convertir directement en K l’algorithme itératif de multiplication de matrices tiré d’un article de Wikipédia.
• Le pire exemple de code converti en K nécessite de nombreuses affectations de variables globales, des boucles imbriquées et beaucoup de modifications.
• On peut simplifier le code afin de résoudre ces problèmes un par un.

Simplification de la boucle interne

• Dans la boucle interne, sum peut être simplifié en utilisant un fold (/).
• Comme ' (each) renvoie un tableau, la variable globale C peut être supprimée.
• On peut simplifier la boucle en supprimant les variables i, j et k.

Suppression des boucles et minimisation des variables globales

• Il est possible de supprimer la boucle intermédiaire en faisant correspondre directement lignes et colonnes sans k.
• Pour supprimer j, on peut associer chaque colonne de B à A[i].
• Pour supprimer i, on peut utiliser eachleft afin d’associer chaque ligne de A à chaque colonne de B.
• Les variables globales ne sont alors plus nécessaires.

Forme finale de la fonction de multiplication de matrices

• + (transpose) est coûteux, on peut donc l’éliminer.
• Au lieu de multiplier chaque ligne de x par chaque colonne de y, on peut effectuer implicitement le même travail en appliquant chaque ligne de B à l’ensemble de A.
• On obtient finalement une fonction de multiplication de matrices concise et explicite.
• Le processus de simplification du code passe d’abord par plusieurs étapes, mais il peut devenir plus simple et plus intuitif à mesure que l’on gagne en maîtrise de K.
• La multiplication de matrices est une procédure simple, bien adaptée à la prise en charge des tableaux en K.
• D’autres algorithmes, moins adaptés à K, ainsi que la manière de les traiter, seront abordés dans de futurs chapitres.

L’avis de GN⁺

• Cet article montre comment simplifier et optimiser des algorithmes tels que la multiplication de matrices à l’aide du langage K.
• Le feedback immédiat via le REPL et l’amélioration itérative du code sont des caractéristiques centrales de la programmation en K, ainsi qu’une méthode d’apprentissage utile même pour les ingénieurs logiciel débutants.
• Le processus de simplification du code est important pour améliorer ses compétences en programmation, et cet article l’explique de manière concrète et accessible à travers des exemples précis.

[GN⁺]

Avis Hacker News

• Plusieurs personnes remettent en question l'utilité et l'intelligibilité des langages à tableaux.

  • Les langages à tableaux ne conviennent pas à tous les problèmes.
  • Ils sont étonnamment capables pour de nombreux types de problèmes.
  • Les utilisateurs de langages à tableaux sont généralement très intelligents.
  • Apprendre comment fonctionnent les langages à tableaux est un défi majeur.
  • Écrire du code « procédural » dans un langage à tableaux est une très mauvaise idée.
  • Comprendre la programmation tacite est une expérience formidable qui élargit l'esprit.
  • L'expérience que l'on a lorsqu'on internalise les verb trains.
  • La compréhension de la manière dont les langages fondés sur les tableaux traitent des tableaux de toutes dimensions.
  • Comprendre le fonctionnement de under.
  • Comprendre le fonctionnement des exposants de fonctions (function exponents).

• Les aspects remarquables des langages à tableaux sont nombreux, et la liste ci-dessus n'en est qu'un petit échantillon.

  • Observer Aaron Hsu développer un compilateur APL parallèle a convaincu certains du véritable potentiel des langages à tableaux.
  • Discussion autour de la « densité sémantique » du code APL.

• Si vous n'avez jamais entendu parler de la programmation par tableaux et souhaitez une introduction, recommandation de « The Array Cast ».

• Découverte d'APL/APL2 dans les années 70 et coup de foudre, mais un attrait encore plus fort pour la capacité à composer des fonctions.

  • Haskell, parce qu'il est pur et typé, est plus amusant et plus puissant qu'APL.
  • La « notation comme outil de pensée » d'APL semble être une logique servant à justifier une concision excessive.

• La prise de conscience la plus importante dans l'usage des langages à tableaux :

  • Les verbes sont des algorithmes.
  • Une suite de verbes (ou d'adverbes) est la forme de composition la plus directe qui soit.
  • Un programme est une composition d'algorithmes, et non un ensemble de phrases et d'expressions.
  • Une conception qui traite de façon cohérente le domaine et l'image à travers les tableaux, les maps et les fonctions.
  • Une évaluation de gauche à droite qui évite aux yeux de devoir « sauter partout » en lisant le code.
  • Il est possible, et préférable, d'envoyer le code vers les données.
  • Avantage supplémentaire du langage K : on peut implémenter directement des vues (c'est-à-dire des dépendances) et charger du code à chaud via l'interpréteur.

• Question à propos des langages à tableaux : comment effectuer une tâche comme « trouver tous les nombres inférieurs à N pour lesquels la condition P est vraie » ?

  • Dans un langage à tableaux, on génère généralement un tableau de 1 à N, on teste la condition sur ce tableau, puis on applique un masque pour ne récupérer que les éléments qui satisfont la condition.
  • Si N est grand et que la condition est rarement vraie, créer autant de tableaux temporaires semble être un gaspillage de mémoire et de ressources.
  • Les implémentations de langages à tableaux peuvent optimiser ce problème ou le résoudre avec des techniques comme l'évaluation paresseuse (lazy evaluation).

• Expérience avec le langage J : le paradigme des langages à tableaux est biaisé, et il n'est pas certain qu'il soit utile de penser tous les problèmes comme des imbrications de tableaux.

  • Pouvoir créer librement des structures de données qui simplifient le problème peut grandement simplifier la partie algorithmique.
  • Pour utiliser APL/J/K, il faut être plus intelligent à cause de ce biais.

• Impression tirée de la résolution de problèmes en K : le langage K est délibérément obscur.

  • C'est un langage bien adapté aux puzzles et aux solutions ingénieuses, mais travailler avec des tableaux numpy en Python permet aussi d'apprendre les langages à tableaux et à penser en tableaux.

• Exemple en J : calcul du produit scalaire de P et Q avec dot =: +/ . *.

• La syntaxe de K est plus courte, mais il faut garder en tête beaucoup de contexte implicite sur la manière dont le langage fonctionne.