La programmation : une approche fonctionnelle et récursive avec Scheme



Avant propos

Les deux principaux objectifs de ce livre sont de permettre au lecteur d'acquérir une première expérience en programmation fonctionnelle, et surtout d'appréhender la récursivité comme un mécanisme naturel et démystifié. Ainsi ce livre essaye de répondre, par l'exemple et l'exercice, aux problèmes essentiels que pose la programmation récursive : la terminaison des programmes et la peur de l'auto-définition. De plus, le lecteur sera sensibilisé aux principes fondamentaux de la programmation ainsi qu'aux principales structures de données.

L'attrait de la récursivité

La pensée récursive consiste à énoncer une idée en ses propres termes. En Informatique comme en Mathématiques, la pensée récursive se matérialise au travers d'entités qui se définissent par elles-mêmes.

Aussi ce livre s'adresse d'abord à tous ceux qui, soit ont été intrigués ou choqués par l'élégance d'écriture de la programmation récursive, soit ont été charmé par les phénomènes récursifs naturels, la beauté des fractales ou les dessins récursifs d'Escher. Nous proposons une approche synthétique et systématique de la programmation fonctionnelle et récursive à l'issue de laquelle la récursivité ne sera plus un mystère.

Pour la plupart d'entre nous, notre première rencontre avec un mécanisme récursif remonte à nos années passées sur les bancs du lycée. En effet, lors de l'étude des suites mathématiques, des définitions récursives et des preuves par récurrences nous ont été proposées. Mais illustrons plutôt !

La définition même de la suite mathématique U ci-dessous peut paraître choquante de part son caractère d'auto-définition. Cependant la deuxième partie de cette définition signifie simplement que la valeur d'un terme est obtenue en ajoutant deux au triple du terme précédent. D'autre part, sans la première égalité nous ne pourrions calculer aucune valeur de cette suite.

 
         U0=1
         Un=3*Un-1+2 si n>0

De même, comme nous l'expliquerons par la suite, la définition, ci-après, de la fonction longueur, qui calcule le nombre d'éléments d'une liste, peut paraître déroutante. En effet, on peut se rendre compte que l'on utilisera (ligne 5) la fonction alors même que l'on est en train de la définir.


1  (define longueur
2    (lambda (L)     ; liste => nombre
3      (if (null? L)
4          0
5          (+ 1 (longueur (cdr L))))))

Cet exemple met en avant le fort couplage qu'il existe entre une telle définition et notre choix délibéré pour une approche fonctionnelle de la programmation.

La programmation fonctionnelle

La programmation fonctionnelle repose sur la définition de fonctions et leurs applications. En cela, elle s'oppose à la programmation impérative qui, elle, est basée sur l'affectation et l'exécution séquentielle. En ce sens la programmation fonctionnelle est beaucoup plus proche des notations mathématiques et donc permet une expression plus naturelle de la récursivité.

Nous avons aussi été intéressés par la clarté, l'élégance et la propreté que procure une telle programmation. Ainsi le programmeur se concentre sur l'application de règles simples de programmation et sur l'essence de la récursivité. De plus, au niveau pédagogique, une approche fonctionnelle et la mise à l'écart de l'affectation (des effets de bord) permet d'avoir un ensemble simple et homogène de concepts. Une fonction ne pourra en aucun cas produire un effet de bord comme il est possible de le faire dans un langage comme Pascal. Des aberrations sémantiques sont ainsi évitées et l'apprenti programmeur n'a plus à choisir s'il doit définir une procédure ou une fonction.

Notre but n'est pas de présenter la programmation fonctionnelle de façon exhaustive ; de nombreux ouvrages ont présenté ses avantages et mérites, en particulier [Rea89,CM95].

Le choix de Scheme

Scheme est un langage de programmation fonctionnelle de la famille de Lisp. [SG93] est un historique très intéressant de Lisp et de ses dialectes. Deux grandes tendances ont prévalu lors des dernières évolutions de Lisp : le gigantisme et le minimalisme.

Common Lisp [Ste90] qui a été le dialecte Lisp de référence jusqu'à ces dernières années, incarne cette croissance démesurée. Ainsi Common Lisp inclue le maximum de fonctionnalités, des plus usuelles aux plus pittoresques. Il existe par exemple une fonction de conversion des nombres en leurs représentations en chiffres romains !

Scheme a suivi une toute autre direction puisque ce langage a été défini dans un souci de minimalité. Ainsi seuls les concepts primordiaux de Lisp ont été conservés.

 
              << Small is beautiful.
                 Small is powerful.
                 Small is easy to understand. >>
(Préface de Guy L. Steele Jr. dans [Spr89])

Notre choix s'est porté sur le langage Scheme car la minimalité implique souvent la facilité de compréhension. De plus, l'aisance de sa mise en oeuvre permet une expérimentation à travers de nombreux exercices ce qui est pour nous le meilleur moyen de toucher du doigt les problèmes de conception des fonctions récursives. Ainsi, il nous fallait choisir un langage de support adapté à nos objectifs.

Cependant, notre objectif n'est pas l'apprentissage de Scheme dans sa totalité. Bien, au contraire, nous avons volontairement choisi de ne présenter que certaines fonctions et d'éliminer tous les aspects qui auraient pu disperser notre discours. Par contre, lorsque nous avons fait une approximation ou une omission volontaire le lecteur en sera toujours prévenu. Aussi un lecteur averti devra toujours tenir compte de cet aspect fondamental de cet ouvrage. Scheme n'est pour nous que la boîte de Lego avec laquelle nous allons construire des fonctions.

Les objectifs d'acquisition

Détaillons maintenant quels sont pour nous les objectifs d'acquisition de la part du lecteur.

Afin d'atteindre ces objectifs, le présent ouvrage est divisé en différentes parties. La première partie est constituée des Cours et exercices. Chaque << cours >> est organisé de manière logique et met en avant un des aspects qui sera repris par les exercices. Afin que le lecteur puisse travailler de manière autonome tout exercice possède une correction (parfois même plusieurs quand la comparaison est intéressante). Les exercices sont très nombreux, tous sont importants mais certains se ressemblent ; ceux qui sont indiqués par une marque noire sont primordiaux.

Les concepts présentés dans le chapitre 8 dénotent par rapport à l'idée principale développée dans cet ouvrage car ils présentent les aspects non fonctionnels de Scheme. Cependant la lecture de ce chapitre n'est pas requise pour la compréhension de la suite du livre.

Il nous a semblé très important que le lecteur de cet ouvrage prenne conscience que la programmation fonctionnelle récursive ne se limite pas à l'élaboration de simples petites fonctions mais permet aussi de programmer des problèmes complexes en les décomposant. La partie Application met donc en oeuvre les concepts vus dans la première partie, mais dans le contexte de problèmes plus conséquents. Ainsi nous présentons l'algorithme de codage/décodage d'Huffman, un petit système expert et un système de calcul formel.

En Annexe, nous avons regroupé les corrections des exercices et des applications ainsi qu'une liste des principaux interprètes de Scheme disponibles.

Remerciements

Nous exprimons tout d'abord notre gratitude à Gérard Huet, directeur de recherche à l'INRIA Rocquencourt et correspondant de l'Institut, de nous avoir fait l'honneur de préfacer cet ouvrage.

Ce livre est l'aboutissement d'un cours de programmation fonctionnelle et récursive en DEUG à l'Université de Nice -- Sophia Antipolis. C'est avec plaisir que nous remercions Yves Hervier, vice-président de l'Université de Nice -- Sophia Antipolis, responsable du MIPS et coordinateur des enseignements d'Informatique en DEUG, de la confiance qu'il nous a accordée et de son ouverture d'esprit. Sans la confiance et la liberté qu'il nous a offertes ce livre n'existerait pas.

Nous tenons à remercier Jacques Chazarain, Professeur à l'Université de Nice -- Sophia Antipolis, qui nous enseigna la programmation fonctionnelle et nous contamina avec le virus du Lisp, et André Hirschowitz, chercheur au CNRS, grâce à qui nous avons compris les mécanismes et les problèmes de la programmation récursive.

Nous voulons remercier Erick Gallésio pour nous avoir fait connaître Scheme ainsi que pour STk, l'interprète Scheme qu'il développe au Laboratoire I3S du CNRS et de l'Université de Nice -- Sophia Antipolis et avec lequel nous avons testé tous les exemples de ce livre.

Nous tenons aussi à remercier Martine Follen et Werner Keilholz qui, grâce à leur expérience des séances de travaux pratiques, nous ont fait de nombreuses remarques tant sur la forme que sur le fond de cet ouvrage. Nous remercions aussi Jean-Paul Roy pour ses précieuses remarques, Anne-Marie Dery pour sa patiente relecture et Hélène Collavizza ainsi que Mireille Fornarino pour leur enthousiasme.

Un grand merci à Hervé Flores pour la touche humoristique qu'il a apportée à cet ouvrage et pour sa recherche dans la compréhension des concepts que nous voulions illustrer. En effet, les illustrations de cet ouvrage ne sont pas simplement amusantes et sympathiques ; chacune d'entre elles possède une signification précise et représente un des points fondamentaux mis en avant dans chaque chapitre. Nous remercions aussi Sylvia Arditi qui nous a poussé à éditer ce livre et Florence Duriche pour son soutien quotidien.

Ce livre doit beaucoup aux étudiants de DEUG, dont les interrogations et les critiques ont fait progresser la formulation des aspects fondamentaux de cet ouvrage. Enfin que les lecteurs, qui voudront bien nous signaler des faiblesses, des erreurs (dont nous sommes les seuls responsables), formuler leurs remarques ou présenter leurs suggestions en soient vivement remerciés par avance. Les auteurs peuvent être joints par courrier électronique aux adresses suivantes : arditi@unice.fr et ducasse@unice.fr.

Nice, Février 1996.

Laurent Arditi et Stéphane Ducasse