Résumé
Ce cours a pour objectif de présenter les concepts
fondamentaux de la programmation fonctionnelle à travers le
langage Objective Caml. Il est en effet important pour un
élève ingénieur d'être familier avec les
différents paradigmes qui fondent les nombreux langages de
programmation qu'ils seront amenés à utiliser ou
à comprendre. D'autant plus que ces paradigmes ne sont pas si
nombreux: le cursus prévoit d'abord la présentation de
langages impératifs et ensuite aborde les langages à
objets (ce sont parfois les mêmes langages qui sont à la
fois impératifs et à objets, tel Java). Il est donc
utile de découvrir un autre mode de conception et de
programmation via les langages fonctionnels.
Dans un langage fonctionnel, par exemple Lisp, Haskell ou Objective
Caml, il n'y a plus de notion d'état, comme dans les langages
impératifs où l'état est la représentation
en mémoire des données manipulées par le
programme. En particulier, le programmeur ne peut modifier directement
l'état, comme par exemple modifier la valeur d'une variable,
puisqu'il n'a pas accès à l'état courant. D'une
certaine façon, l'idée est que le programmeur doit,
comme le mathématicien et le logicien, s'abstraire de cette
notion de mémoire mutable, considérée comme de
bas niveau, et se concentrer sur la déclaration de
propriétés et d'équations.
Les variables sont donc en réalité des constantes,
comme en mathématique, et les boucles (for, while, repeat etc.)
deviennent alors sans objet. Pour réaliser l'équivalent
des itérations impératives, il faut définir des
fonctions récursives, les paramètres liés aux
arguments lors de l'appel jouant le rôle de la modification de
variables (locales) dans les langages impératifs.
Ce qui vient d'être dit s'applique en réalité
au sous-ensemble purement fonctionnel des langages fonctionnels. En
effet, il est nécessaire qu'un programme produise un effet qui
ne soit pas lié directement à la logique du calcul (ce
qu'on appelle indument un effet de bord dans les langages
impératifs (effet secondaire conviendrait mieux que ce
barbarisme)) ne serait-ce que pour afficher son résultat (le
médium sur lequel se fait cet affichage relevant de
l'état).
L'environnement d'exécution des langages fonctionnels,
déchargeant le programmeur de la gestion explicite de la
mémoire, doit nécessairement inclure un glâneur de
cellules (garbage collector), mais ce n'est pas une
caractéristique car nombre de langages impératifs en
supposent l'usage (Ada, Java, Perl etc.).
Le choix du langage Objective Caml pour illustrer un noyau purement
fonctionnel est justifié par le fait que le langage Caml Light,
qui est une version simplifiée du premier, est
déjà enseigné comme premier langage de
programmation dans les universités et classes
préparatoires en France. Il possède en outre un
système d'inférence de type qui décharge
complètement le programmeur de l'obligation d'annoter,
même partiellement, son programme avec des types, et permet donc
un prototypage rapide. Cette caractéristique est très
pratique pour l'enseignement, car le débutant peut se
concentrer sur son algorithme, comme en shell Unix, tout en
bénéficiant du typage statique fort, qui le
protège des erreurs à l'exécution dues à
d'éventuelles hypothèses sur les données qui
seraient incohérentes par rapport à leur usage.
Les points que nous abordons sont les suivants:
- Notion de langage de description et de métavariable,
c'est-à-dire variable du langage de description, par
opposition à la notion de variable, qui fait partie du
langage décrit.
- Définition d'un mini-noyau d'Objective Caml, dit
mini-ML: notion de programme, phrases, expressions et
syntaxe de ces constructions élémentaires (variables,
fonctions, appels de fonctions, opérateurs
arithmétiques, opérations arithmétiques,
constantes, parenthèse, définition locale).
- Construction d'arbres de programmes mini-ML à partir de
la syntaxe. Cette représentation arborescente permet
d'introduire plus facilement la notion de variable
liée et son contraire, la variable libre. Un
algorithme de calcul des variables liées est proposé
de façon informelle et opère sur les arbres de
programmes. Les occurrences liée sont reliées par une
flèche à leur lieur.
- On définit les notions de liaisons statiques et
d'environnement.
- Logiquement, l'étape suivante consiste à donner un
algorithme informel qui évalue les programmes mini-ML clos,
définissant ainsi la sémantique de
mini-ML. Pour cela il faut présenter la notion de
valeur et de fermeture.
- Après avoir travaillé sur plusieurs exemples, on
présente une définition formelle de
l'évaluation, qui est une fonction partielle récursive
qui plonge les expressions dans les valeurs.
- Mini-ML est ensuite étendu avec les constantes et les
opérateurs booléens, les n-uplets, la
conditionnelle et la liaison locale récursive. Les motifs
irréfutables sont présentés comme une
généralisation des variables liées par une
liaison locale ou une fonction. Ces motifs irréfutables sont
soit une variable, soit un n-uplet de motifs
irréfutables, une parenthèse de motif
irréfutable ou le symbole joker (typographiquement c'est un
tiret bas). Cette extension permet de lier en parallèle des
valeurs à des variables, introduisant la notion de
non-spécification de l'ordre d'évaluation.
- Les types primitifs d'Objective Caml sont
présentés ensuite, ainsi que les définitions de
type. Les types polymorphes sont montrés sur des
exemples comme la fonction identité ou la fonctionnelle qui
compose deux fonctions. L'algorithme d'inférence de type
n'est présenté que très informellement sur ces
exemples et d'autres.
- Jusqu'à présent l'accent portait plus sur la
construction de valeurs que sur leur destructuration, ou
filtrage par motifs. Cette notion est donc maintenant
présentée comme un moyen commode de définir par
cas des fonctions (comme en mathématiques). Ensuite on
précise la différence avec les cascades de
conditionnelles où les conditions reposent sur
l'égalité et donne informellement la sémantique
du filtrage par motifs.
- Un pas dans la généralisation est encore franchi
avec la présentation des types variants (ou
somme), d'abord dans le cas particulier où il
équivaut à une énumération, puis dans sa
généralité (c'est-à-dire portant des
valeurs). Dualement, les filtres irréfutables sont
présentés comme un cas particulier de motifs. Le
pinacle est atteint avec la définition d'un type variant
polymorphe récursif isomorphe à la liste.
- Quelques fonctions sur ce type liste sont données et la
syntaxe prédéfinie ensuite. On montre alors qu'on peut
généraliser et définir aisément le type
des arbres binaires et des arbres binaires de recherche. Ceux-ci
peuvent être alors utilisés pour implanter des
ensembles totalement ordonnés.
- Nous donnons un aperçu des exceptions d'Objective Caml en
les comparant à celles du langage Java et C++
(historiquement, le modèle des exceptions de C++ provient des
langages de la famille ML, à laquelle appartient Objective
Caml, et les exceptions de Java s'inspirent fortement de celles de
C++).
Bibliographie
Emmanuel Chailloux, Pascal Manoury, and Bruno Pagano,
Développement d'applications avec Objective Caml,
O'Reilly & Associates Inc., Avril 2000.
Évaluation
Examen partiel écrit (1/3) ou deux quizz, examen final
écrit (2/3).
Ressources en ligne
