Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Programme, langage, style
Des programmes en Scheme pour un manuel
Article mis en ligne le 17 décembre 2014
dernière modification le 25 janvier 2017

par Laurent Bloch
logo imprimer
Licence : CC by-nd

 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 (première version, avec les programmes en Java, suivie d’une seconde version avec les programmes en Python). Ces deux manuels sont disponibles en librairie ou en ligne librement consultables. Il y a aussi un livre du maître.

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 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, 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.

 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, 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, ils se fourrent le doigt dans l’œil.

 Faut-il des procédures ?

Me voilà donc lancé dans la traduction des programmes ISN 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 et la cinquième des Règles pour la direction de l’Esprit 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 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 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érations 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 la forme do), 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-cœurs et donc du parallélisme entre flux de calculs. Or, comme je l’ai rappelé dans un autre article, le théorème du déterminisme 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.


Forum
Répondre à cet article
Programme, langage, style
Malik - le 29 juin 2017

Bonour M.Laurent Boch
Mes compliments pour votre site, permettant d’accéder et de comprendre l’informatique d’une autre manière, mettant en exergue les dimensions philosophique et surtout sociétale de cette discipline qui ne cessent de nous surprendre. D’autre part, son cote didactique et technique centre sur le langage Scheme, permet aux internautes de tout age (mon cas , age de 55 ans) et d’un niveau basique (Lycee) de s’y mettre a l’informatique en qualite d’un non specialiste, comme outil au profit d’autre discipline.
J’ai parcouru votre livre (Initiation a la Programmation avec Scheme) et il m’a donne l’envie de se mettre a la programmation en Scheme ( je vous transmettrai le feed back en fur et a mesure).
A signaler que j’ai vecu la revolution micro-informatique, en etant l’heureux proprietaire d’un Commodore C-64 (la belle epoque).
Par ailleurs, j’ai l’intention de commencer un MOOC sur python, sur le site Udemy.
Je vous demande est il possible d’elaborer en Scheme un algorithme suivi d’un organigramme, (comme les langages imperatifs), comme vous le savez cette visualisation permet d’apprehender la problematique et la solution.
D’autre part, comme Scheme est base sur le concept de la recursivite, pouvez nous expliquer ce concept mais de facon non matheux et son importance pour Scheme.
Merci et j’espere vous lire prochainement.

Programme, langage, style
Laurent Bloch - le 29 juin 2017

Bonjour et merci de votre message,

Pour ce qui est des organigrammes (ou ordinogrammes, selon certains auteurs), vous avez noté, puisque vous avez mon livre sous la main, que je n’utilise aucune représentation graphique des algorithmes, mais un texte en pseudo-code (cf. sur le site, la mise en page laisse à désirer, c’est mieux dans le livre).

Si je dois le refaire (c’est en projet) j’utiliserai le langage de pseudo-code de Leslie Lamport :

http://lamport.azurewebsites.net/tla/dcas.pdf

https://www.cs.jhu.edu/events/leslie-lamport-microsoft-the-cal-algorithm-language/

Si on préfère une représentation graphique, l’organigramme me semble mal adapté à un langage fonctionnel, et de façon générale à une programmation sans GOTO (c’est-à-dire à la programmation moderne sauf en assembleur éventuellement). J’ai utilisé naguère une représentation arborescente des algorithmes, mieux adaptée, mais je crois que cette méthode est restée confidentielle. L’alternative est représentée par un arbre à trois branches, une à gauche pour la condition, celle du milieu pour l’action si la condition est satisfaite, celle de droite pour l’action si non. La répétition est représentée par un arbre à deux branches, une à gauche pour la condition, l’autre pour l’action à répéter. La séquence... par une séquence d’actions.

Pour la récursivité : j’aborde le sujet dans mon livre, de façon très élémentaire. Le livre de Christian Queinnec et al. chez Dunod Programmation récursive (en Scheme) devrait répondre à vos questions. Cf. aussi le SICP, un livre qui a fait date, en accès libre sur le site.

Bonne programmation !



pucePlan du site puceContact puceMentions légales puceEspace rédacteurs puce

RSS

2004-2017 © Site WWW de Laurent Bloch - Tous droits réservés
Site réalisé sous SPIP
avec le squelette ESCAL-V3
Version : 3.87.15