Des programmes en Scheme pour un manuel

Des programmes en Scheme pour un manuel

Laurent Bloch

La spécialité ISN (informatique et sciences du numérique) en terminale

Depuis la rentrée de septembre 2012, les élèves de terminale S peuvent choisir la spécialité ISN (informatique et sciences du numérique). L'association EPI (Enseignement Public et Informatique), par son groupe ITIC (Informatique et Technologies de l'Information et de la Communication) qui réfléchit à la question depuis 1971, a réalisé un manuel destiné aux élèves [1]. (Première version, avec les programmes en Java, suivie d'une seconde version avec les programmes en Python [2]) Ces deux manuels sont disponibles en librairie ou en ligne librement consultables [3]. Il y a aussi un livre du maître [4].

Ces ouvrages sont excellents. Tout à fait entre nous, quand l'informatique sera enfin introduite comme une matière obligatoire pour toutes les sections de la seconde à la terminale à raison de trois heures par semaine, la substance du manuel de terminale pourra servir pour les trois années, et si les élèves savent tout cela en arrivant au bout ce sera un très bon résultat, qui permettra de démarrer plus vite dans l'enseignement supérieur.

Pour enseigner l'informatique il faut un langage

Bien sûr, l'enseignement de l'informatique suppose l'usage d'un langage, et comme je l'ai écrit dans un article de ce site [5] le choix de ce langage importe, surtout pour un premier langage. Une fois que l'on a déjà mis le pied à l'étrier de la programmation et que les tournures d'esprit nécessaires ont commencé à être acquises, on peut s'adapter à un autre langage, même abstrus, mais pour cette acquisition initiale, c'est délicat parce que le risque d'échec n'est pas absent.

Comme les opinions à ce sujet diffèrent, les enseignants ont des démarches variées, et chacun a son langage de prédilection. Ainsi sont apparus, pour ce manuel ISN, des traductions des exemples du livre dans d'autres langages, publiées sur le site de Gilles Dowek [6], l'auteur principal. C'est au cours d'une conversation avec lui qu'il m'a proposé de rédiger la version de ces programmes en Scheme, mon langage de prédilection, ce que je me suis efforcé de faire, et que j'introduis ici. Vous pouvez consulter les programmes ici [7].

Il faut programmer effectivement

Certains beaux esprits suggèrent (depuis des décennies) que la programmation effective ne serait que l'aspect final et subalterne d'une activité intellectuellement plus intense et enrichissante, la conception d'algorithmes. Ils n'ont pas dû beaucoup essayer.

Décrire un algorithme non trivial de façon informelle est une chose qui peut être difficile, avoir l'idée initiale de Knuth-Morris-Pratt ou de QuickSort demande un effort intense et justifie les prix qui en ont récompensé les auteurs (le Turing Award) ; notons d'ailleurs que ceux-ci se sont donné la peine de les programmer, et c'est d'ailleurs sans doute ainsi qu'ils ont trouvé. Maintenant, une fois que l'on connaît QuickSort, en exposer le principe de façon informelle n'est pas trop difficile. En écrire la spécification en pseudo-code peut être plus délicat, mais écrire le programme qui incarne cet algorithme de façon exacte est beaucoup plus difficile. Et c'est bien pire pour Knuth-Morris-Pratt [8], un algorithme particulièrement subtil, même l'exposé qui en est donné dans le livre classique de Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein est complètement vaseux (ce qui me satisfait, parce que si de telles sommités pataugent, mes propres faiblesses seront très pardonnables).

Dans le domaine où j'enseigne (clandestinement), la bioinformatique, il ne manque pas de cursus où l'on disserte à propos d'algorithmes, mais sans les programmer, ou alors en sautant la partie la plus laborieuse, comme le retour sur trace (backtracking) de Needleman et Wunsch. Bon, je ne dirais pas que c'est franchement de l'escroquerie intellectuelle, mais si les étudiants s'imaginent ensuite mériter le titre de bioinformaticien [9], ils se fourrent le doigt dans l'oeil.

Faut-il des procédures ?

Me voilà donc lancé dans la traduction des programmes ISN [10] en Scheme. Gilles m'avait bien expliqué : la récursion n'apparaît qu'au chapitre 5, la définition de procédure (fonction, sous-programme...) au chapitre 4. Bon. La récursion n'est pas un trait idiosyncratique de Java ou de Python, encore moins de C ou de C⁺⁺, alors cela se comprend. Quant à la définition de procédure, elle nécessite dans certains de ces langages une telle gymnastique syntaxique que l'on peut comprendre qu'elle soit épargnée aux débutants pendant les premières séances.

Scheme est un langage de la famille Lisp, entièrement basé sur la récursion et la définition de fonction, qui y sont implantées par une syntaxe légère et simple, ce qui permet de les présenter très tôt aux élèves. Pour qui a appris à programmer avec des langages de style différent, c'est déroutant et même difficile, comme ce l'a été pour moi (nourri au PL/1 et à l'assembleur 360 dans ma jeunesse), mais pour des élèves qui débutent avec Scheme cela ne pose pas plus de problèmes qu'un autre langage, et c'est même beaucoup plus facile qu'avec Java ou C⁺⁺, souvent utilisés.

Le concept de sous-programme est axial

Le groupe Itic, à l'issue d'un travail approfondi, a déterminé les quatre concepts qui forment le paradigme (comme on disait dans ma jeunesse) de la science informatique : information, langage, algorithme et machine. J'adhère à ce paradigme, mais il me semble utile de placer, sur un axe orthogonal à ceux du travail de l'Itic (pourquoi en effet se limiter à quatre dimensions ?), le concept de sous-programme, qui malgré son allure modeste est très puissant.

J'ai été convaincu de la fécondité du concept de sous-programme alors que j'essayais sans succès de mettre au point un programme en assembleur constitué d'une seule section de contrôle (CSECT, c'était ainsi qu'étaient nommées les unités de programme autonomes) trop longue. J'avais fait long parce que découper en plusieurs CSECT était laborieux : construire des listes de paramètres, placer leurs adresses dans des registres, sauvegarder et restaurer des contextes, bref j'avais été paresseux. Le collègue qui partageait mon bureau, témoin de mes efforts infructueux, me donna une injonction : « Structure ! ». Je découpai ma grande CSECT en trois petites, et de ce simple fait mon programme fonctionna à ravir. Le simple fait d'appliquer le second des quatre préceptes donnés par Descartes dans le Discours de la méthode [11] et la cinquième des Règles pour la direction de l'Esprit [12] m'avait obligé à clarifier mes idées, à ordonner la cinématique des données et à séparer ce qui devait l'être. Mais c'est justement cet effort qui fait reculer le programmeur paresseux et qui engendre les programmes en plat de spaghettis à l'origine de bien des catastrophes.

Dans bien des langages, la syntaxe des sous-programmes est absconse et confuse aux yeux du débutant, c'est pourquoi le pédagogue plein de sollicitude tarde à l'introduire. Il peut en résulter les inconvénients énoncés ci-dessus, et d'autres à venir ci-dessous.

Éviter l'affectation a des avantages

En Scheme la syntaxe de construction de sous-programme (plutôt nommé procédure) est aussi simple que possible, et surtout on écrit de la même façon la définition de la procédure et son invocation : son nom, suivi de ceux de ses arguments, le tout entre parenthèses. Une syntaxe aussi simple peut être introduite dès les toutes premières séances.

Un programme Scheme typique est donc constitué de beaucoup de procédures très courtes et très simples, avec des variables locales, ce qui évite autant que faire se peut les effets de bord. Les appels de procédure ont un coût, mais tout compilateur moderne fera son affaire de les supprimer (inlining) et de réduire ainsi notre élégante architecture en plat de spaghettis, efficace mais laid, ce qui n'importe guère puisque seuls le compilateur et le processeur en verront les horreurs.

Si l'on ne procède pas ainsi, ce qui sera le cas habituel dans bien des langages, le programme comportera sans doute au début un paquet de variables globales, modifiées par des affectations au cours de son déroulement. On sait que cette façon de faire n'est pas idéale, parce qu'ainsi une partie du programme risque plus d'interférer avec une autre partie assez éloignée, ce qui augmente le risque d'erreur de programmation, parce que le programmeur n'aura pas toutes les parties concernées du texte simultanément sous les yeux : la définition de la variable et les deux affectations en conflit, ce qui fait trois zones du texte.

Or l'inconvénient de l'introduction tardive des procédures, c'est que les étudiants vont commencer à programmer ainsi, par affectation de variables globales, et qu'ils auront ensuite du mal à se défaire de cette habitude dangereuse mais facile : je le sais parce que ce fut mon cas lorsqu'après la lecture du livre de Sussman et Abelson Structure et interprétation des programmes informatiques [13] je décidai de me mettre à Scheme, ce qui ne fut pas sans mal tant c'était contraire à mes habitudes. Merci à Jacques Arsac, dont la recension dans la revue Technique et Science informatique enjoignait à tout informaticien de lire ce livre et d'en faire les exercices ! On n'aurait pu se dérober à une injonction de Jacques Arsac.

La récursion permet d'échapper à l'affectation

Un autre trait du langage Scheme, c'est que la récursion y est un mécanisme simple, alors que dans beaucoup de langages elle est un trait exotique et difficile à manier.

Depuis le théorème de Corrado Böhm et Giuseppe Jacopini [14] on sait que tout programme informatique peut être réalisé par la combinaison de trois constructions : la séquence qui enchaîne sous-programme après sous-programme, l'alternative qui exécute l'un ou l'autre de deux sous-programmes en fonction de la valeur de vérité d'une variable booléenne (ou condition), l'itération qui exécute de façon répétitive un sous-programme jusqu'à ce qu'une variable booléenne (condition de fin) prenne la valeur vraie.

En Scheme l'itération est réalisée par un appel récursif de procédure (ou, techniquement parlant, de lambda-expression). L'appel récursif peut être coûteux en général, mais la définition du langage permet l'écriture d'appels récursifs terminaux, qui offrent les mêmes performances en temps et en encombrement mémoire que les itération classiques des langages impératifs. Bien sûr le compilateur traduira tout cela en branchements et en séquences, mais ces formes vieux jeu resteront entre le compilateur et le processeur, loin des chastes yeux des programmeurs.

Un avantage de la réalisation des itérations par appels récursifs explicites (ou implicites avec les formes do ou let nommé), c'est que l'évolution des données d'une étape à la suivante n'a pas lieu par affectation, mais lors du passage des arguments. Cet avantage appartient aux langages fonctionnels tels que Scheme (mais aussi OCaml, JavaScript, Haskell...), et il prend une importance significative avec la généralisation des processeurs multi-coeurs et donc du parallélisme entre flux de calculs. Or, comme je l'ai rappelé dans un autre article [15], le théorème du déterminisme [16] nous garantit qu'un programme constitué de tâches concurrentes implanté sans recours à l'opération d'affectation sera, de façon inhérente (« gratuitement »), déterministe, puisque chaque tâche délivre son résultat à son successeur sans interférence entre leurs zones mémoire respectives. Voilà une bonne raison d'enseigner les langages fonctionnels, et par expérience je sais que l'on peut aller assez loin avant d'introduire l'affectation, qui est bien sûr indispensable dans bien des cas. Notons aussi que même si la règle pour les passages d'arguments en Scheme est le passage par valeur, il y a une exception pour les vecteurs, passés par référence, ce qui permet des affectations sans interférence avec d'autres instances de la même procédure.

17 décembre 2014

Laurent Bloch

Paru sous licence Creative Commons BY sur le site de Laurent Bloch.
http://www.laurentbloch.org/MySpip3/spip.php?article303

NOTES

[1] http://www.eyrolles.com/Informatique/Livre/informatique-et-sciences-du-numerique-9782212135435

[2] http://www.eyrolles.com/Informatique/Livre/informatique-et-sciences-du-numerique-edition-speciale-python-9782212136760

[3] https://wiki.inria.fr/sciencinfolycee/Fichier:Informatique_et_Sciences_du_Numérique_-_Spécialité_ISN_en_Terminale_S.pdf

[4] http://www.cndp.fr/crdp-paris/Introduction-a-la-science,27388

[5] http://www.laurentbloch.org/MySpip3/spip.php?article48

[6] https://who.rocq.inria.fr/Gilles.Dowek/Isn/

[7] http://www.laurentbloch.org/MySpip3/spip.php?article302

[8] http://fr.wikipedia.org/wiki/Algorithme_de_Knuth-Morris-Pratt