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.

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 :
• La Programmation fonctionnelle dit qu'exécuter un programme revient à évaluer un arbre d'expression, et le résultat du programme est la valeur de l'arbre. C'est cette valeur qui donne son sens au programme.
• La Programmation impérative dit qu'exécuter un programme revient aussi à évaluer un arbre, avec ou sans valeur de retour. Au fur et à mesure de l'évaluation de l'arbre, des actions sont produites sur le monde extérieur. Ce sont elles qui donnent son sens au programme.


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 :

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