La Programmation Fonctionnelle


Les trois paradigmes principaux de programmation

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 (exemples récents : l'introduction récente par Java 8 des fermetures de Scheme, ou les continuations avec le callcc de Ruby). 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, 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, dont la valeur n'est pas importante. 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 (!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 d'engranger beaucoup [trop] de $$.

Et la programmation fonctionnelle, dans tout cela ? Son discours est très clair, voire 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 qui sont appliquées à des arguments. Au lieu d'écrire

{ I1 ; I2 ; }

on écrit :

f o g

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 dans ce cours 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.

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]. En L3, le cours Paradigmes et Interprétation utilise Typed Scheme pour illustrer les problèmes sémantiques internes à un langage de programmation.

Historiquement, le Grand Ancêtre est le langage LISP [LISt Processor], 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, ou encore écrire des programmes qui se modifient en s'exécutant [ce qui est le propre d'un virus informatique, mais aussi de l'intelligence humaine]. LISP, une fois dégraissé [la version industrielle COMMON-LISP contient plusieurs centaines de fonctions de base] est un excellent langage "embarqué" dans une application. Citons trois exemples : l'éditeur de texte préféré des programmeurs EMACS, ainsi que le logiciel de CAO le plus populaire AUTOCAD, sont tous deux programmables en AutoLISP, même si leurs noyaux sont écrits... en C [la majeure partie d'Emacs étant d'ailleurs écrite directement en LISP]. Certains jeux 3D sur consoles sont écrits 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 le lambda-calcul]. Typiquement, vous voulez une programmation par objets, ou bien un goto, qui n'existent pas en SCHEME ? Vous les implémentez en SCHEME [en Master d'Informatique quand même...]. Donc un langage de haut niveau mais de suffisamment bas niveau pour lui incorporer des facilités que ses concepteurs lui ont [volontairement ou pas] refusées. 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...

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