LICENCE SCIENCES & TECHNOLOGIES 1 année … · ALGORITHMIQUE ET PROGRAMMATION FONCTIONNELLE Introduction ousV connaisssez le langage C , pourquoi apprendre un nouveau langage?

Université

Joseph

Fourier

UFR IMAG

Département

Licence Sciences

et Technologie

LICENCE SCIENCES & TECHNOLOGIES

1re année

INF121

ALGORITHMIQUE ET PROGRAMMATION FONCTIONNELLE

Introduction

Vous connaisssez le langage C, pourquoi apprendre un nouveau langage ? Ce n'est pas le

langage ocaml en lui-même qui est intéressant mais le modèle de programmation qui lui correspond :

la programmation fonctionnelle. Ce modèle de programmation induit une nouvelle façon de décomposer

et de résoudre un problème.

Pour un informaticien il est important de connaître plusieurs modèles de programmation pour choisir

celui qui est le plus adapté au problème qu'il doit résoudre, c'est-à-dire celui qui donnera le programme

le plus simple, le plus élégant avec le moins d'e�ort et de risque d'erreur.

Il n'y a pas de langage meilleur qu'un autre, ils sont tous aussi puissants : on sait que tout ce qu'on

peut faire dans l'un peut être fait dans l'autre. Mais la solution s'exprime peut-être plus simplement

dans l'un que dans l'autre. Par exemple,

� s'il s'agit de programmer une carte vidéo et de manipuler des tableaux ; C sera bien adapté.

� s'il s'agit de programmer des algorithmes qui ne travaillent pas sur des tableaux mais sur des struc-

tures récursives ; ce sera plus simple en ocaml.

� pour d'autes types de problèmes qui nécessitent de résoudre des contraintes ; le modèle de program-

mation logique par contrainte sera plus approprié.

Ce ne sont que quelques exemples parmi la dizaine de modèles de programmation connus à ce jour.

La programmation fonctionnelle en ocaml est-elle di�érente de la programmation im-

pérative en C ? Le langage C est un représentant parmi d'autres (Java,Pascal,...) des langages dits

impératifs. Ils sont nommés ainsi pour indiquer que la programmation impérative consiste à donner des

ordres à la machine, par exemple :

x=3 : met la valeur 3 en mémoire dans la variable x !

for(i=0 ; i<5 ; i=i+1){...} : répète 5 fois . . . !

Le langage ocaml fait partie des langages dits foncionnels, nommés ainsi pour indiquer que la pro-

grammation fonctionnel consiste à dé�nir des fonctions.

Dans les langages fonctionnels, l'a�ectation et les itérations (for,while) n'existent pas. Les seuls points

communs avec les langages impératifs sont le branchement conditionnel if...then...else... et la

dé�nition de fonctions. Les langages fonctionnels sont issues de la collaboration entre mathématiciens

et informaticiens :

� ils ont la rigueur des mathématiques ;

� ils reposent sur peu de concepts (type,fonction,récursivité) mais très puissants ;

� ils sont aussi expressifs que les autres langages ;

� ils insistent sur la dé�nition de types et la véri�cation de type permet d'éviter de très nombreuses

erreurs de programmation ;

� ils apprennent à programmer en ré�echissant mathématiquement au problème.

� ils résolvent élégamment certains problèmes compliqués.

Types, expressions, fonctions

et constructions du langage ocaml

2

Table des matières

1 Les types de base 5

1.1 Les booléens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Les nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Les caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Les types séquences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Le type Texte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5.1 Opérations sur les données de type Texte . . . . . . . . . . . . . . . . . . . . . . 9

1.5.2 Généralisation des opérations sur les textes . . . . . . . . . . . . . . . . . . . . 11

1.6 Le type Chaîne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.7 Opérations de conversion entre Texte et Chaîne . . . . . . . . . . . . . . . . . . . . . . 12

1.8 Opérateurs de comparaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Dé�nition de types complexes 15

2.1 Dé�nir et nommer un type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Dé�nir un type par énumération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Construire un produit de types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4 Construire une somme de types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Constructions du langage Ocaml 23

3.1 Expression conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Nommage d'une expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3 Expression de �ltrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4 Expression de �ltrage avec condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5 Filtrage avec condition versus conditionnelles imbriquées . . . . . . . . . . . . . . . . . 27

4 Dé�nition de fonctions 29

4.1 La spéci�cation : un contrat entre l'utilisateur et le programmeur . . . . . . . . . . . . 30

4.2 Le programmeur est aussi l'utilisateur de ses propres fonctions . . . . . . . . . . . . . . 31

4.3 Dé�nition de fonctions partielles = fonctions avec condition . . . . . . . . . . . . . . . 32

4.4 Respectez la spéci�cation laisse malgré tout de la liberté . . . . . . . . . . . . . . . . . 33

3

4

Chapitre 1

Les types de base

définition (Type d'une expression) Les ordinateurs n'apprécient pas les ambiguités. Ils font la

distinction entre l'entier naturel 1 et le réel 0.99999.... En mathématique les deux versions sont égales,

tandis que pour un ordinateur, ces données sont de nature di�érente1, on dit qu'elles sont de type

di�érent.

Notation Toutes les expressions manipulées en informatique sont typées et on utlise la notation � e : T�pour indiquer que l'expression e est de type T.

Remarque Un type en informatique correspond à un ensemble de valeurs en mathématiques. Les ma-thématiciens et les informaticiens utilisent un vocabulaire et des notations di�érentes mais équivalentes. Onpeut donc indi�éremment parler de types ou d'ensembles.

mathématique informatique

e ∈ T se lit e : T se lit

la valeur de e appartient à l'ensemble T la valeur de l'expression e est de type T

Exemples

5 ∈ Z 5 : int

2× n ∈ Z 2 * n : int


Bool bool

Z int

R float

Car char

Chaîne string

Les types de base sont limités mais il est possible de dé�nir de nouveaux types. On peut alors donner

très précisement le type d'une fonction comme on le fait en mathématique.

L'objectif de ce chapitre est de présenter les moyens de construire des types.

1L'ordinateur n'utilise pas les mêmes quantités de mémoires pour stocker un entier ou un réel.

5

1.1 Les booléens

Les booléens vrai et faux qui appartiennent à l'ensemble mathématique Bool sont notées true et false

en ocaml et sont de type bool.

Opérations Ocaml dé�nies sur les booléens

français mathématique informatique type Ocaml des opérateurs

a et b a ∧ b a && b bool → bool → bool

a ou b a ∨ b a || b bool → bool → bool

non a ¬a not a bool → bool

égalité b1 = b2 (b1 = b2) bool → bool → bool

di�érence b1 6= b2 (b1 <> b2) bool → bool → bool

Exercice 1.1 Construire les tables de vérités des opérateurs et , ou , non . Véri�ez vos tables devérité en tp en tapant les expressions dans l'interpréteur Ocaml.

1.2 Les nombres

En Ocaml, les entiers relatifs (Z) sont notés int. Contrairement à Z qui est in�ni, int est un ensemble

�ni : il contient uniquement les entiers représentables sur 32 ou 64 bits selon les processeurs. La taille

des entiers int est donc limitée par les capacités du processeur.

En Ocaml, les réels (R) sont notés float. Une donnée de type float a une taille et une précision

limitée par la capacité du processeur.

Pour raisonner nous utiliserons les ensembles mathématiques suivants :

DÉFINITION MATHÉMATIQUE D'ENSEMBLES

déf N = Z+

déf N∗ = N \ {0}

déf Z∗ = Z \ {0}

déf R∗ = R \ {0}

déf R+ = {r | r ∈ . . . ∧ r > 0}

déf R− = {r | . . . . . . . . . . . ∧ . . . . . . . . . .}

et aussi

déf 2N = {2k | . . ∈ N} les entiers naturels . . . . . . . . . .

déf 2N+ 1 = { . . . . . . . . . . . . | . . . . . . . . . . . } les entiers naturels impairs

6

Opérations Ocaml dé�nies sur les entiers et les réels

français mathématique informatique type Ocaml des opérateurs

addition a + b a + b int → int → int

a +. b float → float → float

soustraction a− b a - b int → int → int

a -. b float → float → float

multiplication a× b a * b int → int → int

a *. b float → float → float

division réelle ab a /. b float → float → float

division entière a÷ b a / b int → int → int

modulo a mod b a mod b int → int → int

1.3 Les caractères

L'ensemble des caractères est noté Car. Cet ensemble mathématique rassemble tous les caractères. Il

correspond au type char en Ocaml. En mathématique et en informatique les valeurs de type caractère

sont notées entre guillemets simples (ex. 'c'). Pour faciliter le raisonnement on distingue plusieurs sous

ensembles de caractères.


déf Minuscule = {'a', . . . , 'z'}

déf Majuscule = {'A', . . . , 'Z'}

déf Lettre = Minuscule ∪Majuscule

déf Chi�re = {'0', . . . , '9'}

déf Espace = {' ', '\t'}

déf Saut de ligne = {'\n'}

déf Symbole = les autres caractères du clavier

déf Car = Lettre ∪ Chi�re ∪ Espace ∪ Symbole ∪ Saut de ligne

Opérations sur les données de type caractère

Les seuls opérateurs binaires associés au type caractère sont les opérations de comparaison (<=,<,>,>=),

le test d'égalité (=) et le test de di�érence (<>) qui sont de type Car→ Car → Bool.

Nous utiliserons aussi les fonctions suivantes :

SPÉCIFICATION MATHÉMATIQUE Code ascii d'un caractère

Pro�l int-of-char : Car → N

Sémantique : int-of-char (c) est le numéro du caractère c dans la table ascii

7

Exemples

1. int-of-char ('0') = 48

2. int-of-char ('a') = 97

SPÉCIFICATION MATHÉMATIQUE Caractère correspondant à un code ascii

Pro�l char-of-int : N → Car

Sémantique : char-of-int (n) est le neme caractère de la table ascii

Exemples

1. char-of-int (49) = '1'

2. char-of-int (65) = 'A'

1.4 Les types séquences

Les mathématiciens français et les informaticiens anglo-saxons utilisent un vocabulaire di�érent pour

parler des séquences :


séquence list

séquence de caractères, en français character list, en anglais

notée Séq (Car) en math char list en Ocaml

exemple : [ 'o' ; 'c' ; 'a' ; 'm' ; 'l']

séquence d'entiers, en français integer list, en anglais

notée Séq (Z) en math int list en Ocaml

exemple : [ 1 ; 3 ; 5 ; 7 ; 9 ]

La séquence vide est notée [ ]L'ensemble des séquences non vide d'éléments de type T est noté Séq (T )∗.

DÉFINITION MATHÉMATIQUE D'UN ENSEMBLE

déf Séq (T )∗ = Séq (T ) \ { [ ] }

1.5 Le type Texte

Texte désigne l'ensemble des séquences de caractéres (ex. ['o' ;'c' ;'a' ;'m' ;'l']).

Le texte vide est noté [ ].Texte∗ désigne l'ensemble des textes privé du texte vide.

Plus précisement, on dé�nit l'ensemble Texte comme l'ensemble des séquences de caractères.

8

DÉFINITION MATHÉMATIQUE DE L'ENSEMBLE Texte

déf Texte = Séq (Car)

On traduit ensuite la dé�nition mathématique en un type informatique.

DÉFINITION INFORMATIQUE DU TYPE texte

type texte = char list ;;

1.5.1 Opérations sur les données de type Texte

Le type Texte est muni des opérations dé�nies pour toute séquence (voir chapitre 2).

- Concaténation L'opération de concaténation de deux séquences, noté @ permet de coller deux

textes. L'opérateur (@ ) a pour type . . . . . . . . . . → . . . . . . . . . . → Texte.

Exemple ['o' ;'c'] @ ['a' ;'m' ;'l'] = ['o' ;'c' ;'a' ;'m' ;'l']

Question L'opération de concaténation peut-elle donner un texte vide ?

- Ajout à gauche L'opérateur ( :: ) permet d'ajouter un caractère à gauche d'un texte,

il a pour type . . . . . . . → Texte → . . . . . . . . . .

. .

.

Exemple 'o' :: ['c' ;'a' ;'m' ;'l'] = ['o' ;'c' ;'a' ;'m' ;'l']

Propriété Quels que soient c une valeur de type Car et t une valeur de type Texte,

on a l'égalité c :: t = [c] @ t

Autrement dit, ajouter un . . . . . . . . . . . . . . . à . . . . . . . . . . . d'un texte avec l'opérateur . . . . donne le

même résultat que . . . . . . . . . . . . . . . er le texte . . . . fait d'un . . . . . . caractère et le . . . . . . . . t à l'aidede l'opérateur @ .

- Tête La fonction hd est l'abbréviation du mot anglais head qui signi�e tête.

SPÉCIFICATION MATHÉMATIQUE Premier caractère d'un texte

Pro�l hd : Texte∗ → . . . . . . .

Sémantique : hd (t) est le premier caractère du texte t

Exemples

1. hd(['o'; 'c'; 'a'; 'm'; 'l']

)= 'o'

2. hd([ ]

)provoque une erreur

- Queue La fonction tl est l'abbréviation du mot anglais tail qui signi�e queue.

SPÉCIFICATION MATHÉMATIQUE Texte sans son premier caractère

Pro�l tl : Texte. . → . . . . . . . . . .

Sémantique : tl (t) est le texte t privé de son premier caractère

9

Exemples

1. tl(['o'; 'c'; 'a'; 'm'; 'l']

)= ['c'; 'a'; 'm'; 'l']

2. tl([ ]


Propriété Complétez les pointillés avec les types des expressions.

∀t ∈ Texte, on a l'égalité t = hd (t)︸︷︷︸. . . . . .

:: tl (t)︸︷︷︸. . . . . . . . .

- Dernier SPÉCIFICATION MATHÉMATIQUE

Pro�l dernier : . . . . . . . . . . . . → Car

Sémantique : dernier (t) est le dernier caractère du texte t

Exemples

1. dernier(['o'; 'c'; 'a'; 'm'; 'l']

)= . . . . . .

2. dernier([ ]

). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- Début SPÉCIFICATION MATHÉMATIQUE

Pro�l debut : . . . . . . . . . . . . → Texte

Sémantique : debut (t) est le texte t privé de son dernier caractère

Exemples

1. debut(['o'; 'c'; 'a'; 'm'; 'l']

)= [ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ]

2. debut(. . .


Propriété Complétez les pointillés avec les types des expressions pour trouver l'opérateur manquant.

∀t ∈ Texte∗, on a l'égalité t = debut (t)︸︷︷︸. . . . . . . . .

. . . . [

. . . . . .︷︸︸︷dernier (t) ]︸︷︷︸. . . . . . . . .

Remarque Les fonctions hd, tl, dernier et début ne doivent pas être appliquées à un texte vide. Celaprovoquerait une erreur d'exécution du programme signalée par Exception : message d'erreur .

10

Exercice Complétez les pointillés avec les types des expressions, trouvez les opérateurs manquants, endéduire la spéci�cation de la fonction coeur et réaliser la fonction coeur à l'aide des fonctions précédentessur les textes.

∀t ∈ Texte, on a l'égalité t︸︷︷︸. . . . . . . . . .

=

. . . . . . .︷︸︸︷hd (t) . . . .

Texte︷︸︸︷coeur (t) . . . . . .

. . . . . . . . . .︷︸︸︷dernier (t) . .︸︷︷︸. . . . . . . . . .

SPÉCIFICATION MATHÉMATIQUE de la fonction coeur

Pro�l coeur : . . . . . . . . . . . . → . . . . . . . . . .

Sémantique : coeur (t) retourne le texte t . . . . . . . . . de . . . . . . . . . . . . . . . . . . . . . . et de . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

RÉALISATION INFORMATIQUE

Algorithme : coeur (t) = . . . ( . . . . . . . . . . ( t ))

1.5.2 Généralisation des opérations sur les textes

Exercice Les textes sont des séquences de caractères.

Les opérations précédentes sur les textes peuvent s'appliquer à tout sorte de séquences. Par exemple,l'opération d'ajout à gauche peut s'appliquer à des séquences contenant des valeurs d'un type T quelconque.

Pro�l ( :: ) : T → Séq (T ) → Séq (T )

En vous inspirant de cet exemple, complétez les pro�ls génériques des opérateurs et des fonctions suivantes :

Pro�l ( @ ) : . . . . . . . . . . . . . → . . . . . . .(T ) → Séq ( . . . )

Pro�l hd : Séq (T )∗ → . . .

Pro�l tl : . . . . . . . . . . . . . . . → Séq ( . . . )

Pro�l debut : . . . . . . . . . . . . . . . → Séq ( . . . )

Pro�l dernier : . . . . . . . . . . . . .∗→ . . .

1.6 Le type Chaîne

Pour programmer on utilise souvent les chaînes de caractères qui o�re une notation plus compacte

que les séquence de caractères. Les chaînes de caractères sont notées entre des guillemets doubles (").

L'ensemble des chaînes de caractères est noté Chaîne. Le type Ocaml correspondant à l'ensemble

Chaîne est string.

11

Opération de concaténation sur les données de type Chaîne

SPÉCIFICATION MATHÉMATIQUE concaténation de chaînes de caractères

Pro�l ( ˆ ) : Chaîne→ Chaîne → Chaîne

Exemples :

1. ("o" ˆ "caml") = ("oc" ˆ "aml") = . . . = ("oca" ˆ "ml") = ("ocam" ˆ "l") = "ocaml"

2. ("" ˆ "ocaml") = "ocaml" = ("ocaml" ˆ "")Propriété ∀ch ∈ Chaîne, on a l'égalité ("" ˆ ch) = ch = (ch ˆ "")

1.7 Opérations de conversion entre Texte et Chaîne

Il ne faut pas confondre les chaînes de caractères de type Chaîne et les séquences de caractères de type

Texte. Ce sont des données de nature di�érente. Retenez que Chaîne 6= Texte.

"ocaml"︸︷︷︸Chaîne

6= ['o'; 'c'; 'a'; 'm'; 'l']︸︷︷︸Texte

En revanche les fonctions ci-apprès permettent de passer des chaînes de caractères aux séquences de

caractères et vice-versa.

SPÉCIFICATION MATHÉMATIQUE texte vers chaine

Pro�l tvc : Texte → Chaîne

Exemples :

1. tvc(['o' ;'c' ;'a' ;'m' ;'l']

)= "ocaml"

2. tvc([ ]

)= ""

SPÉCIFICATION MATHÉMATIQUE chaine vers texte

Pro�l cvt : Chaîne → Texte

Exemples :

1. cvt("ocaml"

)= ['o' ;'c' ;'a' ;'m' ;'l']

2. cvt(""

)= [ ]

Propriété Complétez les pointillés avec le type des expressions.

1. ∀t ∈ Texte, on a l'égalité cvt (

. . . . . . . . . . . . .︷︸︸︷tvc (t) )︸︷︷︸

. . . . . . . . . .

= .︸︷︷︸Texte

2. ∀c ∈ . . . . . . . . . . . . . , on a l'égalité . . . . . . (

Texte︷︸︸︷. . . . . . (c) )︸︷︷︸

Chaîne

= c︸︷︷︸. . . . . . . . . . . . .

12

Remarque Prenez garde à ne pas confondre, le caractère 'a' de type Car avec "a" qui est de typeChaîne et ['a'] qui est de type Texte, c'est-à-dire Séq (Car).

1.8 Opérateurs de comparaison

Les opérateurs de comparaison (<=,<,>,>=), le test d'égalité (=) et le test de non-égalité (6=) noté <>

en ocaml sont dé�nis pour tous les types ocaml et sont automatiquement créés lorsqu'on dé�nit un

nouveau type ocaml. Ils ont donc un pro�l générique : T → T → Bool.

13

14

Chapitre 2

Dé�nition de types complexes

2.1 Dé�nir et nommer un type

Les dé�nition de types permettent de décrire des données très complexes manipulées par un programme

et de leur donner des noms simples et intuitifs qui rendront les programmes plus compréhensibles.

L'utilisation de noms bien choisis facilite la conception, la mise au point, la lecture, la maintenance et

la réutilisation des programmes.


déf Nom du type = ensemble mathématique

DÉFINITION INFORMATIQUE D'UN TYPE

type nom du type︸︷︷︸en minuscule

= une construction de type ocaml ;;

Exemple Le type Texte que nous avons déjà utilisé n'est pas un type prédé�ni du langage ocaml. Ondé�nit l'ensemble des textes comme l'ensembles des séquences de caractères.


déf Texte = Séq (Car)


type texte = char list ;;

Exercice Mathématiquement un Alphabet est une séquence de lettres minuscules. Complétez les dé�ni-tions ci-dessous.


déf Alphabet = Séq ( . . . . . . . . . . . . . . . . . . . )

15


type ................ = minuscule ........ ;;

2.2 Dé�nir un type par énumération

On peut dé�nir un ensemble en énumérant tous ses éléments. On peut dé�nir un type de la même

manière.

Exemple 1 Le type des booléens est dé�ni par une énumération �nie.

DÉFINITION MATHÉMATIQUE DE L'ENSEMBLE Bool

déf Bool = {vrai , faux}

DÉFINITION INFORMATIQUE DU TYPE Le type bool est déjà dé�ni en caml

type bool = true | false ;;

Exemple 2 Le type énuméré famille correspond à l'ensemble Famille de cartes est dé�ni par l'énumé-ration de ses éléments :

DÉFINITION MATHÉMATIQUE DE L'ENSEMBLE Famille

déf Famille = {♥,♦,♠,♣}

DÉFINITION INFORMATIQUE DU TYPE famille

type famille = Coeur | Carreau | Pique | Trefle︸︷︷︸Les noms de constantes symboliques doivent commencer par une Majuscule

;;

Exemple 3 Le type Mois est dé�ni par énumération.


déf Mois = {Jan,Fev,Mar,Avr,Mai,Juin,Jul,Aou,Sep,Oct,Nov,Dec}


type mois = Jan | Fev | Mar | Avr | Mai | Juin | Jul | Aou | Sep | Oct | Nov | Dec ;;

Remarque importante Jan, Fev, . . . , Dec sont des constantes symboliques qui n'ont pas de valeur.Il ne faut pas confondre les constantes du type énuméré Mois avec les textes "Jan","Fev",...,"Dec".

"Jan"︸︷︷︸chaîne

6= Jan︸︷︷︸constante symbolique

6= ['J' ;'a' ;'n']︸︷︷︸séquence de caractères

16

2.3 Construire un produit de types

définition (Vecteurs et produit cartésien d'ensembles vs. n-uplets et produit de

types) Les informaticiens et les mathématiciens utilisent un vocabulaire di�érent pour parler de la

même chose. Il faut connaître les deux terminologies. Les vecteurs des mathématiques sont appelés

n-uplets en informatique où n indique la taille du vecteur.


le vecteur (π, 0) le 2-uplet (3.14159,0.0)

appartient à R×R est de type float * float

le produit cartésien d'ensemble le produit de type

Z×Minuscule× Bool int * minuscule * bool

contient le vecteur (1, 'a', vrai ) accepte le 3-uplet (1,'a',true)

Les éléments du produit cartésien d'ensembles Z×Minuscule×Bool sont les vecteurs à 3 composantes

constitués d'un entier, d'une lettre minuscule et d'un booléen. Le type correspondant à cet ensemble

est le type produit int * minuscule * bool dont les éléments sont des 3-uplets.

Exemple 1 : le type Coordonnées Les coordonnées des points du plan sont des couples (x, y) qui ap-partiennent à R2. On peut dé�nir le Coordonnées qui traduira notre intention de modéliser des coordonnéespar des couples de réels.


déf Coordonnées = R×R


type coordonnees = float * float ;;

On peut alors dé�nir et utiliser des variables de type coordonnées


posons c ∈ Coordonnées = (0.5, 2.1) let (c : coordonnees) = (0.5,2.1) ;;

l'interpréteur caml répond

val c : c = (0.5, 2.1)

Ensuite, il est possible de décomposer c a�n de retrouver ses composantes

posons (x, y) = c let (x,y) = c ;;

l'interpréteur caml répond

x vaut donc 0.5 val x : float = 0.5

y vaut donc 2.1 val y : float = 2.1

17

Exemple 2 : le type Date Une date peut être représentée sous la forme d'un vecteur (j, m, a) où jindique le numéro du jour dans le mois, m est le mois et a l'année. Cette représentation correspond à ladé�nition mathématique d'un ensemble produit :


déf Jour = {1, . . . , 31}

déf Mois = {Jan,Fev,Mar,Avr,Mai,Juin,Jul,Aou,Sep,Oct,Nov,Dec}

déf Année = Z

déf Date = Jour×Mois× Année

DÉFINITION INFORMATIQUE DE TYPES

type jour = int ;; (* {1,...,31} *)

type mois = Jan | Fev | Mar | Avr | Mai | Juin | Jul | Aou | Sep | Oct | Nov | Dec ;;

type annee = int ;;

type date = jour * mois * annee ;;

Les valeurs de type date sont donc des 3-uplets constitués d'un entier (restreint à {1, ..., 31}),d'un mois dont les valeurs sont des constantes et d'un entier. Voici quelques exemples de

valeurs de type date :� (31,Dec,-5000) et (1,Jan,2008) sont de type date et respectent les contraintes indi-

quées en commentaire.

� (64,Oct,2008) est acceptée par le type date mais ne respecte pas les contraintes indi-

quées en commentaire.

Remarque On a choisi de représenter l'ensemble Jour par le type int en prenant soin d'ajouter encommentaire une contrainte qui précise qu'on considère uniquement les entiers entre 1 et 31. Dans ce casl'interprète Ocaml considerera tout entier comme un jour acceptable et ne signalera pas d'erreur si onutilise 999 comme un numéro de jour. On aurait pû faire un autre choix et dé�nir jour comme un typeénuméré :


type jour = J1 | J2 | J3 | J4 | ... | J29 | J30 | J31 ;;

Dans ce cas ocaml peut faire des véri�cations très précise mais on ne peut plus faire de

calculs sur les jours car J1, . . . , J31 ne sont pas des nombres, ce sont justes des noms de

constantes.

Voici quelques exemples de valeurs de type date correspondant à cette seconde dé�nition :� (J31,Dec,-5000) et (J1,Jan,2008) sont de type date

� (J64,Oct,2008) n'est pas accepté par le type date

� Que dire de (J31,Fev,2000) ?

Exemple 3 : les types Valeur et Figure On aimerait dé�nir l'ensemble des cartes à jouer. On distinguel'ensemble des Figures (As, Rois, Dames, Valets) et celui des Valeurs de 7 à 10 pour les di�érentes famillespossibles ♥,♦,♠,♣.

18


déf Famille = {♥,♦,♠,♣}

déf Tête = {As,Roi,Dame,Valet}

déf De7à10 = {7, 8, 9, 10}

déf Figure = Tête× Famille

= {(As,♥), (Roi,♥), (Dame,♥), (Valet,♥), . . . , (Valet,♣)}

déf Valeur = De7à10× Famille

= {(7,♥), . . . , (10,♥), (7,♦), . . . , (10,♦), (7,♠), . . . , (10,♠), (7,♣), . . . , (10,♣)}

DÉFINITION INFORMATIQUE DE TYPES

type famille = Coeur | Carreau | Pique | Trefle ;;

type tete = As | Roi | Dame | Valet ;;

type de7a10 = V7 | V8 | V9 | V10 ;;

type figure = tete * famille ;;

type valeur = de7a10 * famille ;;

2.4 Construire une somme de types

On peut dé�nir un type comme la réunion de plusieurs types à condition de nommer chacuns des types

que l'on souhaite réunir. On dit qu'on fait la somme des types.

Exemple 1 On aimerait dé�nir le type Nombre comme l'union de l'ensemble des entiers et de celuides réels. C'est inacceptable en informatique car les entiers et les réels ne sont pas de même nature.

Remarque Les ordinateurs doivent distinguer les entiers et les réels car les opérations sur les réelset celles sur les entiers sont e�ectuées par des parties di�érentes du processeur : le calculateur pour lescalculs �ottants est di�érent du calculateur utilisé pour les calculs sur les entiers.

Pour réunir les entiers et les réels en un seul type Nombre il faut faire la somme des types à l'aide deconstructeurs.

� On crée un constructeur Entier qui prend en argument une donnée de type Z et construit unedonnée de type Nombre .

Le constructeur Entier est de type : Z → Nombre.

Entier(7) est une donnée de type Nombre .

� On crée un constructeur Reel qui prend en argument une donnée de type R et construit une donnéede type Nombre .

Le constructeur Reel est de type : R → Nombre.

Reel(3.14) est une donnée de type Nombre .

� Les deux constructeurs Entier et Reel construisent des Nombres.

Le nom du constructeur permet à l'interprète Ocaml de distinguer si le nombre est un entier ou unréel bien que Entier(7) et Reel(3.14) soient deux données du même type Nombre .

Grâce aux constructeurs on a donc réussi à réunir les types entiers et réels tout en préservant leursdi�érences.

19

� Les ensembles { Entier(e) | e ∈ Z} et { Reel(r) | r ∈ R} sont tous deux des ensembles deNombres donc on peut en faire l'union.

DÉFINITION MATHÉMATIQUE DE L'ENSEMBLE Nombre

déf Nombre = { Entier(e) | e ∈ Z}∪ { Réel(r) | r ∈ R}

DÉFINITION INFORMATIQUE DU TYPE nombre

type nombre = Entier of int

| Reel of float ;;

À retenir Principe de construction d'un type somme Pour réunir des types incompatibles,

on utilise un procédé qui consiste à ajouter le nom du type devant ses valeurs. On dé�nit un nouveau

type qui fait la somme des types en utilisant des constructeurs.

Exemple 2 On aimerait maintenant dé�nir le type Carte comme l'union des ensemble Valeur etFigure dé�nis précédemment. C'est impossible car les éléments de ces ensembles ne sont pas de mêmenature :

(7,♥) et (As,♥) sont de type di�érent : De7à10× Famille 6= Tête× Famille

La seconde composante est de type Famille dans les deux cas mais la première composante est de typeentier dans (7,♥) tandis qu'elle est de type Tête dans (As,♥).Pour réunir les ensembles Valeur et Figure il faut faire la somme des types à l'aide de constructeurs.

� On crée un constructeur Valeur qui prend en argument une donnée de type Valeur et construitune donnée de type Carte .

Le constructeur Valeur est de type : Valeur → Carte.

(7,♥) est une donnée de type Valeur ; Valeur(7,♥) est une donnée de type Carte .

� On crée un constructeur Figure qui prend en argument une donnée de type et construit une donnéede type Carte .

Le constructeur Figure est de type : Figure → Carte.

(As,♥) est une donnée de type Figure ; Figure(As,♥) est une donnée de type Carte .

� Les deux constructeurs Valeur et Figure construisent des Cartes.

� Les ensembles { Valeur(v) | v ∈ Valeur} et { Figure(f) | f ∈ Figure} sont tous deux desensembles de Cartes donc on peut en l'union.


déf Carte = { Valeur(v) | v ∈ Valeur}∪ { Figure(f) | f ∈ Figure}


type carte = Valeur of valeur

| Figure of figure ;;

On aurait pû dé�nir le type Carte directement sans dé�nir les types Valeur et Figure . Voici ce qu'onécrirait dans ce cas. Le deux solutions sont totalement équivalentes.

20


déf Carte = { Valeur(v) | v ∈ {7, . . . , 10} × Famille}∪ { Figure(f) | f ∈ Tête× Famille}


type carte = Valeur of de7a10 * famille

| Figure of tete * famille ;;

Exercicea) Dé�nissez mathématiquement l'ensemble Jeu de carte comme l'ensemble des séquences de cartes puisle type Ocaml correspondant.


déf Jeu de carte = . . . . . . .( . . . . . . . . . . )


type jeu_de_carte = .......... ........ ;;

b) Dé�nissez les-carreaux comme la séquence des cartes de la famille ♦.

SPÉCIFICATION MATHÉMATIQUE

posons les-carreaux = [Valeur(7,♣) ; . . . ; Valeur(10,♣) ; Figure(Valet,♣) ; . . . ; Figure(As,♣)]


let (les_carreaux : ........................) =

[ Valeur(7,Carreau) ; .................................. ;

.................................. ; ............(10,Carreau) ;

............(Valet,Carreau) ; Figure(........,Carreau) ;

...................................... ; ....................................

]

;;

21

22

Chapitre 3

Constructions du langage Ocaml

définition On appelle expression les constructions du langage qui ont une valeur. Les construc-

tions qui n'ont pas de valeur sont des instructions.

Exemple� L'a�ectation x ← 2 des langages impératifs est une instruction : �x ← 2� n'a pas de valeur.� x+1 est une expression : �x+1� représente une valeur.

Remarque Dans les langages fonctionnels purs toutes les constructions ont une valeur, ce sont desexpressions. En particulier, l'a�ectation n'existe pas !

3.1 Expression conditionnelle

Le branchement conditonnel est exprimé par la construction

(if cond then expr1 else expr2)

C'est une expression qui a pour valeur celle de l'expression expr1 ou de l'expression expr2 selon la

valeur de la condition booléenne cond. Précisement :

(if cond then expr1 else expr2) =

expr1 si cond vaut true

expr2 si cond vaut false

Règle de typage La construction (if ..then ..else ..) doit respecter les contraintes de typage :

(if cond︸︷︷︸. . . . . . . .

then expr1︸︷︷︸. . .

else expr2︸︷︷︸. . .

)

︸︷︷︸. . .

Remarque La construction (if cond then expr1) sans partie else est interdite car lorsque condvaut false, l'expression (if cond then expr1) n'a pas de valeur.

3.2 Nommage d'une expression

Les mathématiciens utilisent abondamment la construction

posons x ∈ T = expression

qui permet de donner un nom x à une expression. On utilise alors le nom x plutôt que de réécrire

expression (qui peut être complexe ou pénible à écrire). Cette construction existe en Ocaml et se note

en anglais :

23

let (x : t) = expression ;;

Le x de type t ainsi dé�ni peut être utilisé partout dans le programme Ocaml. On dit que la dé�nition

de x a une portée globale, c'est-à-dire qu'elle porte sur tout le programme.

Exemple

SPÉCIFICATION MATHÉMATIQUE posons π ∈ R = 3, 141592653589

RÉALISATION INFORMATIQUE let (pi:float) = 3.141592653589 ;;

Restriction de la portée d'une dé�nition Lorsqu'on veut utiliser la valeur de x uniquement dans

une expression on peut limiter la portée de la dé�nition de x. On utilise pour cela la construction :

posons x = expression dans expr où expr est une expression utilisant x

qui se note en Ocaml :

let x = expression in expr ;;

Principe d'évaluation La construction let ... in ... est une expression qui s'évalue de la manière

suivante :

1. on commence par évaluer l'expression,

2. on remplace dans expr toutes les occurrences de x par la valeur de expression,

3. on évalue expr.

Exemple

let x = max (3,4) in x + max (5, x)

est équivalent à

max (3,4) + max (5, max (3,4))

Règle de typage La construction let ... in ... doit respecter les constraintes de type :

(let x︸︷︷︸. . .

= expression︸︷︷︸. . .

in expr utilisant x︸︷︷︸. . . .

)

︸︷︷︸. . . .

Remarque 1 Cette construction a l'avantage de n'évaluer qu'une fois l'expression expr.

Le nom x introduit est local à la construction let ... in ..., c'est-à-dire que x n'est pas connu en dehors dela partie expr. On dit que la portée du nom x se limite à la partie expr.

Remarque 2 Il est possible d'imbriquer les expressions let ... in ... et d'e�ectuer plusieurs nommagessimultanément (let x1 = expr1 and x2 = expr2 in ...).

Remarque 3 La construction let utilisée de la manière suivante : let (x,y) = v ;;

permet de décomposer un vecteur v en chacunes de ses composantes x, y, comme dans l'exemple du typeCoordonnées du �2.3 et l'exercice sur les relations entre intervalles.

24

3.3 Expression de �ltrage

Le �ltrage permet d'associer des valeurs à des motifs reconnaissables. Pour réaliser un �ltrage en

Ocaml on utilise la construction (match .. with ..) que l'on peut traduire par (reconnaître .. parmi..).

Notation et principe d'évaluation

(match expr with

| motif 1 -> expr1

| . . .| motif n -> exprn

)

Cette construction s'évalue de la manière suivante : on compare la valeur de l'expression expr avec le

premier motif motif 1, si ce motif reconnaît expr le résultat de la construction (match .. with ..)

est la valeur de l'expression expr1 ; sinon on passe au motif suivant. Si aucun motif n'a reconnu la

valeur expr, l'évaluation échoue et provoque une erreur.

Exemple 1 Le �ltrage permet d'associer le nombre de jour à une variable m de type Mois (voir 2.2).Chaque motif essaie de reconnaître la valeur m et rend le nombre de jour correspondant. Remarquezqu'on peut regrouper les motifs qui rendent le même résultat.

(match m with

| Fev -> 28

| Avr | Juin | Sep -> 30

| Jan | Fev | Mar | Mai | Jul | Aou | Oct | Dec -> 31

)

Remarque 1 Vous constatez que le programmeur a oublié le mois de novembre. L'interprèteOcaml détecte cet oubli : il véri�e que les motifs couvrent toutes les valeurs possibles du type mois ;il découvre qu'il manque le mois de novembre et a�che le message suivant1 :

Warning: this pattern-matching is not exhaustive.

Here is an example of a value that is not matched: Nov

La véri�cation de l'exhaustivité du �ltrage permet à Ocaml de détecter une erreur et permet auprogrammeur de la corriger.

Remarque 2 Vous constatez que le programmeur a mis deux fois le mois de février et donne deuxvaleurs di�érentes pour Fev : 28 et 31. L'interprète Ocaml détecte cette incohérence, souligne le motifqui pose probléme (le second Fev) et a�che le message suivant2 :

Warning: this match case is unused.

La véri�cation de l'exhaustivité du �ltrage permet à Ocaml de détecter une erreur et permet auprogrammeur de la corriger.

À retenir Lorsqu'on utilise une expression de �ltrage, il faut qu'elle soit exhaustive, c'est-à-

dire qu'elle comporte un motif pour chaque valeur possible de expr. Dans le cas contraire, l'interprète

Ocaml signalera une erreur.

Exemple 2 L'expression de �ltrage suivante associe à la variable c de type Carte (voir page 19) unnombre de points correspondant à son rang.

1(Traduction) Attention : cette reconnaissance de motif n'est pas complète. Voici un exemple de valeur qui n'est pasreconnue : Nov

2(Traduction) Attention : ce motif n'est jamais utilisé.

25

(match c with

| Valeur(v,f) -> v

| Figure(Valet,f) -> 11

| Figure(Dame,f) -> 12

| Figure(Roi,f) -> 13

| Figure(As,f) -> 14

)

Exemple 3 L'expression de �ltrage suivante vaut vrai si et seulement si la variable l est une voyelleminuscule.

(match l with

| 'a' | 'e' | 'i' | 'o' | 'u' | 'y' -> true

| _ -> false

)

Remarque Le motif �-� est le motif universel. Il reconnaît toutes les expressions et les acceptesans condition. Il faut donc toujours le placer en dernier.

D'autre part, lorsqu'on utilise �-�, le �ltrage est forcément exhaustif et cela empêche caml de détecterdes oublis du programmeur. Il faut donc utiliser �-� avec précaution et parcimonie ; uniquement quandl'énumération est très très longue ou impossible.

Règle de typage La construction (match .. with ..) doit respecter les contraintes de typage :

match

T︷︸︸︷expr with

| motif 1︸︷︷︸T

-> expr1︸︷︷︸T ′

| . . .

| motif n︸︷︷︸T

-> exprn︸︷︷︸T ′

est de type T ′

3.4 Expression de �ltrage avec condition

La construction motif when condition -> résultat permet d'ajouter une condition à une recon-

naissance par motif.

Notation et principe d'évaluation

(match expression with

| motif 1 when condition1 -> expr1

| . . .| motif n when conditionn -> exprn

)

Une branche du �ltrage match expression with sera prise uniquement quand les deux conditions

sont réunies :

1. L'expression est reconnue par le motif

2. L'évaluation de la condition associée donne vrai

26

Exemple 4 L'expression de �ltrage ci-dessous permet de calculer le nombre de point correspondant à unevariable c de type Carte en tenant compte de la variable atout de type Famille (voir page 19).

Implantation à l'aide de motifs avec condition

match c with

| Valeur(9,f) when f = atout -> 15

| Figure(Valet,f) when f = atout -> 30

| Valeur(v,_) -> v

| Figure(Valet,_) -> 11

| Figure(Dame,_) -> 12

| Figure(Roi,_) -> 13

| Figure(As,_) -> 14

;;

Remarque Dans une expression de �ltrage on peut avoir des motifs avec et des motifs sans condition.On ajoute des conditions au motifs uniquement lorsque c'est nécessaire.

Exemple 5 L'expression de �ltrage ci-dessous doit donner le Signe de l'entier x parmi les trois cas possiblesdé�nis par :


déf Signe = {Negatif, . . . . . . . . ,Positif}


type signe = .............. | Nul | Positif ;;

Implantation incorrecte

match x with

| x when x>0 -> Positif

| x when x<0 -> Negatif

;;

Remarque Il est important que l'expression de �ltrage soit exhaustive. Ici, le programmeur a oublié uncas. Si x = 0 l'évaluation de l'expression de �ltrage produira une erreur : Exception: Match_failure.

qui signi�e erreur de �ltrage.

Implantation correcte

match x with

| x when x>0 -> Positif

| x when x<0 -> Negatif

| _ -> ......

;;

27

3.5 Filtrage avec condition versus conditionnelles imbriquées

Le �ltrage avec conditions permet de réaliser des if...then...else... imbriqués. Il n'y a pas une solutionqui soit systématiquement meilleure que l'autre. Il faut choisir celle qui est la plus élégante.

Exemple On reprend l'exemple du signe d'un entier x ∈ Z et on souhaite écrire une fonction signe-de

qui donne le signe de x.


Pro�l signe-de : Z→ Signe

Sémantique : signe-de (x) est le signe de l'entier x

Exemples

1. signe-de (0) = Nul

2. signe-de (1) = Positif

3. signe-de (-1) = Negatif


Implantation 1 à l'aide de if...then...else... imbriqués

let (signe-de : int -> signe) =

function x -> if x<0 then ...............

else if ...... then Positif

else (* x=0 *) ......

;;

Implantation 2 à l'aide d'un �ltrage avec condition


function�� x -> match x with

| x when x<0 -> ...............

| x when ...... -> Positif

| x when x=0 -> ......

;;

Remarque La partie encadrée est inutile en caml et on peut se contenter d'écrire :

Implantation 2' : autre notation acceptée par caml


function

| x when x<0 -> ...............

| x when ...... -> Positif

28

| x when x=0 -> ......

;;

Remarquez que la partie � x -> match x with � est optionnelle.L'implantation 2' se lit de la manière suivante : signe-de est une fonction qui donne Negatif quand x < 0,qui donne Positif quand x > 0 et Nul quand x = 0.

29

30

Chapitre 4

Dé�nition de fonctions

En informatique la dé�nition d'une fonction doit comporter deux parties :

1. une spéci�cation c'est-à-dire une description mathématique de la fonction présentée ainsi :


Pro�l nom de la fonction : type de la fonction

Sémantique : rôle de la fonction

2. une réalisation de la fonction dans un langage de programmation présentée ainsi :


Algorithme : l'algorithme décrit le principe utilisé pour réaliser la fonction

Implantation (en caml dans ce cours)

let (nom de la fonction : type de la fonction ) = function ...

Exemple 1 : maximum de deux entiers

SPÉCIFICATION MATHÉMATIQUE (fournie par l'utilisateur au programmeur)

Pro�l max2 : Z× Z → Z

Sémantique : max2 (x, y) est le plus grand des entiers x et y

Exemple : max2 (0, 1) = 1

Propriétés

1. ∀x ∈ Z, max2 (x, x) = x

2. ∀x ∈ Z, max2 (x,−x) = |x|

31

RÉALISATION INFORMATIQUE(mise au point par le programmeur de manière à

respecter la spéci�cation de l'utilisateur)

Algorithme : max2 (x, y) =

x si x > y

y si x < y

x (ou y) si x = y

Implantation en caml

let (max2 : int * int -> int) =

function (x , y) ->

if (x>y) then x else y

;;

4.1 La spéci�cation : un contrat entre l'utilisateur et le programmeur

En informatique, on distingue deux parties dans la dé�nition d'une fonction :

1. la spéci�cation mathématique de la fonction. Elle décrit :

� les conditions d'utilisations de la fonction (son pro�l), c'est-à-dire quels paramètres il faut lui donner :combien et de quels types, quels résultats elle rend : combien et de quels types ;

� ce que fait la fonction (sa sémantique), c'est-à-dire quel résultat elle rend et les propriétés de cerésultat (les exemples et les propriétés).

2. la réalisation informatique de la fonction. Elle décrit le principe (l'algorithme) qui permet de pro-duire le résultat attendu et fournit une version de l'algorithme écrit un langage de programmation(l'implantation).

La spéci�cation mathématique est destinée à l'utilisateur de la fonction qui veut savoir comment il l'utiliser.La réalisation informatique est faîte par le programmeur qui doit trouver et implanter un algorithme quirespecte la spéci�cation informatique. La spéci�cation informatique joue le rôle d'un contrat entre un client(l'utilisateur) et le fournisseur (le programmeur).

Exemple 2 : on réutilise le type Mois dé�ni page 16. Imaginons qu'un utilisateur ait besoin d'unefonction juste-avant qui prend un couple de Mois (m1,m2) et qui vaut vrai si le mois m1 est exactementle mois avant m2. On convient que le mois de décembre est avant le mois de janvier de l'année suivante.L'utilisateur s'adresse à vous, programmeur caml. Il vous donne la spéci�cation et vous devez réaliser lafonction.


Pro�l juste-avant : Mois×Mois → Bool

Sémantique : juste-avant (m1,m2) est vraie si et seulement si m1 est le mois qui précède m2

Exemple : Les exemples servent à préciser le résultat attendu dans les cas particuliers, comme :

juste-avant (Dec,Jan) = vrai

Propriété ∀m ∈ Mois, juste-avant (m,m) = faux

32


Algorithme � c'est la description du principe qui permet d'arriver au résultat : On énumère l'en-

semble des . . . . couples (m1,m2) qui satisfont la relation �est juste avant� :

{(Jan,Fev), (Fev,Mar), . . . , (Dec,Jan)}

Implantation � c'est la traduction du principe dans un langage de programmation

let (juste_avant : mois * mois -> ........) =

function ( m1 , m2 ) ->

match (m1,m2) with

| (Jan,Fev) | .................. | .................. | ..................

| .................... | .................... | .................... | ....................

| (......,......) | (......,......) | (......,......) | (Dec,Jan) -> ........

| _ -> ..........

;;

4.2 Le programmeur est aussi l'utilisateur de ses propres fonctions

Souvent les programmeurs travaillent en équipe : ils utilisent les fonctions des autres et pour cela ils lisent lesspéci�cations a�n de savoir comment bien utiliser la fonction d'un autre ou bien ils écrivent la spéci�cationd'une fonction et c'est un autre programmeur qui la réalisera. Un programmeur est aussi l'utilisateur de sespropres fonctions et la spéci�cation est utile pour se souvenir rapidement de ce que fait une fonction qu'ila écrite des mois ou des années auparavant. Dans tous ces cas il est utile d'écrire la spéci�cation pour sesouvenir de la bonne manière d'utiliser une fonction.

Exemple 3 : on réutilise le type Nombre dé�ni page 19. Imaginons qu'en tant qu'utilisateur vous ayezbesoin d'une fonction qui prend en paramètre deux Nombre et les additionne. On commence par rédiger laspéci�cation a�n de décire le rôle de la fonction avant de la réaliser.


Pro�l addition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . → Nombre

Sémantique : addition (n1, n2) est le nombre Entier ou Reel correspondant à l'addition la plus

précise possible des valeurs représentées par n1 et n2

Exemples :

1. addition (Entier(e1),Entier(e2)) = Entier(e1 + e2)

2. addition (Entier(e),Reel(r)) = Reel( . . . . . . . . . . . . . . . . . . . . . (e)︸︷︷︸on convertit e en . . . . .

+. r)


Algorithme : Selon le type de n1 et de celui n2 on choisit l'opérateur d'addition à utiliser parmi

33

Pro�l (+) : int → int → int

Pro�l (+.) : float → float → float

Lorsque c'est nécessaire on convertit un entier en réel grâce à la fonction

Pro�l float-of-int : int → float

Cette convertion ne perd pas de précision car Z . . .R.

Implantation

let (addition : nombre * ............ -> ............) =

function (n1 , n2) ->

match (n1,n2) with

| (Entier(e1), Entier(e2)) -> ............( e1 + e2 )

| (........(r1) , Réel(r2)) -> ........( r1 +. r2 )

| (............(e), Réel(r)) -> ........( (float_of_int e) .... r )

| (........(r) , Entier(e)) -> ........( r +. ................................ )

;;

4.3 Dé�nition de fonctions partielles = fonctions avec condition

Une fonction partielle sur les entiers est une fonction qui n'est pas dé�nie pour tous les entiers possibles. C'estpar exemple le cas de la division euclidienne de a par b qui est dé�nie uniquement b > 0. La constructionwhen permet de signaler dans l'implantation de la fonction div que c'est une fonction partielle.

Exemple 5 La division euclidienne d'un entier a par un entier b doit donner un quotient q et un reste rtels que : a = b× q + r avec q, r ∈ N et r < b.On dit que la fonction div est partielle puisqu'elle n'est pas dé�nie pour tous les entiers b possibles. Elle n'ade sens que pour b > 0.


déf N∗ = {n ∈ Z |

�� n >0 }


type nat_positif = int (*�� >0 *)


Pro�l div : Z×N∗ → N×NSémantique : div(a, b) est le couple (quotient,reste) de la division euclidienne de a par b

34

Exemples

1. div(5, 3) = (1, 2)2. div(5, 0) = erreur : la fonction n'est pas dé�nie dans le cas b = 03. div(5,−3) = erreur : la fonction n'est pas dé�nie dans le cas b < 0

RÉALISATION INFORMATIQUE La construction � function .. when condition � permet de pré-ciser que la fonction est dé�nie uniquement lorsque b > 0. La condition b > 0 correspond à la conditionencadré de l'ensemble N∗ et du type nat_positif.

Implantation

let (div: int * nat_positif -> nat * nat) =�� function (a,b) when b>0 ->

let q = a/b

and r = a mod b

in (q,r)

;;

Remarque L'utilisation de la fonction div avec b = −3 ou b = 0 provoque une erreur Match_failure.Ce n'est pas une faute du programmeur ; au contraire, c'est voulu et le programmeur a parfaitement faitson travail puisque la fonction div est conforme à la spéci�cation qui prévenait dans le pro�l de div et dansles exemples qu'il ne fallait pas utiliser div avec un b ≤ 0.

4.4 Respectez la spéci�cation laisse malgré tout de la liberté

La spéci�cation est un contrat entre l'utilisateur et le programmeur. Pour que l'utilisateur ne soit pas surprispar les résultats de votre implantation il faut veiller à bien respectez la spéci�cation.

Exemple 6 : Réalisation du prédicat est-voyelle par �ltrage sur le type énuméré des caractèresImaginons qu'en tant que programmeur vous ayez besoin d'un prédicat est-voyelle qui indique si une lettreminuscule est une voyelle. Spéci�ez puis réalisez le prédicat est-voyelle .

définition (prédicat) Un prédicat est une fonction qui rend un booléen.

SPÉCIFICATION MATHÉMATIQUE du prédicat est-voyelle

Pro�l est-voyelle : Minuscule → . . . . . . . .

Sémantique : est-voyelle (l) est . . . . . . . si et seulement si l ∈ {'a', 'e', 'i', 'o', 'u', 'y'}

Exemples

1. est-voyelle ('a') = . . . . . . . .

2. est-voyelle ( . . . . . . ) = faux3. est-voyelle ('A') n'est pas prévu par le type Minuscule

Dans cette spéci�cation le comportement de la fonction est-voyelle n'est dé�ni que pour les minuscules, iln'est pas précisé pour les lettres majuscules.

35

Conclusion Le programmeur est donc libre de choisir le comportement de la fonction est-voyelle pourles majuscules : il peut rendre soit vrai , soit faux . Mais il peut aussi choisir de ne pas dé�nir la fonctionpour les lettres majuscules et dans ce cas la fonction retournera Match_failure.

Plusieurs implantations possibles Nous allons examiner des implantations di�érentes qui ne rendentpas les mêmes résultats et qui pourtant respectent toutes cla spéci�cation. Avant cela examinons commentsont dé�nis les caractères.

DÉFINITION MATHÉMATIQUE DE L'ENSEMBLE des caractères, par énumération �nie

déf Car = {'a', . . . , 'z', 'A', . . . , 'Z', '@', '#', '$', . . . , '%'}

DÉFINITION INFORMATIQUE DU TYPE

type char = 'a' | . . . 'z' | 'A' | . . . | 'Z' | '@' | '#' | '$' | . . . | '%' ;;

Le type char est prédé�ni en caml sous la forme d'un type énuméré.

Puisque le type char est un type énuméré on peut utiliser le �ltrage match ... with... sur les caractèreset caml indiquera si on a oublié des cas. On peut donc dé�nir la fonction par énumération.


Algorithme : On énumère les lettres minuscules qui satisfont la condition �être une voyelle�.

Implantation 1

let (est_voyelle : minuscule -> bool) =

function l -> match l with

| 'a' | 'e' | 'i' | 'o' | 'u' | 'y' -> true

| _ -> false

;;

Implantation 1' : autre notation acceptée par caml

let (est_voyelle : minuscule -> bool) =

function

| 'a' | 'e' | 'i' | 'o' | 'u' | 'y' -> true

| _ -> false

;;

Remarquez que la partie � l -> match l with � est optionnelle.

L'implantation 1' se lit de la manière suivante : est-voyelle est une fonction qui à chaque lettre'a', 'e', 'i', 'o', 'u', 'y' associe true et qui associe false aux autres lettres (y compris les voyelles enmajuscule).

Les implantations 1 et 1′ ci-dessus respectent la spéci�cation puisqu'elles rendent vrai pour les voyelles enminuscule. On propose maintenant une autre implantation.

36

Exercice 1 L'implantation 2 ci-dessous respecte-elle la spéci�cation de est-voyelle ?

Implantation 2

let (est_voyelle : char -> bool) =

function

| 'a' | 'e' | 'i' | 'o' | 'u' | 'y'

| 'A' | 'E' | 'I' | 'O' | 'U' | 'Y' -> true

| _ -> false

;;

. . . . . . puisque la spéci�cation ne . . . . . . . . . . . . pas ce qu'il faut . . . . . . . . . . . . . . . . comme résultat pour les

lettres . . . . . . . . . . . . . . . . . . . donc le programmeur est libre de . . . . . . . . . . . la valeur à rendre pour les voyelles

en . . . . . . . . . . . . . . . . . . .

Exercice 2 Proposez une nouvelle spéci�cation plus précise qui correspond à l'implantation 2.

SPÉCIFICATION MATHÉMATIQUE du prédicat est-voyelle

Pro�l est-voyelle : . . . . . . . . . . . → . . . . . . . .

Sémantique : est-voyelle (l) est . . . . . . . si et seulement si

l ∈ {'a', 'e', 'i', 'o', 'u', 'y'} . . { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . }Exemples :

1. est-voyelle ('a') = . . . . . . . . = est-voyelle ('A')

2. est-voyelle ('z') = . . . . . . . . = est-voyelle ('Z')

Propriété ∀l ∈ . . . . . . . . . . . , est-voyelle (l) . . . est-voyelle (majuscule( . ))

37

Documents

LICENCE SCIENCES & TECHNOLOGIES 1 année … · ALGORITHMIQUE ET PROGRAMMATION FONCTIONNELLE Introduction ousV connaisssez le langage C , pourquoi apprendre un nouveau langage?