Voilà des semaines qu'on en parle et qu'il préoccuppe en sourdine un petit coin de notre matière grise : le KHP.
Le Kata Harry Potter :
Je vends des livres; mes livres coûtent 8 euros pièces, mais je fais des réductions sur la série Harry Potter : pour 2 volumes (différents) la réduction est de 5%. Pour 3 volumes (idem) elle est de 10 %, pour 4 elle est de 20%, pour 5 de 25%. Afin d'éviter les maux de tête lors du paiement à la caisse, il me faudrait un programme qui, étant donnée une liste de volumes identifiés par leur numéro, en calcule le prix en appliquant la meilleure réduction possible. Quelques exemples :
- un volume quelconque : 8,00
- deux volumes identiques : 16,00
- les volumes 1,2 : 15,20
- les volumes 1,1,2 : 23,20
- les volumes 1,2,3,4,5 : 30,00
- les volumes 1,1,2,2,3,3,4,5 : 51,20 (et non 51,60)
Face à ce problème, il y a eu autant de réactions différentes que de participants au Dojo. En caricaturant légèrement (pardon d'avance à ceux qui se reconnaîtront :-) je peux relater trois d'entre elles:
Zeppo : Ah, ok. C'est un problème de partitionnement de listes. Prendre toutes les partitions possibles de la liste de livres; calculer le prix total de chaque partition; renvoyer la partition la moins chère. Bien sûr, cette solution est inutilisable au delà de 8 livres, mais bon voilà..
Harpo : Il doit y avoir une façon de créer les lots de livres en tenant compte simplement des caractéristiques de la table des réductions. Qu'est-ce qu'elle nous dit cette table ? Si on peut étudier les tarifs et trouver une loi de progression, alors on n'a pas besoin de créer toutes ces partitions.
Zeppo : Il faudrait pouvoir limiter le nombre de partitions créées; des tas de combinaisons sont en fait sans intérêt pour le problème donné.
Harpo : Même avec des facteurs limitants, on reste dans un problème bigrement trop complexe pour des temps de réponse acceptables.
Zeppo : Etudier la liste des réductions, OK. Mais cette liste peut être amenée à changer, et là le programme ne marcherait plus..
Groucho : Les gars, si on faisait le boulot qui nous est demandé ? Faire deux lots de 4 plutôt qu'un lot de 5 et un lot de 3: j'ai l'intuition que c'est la seule et unique règle d'optimisation à prendre en compte. Hop : on n'a qu'à remplir des paniers, pas deux fois le même livre dans le même panier. Ensuite on optimise : s'il y a des paniers de 5 et de 3, j'en fais des paniers de 4. Et l'affaire est dans le sac.
Zeppo, Harpo : ...
C'est un problème de génie logiciel. Est-ce un problème d'Ingénieur ou de Mathématicien ? Le Mathématicien réfléchit au temps qu'il faudrait pour trouver la réponse dans un cadre général : "soit r,s,t,u les réductions associées à l'achat de 2,3,4 ou 5 livres... etc.". L'Ingénieur entend le Mathématicien, mais il réfléchit aussi au temps qu'il reste pour écrire un programme utilisable par le client pour son problème donné : précisément 5, 10, 20 puis 25%. Le Mathématicien trouve une solution universelle et éternelle, ou pas de solution. L'Ingénieur trouve un répit jusqu'à demain, car tout programme utile est amené à changer.
J'ai tenté de présenter le Kata "Jeu de la vie optimisé".
Voilà comment çà c'est passé :
L'idée était de reprendre et de continuer le joli coup de Manu : utiliser des grands entiers au lieu de chaînes de caractères pour représenter les entités qui naissent, survivent ou meurent dans le jeu de la vie. En Ruby, les grands entiers font une sorte de pont entre le niveau d'expression du langage et la représentation interne propre aux microprocesseurs, et ce pont permet des parallélisations intéressantes, notamment grâce aux opérations de masquage. J'avais donc un plan, plusieurs répétitions dans les doigts, et donc de quoi faire une présentation prometteuse (pensez donc : une division par dix du temps de calcul !).
Je n'ai pas tenu les délais, et même si les avais tenu, je crois que la présentation n'aurait pas suscité un grand enthousiasme. Mais j'ai appris deux ou trois choses que je ne savais pas encore à propos de cet exercice.
Tout d'abord, j'ai voulu en faire trop en même temps : articuler une solution à base de mise en table des résultats possibles du calcul de génération, masquage et décalage pour "fenêtrer" la zone de calcul dans le terrain, utiliser par convention un "bord" du terrain pour simplifier la routine centrale (pattern Sentinelle).
Ensuite j'ai présenté une approche typiquement "j'ai un plan (mais vous ne saurez vraiment qu'à la fin que ça peut marcher)", plus communément appelée approche "Bottom-Up" : on part des briques de base pour en construire des plus grandes puis des pans entiers et enfin le programme. C'est intéressant, mais çà donne au Kata un certain suspense qui nuît à sont aspect narratif. Le consensus autour de la démarche TDD n'est pas une simple coïncidence au Dojo : le code présenté doit se dérouler naturellement test après test, et la forme doit émerger de ce déroulement. Ce qui se passe dans le cas contraire, c'est la promesse d'un dénouement final, avec le risque que le gong sonne trop tôt. Mais le public ne vient pas au Dojo pour le suspense.
Enfin, j'ai ressenti avec une vivacité particulière le conflit inhérent à l'exercice d'équilibriste que nous appelons le Kata : vous devez exécuter un design dans un temps imparti. Vous devez faire en sorte que ce design passe les tests qui correspondent à l'énoncé et aussi que ce design soit approuvé par votre auditoire. Si bien qu'il y a grosso modo deux façons (non exclusives) de chuter sur le tatami : l'heure à sonné, ou le public a décroché.
A un moment donné, j'étais aux prises avec
- une initialisation de tableau défectueuse,
- une remarque à prendre en compte sur l'expressivité de mon code
- une remarque à prendre en compte sur un prochain test possible qui ne passerait sûrement pas
- le délai qui, lui, était passé de plusieurs minutes.
Et j'ai pensé "Bien sûr, ILS peuvent m'interrompre à tout bout de champ, et comme ça m'empêcher de finir.", Cette bouffée de parano a produit un déclic, et m'a fait réaliser l'absurde de la situation : réclamer l'arrêt des interruptions pour faire passer mon code. Comme je ne voulais pas non plus réclamer du temps (c'est inutile) j'ai jeté l'éponge, et tout est redevenu normal.
Et voilà ce que j'ai appris :
Le Kata est un exercice difficile de programmation et de communication, durant lequel il est impossible de ne pas éprouver la boucle de rétroaction positive PRESSION / QUALITE : le stress lié à l'enjeu et aux délais vous pousse à la précipitation; la précipitation engendre des défauts, un exposé moins clair; il faut corriger et réexpliquer, ce qui prend du temps et accentue le stress lié aux délais.. Comme dit Manu, "Tu réexplique une fois, et c'est cuit". Par conséquent les progrès sont à trouver autant du côté programmation (élégance, expressivité, connaissance des patterns de base) que du côté communication (idées, design, expressivité, rigeur, et surtout écoute des autres).
C'est une épreuve sous-tendue par une discipline. Il me semble qu'un Kata réussi doit répondre au critères suivants :
- énoncé satisfait
- code répondant aux 4 règles : passe tous ses tests, exprime l'intention, ne contient pas de redondance, économe en classes/méthodes/lignes
- respect des délais
- adhésion de l'assemblée à l'exécution présentée.
Ce dernier point est particulièrement critique. Le Kata est un exercice collectif. Vous ne pourrez jamais réussir une présentation "malgré" vos auditeurs.
Il me semble que quand on est capable de réussir cet exercice, on est mieux préparé pour répondre à ces défis quotidiens du développement logiciel en équipe :
- trouver une rapidement et concrètement une solution correcte à un problème,
- exposer une idée de design et la rendre faisable pour l'ensemble de l'équipe,
- écouter, comprendre et se faire comprendre.
C'est un exercice fascinant, autant par les illusions qu'il vous fait perdre à propos de vos compétences que par les ressources inconnues qu'il permet de découvrir en vous.
Enfin, même flanqué sur le tatami avec un genou douloureux, c'est toujours aussi génialement amusant.
J'ai comme l'intuition que dans un an ou deux, nous pourrons, à force d'entraînement, réussir cet exercice : coder en une heure une solution correcte, expressive et approuvée, sur un sujet tiré au hasard. Autrement dit, devenir virtuose au point de savoir improviser.
J'ai proposé un sujet de kata il y a trois semaines environ, que nous avons rebaptisé le "Kata Potter". Il y s'agit de calculer un montant total pour un ensemble de livres achetés, en choisissant dans une liste connue de réductions la combinaison qui donnera le coût minimum à payer. Les montants de chaque réduction et leur cadre d'application est déterminé dans le problème de façon à ce qu'un algorithme vorace utilisant comme heuristique la plus forte réduction applicable ne fonctionne pas.
Cet exercice me fascine, car lorsqu'on le présente à des informaticiens, la plupart d'entre eux (y compris les débutants) ont une idée claire de l'algorithme à utiliser, et ne mesurent pas la difficulté à le mettre en oeuvre. La fonction centrale réside en construire la liste des partitions possibles de l'ensemble des livres achetés (pour ensuite ne garder que la partition conduisant au prix total minimum) et induit des manipulations complexes de structures de listes imbriquées. Par ailleurs, l'explosion combinatoire de cet algorithme rend rapidement obligatoire l'utilisation d'heuristiques de limitation d'exploration, ce qui complique encore le partitionnement.
Douce ironie -- cela fait maintenant trois semaines que je cherche à trouver une solution à ce problème, et que mes algorithmes d'optimisation sont faux. Tentant une approche non optimisée, nous avons étudié l'algorithme de partitionnement lors de la dernière séance du dojo, mais n'avons pas réussi à produire une liste correcte de partitions pour un ensemble de 3 éléments. Là où je souhaitais pimenter notre travail par un problème non trivial, je ne peux que constater mon incapacité actuelle à le résoudre.
Christophe a remarqué après la séance -- "nous n'avons pas réussi, mais nous apprenons à aimer le plateau" -- faisant référence au modèle d'apprentissage selon lequel les progrès arrivent par paliers. Au-delà de la poésie de cette expression et de l'optimisme qui nous permettait de regarder notre échec de manière plus positive, je trouve cette attitude pleine de sens.
Constatant que je passe plus de temps que prévu à mon niveau d'apprentissage actuel, je dois me faire de cet état cognitif un allié, un territoire où les découvertes de chaque zone inexplorée sont autant d'opportunités pour mieux comprendre ce qui m'y retient. Quitte à rester quelque part, autant apprendre à aimer cet endroit. Et plutôt que de regarder avec insistance le haut de la marche suivante, inaccessible, mieux vaut avec humilité se réjouir des surprises que nous réserve la marche sur laquelle nous nous trouvons.
La démonstration de katas alimente une discussion récurrente depuis quelques
séances : bien que la combinaison d'un développement piloté par les tests et
d'un remaniement impitoyable amène à une conception émergeante, une telle
démarche permet-elle de "re-découvrir" des algorithmes classiques ? En d'autres
termes : face à un problème algorithmique donné, peut-on monter l'algorithme
complet depuis une approche naïve, strictement "bottom-up", s'intéressant à
faire passer un à un les tests de recette caractérisant cet algorithme ?
Je n'ai pas encore la réponse, mais je soupçonne que la réponse n'est pas aussi
simpliste. En ayant répété le kata à l'avance, la personne qui le présente ne
cherche plus à "découvrir" quel est l'algorithme, mais à l'amener de façon la
plus naturelle qui soit à son assistance. Un peu comme un écrivain peut avoir en
tête un scénario, et cherche à raconter une histoire à son lectorat sans que
celui-ci est l'impression que les actions des protagonistes soient "forcées", à
rebrousse-poil de leur psychologie et du contexte exposés. Bien avant
l'originalité, c'est sur ce critère que je fonde mon appréciation d'une
histoire, qu'il s'agisse d'un film, d'une nouvelle ou d'un feuilleton.
Je commence à entrevoir un aspect important d'une démonstration de kata. Il me
semble inutile de "faire croire" à mon assistance que je ne connais pas
l'algorithme que je vais dérouler, par contre si je l'amène élément par élément,
je peux donner à l'assistance l'opportunité de le "(re)découvrir". Si chaque
test de recette est une opportunité pour amener de nouveaux éléments à mon
algorithme, il m'importe de trouver la manière qui me permet de planter chaque
nouvel élément de la façon la plus innocente qu'il soit, et ne le développer
que dans pour des tests de recette ultérieurs. Je sens une plus-value narrative
à amener chaque élément de mon code comme autant d'intrigues secondaires, qui
ne passent au premier plan que par la suite. L'attention de mon assistance est
accrue, et le scénario/algorithme que je dévoile peu à peu est d'autant mieux
retenu, d'autant plus facile à retenir, d'autant plus apte à susciter un
feedback pertinent.