La Programmation Fonctionnelle, avec Scheme
Les trois paradigmes principaux de programmation
L'ancienne option D (épreuve informatique) de l'agrégation de maths disparaît en 2022, elle est remplacée par deux options B (calcul scientifique) et C (algèbre et calcul formel). Il existe maintenant une agrégation d'informatique. Il existe de même un CAPES Informatique à côté du CAPES de maths usuel. Pour l'agrégation, la connaissance des trois principaux paradigmes de programmation est demandée.
Le paradigme fonctionnel est la face puriste de la programmation. Parfois vu comme un lambda-calcul appliqué, on peut y raisonner comme en maths, faire des démonstrations par récurrence, des analyses récursives de complexité, et acquérir une rigueur certaine. Les fonctions récursives sont au coeur de ce paradigme, au lieu du concept de boucle qui n'existe pas en mathématiques. La quasi-totalité des UFR Sciences propose une formation à la programmation fonctionnelle dans le cursus L1-L2-L3-Info.
Voici un programme Scheme calculant la dérivée seconde approchée de la fonction logarithme au point x=2. La rédaction de ce petit programme dans un langage comme C illustrera chez le lecteur dubitatif la spécificité et la concision de la programmation fonctionnelle :
(define (D f) ; dérivée première approchée d'une fonction f (lambda (x) (/ (- (f (+ x 0.01)) (f x)) 0.01))) > ((D (D log)) 2) ; approximation de log"(2) -0.24752168910069372
Un langage qui n'est pas capable d'exprimer un tel calcul de manière aussi simple n'est - à mon sens - pas qualifié pour enseigner la programmation dans le cadre d'une spécialité du cours de maths d'une Terminale S. Notez que Python s'exprime aussi facilement, même s'ils n'implémente pas vraiment la programmation fonctionnelle (la récurrence n'y est pas optimisée, pénalisant donc les fonctions récursives)...
Le paradigme procédural (ou impératif) est le plus ancien. Apparu avec Fortran, poursuivi avec Pascal et C, il met en avant l'appel de procédure pour effectuer un calcul séquentiel. La programmation impérative considère qu'un texte de programme est une suite d'instructions pilotant un ordinateur, au contraire de la programmation fonctionnelle pure, où la notion d'instruction n'existe pas plus qu'en maths. L'itération est le mécanisme central pour effectuer un calcul répétitif, la récursivité y est rarement optimisée. Après Pascal qui fut le chantre de la programmation structurée des années 1970-90, c'est actuellement le langage C qui en est le représentant largement majoritaire, un véritable modèle de machine. Certaines UFR utilisent des langages introductifs plus simples comme Javascript, Python ou Visual Basic pour présenter la programmation impérative. Il reste que C est un langage incontournable pour les professionnels qui travaillent au plus près de l'architecture de l'ordinateur et du système d'exploitation. Souvent présenté comme un langage machine de haut niveau, nombre de compilateurs se contentent à l'heure actuelle d'effectuer une traduction vers C. Le langage C n'a pas été tenu à l'écart de la tendance forte vers la programmation par objets, avec C++ (ou Objective C chez Apple, et C# chez Microsoft).
Le paradigme à objets est d'apparition ancienne (1967), il émergea réellement avec Smalltalk au milieu des années 70, mais n'a vraiment été popularisé qu'avec les langages Java et C++ dans les années 1990. Le mot d'ordre est la réutilisation du logiciel et son extensibilité. Pour ce faire, ces langages s'appuient sur la notion de classe et d'objet (analogue à la terminologie d'ensemble et d'élément en maths). Les objets ont du savoir-faire sous la forme de méthodes qui ne sont autres que des fonctions mais destinées à être transmises à un objet receveur sous la forme d'un message. Le calcul est donc décentralisé dans les objets, dont les méthodes peuvent être fonctionnelles ou impératives. Qui plus est, certaines méthodes, dites statiques en Java par exemple, sont propres à la classe et non à l'objet, permettant ainsi une programmation procédurale classique à la C. La quasi totalité des langages majeurs actuels possèdent des objets (C avec C++ et Objective-C, Caml, Scheme, Python, etc), ceux-ci étant devenus la pierre angulaire du développement logiciel moderne. Malgré les qualificatifs dont ils se parent [tout est objet, etc], peu de langages parviennent à la cohérence de Smalltalk dans ce domaine.
Les trois paradigmes cités ci-dessus sont complémentaires. Aucun d'eux ne permet d'effectuer avec la meilleure souplesse une tâche informatique quelconque. Un informaticien doit avoir pratiqué ces trois paradigmes pour appréhender parfaitement l'évolution de l'un quelconque d'entre eux (exemple : l'introduction par Java 8 des fermetures théorisées en Scheme depuis des dizaines d'années). Ceci vaut en particulier pour un étudiant sortant de L1-L2-L3.
En résumant grossièrement : |
Alors quoi ?
Alors le programmeur existe [occasionnellement ou professionnellement] pour programmer un ordinateur. Pour la plupart des langages de programmation, cela signifie : écrire des suites d'instructions qui seront exécutées les unes après les autres pour piloter la machine dans une direction bien précise, vers la solution d'un problème. Au fur et à mesure du déroulement de l'exécution d'un tel programme, la mémoire de la machine va être mise à contribution et sera modifiée par des instructions explicites, par exemple en Java par une affectation x = x+1. Cette mécanique, si bien huilée pour la machine, est souvent difficilement reçue par le débutant qui se retrouve plongé dans un monde virtuel d'objets dont l'état ne cesse d'être modifié au cours du temps. Deux millénaires de pratique mathématique n'ont toujours pas abouti à la nécessité d'introduire le temps, de modifier les objets au cours d'une démonstration, ni d'introduire de nouvelles structures comme la boucle. Avez-vous déjà rencontré des propositions logiques qui seraient vraies au début d'une démonstration et fausses à la fin [oui, dans le cas d'un raisonnement par l'absurde, mais ceci donne précisément une contradiction !]. Le mathématicien boucle-t-il ?...
La difficulté surgit en effet à partir du moment où l'on pose le problème de la rigueur. Ecrire un programme, c'est bien, c'est ludique. Certains ressentent même un délicieux chatouillement intellectuel lorsque le programme s'avère incorrect, la recherche de l'erreur étant alors ressentie comme un défi. Hélas, la distance volontairement mise entre l'activité de programmation et la pensée mathématique ordinaire a pour malheureuse conséquence de priver le programmeur d'une méthodologie permettant de penser les programmes [de panser les programmes...]. Oh, ce n'est pas tout-à-fait vrai, les théoriciens ont vite vu que le bât blessait, et ont forgé des outils issus de la bonne vieille Logique. De la Logique de Hoare aux invariants de boucle, il existe bel et bien des moyens intellectuels fiables et précis pour s'assurer de la validité d'un programme [écrit en C par exemple], ou mieux encore pour aider à le construire. Il s'agit néammoins de techniques difficiles [à utiliser et à enseigner, en-dehors des cas d'école], et une fois qu'on sait qu'elles existent, c'est un tout autre problème de les utiliser régulièrement. Ne semble-t-il pas - hélas - plus "simple" de se placer le plus vite possible au voisinage du programme correct, pour converger ensuite ?
while not correct : corriger()
Mais correct, cela signifie souvent perçu comme tel, via quelques essais [le plus souvent gentils] à la clé. Perdu : essayer un programme permet seulement d'être sûr qu'il est incorrect, et non le contraire. Votre programme marche ? Prouvez-le avant que le réacteur n'entre en fission... Ah, euh, mais je...
Ces problèmes sont difficiles. Ce qui n'empêche pas la science d'avancer, ni l'industrie de tourner, ni Bill et Tim d'engranger beaucoup [trop] de $$.
Et la programmation fonctionnelle, dans tout cela ? Son discours est très clair, quasi idéologique. Si l'on veut être rigoureux, il suffit d'utiliser le langage des mathématiques. Hélas, ce langage n'est pas directement exécutable sur un ordinateur. Il s'agit donc de trouver un langage de programmation qui en soit le moins éloigné possible, c'est-à-dire qui soit capable de se contenter des mêmes mécanismes mentaux primitifs. Les langages usuels de programmation fonctionnelle [dont l'ambition n'est cependant pas de "faire des mathématiques"] ont choisi de privilégier deux choses :
Au niveau des données, la notion de fonction et la structure d'arbre [souvent linéarisé sous forme de liste]. Soit dit en passant, le texte concret d'une fonction a dans le monde LISP immédiatement une structure d'arbre puisque c'est une liste ! Les programmes ont donc la même structure que les données, idée d'une puissance phénoménale.
Au niveau du contrôle de l'exécution, la composition de fonctions et le principe de récurrence.
Il n'y a donc pas d'instructions à proprement parler, seulement des expressions formées de fonctions f(x,g(y,z)) appliquées à des arguments. Au lieu d'écrire :
{ i1 ; i2 ; }
on écrit :
f2 o f1
Et au lieu de boucler, on raisonne par récurrence [en découvrant au passage que le concept d'itération n'est qu'un cas particulier de récurrence, ce qui après tout est une belle revanche de la théorie].
Nous ne nous occuperons pas de l'utilisation des langages de programmation fonctionnelle pour l'écriture de logiciels en grandeur réelle, cela pose d'autres problèmes [bien qu'il existe d'excellents compilateurs]. Notre pari, c'est que si vous avez reçu une bonne formation à la programmation impérative [avec Java ou Python] et à la programmation fonctionnelle [avec Scheme], vous serez bien armés pour aborder une seconde étape de la programmation, soit en tant que mathématiciens ou ingénieurs [avec des logiciels de calcul formel comme Maple, Maxima ou Mathematica] soit en tant qu'informaticiens car vous serez à même de comprendre une bonne part de ce qui fait la différence entre les langages de programmation, sur le double plan de l'efficacité à l'exécution et de l'efficacité à la conception des programmes.
Scheme (personnifié par Racket)
Attention quand même. Scheme n'est pas un langage de programmation purement fonctionnel [il en existe, par exemple Haskell]. Il contient aussi les mécanismes impératifs [séquencement d'instructions, affectations, tableaux, chaînes de caractères, graphisme, fichiers, etc.], à l'exception du typage statique [ce qui est ressenti comme une qualité par certains, et comme un défaut par d'autres, bien que Racket travaille aussi dans cette voie avec son Typed Scheme]. Dans le cadre de votre formation, l'accent sera mis sur la partie purement fonctionnelle de SCHEME, sauf dans l'option Scheme avancé, où le mécanisme d'affectation verra sa véritable utilité pour modéliser l'état local d'une fermeture [closure en anglais]. Il existe dans Racket (celui que j'utilise en cours et dans PCPS) un Scheme typé nommé Typed Racket pour illustrer dans les cours sur les paradigmes de programmation (un des meilleurs est PLAI) les problèmes sémantiques internes à un langage de programmation.
Historiquement, les Grands Ancêtres sont le lambda-calcul et les fonctions récursives, qui sont des théories de logique mathématique assez spartiates. Très intéressant, mais je vous déconseille de commencer par là.
Pour une approche non spartiate au lamba-calcul, qui plus est dans une page Web à la place de HTML+Javascript, vous pouvez regarder le projet LambdaWay de l'architecte Alain Marty, qui vous guidera jusqu'au combinateur Y, aux racines de la récursion...
La première concrétisation des deux théories précédentes fut l'apparition vers 1958 du langage Lisp [LISt Processing], créé par John McCarthy vers 1958, un peu après Fortran [FORmula TRANslator, 1955]. Ce sont les deux premiers langages vraiment évolués de l'Informatique, et ils résistent bien aux modes, preuves de leur vigueur. Alors que Fortran naquit des besoins numériques des militaires et des gestionnaires, Lisp vit le jour au célèbre MIT [Massachusetts Institute of Technology] pour résoudre des problèmes plus "symboliques" liés à l'Intelligence Artificielle [IA, 1956: la démonstration automatique de théorèmes, la planification au jeu d'échecs, la compréhension des langues naturelles, le calcul formel, les mécanismes cognitifs, etc]. Une motivation plus profonde de LISP était d'obtenir un langage auto-référent, c'est-à-dire qui puisse parler de lui-même. Il est en effet très facile d'écrire Lisp en Lisp, tout comme un manuel de grammaire du français est lui-même rédigé en français sans avoir besoin d'un langage encore "au-dessus". Pour le programmeur, cela signifie qu'il peut passer en paramètre des bouts de programme, ou encore synthétiser une fonction lors de l'exécution du programme, voire écrire des programmes qui se modifient en s'exécutant [ce qui est vrai pour un virus informatique, et pour l'intelligence humaine]. Lisp, une fois dégraissé [la version industrielle est Common-Lisp] est un excellent langage "embarqué" dans une application. Citons trois exemples : un éditeur de texte célèbre chez les programmeurs Emacs, ainsi que le logiciel de CAO le plus populaire AutoCAD, sont tous deux programmables en Lisp [Emacs-Lisp et AutoLISP], même si leurs noyaux sont écrits... en C [la majeure partie d'Emacs étant d'ailleurs écrite directement en Lisp]. Certains des premiers jeux 3D sur consoles ont été programmés dans des dialectes spécialisés de Lisp. Même le robot Pathfinder de la NASA exécutait du Common Lisp en explorant la planète Mars ! Les langages de programmation ne sont pas opposés mais complémentaires.
Scheme est né d'une volonté de réduction et de purification de Lisp, et son utilisation est sortie du cadre étroit de l'IA pour se focaliser à la fois sur l'enseignement aux débutants et sur la recherche fondamentale [liée à la sémantique -le sens- des langages de programmation, et au lambda-calcul].
Typiquement, vous voulez reconstruire une programmation par objets, ou bien une instruction GOTO ? Et bien, vous les implémentez en Scheme. Donc un langage de très haut niveau mais de suffisamment bas niveau pour lui incorporer des facilités que ses concepteurs lui ont [volontairement ou pas] refusées dans la version de base normalisée. Son utilisation déborde actuellement des deux cadres débutants/recherche : le projet Guile par exemple de la Free Software Foundation [GNU, voir aussi Richard Stallman le créateur d'Emacs] a choisi Scheme comme langage universel d'extension dans ses applications.
• Sur la page du
séminaire Richard Berry
au Collège de France, en mai 2013, Manuel Serrano
(INRIA Sophia-Antipolis) a montré comment utiliser Scheme pour programmer de manière
diffuse
le Web 2.0 avec HOP.
• Une vidéo de Jean-Jacques Lévy sur le
lambda-calcul et la programmation fonctionnelle
aussi en provenance du Collège de France.
• Les transparents de la conférence de Guy Steele
sur l'histoire de Scheme
(ou bien ici, il en est d'ailleurs l'un des inventeurs,
avec Gerald Sussman)...
Voilà grosso modo la philosophie : réconcilier puissance, extensibilité et minimalisme. Avec en prime le plaisir de programmer :
"The spirit of LISP hacking can be expressed in two sentences.
Programming should be fun. Programs should be beautiful."
-Paul Graham