Cet article est la transcription de la séance du Séminaire Codes sources que j’ai donnée le 30 janvier 2020, à l’invitation de Baptiste Mélès, pour répondre à la question de savoir quel langage utiliser pour enseigner la programmation. Il fait suite à l’article Python et Biopython.
La programmation fonctionnelle est un assaut radical et élégant contre toute la pratique de l’écriture de programmes. Elle s’écarte totalement de la mentalité du programmeur qui « fait ci et puis après fait ça ». Vous devez recâbler votre cerveau d’une façon assez différente.
« Faire ci et puis après faire ça »
C’est la tendance spontanée du programmeur débutant, encouragée par le style de beaucoup de langages, surtout en mode interprété.
En général cela finit de façon horrible, ainsi :
Cette façon de faire est peu satisfaisante. Tous ceux qui utilisent Python pour enseigner sérieusement la programmation sont d’accord sur le fait qu’il faut interdire la fonction input
.
Pour construire un programme il faut...
Corrado Böhm et Giuseppe Jacopini on montré en 1966 que tout algorithme pouvait être programmé avec trois constructions :
– séquence d’instructions ;
– alternative ;
– répétitive.
Ce résultat est au fondement de la programmation structurée des années 1970, une étape considérable dans l’art de la programmation, qui énonce qu’une qualité éminente d’un programme sera sa lisibilité par un être humain, et qui préconise de ce fait le renoncement à l’instruction go to
.
Leur article est une des deux références de celui de Dijkstra, Go to Statement Considered Harmful (1968) (l’autre est un article de Wirth et Hoare sur Algol).
Environnement de programmation
Voici ce que présente à son utilisateur un environnement de programmation assez représentatif de ce qui se fait.
C’est assez commode d’usage, mais un univers fermé.
Finalement, avec Biopython :
Voici ce que l’utilisateur profane de Biopython est enclin à écrire pour visiter une séquence biologique, ici de protéine, issue de la banque classique SwissProt :
Biopython répond :
Recherche de séquences
ce qui donne :
Les principales banques de séquences sont :
– GenBank (61 millions de séquences) et EMBL pour les séquences nucléotidiques ;
– UniProt, Swiss-Prot (561 568 séquences) et TrEMBL pour les protéines ;
– PDB, SCOP et CATH fournissent des informations de structure spatiale des protéines, nécessaires aux logiciels de modélisation moléculaire ;
– PubMed est une banque de données bibliographiques.
Code génétique
Le génome est codé dans un alphabet à quatre lettres, A (adénine), C (cytosine), T (thymine), G (guanine) de l’ADN, les nucléotides. Un gène (un ou plusieurs mots du génome), pour être exprimé, doit d’abord être transcrit en ARN messager (même séquence que l’ADN en remplaçant le T de la thymine par U de l’uracile), qui va le transmettre au mécanisme de traduction cellulaire.
Le génome permet la biosynthèse de protéines. Un gène codé dans l’ADN est transcrit en ARN par l’enzyme ARN polymérase, nucléotide pour nucléotide en remplaçant le T (thymine) de l’ADN par le U (uracile) de l’ARN. Ce brin d’ARN messager est ensuite traduit en protéine par le ribosome, un organe de la cellule qui assemble les acides aminés pour former les protéines conformément au code génétique. C’est ainsi que les protéines (éventuellement toxiques pour l’hôte) encodées dans l’ADN d’un virus sont synthétisées par le mécanisme cellulaire de l’hôte.
Les acides aminés constitutifs des protéines présentes dans les organismes vivants sont au nombre de 20. Pour désigner 20 entités différentes avec un alphabet de 4 caractères il faut 3 caractères. Les parties codantes du génome sont donc traduites par groupes de 3, les codons. Un codon de trois nucléotides permettrait de désigner 64 acides aminés, mais il n’y en a que 20 : certains acides aminés sont désignés par plusieurs codons, le code génétique est un code dégénéré.
Acides aminés
Ci-dessous la liste des acides aminés, leurs noms et leurs abréviations, suivis des codons (ici d’ARN) qui codent pour chacun.
Ci-dessous un diagramme, emprunté au professeur Loren Williams, de Georgia Tech, qui résume les principales propriétés des acides aminés :
Avez-vous déjà vu une protéine ?
Une vraie protéine, pas celles que vous trouvez dans les distributeurs de boisson des salles de gymnastique.
En voici une, issu d’un xénope tropical, sorte de crapaud griffu africain aimé des biologistes pour certaines propriétés intéressantes :
Alignement de séquences
Un petit exemple didactique :
qui donne ceci :
BLAST bien sûr...
Biopython procure un accès commode à BLAST, le logiciel préféré des biologistes (avec EndNote). En fait la force de Biopython est de pouvoir manipuler des données de séquences biologiques par les différents logiciels classiques du domaine en effectuant les conversions de format et de conventions de passage de paramètres sans que le biologiste ait à s’en soucier.
Si on connaît l’identifiant GenBank, avec la ligne de commande :
./BLAST-biopython.py blastn nt 8332116
BLAST évalue la pertinence statistique du score par une analyse de la distribution des scores d’alignement entre la séquence-test et l’ensemble des séquences cibles, et calcule la probabilité et l’espérance mathématique de trouver un alignement donnant un score donné parmi les cibles, uniquement du fait du hasard. L’espérance mathématique est notée e-value.
Apprend-on ainsi à programmer ?
Non bien sûr, on aligne des recettes sans comprendre leur mécanisme.
– L’expérience IHM (interface humain-machine) nous apprend qu’écrire une instruction est facile ;
– la preuve par le tableur : on apprend facilement à écrire des formules de calcul dans les cases, cependant que le logiciel fournit la charpente qui les assemble de façon cohérente ;
– décomposer un problème plus vaste en sous-problèmes est difficile ;
– d’où la propension à « faire ci et puis après faire ça ».
Ce qu’il faut enseigner, c’est donc la conception et la réalisation de sous-programmes, et leur assemblage.
C’est une bonne raison d’encourager le style fonctionnel, praticable avec la plupart des langages, mais certains l’encouragent plus que d’autres.
Tri Rapide en Python
Tri Rapide en Scheme
Le programme ci-dessous accepte en paramètre d’entrée le nom d’un fichier qui contient la suite des nombres qui constituent le vecteur à trier. Ces nombres doivent être disposés selon la syntaxe des vecteurs de Scheme, c’est-à-dire précédés des caractères #( et suivis du caractère ).
Comme ce programme était utilisé pour trier des vecteurs de nombres entiers, à l’incitation de Manuel Serrano j’ai utilisé les fonctions d’arithmétique entière explicites =fx +fx -fx <fx >fx
, ce qui améliore considérablement les performances. Pour trier des valeurs d’autres types, tels que chaînes de caractères ou nombres en virgule flottante le programme devrait être modifié pour utiliser les fonctions de comparaison appropriées.
Ce programme utilise quelques autres facilités procurées par le compilateur Bigloo, utiles à la manipulation de grands volumes de données comme nous le verrons lorsque nous aborderons la question des mesures de performances.
Tri rapide en C
Ce programme illustre la raison pour laquelle C n’est pas un langage adapté à l’enseignement de la programmation à des débutants : si la fonction quicksort
est intelligible, même si la syntaxe n’est peut-être pas un modèle de lisibilité, main
et comptemots
sont parfaitement cryptiques. Or c’est avec ce genre de sujets que les informaticiens sont appelés à se débattre quotidiennement. J’ai fait appel à l’aide d’Emmanuel Lazard pour la solution de ces problèmes très techniques.
Quels systèmes de programmation pour l’enseignement ?
La vitesse des programmes produits pour tel ou tel langage avec tel ou tel système de programmation n’est pas le premier critère de choix d’un langage pour l’enseignement, mais il est bon de savoir si ce langage est utilisable de façon réaliste pour traiter des problèmes réels.
Je n’aime pas les environnements de programmation intégrés : ils procurent certes un premier abord facile pour l’étudiant, mais ils lui dissimulent les interactions avec le système d’exploitation et avec les fichiers, or dans la pratique quotidienne de l’informaticien ces interactions sont une des principales sources de difficultés, et il est donc indispensable de s’y frotter. Pour la même raison, il faut que les étudiants compilent leurs programmes, afin d’observer le comportement d’un programme exécutable doté de son vecteur d’état et de ses interfaces avec le monde extérieur. Bref, les interpréteurs sont des logiciels utiles pour mettre le pied à l’étrier, mais cette étape doit être franchie.
Les environnements de programmation intégrés encouragent un style médiocre, le laxisme et l’imprécision dans la déclaration des variables, le déplorable dialogue « entrer les données - calculer - afficher les résultats ».
Mesure de performances du tri rapide (QuickSort)
Pour donner une idée (partielle et rudimentaire) des capacités de quelques systèmes de programmation à traiter des problèmes réels j’ai choisi d’appliquer l’algorithme classique d’Anthony Hoare au tri rapide d’un tableau de 200 millions de nombres entiers tirés au hasard entre 0 et un milliard, avec les programmes dont le texte figure ci-dessus. Voici, à toutes fins utiles, le programme de génération du tableau :
Sans surprise, Python échoue sans message d’erreur explicite au bout d’une cinquantaine de minutes, mais il serait vain de s’en offusquer : les auteurs du langage préviennent que le langage ne procure pas la récursion terminale, et qu’ils ne garantissent rien au-delà d’une profondeur d’appel récursif de 1000.
De façon plus choquante plusieurs implémentations de Scheme échouent également, ce qui donne à craindre que ce ne soient pas de vrais compilateurs, mais plutôt qu’ils construisent des exécutables en embarquant l’interprète. Cela ne justifie pas vraiment l’échec, que la récursion terminale devrait éviter.
Restent le compilateur Bigloo et, comme point de référence, le compilateur gcc pour C. Le texte des programmes indique où sont pris les points de mesure, j’ai veillé à éliminer les temps d’entrées-sorties. Pour C j’ai essayé plusieurs méthodes, avec rusage
et avec clock
, il n’y a pas de différence sensible. Voici les résultats :
Le programme C est plus rapide, ce qui est logique parce que c’est un langage de plus bas niveau, mais Bigloo reste dans les mêmes ordres de grandeur, ce qui dénote un vrai compilateur optimisant. De toute façon ces mesures sont intrinsèquement approximatives, ne serait-ce que pour des phénomènes liés à l’usage du cache.
Danger des mesures de performances
Les performances indiquées ci-dessus ont été observées sur un ordinateur particulièrement lent : Acer Aspire XC-100, processeur AMD E1-1200, deux cœurs, 1,4 GHz, 18 W. Ainsi j’ai obtenu des valeurs numériques plus grandes, donc une meilleure précision. Et surout cela n’a pas trop chauffé.
J’ai imprudemment fait tourner ces programmes sur un petit ordinateur portable doté d’un processeur Intel Core I7 7500U, deux cœurs, 2,7 GHz. Mal m’en a pris : ultra-mince, mal ventilé, la chaleur dégagée par l’appareil a détérioré les lignes de commande de l’écran non démontable, il faudrait changer tout le dos, la réparation coûterait pratiquement le prix de l’ordinateur. Pensez-y quand vous ferez vos propres essais !
Avantages du style fonctionnel
– Le ralentissement des progrès de la vitesse des processeurs, le
recours aux GPU et d’autres facteurs stimulent le recours au calcul
parallèle ;
– garantir qu’une tâche ne modifiera pas l’état du système pris
comme hypothèse par une autre tâche est nécessaire au déterminisme
du calcul ;
– le style fonctionnel limite le recours à l’affectation et par là facilite
la satisfaction de cette condition.
Le marché florissant de la lambda-expression
Expedia did “over 2.3 billion Lambda calls per month” back in December 2016. That number jumped 4.5 times year-over-year in 2017 (to 6.2 billion requests) and continues to rise in 2018. Example applications include integration of events for their CI/CD platforms, infrastructure governance and autoscaling.