TD Programmation fonctionnelle CS-110

Chapitre 1 : Langage des expressions et des fonctions

Introduction

Le cours CS-110 est un cours d'introduction à l'algorithmique. Vous apprenez à créer de "beaux" programmes, concis dans leur expression, généraux dans leur application et facilement compréhensibles. Ce but est atteint par l'introduction de techniques d'abstraction et l'utilisation d'un langage de programmation, CAML, ayant une syntaxe très simple. Vous apprenez ainsi dans ce cours des techniques de raisonnement applicables ensuite avec n'importe quel langage de programmation.

Les travaux dirigés du cours CS-110 vont vous permettre d'approfondir et d'appliquer les notions vues en cours. Le but de ces TDs est donc que vous compreniez vraiment le cours de programmation fonctionnelle et les raisonnements effectués. N'hésitez donc pas à me poser des questions si quelque chose n'est pas clair au niveau du cours ou dans un exercice. On est ensemble pour faire des erreurs dans les exercices, comprendre ces erreurs et ainsi comprendre le cours plus en profondeur.

Si vous rencontrez une difficulté quelconque sur un exercice lorsque vous travaillez en dehors des séances, n'hésitez pas à m'envoyer un mail (Anne.Benoit@imag.fr) pour pouvoir en discuter, et pouvoir faire pendant les séances des exercices supplémentaires sur les points qui ne vous paraissent pas clairs. C'est en effet en creusant les difficultés que vous rencontrez que vous pourrez au mieux comprendre et assimiler le cours.

Rappels de notations

En programmation fonctionnelle, on manipule des expressions et des fonctions. Les expressions peuvent être de différents types. Nous commençons par exposer ces types. Nous présentons ensuite la notion d'expression, puis la notion de fonction.

Type d'une expression

Types de base

• les entiers : $1$, $20$, $-14$ sont de type entier.
• les réels : $1.1$, $20.0$, $-14.44$ sont de type réel.
• les booléens : $vrai$ et $faux$ sont de type booléen.
• les caractères : un caractère est dénoté en l'entourant de guillemets. Ainsi, $''a''$ et $''Z''$ sont de type caractère. L'espace ($''\;''$) est un caractère comme les autres.
• les textes : regroupe toutes les chaînes de caractères, quelle que soit leur longueur. Le texte vide est noté $[]$ et le texte singleton formé d'un caractère est noté par exemple $[''a'']$ (pour le différencier du caractère $''a''$). Les textes constitués d'au moins deux caractères sont notés entre guillemets, comme par exemple $''toto''$.

Types construits

Ces types sont construits à partir des types de base.

• les n-uplets : un n-uplet de valeurs est décrit entre des chevrons (< et >), les valeurs étant séparées par des virgules. Le type d'un n-uplet est le produit (au sens ensembliste du terme) des types de chacune des valeurs. Pour définir un produit de types, on peut de manière équivalente, ou bien décrire un n-uplet de types, ou bien décrire un n-uplet de champs, un champ étant formé d'un nom et d'un type.
  n-uplet de types - intervalle : le type <entier, entier>. <1, 2> est de type intervalle.
  n-uplet de champs - inter : le type <inf : entier, sup : entier>. <1, 2> est de type inter.

• les tableaux : pour définir un tableau, on décrit son intervalle de définition et le type de ses éléments.
  Elem : un type; T : un tableau sur [3..6] d'Elem
  Pour décrire une valeur de type tableau, on énumère entre crochets les valeurs élémentaires dans l'ordre des indices croissants. $[1,34,23,2]$ est un tableau d'entiers.

Les Expressions

Une expression a un type et une valeur. $1$, $2.3$, $''toto''$ sont des expressions de base. On peut créer des expressions plus complexes en utilisant des opérateurs, de la désignation d'expressions ou des conditionnelles, comme nous le détaillons ci-dessous.

Opérateurs

• Les opérateurs arithmétiques $+$, $*$, ... ainsi que les opérateurs de comparaison $<$, $=$, ... peuvent être appliqués aux nombres.
  Ainsi, $2*3$ est une expression de type entier qui a pour valeur $6$, $2.1+3.3$ est une expression de type réel qui a pour valeur $5.4$, $3<4$ est une expression de type booléen qui a pour valeur $vrai$.
• Les opérateurs logiques $non$, $et$, $ou$, ... peuvent être appliqués aux booléens.
  Ainsi, $vrai\;ou\;(non\;faux)$ est une expression de type booléen qui a pour valeur $vrai$.
• Sur les caractères, on peut utiliser uniquement les opérateurs de comparaison $=$ et $\neq$.
  Ainsi, $''a'' = ''A''$ est une expression de type booléen qui a pour valeur $faux$.
• Divers opérateurs sont disponibles sur les textes :
  - L'opération de concaténation de textes est notée $\&$. Ainsi, $''bon'' \& ''jour''$ est une expression de type texte qui a pour valeur $''bonjour''$.
  - On dispose d'un opérateur pour ajouter un caractère à gauche ou à droite d'un texte. Ainsi, $''t''_\circ ''oto''$ et $''tot'' \bullet ''o''$ sont des expressions de type texte qui ont pour valeur $''toto''$.
  - Si t est un texte non vide, premier(t) dénote le premier caractère du texte t, fin(t) dénote le texte formé de t sans son premier caractère, dernier(t) dénote le dernier caractère du texte t, début(t) dénote le texte formé de t sans son dernier caractère. Par exemple, pour t=$''toto''$, premier(t) est une expression de type caractère qui a pour valeur $''t''$, et début(t) est une expression de type texte qui a pour valeur $''tot''$.
• Sur les tableaux, on a la notion de sélection pour accéder à un élément dans le tableau. On utilise la notation indicée pour sélectionner un élément du tableau. Ainsi, si T est un tableau d'entiers sur [3..6], $T_4$ est de type entier (on peut aussi écrire T[4]).
• Sélection pour les n-uplets de champs : Si on considère l'expression <1, 2> qui est de type inter (défini lors de la présentation du type n-uplet), alors $inf$ de <1, 2> est une expression de type entier qui a pour valeur 1, et $sup$ de <1, 2> est une expression de type entier qui a pour valeur 2. En revanche, on ne peut pas sélectionner directement les éléments d'un n-uplet de types.

Désignation d'expressions

Pour clarifier la compréhension d'une expression, il est souvent utile de nommer une sous-expression et de l'utiliser ensuite dans une autre expression.

• soit $x=E$ dans $F$ : dans l'expression $F$, toute occurrence de $x$ est remplacée par la valeur de l'expression $E$. On dit que la valeur $E$ est associée au nom $x$.
• soit $x_1=E_1$, $x_2=E_2$..., $x_k=E_k$ dans $F$ : plusieurs associations nom-valeur sont définies en même temps, mais elles sont indépendantes les unes des autres : la valeur associée à $x_i$ n'est pas connue dans une expression $E_j$.
• soit $x_1=E_1$ dans soit $x_2=E_2$ dans ... soit $x_k=E_k$ dans $F$ : dans cette construction imbriquée, $x_i$ est connu dans $E_j$ pour $i<j$.

Dans tous les cas, l'expression soit ... dans $F$ est du type de l'expression $F$, et elle a la valeur de l'expression $F$ évaluée dans un certain contexte. Nous abordons ici la notion de ``portée'' d'une variable, présente dans tout langage de programmation. Les exercices de TD puis de TP permettent de mieux comprendre cette notion.

Expression conditionnelle

La notion d'expression conditionnelle tient une place importante dans la programmation fonctionnelle.

• si $C$ alors $E_1$ sinon $E_2$ : $C$ est ici la condition, c'est une expression de type booléen. Si sa valeur est $vrai$, l'expression vaut $E_1$. Sinon elle vaut $E_2$.
• selon { description du domaine }
  . $C_1:E_1$
  . ...
  . $C_k:E_k$
  . [sinon$:E_{sinon}$]
  Ici, $C_1$, ..., $C_k$ sont les conditions, et la valeur de cette expression dépend de la condition qui est vraie. Ainsi, si $C_i$ vaut $vrai$, la valeur est celle de $E_i$. Par définition, une et une seule des conditions est vraie. La partie $sinon$ est facultative, elle représente la condition non $C_1$ et $...$ et non $C_k$.
• remarque sur les expressions conditionnelles à valeur booléenne : pour éviter de rendre les programmes illisibles, il est important de remarquer qu'une expression conditionnelle du type ``si $C$ alors $vrai$ sinon $faux$'' est totalement équivalente à l'expression ``$C$''. De même, ``si $C_1$ alors $vrai$ sinon $C_2$'' équivaut à ``$C_1$ ou alors $C_2$'', et ``si $C_1$ alors $C_2$ sinon $faux$'' équivaut à ``$C_1$ et puis $C_2$''.

Les fonctions

• spécification : nom_fonction : type_paramètres $\rightarrow$ type_résultat { description_fonction }
  Lors de la spécification d'une fonction, on précise le type des paramètres et du résultat. Par exemple :
  somme : deux entiers $\rightarrow$ un entier { somme de deux entiers }

• réalisation : nom_fonction( $param_1, ..., param_k$) : expression_résultat
  L'expression du résultat est une expression qui peut utiliser les expressions passées en paramètre $param_1, ..., param_k$. Par exemple :
  somme(a,b) : a + b

Il est important de remarquer qu'il existe plusieurs façons de passer un n-uplet de types en paramètre d'une fonction. Nous illustrons ceci sur un exemple :
diff : <un entier, un entier> $\rightarrow$ un entier { différence entre les deux entiers }
Première réalisation : diff(<a, b>) : b - a
Deuxième réalisation : diff(I) : soit <a, b> = I dans b - a Anne Benoit - Septembre 2001