Cours Caml

Cours la programmation fonctionnelle avec Ocaml


Télécharger Cours la programmation fonctionnelle avec Ocaml

★★★★★★★★★★3.5 étoiles sur 5 basé sur 1 votes.
Votez ce document:

Télécharger aussi :


Introduction à la programmation fonctionnelle avec Ocaml

1 Introduction

Depuis les débuts de l’informatique une très grande quantité de langages de programmation (voir figure 1 ) sont apparus, si bien qu’il est parfois difficile de faire un choix, de les comparer ou tout simplement de les distinguer. Les paradigmes de programmation sont à cet égard un précieux outil. Il s’agit de styles de programmation communément acceptés par les programmeurs, avec la particularité de bien s’adapter à certains types de problèmes, et auxquels adhèrent plus ou moins la grande majorité des langages. Parmi les styles les plus connus on trouve la programmation impérative, la programmation objet, la programmation logique, la programmation fonctionnelle. Peu de langages de appartiennent à une seule de ces catégories. Le plus souvent, ils sont hybrides : ils se classent majoritairement dans une catégorie, tout en intégrant des capacités intéressantes appartenant à  d’autres styles. La connaissance de plusieurs paradigmes permet au programmeur de discerner parmi la jungle des langages, et de comprendre et d’exploiter au mieux les avantages des différents styles.

Ocaml est un langage fonctionnel incorporant plusieurs paradigmes de programmation. Il est issu du langage ML, et a récemment influencé le langage F# de la plate-forme .NET développeé par Microsoft. Il incorpore des traits impératifs et objets ainsi que de puissantes constructions modulaires. Il est développé à l’INRIA depuis les anneés 80. Ocaml est un langage intéressant à plusieurs égards :

–  Ocaml est fortement typé  avec des types inférés statiquement et du polymorphisme paramétrique. Cela en fait un langage sûr et facile à employer.

–  Ocaml possède les traits habituels des langages objets : classes, instances, héritage multiple et liaison retardeé. Il propose aussi des constructions plus évolueés : parmi celles-ci les classes abstraites et les classes paramétreés.

–  Ocaml possède un système de modules très génériques, un mécanisme de programmation par filtrage puissant autorisant une écriture de fonctions concise et claire, des structures des donneés récursives expressives et faciles à décrire et à exploiter via la programmation par filtrage.

–  La  sémantique  de  Ocaml  est  bien  définie  et  la  partie  purement  fonctionnelle  est  particulièrement adapté  au raisonnement mathématique sur les programmes que nous aborderons en deuxième partie de ce cours.

–  Ocaml possède un glaneur de cellules (garbage collector), et des nombreuses bibliothèques. Il peut exécuter des processus légers (threads) et communique sur Internet (ouverture de canaux de communication, applications client-serveur, etc.). Il offre également la possibilité d’interagir avec le langage C.

History of Programming Languages

FIGURE 1 – La jungle des langages de programmation

–  Ocaml est un langage compilé qui possède une boucle interactive : les tests y sont plus faciles. On peut également produire du code exécutable portable (bytecode) ou natif, dont l’efficacité est proche du code C dans certains cas.

Malgré ses origines académiques Ocaml est un langage dont l’utilisation dépasse le domaine de la recherche en langages et leurs outils associés. Il est utilisé  pour l’enseignement dans des nombreuses universités en France, aux Etats Unis et au Japon, et dans les classes préparatoires franc¸aises. Il est de plus en plus adopté en industrie : dans l’industrie aéronautique pour l’analyse des programmes, en vertu de sa sûreté  de programmation (projet Astreé : Analyse Statique de logiciels Temps-RE´ el Embarqués) ; pour le controˆle des systèmes critiques en avionique (Airbus) et dans le secteur nucléaire. Des grands groupes de l’industrie du logiciel utilisent Ocaml (F# :Microsoft, Intel, XenSource). Il est employé  également pour écrire des applications dans le secteur financier (Jane Street Capital, Lexifi), par des projets libres comme MLDonkey (peer-to-peer), GeneWeb (logiciel de généalogie), Unison (logiciel de synchronisation de fichiers multi-plateforme dans certaines distributions Linux), par certains logiciels de l’environnement KDE, par des systèmes bio-informatiques pour l’analyse des protéines, et par beaucoup d’autres.

1.1 La programmation fonctionnelle

La programmation fonctionnelle est fondeé sur la notion mathématique de fonction. Une fonction relie les éléments de deux ensembles : le domaine et le co-domaine de la fonction. Ainsi, à  chaque valeur du domaine, la fonction fait correspond une unique valeur de son co-domaine.

  tri :   suite d’articles   →   suite d’articles triés

  s   ›→ tri(s)

La caractéristique essentielle des fonctions est d’associer une seule valeur image pour chaque valeur du domaine, de manière stable et indépendante du contexte. En mathématiques, une fonction appliqueé sur un même argument, donne toujours le même résultat : elle ne change pas de résultat selon la valeur des variables ou de ”l’état du système”. Les opérations des langages de programmation impératifs ne jouissent pas de cette stabilité. Voici par exemple une opération simple en langage C :

i n t  i  =  0 ;

i n t  f  ( i n t  j ) { i = i + j ;

return i ;

}

L’opération f ne correspond pas à une fonction : son résultat n’est pas seulement fonction de son argument j mais aussi de la valeur courante de la variable globale i, qui de plus est modifieé lors de chaque appel. Le résultat obtenu dépend donc de l’état des variables au moment de l’appel, et modifie directement cet état. L’opération f ne peut pas être étudieé en dehors de son contexte.

L’ideé  derrière  la  programmation  fonctionnelle  est  de  favoriser  la  réalisation  des  calculs  à  l’aide  de fonctions au sens mathématique du terme. Ceci afin de tirer parti de leur séparation du contexte et de la stabilité qui en découle.  

1.1.1Les fonctions vues comme des valeurs

En programmation fonctionnelle les fonctions sont des valeurs au même titre que les entiers, les enregistrements ou les tableaux. Ainsi par exemple, il est possible de stocker une fonction dans une variable ou dans un tableau afin de l’appliquer plus tard à son argument, ou de passer une fonction en paramètre à une autre fonction. Cela élève les fonctions au statut des donneés. On parle alors de pleine fonctionnalité ou ordre supérieur ou encore des fonctions comme étant des entités de première classe. Il en découle un mécanisme de généralisation assez puissant. Considérons par exemple la fonction de tri d’un ensemble d’articles. Son fonctionnement dépend du critère d’ordonnancement à employer pour réaliser le tri. Plutoˆt que de fixer celui-ci dans la fonction de tri, on peut le lui passer en tant qu’argument. La fonction de tri devient générale à tout critère et peut être employeé dans beaucoup de contextes.

  tri :   critère de comparaison × suite d’articles   →   suite d’articles triés

(fcomp, s)

Cette généralisation en Ocaml prendra la forme :

›→

tri(fcomp, s)

l e t   t r i ( f compare , a r t i c l e s ) = . . .

Dans d’autres langages, ce genre de généralisation est plus lourde à  implanter. Par exemple, en C, il faudra transmettre la fonction au moyen d’un pointeur, en Java il faudra transmettre la fonction à l’intérieur d’un objet dont on aura définit la classe ou l’interface auparavant.

i n t e r f a c e Order boolean compare ( O b j e c t a , O b j e c t b ) ;{ 

}

O b j e c t [ ]  t r i  ( O b j e c t [ ]  a r t i c l e s  ,  Order  o ) ;

1.2 La programmation générique par les types

L’ideé derrière la programmation générique ou généricité est de ne pas restreindre inutilement le type des donneés et des fonction, mais au contraire, de le rendre génériques à toute valeur compatible avec leur définition. En pratique, ceci est fait par le biais de paramètres de types qui jouent le roˆle de type générique, pouvant être remplacé plus tard par un type spécifique. Par exemple, en Java 1.5 on peut définir le type d’une cellule (dans une liste chaîneé) dont la nature du contenu dépend du paramètre de type A :

c l a s s C e l l u l e <A> {A c o n t e n u ; C e l l u l e s u i v a n t };

En C++, on utilisera les partons (templates) pour généraliser le type d’une fonction. Par exemple, voici la fonction identité qui renvoie son arugment sans lui appliquer aucune opération :

t e m p l a t e <typename A>

A i d e n t i t y (A x ) { return x ; }

Ce mécanisme de généralisation est présent dans beaucoup de langages : C++, Java, Ada, Haskell, Eiffel, SML, Ocaml. Il permet de concilier flexibilité du typage avec la rigueur du typage statique ; il favorise fortement la réutilisation du code, et permet également le typage plus précis (avec moins d’erreurs) du code générique. Il s’agit d’un exemple réussi de mélange de styles de programmation dans la mesure ou` il a été adopté par différents langages de styles très divers.

1.3 Avantages et contraintes de la programmation fonctionnelle

La programmation fonctionnelle pure (sans effets de bord) présente beaucoup d’avantages :

1.  “Modularité” de la programmation, simplification du débogagge : les fonctions au sens mathématique peuvent être considéreés comme des boîtes noires au sein des programmes. Il devient plus facile de les concevoir séparément, de circonscrire leurs effets, et d’isoler les erreurs. Par ailleurs, la généralisation des fonctions par le biais de paramètres fonctionnels favorise la structuration des programmes et la réutilisation d’algorithmes.

2.  Formalisme mathématique sous-jacent : cela permet la vérification du langage (compilateur, typage, sémantique formelle) mais aussi des programmes via diverses analyses, tests ou à l’aide de prouveurs automatiques.

3.  Généricité, flexibilité, réutilisation : la programmation générique par les types favorise la réutilisation du code tout en assurant un typage précis. Les fonctions et les donneés deviennent plus génériques et donc potentiellement réutilisables.

Ces avantages ont un prix : les contraintes imposeés par l’usage de la programmation fonctionnelle pure, parmi lesquelles on peut mentionner :

–  Pas d’effets de bords : pas d’affectation, pas de variables modifiables. Seules les constantes sont admises ;

–  Une fonction ne peut pas changer ce qui lui est extérieur ;

–  Le comportement d’une fonction ne peut pas être modifié de l’extérieur ; – Certaines constructions sont proscrites : boucles itératives, goto.

–  La récursivité est à utiliser afin de coder les boucles.

–  La gestion implicite de la mémoire devient indispensable.

2 Débuter avec Ocaml : quelques principes

Ocaml est un langage compilé. Au choix, il peut être compilé vers un langage intermédiaire (bytecode) ou vers du code natif avec des performances comparables à celles du code C. Il possède également un mode interactif ou` il analyse et répond à chaque phrase entreé par l’utilisateur.

2.1 Le mode interactif

Pour lancer Ocaml en mode interactif on tape la commande ocaml dans la fenêtre des commandes (sous Unix). Vous aurez la réponse :

% ocaml

O b j e c t i v e Caml v e r s i o n 3 . 0 7

#

Le  caractère  # invite  l’utilisateur  à  entrer  une  phrase  écrite  dans  la  syntaxe  Ocaml  ,  phrase  qui  par exemple nomme une valeur, explicite une définition ou décrit un algorithme. En mode interactif, chaque phrase Ocaml doit terminer par ;; puis l’utilisateur valide sa frappe par un retour chariot. Dès lors, Ocaml analyse la phrase :

–  calcule son type (inférence des types),

–  la traduit en langage exécutable (compilation)

–  et enfin l’exécute afin de fournir la réponse demandeé.

En mode interactif, Ocaml donne systématiquement une réponse qui contient :

–  Le nom de la variable déclareé s’il y en a.

–  Le type inféré par le typage. – La valeur calculeé par l’exécution.

# let x = 4+2;; val x : int =

La réponse d’Ocaml signale que l’identificateur x est déclaré (val x), avec le type des entiers (:int) et la valeur calculeé 6 (=6). Un exemple qui utilise la valeur xd éjà déclareé :

# x * 3;; : int = 18  

2.2 Le mode compilé

Considérons un fichier source avec le code suivant :

    p r i n t s t r i n g   ” H e l l o  World !\ n ” ; ;    

Sous une fenêtre de commande Unix nous pouvons compiler, lier et exécuter ce programme par la commande :

ocamlc -o hello ./hello Hello World!

2.3 Quelques principes

Valeurs de première classe Un valeur est dite de première classe si elle peut être rec¸ue et/ou passeé en argument à une fonction, ou si elle peut être stockeé dans une variable. Les valeurs manipuleés en Ocaml sont les objets, les valeurs de base (de type int, bool, string, etc.), les fonctions, les valeurs de types construits, prédéfinis (listes, tableaux, etc) ou définis par l’utilisateur. Toutes ces valeurs sont de première classe.

Pas de variables modifiables Dans la partie strictement fonctionnelle d’Ocaml il n’y a pas de variables modifiables. Il est seulement possible de déclarer des constantes nommeés (identificateurs), mais leur valeur ne pourra changer au cours du programme. Par exemple

l e t a = 7 ;

v a l a : i n t = 7

permet de déclarer une nouvelle constante a lieé à la valeur 7.

Environnement Ensemble de liaisons entre identificateurs ayant été déclarés et leurs valeurs. On distingue deux sortes d’environnement : global et local avec respectivement des liaisons globales et locales.

Typage fort et inférence de types Ocaml est un langage fortement typé : toute phrase du langage se voit attribuer un type. La compilation échoue si le typage du programme est incorrecte. Mais aucune annotation de types n’est nécessaire pour typer les valeurs : le typeur infère leurs types, y compris pour les fonctions (qui sont des valeurs comme les autres). Par exemple, un identificateur lié à un entier par un let se voit attribuer le type entier ; une fonction qui effectue une opération de concaténation sur son argument se voit attribuer un type ou` l’argument est de type string.

# l e t a = 7 ; v a l a : i n t = 7

# l e t b e g a i e x = x ˆ ”−” ˆx ; ; v a l b e g a i e : s t r i n g −> s t r i n g

Les expressions Constructions du langage dont le but est de calculer une valeur dite résultat de l’expression. Une expression est constitueé soit d’une constante, soit d’opérations et/ou appels de fonctions. On évalue une expression afin d’obtenir son résultat. Le type d’une expression est celui de sa valeur résultat. En supposant que x vaut -2, et que la fonction f teste si son argument est positif, voici quelques exemples d’expressions avec leurs valeurs et leurs types :

expression

valeur

type

5

5

int

3 + x

1

int

f(3)

true

bool

f(x) || x=7

false

bool

if x>0 then 1 else 2

2

int

Toute expression a un type Ocaml étant un langage fortement typé, toute expression se doit d’avoir un type. Dans le tableau précédent, notez par exemple que la conditionnelle if x>0 then 1 else 2 est une expression, et en tant que telle permet de calculer une valeur (1 ou 2 selon la valeur de x). Par conséquent

son type est le type de cette valeur calculeé, à savoir int.

Les programmes en Ocaml sont constitués uniquement de déclarations et d’expressions Ocaml est un langage déclaratif, autrement dit, le style d’écriture privilégié  est celui de la description de calculs à réaliser.

3 Déclarations et types

3.1 Déclarations globales et locales

Déclarations globales Un identificateur est déclaré globalement par le mot clef let :

# l e t x = 7 ; ; v a l x : i n t = 7

# x + 2 ; ;

− : i n t = 9

# l e t y = x + 7 ; ;

− : i n t = 14

L’identificateur ainsi déclaré  est ajouté  dans l’environnement global du programme. Dès lors, il peut être utilisé lors d’un calcul ultérieur.

Déclaration  locale  à  une  expression  Un  identificateur  est  déclaré  localement  à  une  expression  par  la construction let in :

# l e t y = 5 i n x ∗y ; − : i n t =45

Une déclaration locale permet de constituer un environnement local visible seulement dans l’expression qui suit le in. L’expression après le in est évalueé dans l’environnement global augmenté de cet environnement local déclaré avant le in. La construction let  in est une expression, comme le montre le message donné par la boucle interactive : il n’y a pas d’indication val nomV ar:, autrement dit, aucun identificateur n’est déclaré. En revanche, le résultat de l’expression après le in est calculé  et renvoyé  en résultat final.

# l e t y = 3 i n x+y ; ;

− :  i n t  =  10

# y ; ;

Unbound v a l u e y

Redéfinitions et masquage : Les identificateur déclarés jusqu’ici sont constants : la liaison entre un identificateur x et sa valeur v, au moyen d’une déclaration let x =v, ne peut être modifieé. On pourra introduire une nouvelle liaison pour x, let x = v1 qui masque la première dans la suite du programme, mais on ne pourra pas la modifier.  

3.2 Les types

Comme la plupart des langages Ocaml offre des types de base prédéfinis et des types composites, dont certains sont prédéfinis et d’autres sont à déclarer par l’utilisateur.

–  types de base prédéfinis : entiers, booléans, caractères, reéls et le type vide. Le tableau suivant exhibe les types de base plus un type composite prédéfini : les chaînes de caractères. Pour chaque type nous donnons quelques exemples de constantes du type ainsi que les opérations primitives définies sur celui-ci. Le symbole ˆ est l’opérateur de concaténation des chaînes de caractères.

Type de base

Constantes

Primitives

unit

()

pas d’opération !

bool

true false

& || not

&

char

’a’   ’\n’   ’\097’

code, chr

int

1   2   3    

+     *   /   max_int

float

1.0   2.   3.14  



+.   -.   *.   /. cos

string   (composite)

"a\tb\010c\n"

ˆ   s.[i]   s.[i]

–  types composites : nous indiquons s’il s’agit d’un type prédéfini ou à définir par l’utilisateur, et s’il s’agit ou non d’un type modifiable, nous donnons un exemple, et enfin le nom du type en Ocaml.

Types composites

Caractéristiques

Exemple

Type Ocaml

tableaux

prédéfini, modifiable

[<1;2;3>]

int array

chaînes

prédéfini, modifiable

"bonjour"

string

n-uplet

prédéfini

(4,"abc",true)

int*string*bool

enregistrement

à déclarer

{nom="Dupond";num=017789}

< nomType >

inductif

à déclarer

Noeud(1, Vide, Vide)

< nomType >

listes

prédéfinis

[’a’; ’b’; ’7’]

char list

objets

à déclarer

non présenté

< nomType >

Primitives de comparaison : =, > , < , >=, <=, <>. Elles sont valables pour tous les types (y compris les types composites et les fonctions). Appliqués sur des types composites, la comparaison suit les règles d’une comparaison lexicographique : on compare les composantes de chaque valeur en tenant compte de leurs positions respectives.

Exemples :

# 1+ 2 ; ;

− : i n t = 3

# 1 . 5 + . 2 . 3 ; ;

− : f l o a t = 3 . 8

# l e t x = ” cou ” i n x ˆx ; ;

− : s t r i n g = ” coucou ”

# 2 > 7 ; ;

− : b oo l = f a l s e

# ” b o n j o u r ” > ” bon ” ; ; − : b oo l = t ru e

# ” durand ” < ” m a r t i n ” ; ; − : b oo l = t ru e

# ” ab ” = ” ba ” ; ;

− : b oo l = f a l s e

3.2.1Types n-uplets

Un n-uplet est un assemblage de n valeurs vi de types hétérogènes, séparés par des virgules et possiblement entourés de parenthèses : (v1, v2, . . . vn)

# ( 1 , t ru e ) ; ;

−: i n t ∗ bo o l = ( 1 , t ru e )

# l e t l i v r e = ( ” P a r o l e s ” , ” P r e v e r t , J a cq u e s ” , 1 9 3 2 ) ; ; v a l l i v r e : s t r i n g ∗ s t r i n g ∗ i n t =( ” P a r o l e s ” , ” P r e v e r t , J a c q u e s ” , 1932 )

Un n-uplet est semblable à  un enregistrement à  n champs sans étiquettes. L’avantage des n-uplets sur les enregistrements réside dans leur utilisation primitive, sans déclaration préalable. De son coˆté, un type enregistrement doit être déclaré avant toute utilisation.

Le type d’un n-uplet : Le type d’un n-uplet (v1, v2, . . . , vn) est t1  ∗  t2. . . tn, ou` ti est le type de la composante vi. Il s’agit du produit cartésien des types de chacune des composantes.

Un n-uplet permet de mettre dans un “paquet” autant de valeurs que l’on veut. Cela est pratique, si une fonction doit renvoyer plusieurs résultats :

# l e t d i v i s i o n e u c l i d i e n n e x y = ( x / y , x mod y ) ; ; v a l d i v i s i o ne u c l i d i e n n e : i n t>i n t>i n ti n t = <fun >

# d i v i s i o n e u c l i d i e n n e 5 2 ; ;

− : i n ti n t = ( 2 , 1 )

3.2.2Le type enregistrement

Un enregistrement est une collection de valeurs de types hétérogènes, ou` chaque valeur est accompagneé d’une étiquette permettant de sélectionner la valeur qui l’accompagne. Les enregistrements sont des types à déclarer par le programmeur.

#  t y p e  c l i e n t  =  { numero :  i n t ;  nom :  s t r i n g ;  s o l d e :  f l o a t } ; ; t y p e c l i e n t = { numero : i n t ; nom : s t r i n g ; s o l d e : f l o a t }

On construit une constante d’enregistrement en donnant des valeurs pour chacun de ses champs déclarés :

# l e t durand = { numero = 265 ; nom = ” Durand ” ; s o l d e = 0 . 0 } ; ;

v a l durand : c l i e n t ={ numero = 265 ; nom=” Durand ” ; s o l d e =0}

On sélectionne la valeur d’un champ c, dans l’enregistrement e, par la notation e.c

# durand . numero ; ; − : i n t = 265

à moins de préciser le contraire, les champs d’un enregistrement ne sont pas modifiables : on ne peut pas changer les valeurs dans les champs, mais on peut les recopier. La fonction suivante prend un client et un nouveau solde et attribue ce nouveau solde au client. Pour cela, elle construit un nouvel enregistrement ou` sont recopiés tous les champs inchangés :

#  l e t  n o u v e a u s o l d e  c  s  =  { numero  = c . numero ; nom  =  c . nom ;  s o l d e  =  s } ; ; v a l n o u v e a u s o l d e : c l i e n t −>f l o a t> c l i e n t = <fun >

  #  l e t  durand =  { numero  =  265 ;  nom  =  ” Durand ” ;  s o l d e =   0 . 0 } ;

; v a l  durand  : c l i e n t  = { numero = 265 ; nom=” Durand ” ; s o l d e =0}

# l e t d u r a n d B i s =  n o u v e a u so l d e durand 5 0 . 3 4 ; ;  v a l  d u r a n d B i s  :  c l i e n t  =  { numero  =  265 ;  nom  =  ” Durand ” ;  s o l d e  =  50 . 34 }  

4 Les fonctions

Déclarer une fonction : Un identificateur de fonction est déclaré comme tout autre identificateur, à l’aide d’un let. La syntaxe d’une déclaration de fonction est :

l e t <nom−f o n c t i o n > = <corps −f o n c t i o n > l e t <nom−f o n c t i o n > <(param1, param2, . . . paramn)><corps −f o n c t i o n > l e t <nom−f o n c t i o n > <param1> <param2> . . . <paramn> = <corps −f o n c t i o n >

La liste de paramètres peut être constitué d’un unique paramètre (entouré ou non de parenthèses), d’un nuplet de paramètres 2 (entouré de parenthèses) ou de plusieurs paramètres séparés par des espaces. Voici un premier exemple de fonction avec un seul paramètre :

# l e t double ( y ) = y ∗ 2 ; ; v a l double : i n t>i n t = < fun >

Le type d’une fonction : est noté t→   q, ou` t est le type d l’argument et q celui du résultat de la fonction. Dans le cas de la fonction double, l’argument et le résultat sont de type entier.

Appliquer une fonction : On applique une fonction en la faisant suivre de son argument (éventuellement entre parenthèses) :

# double ( 9 ) ; ;

−  :  i n t  = 18

double  9 ; ; −  :  i n t  = 18

#  l e t  z  =  double ( x )  ; ; v a l z : i n t = 12

2. Autrement dit, d’une valeur de type n-uplet.

4.1 Les fonctions à plusieurs arguments

Une fonction peut prendre plusieurs arguments : soit sous la forme d’un n-uplet d’arguments, soit en séparant les noms des paramètres par des espaces, avant la définition du corps.

Fonction avec n-uplet d’arguments : Les arguments de la fonction sont encapsulés dans un n-uplet. Techniquement, la fonction prend un seul argument qui est constitué par un n-uplet de valeurs :

# let somme (x,y) = x+y;; val somme : int * int -> int =

# somme (2,3);;

: int = 5

La fonction somme possède un seul argument, qui est ici une paire. Ceci est reflété par le type de la fonction : int ×  int →  int, ou` int ×  int est le type de l’argument, et int est le type de son résultat.

Type d’un fonction avec n-uplet d’arguments : La fonction :

let f(x1, x2, . . . , xn) = corps

possède un argument, qui est un n-uplet de valeurs (x1, x2, . . . xn) et un résultat calculé par corps. Le type du n-uplet (x1, x2, . . . , xn) est t1t2. . .tn, ou` ti est le type de chaque xi. Donc, le type de f est :

t1t2. . .tntcorps

Fonction avec plusieurs arguments séparés : Les arguments de la fonction sont énumères séparément, et sont séparés par des espaces :

#   let moyenne x y = (x+.y)/. 2.0;; val moyenne : float -> float -> float =

Cette fonction prend deux arguments x et y de type float (les deux premiers float dans le type de la fonction), et renvoie un résultat de ce même type : float (le troisième float du type). L’application de la fonction se fait en faisant suivre le nom de la fonction de tous ses arguments donnés un par un et séparés par des espaces :

# moyenne 15.0 12.6;;

: float = 13.8

Type d’une fonction avec argument séparés : Si f est une fonction à deux arguments, son type est alors de la forme : t1  →t2   →tcorps ou`, t1, t2 sont les types des arguments, et tcorps est le type du résultat. On notera donc, que le type d’une fonction contient autant de flèches qu’il y d’arguments séparés dans la fonction.

4.2 Les fonctions récursives

En programmation impérative les processus répétitifs sont programmés à  l’aide de boucles itératives, dont la condition d’arrêt dépend souvent de la valeur d’une variable qui est modifieé au sein de la boucle. En programmation fonctionnelle pure, les variables modifiables étant proscrites, on se sert de la récursivité pour écrire les boucles. Supposons qu’on ait à écrire une fonction qui calcule la factorielle n! d’un entier n ≥ 0, selon la formule :

  0! =   1

n! = 1 × 2 × . . . × (n − 1) × n

Par exemple, 4! = 1 × 2 × 3 × 4 = 24. On peut écrire cette fonction en Ocaml de manière récursive :

# l e t r e c f a c t n =

i f  n<2  t h e n  1 e l s e n f a c t  ( n − 1 ) ; ; v a l f a c t : i n t>i n t = <fun >

# f a c t 5 ; ;

− : i n t = 120

Examinons le comportement de fact. Si n < 2, à savoir, si n = 1 ou n = 0, la fonction retourne le résultat 1, qui est le bon résultat aussi bien pour 0! que pour 1!. Si 2 la fonction calcule n  fact( 1). Cela revient à recommencer un nouvel appel à fact mais cette fois, pour un argument qui n’est plus ≥ × n mais−  ( 1). On pourrait résumer ce cas du calcul comme ceci : pour calculer fact(n) il suffit de calculer fact( 1) puis de −−multiplier   ce résultat par n. Comme le symbole fact apparaît dans la définition de la fonction, cette définition est récursive et nous devons utiliser le mot clé  rec. Déroulons un appel à  la fonction pour n = 5 :

  # f a c t ( 5 )  =   5  f a c t ( 4 )

  =   5  4  f a c t ( 3 )

  =   5  4  3  f a c t ( 2 )

  =   5  4  3  2  f a c t ( 1 )

Correction de fonctions récursives : Un programme est correcte s’il calcule ce que nous voulons qu’il calcule. Comment nous convaincre de la correction d’une fonction récursive ? Notre raisonnement doit se pencher sur les résultats de la fonction pour tous ses cas d’entreés possibles. Plus tard dans ce cours nous utiliserons des techniques mathématiques simples pour ce faire, telles que le raisonnement par récurrence. Nous en donnons un bref aperc¸u ici. Dans un raisonnement par récurrence nous procédons en deux temps. En premier nous devons montrer que la fonction se comporte correctement dans son cas le plus simple. Ensuite, nous devons monter que si la fonction est correcte pour un cas donné, alors elle aussi correcte pour le cas suivant. Pour la fonction fact plus haut cela donne :

–  fact(0), fact(1) sont les cas les plus simples. Dans ces deux cas n < 2 et la réponse est 1 qui est le résultat correct pour 0! et 1!. Donc fact(0) calcule bien 0! et fact(1) calcule 1!

–  Supposons que fact(n-1) donne la réponse correcte, à savoir (n − 1)!. Nous devons monter que le cas suivant fact(n) calcule n!. Comme n ≥ 2 (autrement nous serions dans les cas précédents), la réponse calculeé sera : n*fact(n-1). Comme nous avons supposé que fact(n-1)= (n − 1)!, il devient évident que fact(n) = n*fact(n-1) = ( 1)! = n! : la réponse correcte pour fact(n).

Nous reviendrons en détail sur ce genre de raisonnement plus tard dans ce cours.

4.2.1Fonctions récursives locales

L’itération en programmation impérative utilise l’affectation et les tests sur des variables modifiables afin de gérer les conditions d’arrêt. L’écriture récursive de l’itération nécessite parfois la définition de fonctions récursives prenant en paramètres supplémentaires les valeurs servant à  gérer ces conditions d’arrêt. Considérons l’exemple de la fonction palindrome qui doit tester si une chaîne de caractères passeé en paramètre est un palindrome. Un algorithme classique consiste à se munir de deux indices i, j initialiseés respectivement avec la première et la dernière position de la chaîne :

i  j =?

–  tant que i < j et que les caractères à ces indices sont égaux, on incrémente i, on décrémente j, et on continue ;

–  si les caractères sont différents, on arrête et on renvoie false ;

–  si  j cela signifie qu’on a comparés tous les caractères sans tomber sur des caractères différents : on peut terminer avec true.

Dans cet algorithme, ce sont les valeurs de i, j qui changent à  chaque itération, et qui déterminent la condition d’arrêt. Nous allons écrire cet algorithme récursivement à l’aide d’une fonction palinRec qui prend i, j en paramètres : elle testera les valeurs de i, j et au cas ou` l’on peut continuer, elle fera un nouvel appel récursif avec comme nouveaux paramètres i + 1 et 1. Cette fonction implante la boucle récursive. Elle est locale à la fonction palindrome que nous souhaitons écrire.

l e t p a l i n d r o m e s = l e t r e c p a l i n R e c ( i , j ) = i f ( i <j ) t h e n i f ( s . [ i ] = s . [ j ] ) t h e n  p a l i n R e c  ( ( i + 1 ) , ( j − 1 ))

e l s e f a l s e

e l s e t r ue

i n p a l i n R e c ( 0 , ( S t r i n g . l e n g t h s − 1 ) ) ; ;

  v a l  p a l i n d r o m e  :  s t r i n g  − bo ol  =  <fun >  

La fonction palindrome n’est pas récursive. Elle prend une chaîne s et se contente de faire un appel initial à sa fonction locale palinRec, qui elle est récursive, et qui implante l’itération de notre algorithme. Notez également que la fonction palinRec n’a pas besoin de prendre la chaîne s en argument : elle est visible en tant que paramètre de la fonction principale palindrome.

4.3Les fonctions comme paramètres Les fonctions peuvent recevoir en argument n’importe quelle valeur, y compris d’autres fonctions, puisque celles-ci sont des valeurs de première classe. Il s’agit d’un mécanisme fondamental de généralisation de programmes, au coeur de la programmation fonctionnelle.

Considérons l’exemple d’une fonction qui détermine, à  partir de deux notes passeés en argument, si un élève est rec¸u ou non ainsi que sa note finale. La fonction retourne une chaîne de caractères contenant ces deux résultats. Il y a deux paramètres à partir desquels le calcul peut s’articuler : le mode de calcul à appliquer aux deux notes (quel poids leur donner), et la note moyenne et maximale de référence afin de tester si l’élève est rec¸u (ex : 5 si la note maximale est 10, 10 si la note maximale est 20). Les arguments de cette fonction sont :

–  (n1,n2) : une paire de notes ;

–  modeCalcul : fonction à appliquer sur la paire des notes ;

–  (rMoy,rMax) : notes moyenne et maximale de référence servant à  déterminer si un élève est ou non rec¸u ;

l e t  r e s E l e v e  mode Calcul  ( rMoy , rMax )  ( n1 , n2 )= l e t n o t e F i n a l e = mode Calcul ( n1 , n2 ) i n l e t r e c u = i f ( n o t e F i n a l e >= rMoy ) t h e n ” Recu ” e l s e ” Non r e c u ” i n

l e t  n o t e  =  s t r i n g  o f  f l o a t ( n o t e F i n a l e )  i n l e t  max  = s t r i n go f fl o a t ( rMax )

i n r e c u ˆ ” avec ” ˆ n o t e ˆ ” / ” ˆmax ; ;

v a l r e s E l e v e : ( ’ a  ’ b −>f l o a t ) −>f l o a t  f l o a t> ’ a  ’ b −> s t r i n g = <fun >

Examinons maintenant les calculs effectués dans le corps de cette fonction. Plusieurs résultats intermédiaires sont stockés dans des variables locales (tous les let imbriqués) et un calcul final est effectué  (après le dernier in) et renvoyé par la fonction :

–  noteFinale: variable locale qui contient le résultat d’appliquer le mode de calcul (fonction modeCalcul) sur la paire des notes ;

–  recu: variable locale qui contient la chaîne ”Recu” ou ”Non recu” selon la valeur de noteFinale ;

–  note: variable locale avec la note finale transformeé en chaîne de caractères ;

–  max: variable locale avec la note maximale transformeé en chaîne de caractères ;

–  ligne  finale  :  c’est  le  résultat  renvoyé  par  la  fonction.  Il  s’agit  d’une  chaîne  qui  contient  tous  les résultats intermédiaires calculés.

Nous  pouvons  utiliser  cette  fonction  afin  de  calculer  le  message  à  composer  pour  un  élève  dont  on calcule la moyenne de deux notes avec 10/20 points de moyenne, ou encore pour un calcul sur la base d’une moyenne pondéreé avec 40% pour la première note, et 60% pour la deuxième, et une moyenne de référence à 45 sur 100 points.

# l e t moySimple ( x , y ) = ( x + . y ) / . 2 . 0 ; ; v a l moySimple : f l o a t  f l o a t>f l o a t = <fun >



# l e t moy Ponderee ( x , y ) = ( x  . 0 . 4 + . y  . 0 . 6 ) ; ; v a l moy Ponderee : f l o a t  f l o a t>f l o a t = <fun >

# l e t n o t e A n g l a i s = r e s E l e v e moySimple ( 1 0 . 0 , 2 0 . 0 ) ( 1 1 . 0 , 1 2 . 0 ) ; ;

v a l n o t e A n g l a i s : s t r i n g = ” Recu avec l a no t ede 1 1 . 5 / 2 0 . ”

# l e t note Math = r e s E l e v e moy Ponderee ( 4 5 . 0 , 1 0 0 . 0 ) ( 6 5 . 0 , 4 2 . 0 ) ; ; v a l note Math : s t r i n g = ” Recu avec l a n o te de 5 1 . 2 / 1 0 0 . ”

Type d’une fonction avec paramètres fonctionnels : Le type d’une fonction décrit les types de chacun de ses arguments. Dans le cas d’un argument fonctionnel, son type est celui d’une fonction et contient donc au moins une flèche. Afin de distinguer ce type fonctionnel des flèches et types des autres arguments éventuels de la fonction, le type d’un argument fonctionnel est entouré  de parenthèses. Par exemple le type de la fonction resEleve est :

resEleve : (’a*’b → float) → float*float → ’a*’b → string

ou

–  modeCalcul (type d’une fonction) : (’a*’b → float)

Cette fonction est appliqueé à  une paire (n1,n2), d’ou`  le type ’a*’b pour son argument. Son résultat est utilisé comme un float. En tant que type d’une fonction, ce type contient une flèche. Il est mis entre parenthèses pour ne pas confondre celle-ci avec celles correspondant aux autres paramètres de la fonction

–  (rMoy, rMax) : type d’une paire float*float

–  (n1,n2) : type d’une paire polymorphe ’a*’b

–  résultat de la fonction : string

4.4 Les fonctions avec résultat fonctionnel

Une fonction peut renvoyer des valeurs de n’importe quel type, y compris des valeurs fonctionnelles. Cela est possible si la fonction prend plusieurs arguments séparés, et qu’on ne lui applique qu’une partie de ses arguments. La fonction retourne alors une fonction qui ”attend” les arguments qu’on ne lui pas encore passé. Considérons par exemple la fonction resEleve vue plus haut et que nous rappelons ici :

l e t  r e s E l e v e  mode Calcul  ( rMoy , rMax )  ( n1 , n2 )= l e t n o t e F i n a l e = mode Calcul ( n1 , n2 ) i n l e t r e c u = i f ( n o t e F i n a l e >= rMoy ) t h e n ” Recu ” e l s e ” Non r e c u ” i n

l e t  n o t e  =  s t r i n g o f f l o a t ( n o t e F i n a l e )  i n l e t max = s t r i n g o f f l o at ( rMax )

i n r e c u ˆ ” avec ” ˆ n o t e ˆ ” / ” ˆmax ; ;

v a l r e s E l e v e : ( ’ a  ’ b −>f l o a t ) −>f l o a t  f l o a t> ’ a  ’ b −> s t r i n g = <fun >

Elle prend trois arguments. Si nous lui passons seulement son premier argument (le mode de calcul) nous obtenons une fonction qui attend ses deux autres arguments. La fonction est alors spécialisé pour un mode de calcul particulier (celui passé en paramètre), et attend une moyenne et note maximale de référence ainsi qu’une paire de notes sur qui s’appliquer.

# l e t res Moyenne Simple = r e s E l e v e moySimple ; ; v a l res Moyenne Simple : f l o a t  f l o a t>f l o a t  f l o a t> s t r i n g = <fun >

# res Moyenne Simple ( 1 0 . 0 , 2 0 . 0 ) ( 5 . 0 , 1 6 . 5 ) ; ;

− : s t r i n g = ” Recu avec 1 0 . 7 5 / 2 0 . ”

Ce mécanisme est connu sous le nom d’application partielle. Il permet de spécialiser des fonctions très génériques lorsque certains de ses paramètres sont connus, en attendant de les appliquer au reste de leurs donneés d’entreé.

4.5 Fonctions définies par cas ou par filtrage

Le filtrage est un mécanisme de reconnaissance de motifs syntaxiques que l’on peut appliquer sur une donneé structureé afin d’extraire quelques unes de ces composantes. C’est un mécanisme puissant et concis que nous utiliserons afin de définir des fonctions par cas sur la structure syntaxique de leurs arguments.

Motif :Patron syntaxique d’une valeur à reconstituer, composé de constantes et/ou d’identificateurs à lier. Quelques exemples de motifs :

Motif

il permet de reconnaître

2

constante 2

(0,x)

toute paire avec un 0 en 1ère composante

y

toute valeur

{cle=k; contenu=c}

enregistrement avec champs cle et contenu

{cle=7}

enregistrement avec au moins un champ cle égal à 7

  [0;    ]

liste avec 2 éléments dont le 1er est 0

Filtrage : Il s’agit de la recherche de correspondance entre une valeur et un motif ou patron pour cette valeur. Le filtrage réussit lorsqu’il y a correspondance entre la forme syntaxique du motif et celle de la valeur compareé. On dit alors que la valeur est filtreé (matched) par le motif. Si le motif contient des identificateurs, ceux-ci sont alors liés aux composantes auxquelles ils correspondent dans la valeur. Dès lors, ces identificateurs correspondent à  des composantes de la valeur compareé, que l’on pourra utiliser pour calculer la valeur rendue par l’expression de filtrage. Voici quelques exemples de filtrage :

Motif

Valeur compareé

Réussite

Liaisons

1

1

oui

aucune

x

1

oui

x=1

(0,x,y)

(0,1,6)

oui

x=1, y=6

{cle=k; contenu=c}

{cle=5; contenu="abc"}

oui

k=5, c=”abc”

0

1

échec

(1,x)

(1,2,3)

échec

( ,x, )

(0,1,6)

oui

x=1

Il existe plusieurs manières de définir des fonctions par filtrage en Ocaml. Nous utiliserons les définitions à base de l’expression match with

match e xp r

wi t h  m o t i f  1  − a 1 | m o t i f  2  − a 2 |   . . . .

  |   −> t o u s a u t r e s c a s

Cette expression compare la valeur correspondant à expr successivement à chacun des motifs dans l’ordre de leur définition. Si motifi est le premier à réussir, alors le résultat de l’expression est ai, sinon, soit il y a un cas qui filtre tout  , et le résultat est l’expression qui l’accompagne, soit, si aucun motif ne filtre expr alors le résultat de la reconnaissance est un échec. Voici l’exemple de la fonction qui additionne une paire d’entiers :

#  l e t  somme  x y  = match ( x , y ) wi t h ( 0 , n ) −> n

  |   ( n , 0 ) −> n

| ( a , b ) −> a+b ; ; v a l somme : i n t>i n t>i n t = < fun >

# somme 3 0 ; ; − : i n t = 3

# somme 2 4 ; ;

− :  i n t  = 6    

Examinons le comportement de l’appel somme 3 0

– on exécute (match(3,0) with ) qui compare (3,0) avec chacun des motifs de la fonction :

1.  motif 1 : (0,n) comparé à (3,0)  échec,

2.  motif 2 : (n,0) comparé à (3,0)  réussit et on obtient la liaison   n=3  on exécute la partie à droite de ce motif  le résultat renvoyé est  3

Un filtrage est incomplet  si tous les cas possibles d’une valeur ne sont pas répertoriés. Dans ce cas, un message d’avertissement est indiqué à la compilation.

let est_null x = match x with   0 -> true

  |   1 -> false

Warning P: this pattern-matching is not exhaustive. Here is an example of a value that is not matched:

2

val est_null : int -> bool =

# est_null 1;;

: bool = false

# est_null 3;;

Exception: Match_failure ("", 2, 2).

Pour compléter ce filtrage :

let est_null x = match x with   0 -> true

  |   _ -> false

val est_null : int -> bool =

Pour finir, deux fonctions écrites par filtrage sur un arugment de type enregistrements. Ce fonctions testent si si un client est débiteur ou créditeur. Notez qu’il n’est pas nécessaire de faire apparaître tous les champs du type lors d’un filtrage. La deuxième écriture est donc plus compacte.

t y p e c l i e n t = { numero : i n t ; nom : s t r i n g ; s o l d e : f l o a t ; }

#  l e t  c r e d i t e u r  { numero=  ; nom= ; s o l d e = s }=  s > 0 . 0 ; ; v a l c r e d i t e u r : c l i e n t −> bo o l = <fun >

# l e t  d e b i t e u r  { s o l d e  =  s } =  s 0 . 0 ; ; v a l d e b i t e u r : c l i e n t −> bo o l = <fun >

4.6 Fonctions anonymes

Une fonction anonyme est une valeur fonctionnelle que l’on définit à la voleé sans lui donner de nom, et donc sans passer par une déclaration. Par exemple, la fonction suivante permet de calculer la moyenne d’une paire d’arguments de type float :

# fun ( x , y ) −> ( x + . y ) / . 2 . 0 ; ;

− : f l o a t  f l o a t>f l o a t = <fun >

# ( fun ( x , y ) −> ( x + . y ) / . 2 . 0 ) ( 3 . 5 , 8 . 5 ) ; ; − : f l o a t = 6 .

Ce genre de fonction est utile afin de construire des valeurs fonctionnelles (à passer en paramètre p.e.), mais dont il n’est pas nécessaire de garder une trace dans l’environnement. Par exemple, nous pouvons définir la fonction resMoyenneSimple que nous rappelons ici :

# l e t moySimple ( x , y ) = ( x + . y ) / . 2 . 0 ; ;

# l e t res Moyenne Simple = r e s E l e v e moySimple ; ;

par une définition qui ne déclare pas la fonction moyenneSimple mais qui la construit de manière anonyme.

# l e t res Moyenne Simple = r e s E l e v e ( fun ( x , y ) −> ( x + . y ) / . 2 . 0 ) ; ; v a l res Moyenne Simple : f l o a t  f l o a t>f l o a t  f l o a t> s t r i n g = <fun >

5 Programmes et expressions

Nous donnons ici la syntaxe des expressions et des phrases en Ocaml.

Programmes : Tout ou presque est expression dans un programme Ocaml. Ainsi, un programme est une suite de phrases (déclarations) et d’expressions. La plupart du temps ces dernières sont des appels de fonctions. Voici un exemple de programme :

#  l e t  b a g u e t t e  =  4 . 2 0 ; ; ( ∗ d e c l a r a t i o n  v a l e u r ∗ ) v a l b a g u e t t e : f l o a t =  4 . 2

#  l e t  eu ro x  = x  / . 6 . 5 5 9 5 7 ; ; (  d e c l a r a t i o n  f o n c t i o n  ) v a l e ur o : f l o a t>f l o a t = <fun >

  # eu ro  b a g u e t t e ; ;   (  e x p r e s s i o n )

− : f l o a t = 0 . 640285872397123645

Syntaxe des phrases :

définition de valeur

let x = e définition

de fonction

let f x1 xn = e

définition de fonctions

let [ rec ] f1 x1 = e1 (

mutuellement récursives)

[ and fn xn = en ]  définition

de type(s)

type q1 = t1 [and qn = tn ]

expression

e

Syntaxe des expressions :

définition locale let x = e1 in e2 fonction anonyme fun x1 xn -> e appel de fonction f e1 en

variable

x

(M.x si x est défini dans le module M)

valeur construite

(e1, e2)

(dont les constantes)

1, ’c’, ”aa”

analyse par cas

match e with p1 -> e1 | pn -> en boucle

for

for i = e0 to ef do e done

boucle while

while e0 do e done

conditionnelle

if e1 then e2 else e3 une

séquence

e ; e ’

parenthèses

(e) begin e end

Expression conditionnelle La construction if then else permet d’exprimer l’alternative. Il s’agit d’une expression dont le résultat est celui de l’expression de l’une de ses deux branches.

# if 3>5 then "trois superieur a cinq" else "trois inferieur a cinq";;

: string = "trois inferieur a cinq"

Pour que le typage soit correcte, les expressions dans chacune des branches doivent avoir le même type.

if 3>5 then "trois superieur a cinq" else 5;; Characters 43-44: This expression has type int but is here used with type string

6 La généricité ou polymorphisme paramétrique

La généricité permet de rendre génériques les types de certaines fonctions ou de certaines structures des donneés. Avec un typage générique, ces fonctions ou structures deviennent utilisables sur des donneés de n’importe quel type tout en étant soumises aux contraintes de type décrites par ailleurs par leur typage. Un exemple classique est donneé par la fonction premier permettant d’extraire la première composante d’une paire.

l e t p r e m i e r ( x , y ) = x

Idéalement, cette fonction devrait pouvoir s’appliquer sur n’importe quelle paire de valeurs, et renvoyer en résultat sa première composante :

premier(1, true) ⇒ 1 premier("abc", ’s’) ⇒

"abc" premier(2.4, 0) ⇒ 2.4

Mais quel type lui donner ? Un typage trop spécifique aurait pour effet de contraindre la fonction à un seul type de paires. Un type trop laxiste (par exemple Object en Java) aboutirait à un manque de précision du B sont A vdesec  lapa graménéèricitresde, on types peut,  àtyper savoi cr,ette des fonction types inconnuspour toutes au moment les types de de la pairfinitiones de type de laA ∗fonction,   B ou` A mais qui seront à préciser ou instancier plus tard. Nous avons déjà vu en 1.2 que ce mécanisme est présent en C++ et en Java. En Ocaml, la fonction premier est typeé par :

#  l e t  p r e m i e r  ( x , y )  =  x ; ; v a l p r e m i e r : ’ a ∗ ’ b −> ’ a

# p r e m i e r ( 1 , t r u e ) ; ; − : i n t = 1

# p r e m i e r ( ” abc ” , ’ s ’ ) ; ; − : s t r i n g = ” abc ”

Le type donné à premier contient deux variables de type noteés ’a et ’b. En Ocaml, la généricité est un mécanisme de typage utilisé par défaut lors de l’inférence de types. Ainsi, toute expression est typeé avec le type le plus générique possible qui est compatible avec sa définition, et au cas ou` cela est nécessaire, des paramètres de types sont introduits dans son typage. La généricité est connue également sous le nom de polymorphisme paramétrique. Une fonction est polymorphe si elle possède plusieurs types. Le polymorphisme est paramétrique lorsque les types font intervenir des paramètres de types.

Le type ’a * ’b -> ’a donné  à  premier n’est pas simplement très générique. Il est également précis : il indique qu’il existe un lien entre le types de la première composante de son paramètre et son résultat. Par exemple, si la fonction est appliqueé sur une paire de type int*bool, son résultat sera de type int. Ceci permet au typeur de trouver des erreurs de typage quand ces contraintes ne sont pas respecteés :

#  l e t  x  =  p r e m i e r  ( 1 ,  t ru e )  +  p r e m i e r ( 2 , ” ab ” ) ; ;

v a l x : i n t = 3

# l e t y = p r e m i e r ( 1 , t ru e ) +  p r e m i e r ( ” ab ” , 2 ) ; ; E r r o r :  T h i s  e x p r e s s i o n  has  t y p e  s t r i n g  b u t  an e x p r e s s i o n  was  e x p e c t e d  of  t y p e i n t

Voici pour finir quelques exemples de primitives polymorphes en Ocaml :

# fst;;

-  : ’a * ’b -> ’a =

# snd;;

-  : ’a * ’b -> ’b =

# (=);;

-  : ’a -> ’a -> bool =

# (>);;

-  : ’a -> ’a -> bool =

6.1 Structures des donneés polymorphes

En Ocaml il est possible de déclarer des types correspondant à des structures des donneés polymorphes paramétriques. Les donneés stockeés pourront alors être de n’importe quel type, à  condition bien sûr de respecter les contraintes trouveés par le typage. Dans une telle déclaration – on déclare le paramètre de type devant le nom du type à déclarer ; – ce paramètre doit apparaître dans le corps de la déclaration.

Considérons l’exemple des cellules avec une clé entière, et deux champs de contenu, un pour le contenu courant, un autre pour celui du mois précédent. En Java 1.5 on pourra écrire le type class Cellule

c l a s s C e l l u l e <A> { i n t c l e ; A c o n t e n u ; A mois Prec };

En Ocaml, on déclare le type ’a cellule :

t y p e ’ a c e l l u l e = { c l e : i n t ; c o n t e n u : ’ a ; mois Prec : ’ a } ; ;

Lors du stockage des donneés de ce type, le typeur infère l’instantiation des paramètres de type qui convient à chaque cas : ’a int›→ pour  c1 ; ’a string pour›→  c2 ; une erreur de typage pour c3 (car ’a ne peut pas être instancié à la fois en int et string) :  



# l e t c1 = { c l e = 1 ; c o n t e n u = 3 ; mois Prec = 7 } ; ; v a l c1 : i n t c e l l u l e = { c l e = 1 ; c o n t e n u = 3 ; mois Prec = 7}

# l e t c2 = { c l e = 2 ; c o n t e n u  = ” P a r i s ” ; mois Prec = ” Lyon ” } ; ; v a l c2 : s t r i n g c e l l u l e = { c l e = 2 ; c o n t e n u  = ” P a r i s ” ; mois Prec =” Lyon ” }

  #  l e t  c3  = { c l e = 1 7 ; c o n t e n u = 3 ; mois Prec = ” Lyon ” ; ;   }

E r r o r :  T h i s  e x p r e s s i o n  has  t y p e  s t r i n g  b u t  an  e x p r e s s i o n  was e x p e c t e d  of  t y p e i n t

Une fonction qui prend un argument de type ’a cellule pourra les cas échéant, déduire une instantiation de la variable de type ’a :

#  l e t  sommeContenus  c  =  c . c o n t e n u  +  c . mois Prec ; ; v a l sommeContenus : i n t c e l l u l e −>i n t = <fun >

# l e t donne Mois Prec c = c . mois Prec ; ; v a l donne Mois Prec : ’ a c e l l u l e −> ’ a = <fun >

Le type de la fonction sommeContenus est contraint aux arguments de type int cellule, alors que donneMoisPrec reste polymorphe.

6.2 L’inférence de types

Nous  finissons  cette  partie  avec  un  exemple  d’inférence  de  type  monomorphe.  Cet  exemple  permet d’illustrer la différence entre fonctions polymorphes et monomorphes : elle tient aux contraintes de type que les opérateurs ou expressions dans la définition de la fonction imposent afin d’obtenir un typage correct. Considérons la fonction :

l e t f x = x+1

Sachant que + est un opérateur définit uniquement sur les entiers, et dont le type est + : int ∗int    → int, le typeur déduit les contraintes suivantes : – le type de f est de la forme : f : txtcorps

ou` tx est le type de x (argument de la fonction), et tcorps est le type du corps.

–  pour que x+1 soit bien typé, xdoit    être de type int    tx= int

–  si ces contraintes sont respecteés, alors le résultat de l’opération x + 1 est de type int,   tcorps = int .

Conclusion : f est de type int → int Le typeur infère des types polymorphes en absence de telles contraintes.

7 Les types liste : un type inductif prédéfini

En Ocaml, une liste est une séquence de valeurs de même type, ce type pouvant être quelconque. Il s’agit donc d’un type polymorphe, prédéfini, et dont le nom est ’a list. Selon les éléments stockeés, une liste pourra être de type int list, string list, etc. Voici quelques éléments de syntaxe :

–  [] : la liste vide. Son type est ’a list

–  @ : opérateur de concaténation.

–  [a; b; c] :  liste  formeé  de  trois  éléments  a,b,c.  Les  éléments  de  la  liste  sont  séparés  par  des points-virgules. Cette notation est utiliseé pour les listes donneés en extension (on donne tous leurs éléments) ;

–  a::l liste formeé d’un premier élément a suivi d’une liste l. Cette notation est employeé dans les fonctions sur les listes écrites par filtrage.

Quelques exemples :

# [1;2;3];;

-  : int list = [1; 2; 3]

# ["a";"bc"] @ ["bonjour"];;

-  : string list = ["a"; "bc"; "bonjour"]

# [];;

-  : ’a list = []

# [1]@[];;

-  : int list = [1]

# ["ab";"cd"]@[];;

-  : string list = ["ab"; "cd"]

Liste de paires et liste de listes :

# [(1,’a’); (23, ’c’)];;

-  : (int * char) list = [(1, ’a’); (23, ’c’)]

# [[1;2];[3]];;

-  : int list list = [[1; 2]; [3]]

7.1 Construction de listes

Le type liste en Ocaml correspond à une structure des donneés récursive. En effet, toute liste est :

–  [], soit vide,

–  a::l,  soit formeé d’un élément a, suivi d’une liste l

Le symbole :: est le constructeur des listes. Il s’agit d’une sorte d’opérateur qui prend deux arguments a et l afin de construire une liste par la notation a :: l, ou`

–  a (de type T) est le premier élément de la liste à construire a::l ;

–  l (de type T list) est une liste est la suite de la liste à construire a::l ;

Ainsi, la construction a::l fabrique une nouvelle liste, de type T list, dont le premier élément est a et qui est suivie par tous les éléments dans l. Toutes les listes non vides en Ocaml sont construites à  l’aide de cet opérateur (les autres notations étant du sucre syntaxique). Il doit être appliqué de manière emboîteé, autant de fois que d’éléments on veut inclure dans la liste. Cet emboîtement se termine toujours par une liste vide. Par exemple :

# 1 : : [ ] ; ;

− : i n t l i s t = [ 1 ]

# 1 : : [ 3 ; 5 ] ; ;

− : i n t l i s t = [ 1 ; 3 ; 5 ]

# 1 : : ( 2 : : ( 3 : : [ ] ) ) ; ;

  −  :  i n t  l i s t  =  [ 1 ;  2 ;  3 ]    

7.2 Fonctions sur les listes

Elles sont souvent définies par filtrage sur les deux cas structurellement possibles d’une liste : (a) la liste vide [] ;

(b) la liste non vide a::l, ou` a est son premier élément et l la liste qui le suit.

Par exemple, voici la fonction premier qui extrait le premier élément d’une liste, compare sa liste argument avec ces deux cas possibles :

# l e t p r e m i e r l = match l

  wi t h  [ ]   −> f a i l w i t h ” p r e m i e r ”

|   e : : r e s t e −> e ; ; v a l p r e m i e r : ’ a l i s t −> ’ a = <fun >

# p r e m i e r [ 3 ; 4 ] ; ;

− : i n t = 3

# p r e m i e r [ ’ a ’ ; ’ g ’ ] ; ; − : char = ’ a ’

# p r e m i e r [ ] ; ;

E x c e p t i o n : F a i l u r e ” p r e m i e r ” .

La  construction  prédéfinie  failwith,  lève  l’exception  Failure suivie  du  nom  de  la  fonction  qui  a échoué. Cela arrête l’ exécution du programme dans les cas ou`  la fonction n’est pas définie. La fonction premier est dans la bibliothèque (module) List sous le nom .

Examinons maintenant le comportement de l’appel (premier [3;4;5]) :

1.  [3;4;5] est comparé au premier motif []  échec

2.  [3;4;5] est comparé au motif e::reste  réussite avec les liaisons e=3, reste=[4;5] le résultat renvoyé est e  3

La fonction qui teste si une liste est vide :

# l e t v i d e l = match l

  wi t h  [ ]   −>t ru e

  |     −>f a l s e ; ;

v a l v i d e : ’ a l i s t −> bo o l = <fun >

# v i d e [ 1 ; 2 ] ; ;

− : b oo l = f a l s e

# v i d e [ ] ; ;

− : b oo l = t r u e

Voici maintenant quelques fonctions récursives sur les listes : longueur calcule la longueur d’une liste ; appartient teste si un élément appartient à une liste.

# l e t r e c l o n g u e u r l = match l

wi t h [ ] −> 0

|   : : r e s t e  − 1  +   l o n g u e u r r e s t e ; ; v a l l o n g u e u r : ’ a l i s t −> i n t = <fun >

#  l o n g u e u r  [ ] ; ;

− :  i n t  =  0

# l o n g u e u r [ ” a ” ; ” s a l u t ” ] ; ;

− : i n t = 2

# l e t r e c a p p a r t i e n t e l = match l

wi t h [ ] −> f a l s e

|   a : : r e s t e −> e= a | | a p p a r t i e n t e r e s t e ; ; v a l a p p a r t i e n t : ’ a −> ’ a l i s t −> bo o l = <fun > # a p p a r t i e n t 1 [ 5 ; 6 ; 3 ] ; ; − : b oo l = f a l s e

# a p p a r t i e n t 1 [ 5 ; 3 ; 1 ; 6 ] ; ;

  − :  b oo l  =  t r u e    

Ces fonctions se nomment List.length et dans la librairie. La fonction longueur se comporte de la manière suivante :

–  elle accumule 1 dans la somme du nombre d’éléments pour chaque élément rencontré  en début de liste ;

–  et recommence par un appel récursif sur le reste de la liste ; – renvoie 0 si la liste est vide.

Voici le déroulement de l’appel longueur [1;5;2].

 longueur 1::[5;2]  1 + (longueur [5;2])

 1 + (longueur 5::[2])

 1 + 1 + (longueur [2])

 1 + 1 + (longueur 2::[])

 1 + 1 + 1 + longueur []

 1 + 1 + 1 + 0

 3  

Voici la fonction qui à partir d’une liste l et d’un élément e construit une nouvelle liste ou` la première occurrence de e est remplacé par un élément x.

# l e t r e c r e m p l a c e e x l = match l

wi t h [ ] −> [ ]

| a : : r e s t e  −i f  e= a  t h e n  x : : r e s t e  e l s e  a : : ( r e m p l a c e  e  x  r e s t e ) v a l r e m p l a c e : ’ a −> ’ a −> ’ a l i s t −> ’ a l i s t = <fun >

# r e m p l a c e ’ a ’ ’ b ’ [ ’ e ’ ; ’ 2 ’ ; ’ a ’ ; ’ ? ’ ] ; ; − : char l i s t = [ ’ e ’ ; ’ 2 ’ ; ’ b ’ ; ’ ? ’ ]

# r e m p l a c e 1 6 [ 2 ; 3 ; 4 ] ; ;

  −  :  i n t  l i s t  =  [ 2 ;  3 ;  4 ]    

La fonction remplace construit une nouvelle liste à l’aide du constructeur :: en recopiant tous les éléments de sa liste argument, sauf la première occurrence de e qui est changeé en x.

remplace ’a’ ’b’ [’e’; ’2’; ’a’; ’?’;’h’]  ’e’::(remplace ’a’ ’b’ [’2’; ’a’; ’?’;’h’]) 

’e’::(’2’::(remplace ’a’ ’b’ [’a’; ’?’;’h’])) 

’e’::(’2’::(’b’::[’?’;’h’])) 

[’e’;’2’;’b’;’?’;’h’]

7.3 Le module List de la librairie

Il existe des nombreuses fonctions dans la librairie Ocaml. Elles sont organiseés en modules, et sont accessibles avec la notation pointeé. Les des utilitaires sur les listes sont contenus dans le module List. Par exemple, pour utiliser la fonction length qui calcule la longueur d’une liste, on écrira :

# L i s t . l e n g t h [ ” ab ” ; ” b o n j o u r ” ] ; ; − : i n t = 2

Pour finir, voici quelques fonctions du module List :

–  val length : ’a list -> int Renvoie la longueur (nombre d’éléments) d’une liste donneé.

–  val hd : ’a list -> ’a Renvoie le premier élément d’une liste donneé. Lève l’exception Failure "hd" si la liste est vide.

–  val tl : ’a list -> ’a list Renvoie une liste donneé sans son premier élément. Lève l’exception Failure "tl" si la liste est vide.

–  val nth : ’a list -> int -> ’a Renvoie le n-ième élément d’une liste donneé. Le premier élément est à la position 0. – val rev : ’a list -> ’a list Inversion d’une liste donneé.

7.4 Les fonctionnelles sur les listes

Une fonctionnelle est une fonction qui prend des fonctions en argument. Dans le module List il existe un bon nombre de fonctionnelles fort utiles sur les listes. Par exemple, la fonctionnelle map, prend en argument une fonction f et une liste l, et construit une nouvelle liste, résultat d’appliquer f à  chaque argument de la liste d’entreé l :

map f [a1; a2; . . . an]  [(fa1); (fa2); . . . (fan)]

La fonctionnelle map fait partie du module List. Pour l’utiliser nous pouvons écrire :

# l e t su cc x = x + 1 ; ;

# L i s t . map su c c [ 1 ; 2 ; 3 ] ; ; − : i n t l i s t = [ 2 ; 3 ; 4 ]

Voici une utilisation de map afin d’extraire les numéros de vol d’une liste de vols :

 t y p e v o l = { d e s t : s t r i n g ; num : i n t ; p r i x : f l o a t ; d i s p : i n t } ; ;

l e t  c c s  =  { d e s t =” C a r a c a s ” ;  num= 221 ;  p r i x = 8 0 0 . 0 ;  d i s p = 1 0 }; ; l e t mxc = { d e s t =” Mexico ” ; num= 121 ;  p r i x = 9 0 0 . 0 ; d i s p = 6 } ; ; l e t  mx1  =  { d e s t =” Mexico ” ;  num= 654 ;  p r i x = 7 5 0 . 0 ;  d i s p = 1 0 }; ; l e t mx2 = { d e s t =” Mexico ” ; num= 680 ; p r i x = 7 5 0 . 0 ; d i s p = 5 } ; ; l e t ny = { d e s t =”New York ” ; num= 110 ; p r i x = 4 0 0 . 0 ; d i s p = 5 6 }; ; l e t  l v o l s  =  [ c c s ;  mxc ; mx1 ; mx2 ;  ny ] ; ;

# l e t donneNumVol v = v . num ; ; v a l donneNumVol : v o l −>i n t = <fun > #  l e t  l i s t e N u m V o l s  l  =  L i s t . map  donneNumVol  l ; ; v a l l i s t e N u m V o l s : v o l l i s t −>i n t l i s t = <fun >

#  l i s t e N u m V o l s   l v o l s ; ;

− : i n t l i s t = [ 2 2 1 ; 1 21 ; 6 54 ; 6 80 ; 110 ]

Une implantation possible de map est donneé par :

# l e t r e c map f  l  = match l

  wi t h  [ ]   −> [ ]

|   a : : r e s t e −> ( f a ) : : ( map f r e s t e ) ; ; v a l map : ( ’ a −> ’ b ) −> ’ a l i s t −> ’ b l i s t = <fun >

Dans le type de cette fonction nous avons :

–  (’a -> ’b) : fonction à  appliquer sur chaque élément de la liste, de type ’a, pour obtenir un résultat de type ’b

–  ’a list : type de la liste donneé en entreé

–  ’b list : type de la liste renvoyeé en résultat

Une autre fonctionnelle très utile est filter. Elle prend en argument une fonction booleénne test et une liste l, et construit une nouvelle liste composeé de tous les éléments de l qui rendent vrai le test :

filter test [a1; a2; . . . an]  [ai | test(ai) = true]

L’utilisation ci-dessous permet d’extraire les nombres pairs d’une liste d’entiers :

# let est_pair x = x mod 2 = 0;; val est_pair : int -> bool =

# filter est_pair [1;2;5;6;80];; : int list = [2; 6; 80]  

Voici une implantation possible de filter :

# l e t r e c f i l t e r cond  l  = match l

  wi t h [ ]   − > [ ]

|   a : : r e s t e − >i f ( cond a ) t h e n a : : ( f i l t e r cond r e s t e ) e l s e   f i l t e r cond r e s t e ; ;

v a l f i l t e r : ( ’ a −> bo o l ) −> ’ a l i s t −> ’ a l i s t = <fun >

Nous utilisons filter pour extraire la liste de vols d’une destination donneé. La fonction filtreDest prend une chaîne d et une liste de vols lv et extrait de la liste tous les vols dont la destination est égale à d. Elle s’écrit tout simplement par un appel à filter ou` la fonction de test passeé consiste à vérifier que le champs destination d’un vol est égal à une chaîne donneé :

#  l e t  f i l t r e D e s t  d  l v  =  f i l t e r  ( fun  v  − v . d e s t  =  d )  l v ; ; v a l f i l t r e D e s t : s t r i n g −> v o l l i s t −> v o l l i s t = <fun >

# f i l t r e D e s t ” Mexico ” l i s t e v o l s ; ;

− : v o l l i s t =

[{ d e s t  =  ” Mexico ” ;  num  =  12 1 ;  p r i x  =  9 0 0 . ;  d i s p o  =  6 };

{ d e s t  =  ” Mexico ” ;  num  =  68 0 ;  p r i x  =  7 5 0 . ;  d i s p o  =  5 };

    { d e s t  =  ” Mexico ” ;  num  =  65 4 ;  p r i x  =  7 5 0 . ;  d i s p o  =  10 }]    

Pour finir, voici quelques fonctionnelles du module List (extraits du manuel) :

–  map: (’a -> ’b) -> ’a list -> ’b list

–  for all : (’a -> bool) -> ’a list -> bool Teste si une condition est vrai pour tous les éléments de la liste.

–  exists: (’a -> bool) -> ’a list -> bool Teste si une condition est vrai pour au moins pour un élément dans la liste.

–  mem: ’a -> ’a list -> bool Equivalent de la fonction appartient.

–  filter: (’a -> bool) -> ’a list -> ’a list

–  find: (’a -> bool) -> ’a list -> ’a find p l renvoie le premier élément qui satisfait la condition p et lève une exception s’il n’est pas trouvé.

–  partition:(’a->bool)->’a list->’a list* ’a list partition p l renvoie une paire de listes (l1, l2), ou` l1 contient les élément qui satisfont p, et l2 ceux qui ne la satisfont pas.


100