URL: https://linuxfr.org/users/aluminium95/journaux/donnees-vs-code Title: Données vs Code Authors: Aluminium95 Date: 2016年03月28日T23:00:40+02:00 License: CC By-SA Tags: Score: 27 Bonjour nal, C'est avec humilité que je viens de présenter une « révélation récente », qui si elle est déjà connue, s'accompagne bien mieux d'un exemple : l'avantage certain à construire des données par rapport à celui de construire des instructions. Ce sujet est assez vieux, ne serait-ce que grâce à [[Lisp]] qui permet de considérer (à un niveau assez bas) données et programmes comme interchangeables via son [[Homoiconicité]]. Néanmoins, pour chaque problème à résoudre il faut se poser la question : quelle partie est représentée physiquement en tant que donnée, et quelle partie est procédurale/impérative/mécanique ? Très souvent, il est préférable (dans un premier temps en tout cas) de construire une structure de données qui correspond à une représentation du problème, puis de la détruire en calculant une solution. Une manière simple de le faire est via un [Hylomorphism (computer science)](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29), qui se détermine en donnant deux ingrédients 1. Une fonction simple qui construit un morceau de structure 2. Une fonction simple qui détruit un morceau de structure L'exemple classique de la factorielle devient alors ```haskell fact n = product [1..n] -- Si on regarde comment sont codées les fonctions range et product -- a) construction de la fonction range (inclusive) range a b = unfold (\x -> if x <= b then Just (x,x+1) else Nothing) a -- b) construction de la fonction product product = foldr (*) 1 ``` Tant que l'on reste dans des choses « simples », on est dans un monde parfait où tout est facile, lisible, modifiable à souhaits. Pour prendre un autre exemple académique, demandons-nous ce qu'il faut pour coder un [[tri fusion]] : 1. Une fonction qui crée un arbre binaire équilibré dont les feuilles sont des singletons 2. Une fonction qui fusionne deux listes triées pour en construire une nouvelle triée Classiquement, c'est la pile d'appels récursifs qui va en réalité représenter l'arbre binaire (qui sera alors implicite) en écrivant les noeuds dans l'ordre d'un parcours en profondeur. À quoi ressemble donc le code avec un arbre explicite ? ```haskell mergeSort = detruireArbre . construireArbre data TreeF a b = Feuille [a] | Noeud b b data Tree a = Fix (TreeF a) -- Construction construireArbre :: [a] -> Tree a construireArbre = unfoldTree construireNoeud -- ici on suppose que unfoldTree existe bien construireNoeud :: [a] -> TreeF a [a] construireNoeud [] = Feuille [] construireNoeud [a] = Feuille [a] construireNoeud l = Noeud gauche droite where gauche,droite = halfSplit l -- Destruction detruireArbre :: (Ord a) => Tree a -> [a] detruireArbre = foldTree detruireNoeud detruireNoeud :: (Ord a) => TreeF a [a] -> [a] detruireNoeud (Feuille a) = a detruireNoeud (Noeud a b) = mergeListes a b ``` Certaines fonctions ne sont pas codées (`mergeListes` et `halfSplit`) simplement parce que cela ne change rien à la structure du code. Quels sont donc les différences avec un code récursif normal ? 1. La construction explicite de l'arbre coûte plus de mémoire 2. La modification et la lecture du code devient évidente Bien entendu, comme c'est encore un cas évident, il n'y a pas de réel bénéfices : à priori, quand on code un tri fusion, on veut un tri fusion, et le code n'évoluera pas beaucoup. Malgré tout, on peut très facilement mélanger des tris avec cette construction, pour faire par exemple un tri par insertion quand il y a moins de N éléments, simplement en ajoutant un constructeur à l'arbre, et modifiant les _mini_-fonctions de construction/destruction en conséquence : l'allure générale du code ne varie pas. Mieux, ce sont seulement les _petites_ fonctions (non récursives, pures, simples) qui auront plus de cas. Un exemple plus concret s'est trouvé être la session de qualification au Google Hash Code 2016, le problème est le suivant :> Étant donné une carte avec des entrepôts (possédant des stocks de produits), une liste de commandes et une flottille de drones, comment optimiser un score qui est calculé en fonction du temps mis pour répondre aux commandes (les commandes remplies le plus tôt rapportent plus de points, indépendamment de leur poids/nombre de produits). L'algorithme devait être un algorithme de type glouton, le problème étant à priori difficile. La première solution qui vient à l'esprit, est une solution de type _opérationnelle_ et qui décrit le comportement des drones. Par exemple : Tant qu'il reste des commandes, pour chaque drone, trouver l'entrepôt le plus proche, trouver la commande avec un meilleur score relatif à cet entrepôt, faire le trajet, et déposer. Quel est le problème ? Dans un premier temps, on remarque que cette méthode _impose_ l'utilisation d'effets de bords dans _l'intégralité_ des fonctions (ou alors d'utiliser des fonctions qui se passent l'état courant). Dans un deuxième temps, le débug d'un tel programme est très pénible : la solution la plus économe et efficace est de lancer le programme sur des petits fichiers, et faire une animation, afin de voir globalement ce qu'il se passe. Dans un dernier temps, il est assez fastidieux de faire des choix plus « en avant », par exemple en sélectionnant les _k_ prochaines commandes ... L'alternative étant bien entendu de construire une structure de donnée intermédiaire pour représenter les choix du programme glouton. Naturellement on en vient a construire un arbre, et la solution est une branche de cet arbre (une suite de choix). Quels avantages ? 1. Seule la fonction qui trouve le chemin dans l'arbre a besoin d'un état, et encore. Toutes les autres fonctions seront pures et donc facilement testables de manière indépendantes. 2. Il est possible en utilisant des outils comme [QuickCheck](https://en.wikipedia.org/wiki/QuickCheck) de vérifier certaines propriétés facilement sur du code pur 3. On peut effectivement afficher des (petits) arbres générés aléatoirement pour comprendre quels choix sont localement optimaux sur des petits exemples, en comparant l'algorithme glouton avec une recherche exhaustive. 4. On peut facilement modifier des parties indépendantes du code 1. La génération de l'arbre va décider * Des données accessibles dans les nœuds * De la manière dont sont organisés les fils (triés dans un certain ordre) 2. La destruction/Le parcours de l'arbre va décider * De la façon dont les données sont utilisées (prise ou non en compte) * De la manière dont les choix de branches sont optimisés (sur un,deux niveaux ? combien de fils sont effectivement explorés ? etc.) 5. Une utilisation un peu plus avancée est la suivante : si on travaille sur un set de données précis (ce qui est le cas dans le Hash Code), on peut calculer l'arbre et l'enregistrer dans un fichier, et faire du traitement itératif dessus, en supprimant des branches au fur et à mesure par exemple, ou détruisant des patterns répétitifs. Même si on ne fait pas ce type de traitement, cela permet de gagner du temps sur les tests du code de destruction, puisque l'arbre n'a pas à être recalculé (à nuancer, en `haskell` l'arbre n'est a priori pas calculé totalement avec l'évaluation paresseuse, et donc lire l'intégralité de l'arbre peut devenir moins performant...) Ce qui est amusant c'est qu'au final, la quantité de code est assez similaire : il faut toujours mettre à jours les états, toujours gérer les drones, toujours parser l'entrée standard. Pourtant, il y a une grosse différence : dans le code impératif, on se concentre sur une solution _pas à pas_, et la généraliser pour faire des « grands pas » devient vite pénible. En rendant explicite la donnée, et en permettant de la traiter de manière arbitraire, on s'autorise beaucoup plus de choses, les algorithmes viennent plus naturellement, et sont plus facilement compréhensibles par d'autres êtres humains. PS: certains dirons « où est donc le code ? », la réponse est la suivante : la version proposée était en python, avec pleins de variables globales, codée de manière horrible et donnait des solutions inefficaces. Je n'ai pas eu le courage de convertir complètement l'algorithme en haskell avec un arbre de décision effectif (ce qui rend ce journal un peu hypocrite). PS': je n'ai pas eu le temps de pousser l'analogie très loin, mais la différence entre les deux approches semble être la différence entre une sémantique opérationnelle (à petits pas) et une sémantique dénotationnelle (cf [Sémantique des langages de programmation](https://fr.wikipedia.org/wiki/S%C3%A9mantique_des_langages_de_programmation))

AltStyle によって変換されたページ (->オリジナル) /