Connaître différents langages de
programmation pour choisir le mieux approprié dans chaque situation.
•
Le langage OCaml (où d'autres langages de la même famille) sont de plus en
plus utilisés dans l'industrie.
Voir les infos
en ligne,
e.g.FFT.
Récemment choisi pour des outils système de la distibution Lindow de Linux!
Avertissement
Cette introduction succincte au langage OCaml a pour but de vous permettre
de vous débrouiller avec le langage OCaml.
Ce n'est qu'un survol du langage, vu sous l'angle de la pratique.
•
Les exemples sont simples et classiques.
•
Les constructions de bases sont présentées, mais avec très peu d'exemples.
•
Les constructions particulières au langage OCaml telles que l'utilisation
des fonctions d'ordre supérieur, du filtrage ou du polymorphisme
mériteraient plus de considération et d'exercices.
Il doit vous permettre de vous exercer ensuite:
•
en suivant les travaux dirigés,
•
dans les autres cours (langages de programmation, compilation, programmation
système), ou
•
seul, à partir des nombreux exercices en ligne.
Apprentissage d'un langage
Par la pratique exercez-vous!
Par couper/coller
•
regarder les solutions des exercises;
•
réutiliser en le modifiant pour l'adapter du code déjà écrit,
OCaml est le fruit de développements récents et continus:
•
1975
Robin Milner propose ML comme méta-langage (langage de script) pour
l'assistant de preuve LCF.
Il devient rapidement un langage
de programmation
à part entière.
•
1981
Premières implantations de ML
•
1985
Développement de Caml à l'INRIA.
et en parrallèle,
de Standard ML à Edinburgh,
de “SML of New-Jersey”,
de Lazy ML à Chalmers,
de Haskell à Glasgow, etc.
•
1990
Implamtation de Caml-Light par X. Leroy and D. Doligez
•
1995
Compilateur vers du code natif + système de modules
•
1996
Objets et classes (OCaml)
•
2001
Arguments étiquettés et optionnels, variantes.
•
2002
Méthodes polymorphes, librairies partagées, etc.
•
2003
Modules récursifs, private types, etc.
Domaines d'utilisation du langage OCaml
Un langage d'usage général avec des domaines de prédilection.
Domaines de prédilection
•
Calcul symbolique:
Preuves mathématiques, compilation, interprétation, analyses de programmes.
•
Prototypage rapide.
Langage de script. Langages dédiés.
•
Programmation distribuée (bytecode rapide).
Enseignement et recherche
•
Classes préparatoires.
•
Utilisé dans de grandes universités (Europe, US, Japon, etc.).
let euro x = floor (100.0 *. x /. 6.55957) *. 0.01;;
val euro : float -> float = <fun>
let baguette = 4.20;;
val baguette : float = 4.2
euro baguette;;
- : float = 0.64
exit 0;;
Utilisation du mode interprété
Comme une grosse calculette
Pour la mise au point des programmes
Évaluation des phrases du programme en cours de construction
(utilisation avec un éditeur)
Comme langage de script...
% ocaml < bienvenue.ml
équivalent à la version interactive
% ocaml bienvenue.ml
idem, mais suppression des messages
Conseil
Il faut savoir que le mode interprété existe, qu'il peut parfois aider à la
mise au point, mais à part pour ces usages très particuliers, nous le
déconseillons de façon générale, surtout pour les débutants qui
peuvent être déroutés par l'évaluation incrémentale des phrases d'un
programme.
On peut également en faire un script directement exécutable en indiquant
le chemin absolu de ocaml précédé de #! sur la première ligne du
fichier:
Insérer le contenu de ~remy/emacs/ocaml.emacs
à la fin de votre fichier ~/.emacs
(Quitter emacs après l'installation.)
Édition et compilation
•
le mode OCaml doit être sélectionné automatiquement à l'ouverture
d'un fichier se terminant avec le suffixe .ml ou .mli.
Par exemple, ouvrir un fichier bienvenue.ml et un menu Caml doit
apparaître dans la bar de menus.
Écrire les phrases dans ce fichier.
•
Exécuter la comande Compile dans le menu Caml
(ou son équivalent clavier Control-c Control-c).
Modifier si besoin la commande proposée par défaut.
Tapez Return.
•
Documentation interactive: placer le curseur sur ou juste après un
identificateur. Appeler la commande Help for identifier dans le menu
Caml (ou son équivalent clavier Meta-Control-h).
Version interactive: au choix
•
Ouvrir un fichier bienvenue.ml,
Écrire les phrases dans ce fichier,
Exécuter la commande Eval phrase dans le menu Caml.
(éventuellement, appeler Start subshell dans le menu Caml.)
•
Appeler directement OCaml par la commande Run caml
Mode interprété
Mode vi déconseillé: les accrocs sont laissés à eux-mêmes.
Les programmes
Un programme est une suite de phrases:
– définition de valeur
letx = e
– définition de fonction
letfx1 ... xn = e
– définition de fonctions
let [ rec ] f1x1 ... = e1 ...
mutuellement récursives
[ andfnxn ... = en ]
– définition de type(s)
typeq1 = t1... [ andqn = tn ]
– expression
e
Les phrases se terminent par ;; optionnel entre des déclarations,
mais obligatoires sinon.
(* Cela est un commentaire (* et ceci un commentaire à
l'intérieur d'un commentaire *) sur plusieurs lignes *)
Les expressions
– définition locale
letx = e1ine2
(définition locale de fonctions mutuellement récursives)
– fonction anonyme
funx1 ... 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
matchewithp1->e1 … ∣ pn->en
– boucle for
fori = e0toefdoedone
– boucle while
whilee0 do edone
– conditionnelle
ife1thene2elsee3
– une séquence
e; e '
– parenthèses
(e) begineend
Un vrai petit programme
ls.ml
let all = Sys.readdir ".";;
let filter p =
Array.fold_left
(fun res x -> if p x then x :: res else res) [];;
let has_suffix suf str =
let len_suf = String.length suf inlet len_str = String.length str in
len_suf <= len_str &&
String.sub str (len_str - len_suf) len_suf = suf;;
List.iter print_endline (filter (has_suffix ".ml") all);;
Dans une séqeunce les ; sont obligatoires.
Les expressions de la séquences ne sont pas liées.
La valueur de la dernière expression est retournée.
Types, constantes et primitives de base
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
"a\tb\010c\n"
^s.[i]s.[i] <- c
Polymorphes
tableaux
[| 0; 1; 2; 3 |]
t.(i)t.(i) <- v
tuples
(1, 2) (1, 2, 3, 4)
fst snd
Un opérateur infixe entre parenthèses devient préfixe. Par exemple,
(+)x1x2 est équivalent à x1+x2
Tableaux
Les opérations sur les tableaux sont polymorphes: on peut créer des tableaux
homogènes d'entiers, de booléens, etc.
[| 0; 1; 3 |]
: intarray
[| true; false |]
: boolarray
Les indices de tableaux varient de 0 à n−1 où n est la taille.
Les projections sont polymorphes: elles opèrent aussi bien
sur des tableaux d'entiers que sur des tableaux de booléens.
funx -> x.(0)
: 'aarray -> 'a
funtkx -> t.(k) <- x
: 'aarray -> int -> 'a -> unit
Les tableaux sont toujours initialisées:
Array.create
: int -> 'a -> 'aarray
- Le premier argument est la longueur du tableau
- Le second argument est utilisé pour initialiser toutes les cases du
tableau. Il détermine le type du tableau.
Tableaux (examples)
let digits = Array.create 10 0;;
val digits : int array = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]
let _ =
for i = 0 to 9 do digits.(i) <- digits.(i) + i done;;
let chriffre_trois = digits.(3);;
val chriffre_trois : char = '3'
Polymorphisme:
Array.set;;
- : 'a array -> int -> 'a -> unit = <fun>
Array.set digits;;
- : int -> int -> unit = <fun>
Tuples
Ils sont hétérogènes, mais leur arité est fixée par leur type:
– une paire
(1, 2)
: int * int
– un triplet
(1, 2, 3)
: int * int * int
sont incompatibles.
Les projections sont polymorphes sur les tuples de même arité:
let second_of_triple (x, y, z) = y
second_of_triple : 'a * 'b * 'c -> 'b
Les paires ne sont qu'un cas particulier de tuples, pour lequel les
deux projections fst et snd sont pré-définies.
fst
: 'a * 'b -> 'a
snd
: 'a * 'b -> 'b
Les autres projections doivent être programmées (c.f. ci-dessus).
Les fonctions
Les arguments sont passés sans parenthèses
Écriture recommandée
let middle x y = (x+y) / 2
val middle :
int -> int -> int = <fun>
milieu 5 11;;
Mauvaise écriture (*)
let middle (x,y) = (x+y) /2
val middle :
int * int -> int = <fun>
(*) À droite “milieu” prend un seul argument qui
est une paire.
Fonctions récursives
letrec fact n = if n > 1 then n * fact (n -1) else 1;;
... et mutuellement récursives
letrec ping n = if n > 0 then pong (n - 1) else "ping"
and pong n = if n > 0 then ping (n - 1) else "pong";;
Applications
Exercise 2
Quelle différence y a-t-il entre
(lorsque f, x, y sont des variables):
type monnaie = {nom : string; valeur : float}
let x = {nom = "euro"; valeur = 6.55957}
x.valeur
Analogue à des tuples à champs nommés.
Champs polymorphes
type 'a info = {nom : string; valeur : 'a};;
fun x -> x.valeur;;
- : 'a info -> 'a
Attention! un nom peut en cacher un autre!
L'étiquette nom désigne la projection
de l'enregistrement 'a info, le champ nom du type
monnaie dernier est devenu inaccessible.
Les structures mutables
Seuls les champs déclarés mutable au moment de la définition pourront e6tr
emodifier.
Par exemple
type personne = {nom : string; mutable age : int};;
permettra de modifier le champ age, mais pas le champ nom.
let p = {nom = "Paul"; age = 23};;
val p : personne = {nom = "Paul"; age = 23}
let anniversaire x = x.age <- x.age + 1;;
val anniversaire : personne -> unit = <fun>
p.nom <- "Clovis";;
Characters 0-17:
The label nom is not mutable
Les références
Le passage d'arguments se fait toujours par valeur.
Les constructions &x ou *x de
C qui
retourne l'adresse à laquelle se trouve une valeur ou la valeur qui se
trouve à une adresse n'existent pas en OCaml.
La valeur d'une variable n'est pas modifiable
Mais, on peut modifier les champs d'un enregistrement. Le système a
préféfini le type enregistrement suivant:
type 'a ref = { mutable contents : 'a }
En C/Java
int x = 0;
x = x + 1;
En OCaml:
let x = ref 0;;
x := !x +1;;
Équivalent à:
let x = {contents = 0};;
x.contents <- x.contents +1;;
Peu de valeurs ont en fait besoin d'être des références en OCaml.
Éviter les références inutiles. Le style «fonctionnel» est plus sûr.
Égalité
Égalité structurelle
(notée = et <> pour l'inégalité)
C'est l'égalité mathématique: deux valeurs sont égales si elles ont la même
structure et si leurs sous-structures respectives sont égales.
Égalité physique (notée == et != pour l'inégalité)
C'est l'égalité de l'emplacement mémoire.
Dépend de la représentation des valeurs.
Les valeurs mutables sont toujours allouées.
L'égalité physique implique l'égalité structurelle.
Réservez l'égalité physique aux cas où c'est strictement
ce que vous voulez.
•
Mieux, définissez votre propre égalité!
Les arguments de la ligne de commande
Les arguments passés à un exécutable
sont placés dans le tableau Sys.argv : stringarray
Le nom de la commande est compté (c'est le premier argument).
Exemple La commande Unix echo
echo.ml
for i = 1 to Array.length Sys.argv - 1
do print_string Sys.argv.(i); print_char ' ' done;
print_newline();;
Exercise 5(Commade echo)
Corriger le programme ci-dessus pour qu'il reconnaisse,
comme la commande Unix /bin/echo,
l'option "-n" si elle est passée en premier argument,
ce qui a pour effet de ne pas imprimer de fin de ligne.
Corriger également l'impression de l'espace final
(qui ne doit pas être imprimé).
La librairie Arg permet de lire ces
arguments plus facilement.
Retourner un résultat
La fonction
exit
: int -> unit
Elle arrête le programme et retourne au système d'exploitation la valeur
entière reçue en argument (modulo 256).
Par défaut, une exécution retourne la valeur
0 si elle se termine normalement et une valeur non nulle autrement
(lorsqu'une exception s'échappe, par exemple)
L'usage est de retourner 0 pour une évaluation normale,
et de réserver les valeurs non nulles pour décrire un comportement anormal.
(Sous unix on peut observer le code de retour d'une commande en exécutant
echo$? immédiatement après.)
Exercise 6(Commandes true et false)
Écrire deux programmes true et false qui
se comporte comme les commandes Unix /bin/true et /bin/false,
i.e. qui ne font rien et retourne avec les codes 0 et 1, respectivement).
Le type de fonction compose peut se reconstituer ainsi: Le premier argument
f est une fonction quelconque, donc de type ('a -> 'b) . Le
deuxième argument g est une fonction dont le résultat doit pouvoir
être passé à f donc de type 'a; le domaine de g est
quelconque; donc g est de type 'c -> 'a. Le résultat est une
fonction qui prend un argument x qui doit pouvoir être passé à g
donc du type 'c. Finalement, le résultat final sera retourné par
f, donc de type 'b.
Fonctions anonymes
Ci-dessus, la fonction funx -> f (gx) est anonyme.
let compose = fun f -> fun g -> fun x -> f (g x)
let compose f g x = f (g x);;
sont des définitions équivalentes de la fonction compose.
La fonction puissance
Fonction puissance
letrec power f n =
if n <= 0 then (fun x -> x)
else compose f (power f (n-1));;
val power : ('a -> 'a) -> int -> 'a -> 'a = <fun>
Dérivation
let derivative dx f = fun x -> (f(x +. dx) -. f(x)) /. dx;;
Ce sont les listes qu'ils faut utiliser! Le système pré-définit:
type 'a list = [] | (::) of 'a * 'a list
Racourci
Les trois formes suivantes sont équivalentes:
let l = 1 :: (2 :: (3 :: (4 :: [])));;
let l = 1 :: 2 :: 3 :: 4 :: [];;
let l = [1; 2; 3; 4];;
La fonction reverse
Renforcer l'hypothèse de récurrence:
Une fonction auxilliaire transfert les éléments d'une liste
dans l'autre.
letrec transfert dest source =
match source with
[] -> dest
| head :: rest -> transfert (head :: dest) rest;;
let reverse l = transfert [] l;;
Écriture équivalente (avec une fonction locale)
let reverse l =
letrec transfert dest source =
match source with
[] -> dest
| head :: rest -> transfert (head :: dest) rest
in transfert [] l;;
Exercise 7(Listes à double entrée)
On donne le type double des listes à “double entrée”,
qui possède deux version Gauche et Droite du constructeur
Cellule.
type 'a double =
Vide
| Gauche of 'a * 'a double
| Droite of 'a double * 'a;;
On pourra ainsi écrire
let d = Droite (Gauche (1, Droite (Droite (Vide, 2), 3)), 4);;
La représentation d'une liste à double entrée est une arbre filiforme
(figure de Gauche). On peut lire une liste à double entrée en rebalançant
l'arbre à doite (figure de droite), ce qui revient à faire un parcours
gauche droite des feuilles (dans la figure de droite, on a remplacé les
noeuds Gauche et Vide par ceux des “vrais” listes :: et
[]).
Écire une fonction print_double imprime les noeuds d'une liste
double dans un parcours gauche-droite (print_double
reçoit en premier argument une fonction d'impression d'un nœud).
En remplaçant la fonction d'impression au terminal par une fonction qui
stocke les éléments dans une (vraie) liste, en déduire une fonction
list_of_double qui transforme une liste double en une (vraie) liste
simple (comme illustré par le passage de la figure de gauche à la figure de
droite).
Utiliser la trace pour observer l'exécution de la fonction dédouble.
(On aura intérêt à tracer une version spécialisée pour les entiers):
let dédouble_entiers =
(dédouble : int list -> int double -> int list)
let list_of_double_entiers l = dédouble_entiers [] l;;
#trace dédouble_entiers;;
list_of_double_entiers d;;
Le jeu de carte
Il combine types sommes et types enregistrements:
type carte = Carte of ordinaire | Joker
and ordinaire = { couleur : couleur; figure : figure; }
and couleur = Coeur | Carreau | Pic | Trefle
and figure = As | Roi | Reine | Valet | Simple of int;;
Définition de fonctions de construction auxiliaires:
let valet_de_pic = Carte { figure=Valet; couleur=Pic; }
val valet_de_pic : carte = Carte {couleur=Pic; figure=Valet}
let carte n s = Carte {figure = n; couleur = s}
let roi s = carte Roi s;;
val carte : figure -> couleur -> carte = <fun>
val roi : couleur -> carte = <fun>
Filtrage en profondeur
let valeur x =
match x with
| Carte { figure = As } -> 14
| Carte { figure = Roi } -> 13
| Carte { figure = Reine } -> 12
| Carte { figure = Valet } -> 11
| Carte { figure = Simple k } -> k
| Joker -> 0;;
Un motif peut capturer plusieurs cas.
let petite x =
match x with
| Carte { figure = Simple _ } -> true
| _ -> false;;
Sémantique du filtrage
Lorsqu'un argument est passé à un ensemble de clauses
p1->e1 ∣ … ∣ pn->en
•
la première clause qui filtre l'argument est exécutée, les autres sont
ignorées.
•
si aucune clause ne filtre l'argument, une exception est levée.
Filtrages incomplets
La définition est dite incomplète lorsqu'il existe une expression qui n'est
filtrée par aucun motif. Dans ce cas, un message d'avertissement est
indiqué à la compilation.
let simple x = match x with Carte{figure = Simple k} -> k
Characters 15-58:
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Joker
let simple x = match x with Carte {figure = Simple k} -> k
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
val simple : carte -> int = <fun>
Usage: Il est préférable d'éviter les définitions incomplètes.
Les motifs (patterns)
Ils peuvent:
•
être emboîtés, contenir des produits et des sommes
•
ne pas énumérer tous les champs des enregistrements
•
lier une valeur intermédiaire avec mot clé as
•
n'imposer aucune contrainte (représentés par le caractère _)
Une variable ne peut pas être liée deux fois dans le même motif.
let egal x y = match x, y with z, z -> true | _ -> false;;
Characters 34-35:
let egal x y = match x, y with z, z -> true | _ -> false;;
^
This variable is bound several times in this matching
Exercices
Exercise 8(Jeu de cartes)
Deux cartes sont incompatibles si aucune n'est le Joker et si elles sont
différentes. Elles sont compatibles sinon. Un ensemble de cartes
dont toutes les paires de cartes sont compatibles est compatible.
Les ensemble de cartes sont représenté par des listes, mais considérés à
permutation près.
Écrire une fonction compatibles qui prend un
ensemble de cartes et retourne l'ensemble de toutes les sous parties
compatibles les plus larges possibles.
compatibles
[ roi Trèfle; Joker; roi Carreau; Joker; roi Coeur;
roi Pic; carte Reine Trefle; carte Reine Pic; valet_de_pic ];;
- : carte list list =
[[Carte {couleur=Trèfle; figure=Roi}; Joker;
Carte {couleur=Carreau; figure=Roi}; Joker;
Carte {couleur=Coeur; figure=Roi}; Carte {couleur=Pic; figure=Roi}];
[Joker; Joker; Carte {couleur=Trèfle; figure=Reine};
Carte {couleur=Pic; figure=Reine}];
[Joker; Joker; Carte {couleur=Pic; figure=Valet}]]
En déduire une fonction testant si une main contient un carré (au moins autre cartes compatibles).
Comment généraliser la fonction, de façon à partager le code en commun, en
une fonction
fold : (int -> int -> int) ->int -> ('a -> int) -> 'alist -> int
Donner deux versions de fold, d'abord une seule fonction globale
récursive, puis utiliser une fonction locale récursive auxiliaire en lui
passant le minimum d'argument(s).
exception Perdu
letrec cherche une_aiguille botte_de_paille =
match botte_de_paille with
brin :: botte ->
if une_aiguille brin then brin
else cherche une_aiguille botte
| [] ->
raise Perdu
let k =
trylet name, number =
cherche (fun x -> fst x = "Louis")
[ "Georges", 14; "Louis", 5; ] in number
with Perdu -> 10;;
Exercise 10(Exceptions)
Écrire un programme analogue sans utiliser d'exception.
Remarquer l'analogie avec la construction de filtrage.
Exceptions pré-définis
Exception
Usage
gravité
Invalid_argumentofstring
accès en dehors des bornes
forte
Failureofstring
liste vide, retourne le nom de la fonction
moyenne
Not_foundofunit
fonctions de recherche
nulle
Match_failureof ...
Échec de filtrage
fatale
End_of_file
Fin de fichier
nulle
Sémantique
•
Le type exn est un type somme.
•
La levée d'une exception arête l'évaluation en cours et retourne une
valeur “exceptionnelle” (du type exn).
•
Une exception ne peut être éventuellement rattrapée que si elle a été
protégée par une expression try e1 with m
•
si l'évaluation de e1 retourne une valeur normale celle-ci est
retournée sans passer par le filtre.
•
si l'évaluation de e1 retourne une valeur exceptionnelle, alors celle-ci
est passée au filtre m. Si une des clauses pi->ei filtre
l'exception, alors ei est évaluée, sinon l'exception n'est pas
capturée, et la valeur exceptionnelle est propagée.
•
On peut observer une exception (i.e. l'attraper et la relancer):
try f x with Failure s as x -> prerr_string s; raise x
Usage des exceptions
Il est préférable de définir de nouvelles exceptions plutôt que de
réutiliser les exceptions pré-définies afin d'éviter tout ambiguïté.
On utilise les exceptions pour
•
reporter une erreur et interrompre le calcul en cours;
Par exemple, l'exception Match_failure est levée à l'exécution
lorsqu'une valeur n'est pas filtrée. Elle indique le nom du fichier et la
position filtre en cause.
•
communiquer une valeur de retour rare ou particulière;
Par exemple, les exceptions Not_found et End_of_file sont
utilisées pour programmer et les lever est un comportement tout à fait
normal.
Exemple : la commande Unix cat
Une version restreinte:
trywhile true
do print_string (read_line()); print_newline() donewith End_of_file -> ();;
Exercise 11(La commande cat)
Écrire la version complète, qui concatène l'ensemble des fichiers dont les
noms sont passés en argument ou bien reproduit le flux d'entrée lorsque la
commande est appelée sans argument.
Exercise 12(La commande grep)
Écire la commande unix /bin/grep sur le modèle de la commande
cat et en utilisant la librairie Str.
Pour compiler, on il faut utiliser la commande:
Exercise 13(La commande agrep)
Un raffinement de la commande grep consiste à traiter les lignes par
regions plutôt qu'individuellement. Par exemple,
./agrep -d '^let ' try agrep.ml
permet de recherche les définitions de phrases (dans un fichier bien
indenté) qui contiennent le mot clé. Le premier argument optionnel (sa
valeur par défaut est $ désignant la fin de ligne), ici
^let est le délimiteur1, le second argument, ici try est le motif à rechercher, et
les arguments suivant sont des noms de fichiers.
Chaque ligne filtré par le délimiteur commence une nouvelle région qui
continue jusqu'à la prochaine ligne (exclue) qui est également filtrée par
le délimiteur. La commande agrep imprime sur la sortie standard
chaque région dont une des lignes au moins est contient le motif.
Implémenter la commande agrep.
(On essayera de préserver le comportement incrémental qui consiste à
afficher une région dès que possible, sans attendre la fin du fichier.)
- Écrire une fonction sigma qui prend une fonction f, un tableau et
deux indices et qui calcule ∑i = jkf (t.(i))
- En déduire le calcul de la somme des éléments, des carrés ou la moyenne
des éléments d'un sous-tableau.
- Faire un exécutable à partir de l'exercice précédent. Les arguments sont
reçus sur la ligne de commande.
- Par défaut le programme calcule la somme. Si le premier argument est la
chaîne -carre ou -moyenne, alors il calcule la somme ou la
moyenne des éléments restants.
- Séparer le programme en deux fichier sigma.ml pour le code de la
fonction sigma et calculette.ml pour le code principal.
Écrire un fichier d'interface sigma.mli permettant de compiler
calculette.ml sans avoir à compiler sigma.ml.
Exercise 15(La commande Unix wc) compte l'ensemble des
caractères, mots et lignes de chacun des fichiers passés en arguments ainsi
que les totaux respectifs et les imprimes dans la sortie standard.
Permet de faire du pas à pas en avant et en arrière,
de visualiser l'état de la pile et les valeurs des variables locales.
Mise en œuvre
Compiler avec ocamlc -g
Appeler ocamldebugnom-du-programme
Il existe une interface conviviale pour Emacs: appeler la commande
camldebug (taper ESCXcamldebugnom-du-programme)
Si le programme n'est pas trouvé, il faut
•
ajuster le chemin d'accès (dans le shell avant de lancer emacs)
•
passer le chemin absolu, par exemple sous caml debug, avec
set program nom-absolu-du-programme
Si le programme prend des arguments a1, a2, etc. on peut les
passer par
set arguments a1 a2
La trace arrière (mode batch)
Permet le débogage des exceptions non rattrapées de façon légères.
Compiler avec l'option -g comme pour le débogueur.
Lancer le programme (version bytecode) avec la variable d'environnement
OCAMLRUNPARAM valant "b", soit en affectant cette variable locatement
au lancement du programme:
OCAMLRUNPARAM=b ./mon_programme ses_arguments
ou en affectant cette variable globalement avant de lancer le programme.
Ce sont des types dont la représentation est cachée.
On ne peut manipuler les valeurs d'un type abstrait qu'en les passant
à des fonctions acceptant des arguments du même type.
Polymorphisme
Le typeur infère les types d'un programme. Il existe souvent plusieurs
solutions:
let identity x = x;;
: int -> int
: string -> string
: 'a * 'a -> 'a * 'a
: 'a -> 'a
Le typeur retourne le type le plus général (il en existe toujours un si le
programme est typable).
let identity x = x;;
val identity : 'a -> 'a = <fun>
Les autres se retrouvent par instantiation des variables de type.
On dit que l'identity est polymorphe.
Support du polymorphisme
La construction de liaison introduit le polymorphisme.
let apply f x = f x in apply succ 1, apply print_int 1;;
Limitations
•
un argument de fonction n'est pas polymorphe:
(fun apply -> apply succ 1, apply print_int 1)
(fun f x -> f x);;
Les deux occurrences de apply doivent avoir le même type.
(Sinon, on ne sait plus deviner le type de apply)
•
Un calcul (une application) n'est pas polymorphe:
let f = identity identity in f 1, f true;;
L'expression identityidentity n'est pas polymorphe.
Une application pourrait produire des effets de bords — lecture et
écriture — avec des types différents:
let v = ref [] in v := [ 1 ]; not (List.hd v);;
Variable de type “faible”
Elle indique un type particulier pas encore connu.
let r = ref [];;
val r : '_a list ref = {contents=[]}
La valeur r n'est pas polymorphe (c'est une application).
Une variable de type '_a, dite faible, n'est pas une
variable polymorphe: elle représente un type qui sera fixé utérieurement.
r := [1]; r;;
- : int list ref = {contents=[1]}
r := [true];;
Characters 0-1:
This expression has type int list ref but is here used with
type bool list ref
Les variables peuvent se retrouver afaiblies involontairement:
let map_apply = List.map (fun (f,x) -> f x);;
val map_apply : (('_a -> '_b) * '_a) list -> '_b list = <fun>
perdant ainsi le polymorphisme.
Pour conserver le polymorphisme, il suffit de retarder la spécialisation de
la fonction en passant un argument supplémentaire:
let map_apply l = List.map (fun (f,x) -> f x) l;;
val map_apply : (('a -> 'b) * 'a) list -> 'b list = <fun>
Cela ne change pas le sens lorsque la fonction attend de toute façon un
argument supplémentaire.
Calculs gelés
L'application d'une fonction à un argument effectue le calcul immédiatement.
Il est parfois souhaitable de retarder le calcul
•
Pour éviter un gros calcul inutile.
•
Pour retarder ou répéter les effets de bord associé au calcul.
On peut contrôler le moment d'exécution des calculs à l'aide de
l'abstraction et de l'application.
let plus_tard f x = fun () -> f x;;
let un = plus_tard print_int 3;;
let mark = plus_tard print_string "*";;
mark(); un(); mark();;
*3*- : unit = ()
Exercise 16(Gelé les calculs)
On considère le programme:
let ifzéro n sioui sinon = if n = 0 then sioui else sinon;;
ifzéro 3 (print_string "oui") (print_string "non");;
Expliquer l'anomalie.
Corriger cette anomalie en redéfinissant la fonction
ifzéro avec le type int -> (unit -> 'a) -> (unit -> 'a) -> 'a. On donnera le programme
corrigé complet.
Exercise 17(Calculs paresseux) Un stream est une liste potentiellement infinie.
Elle doit bien sûr être représentée de façon finie, les calculs des
s'effectuant paresseusement au fur et à mesure des besoins et mémorisés pour
une relecture ultérieure.
On peut le représenter par le type concret suivant:
type 'a stream = 'a status ref
and 'a status =
Nil
| Cons of 'a * 'a stream
| Exception of exn
| Frozen of (unit -> ('a * 'a stream));;
Un stream dont le statut est une exception est un stream dont l'évaluation
a lancé (et donc devra relancer) cette exception.
1. Définir les fonctions hd, tl et nth sur les streams
qui retournent le premier élément, le reste du stream, et le nième
élément. (On aura avantageusement factoriser le code de hd et tl
en utilisant une fonction auxiliaire next.)
2. Donnez également des fonctions de construction
nil, cons : 'a -> 'astream -> 'astream
et une fonction freeze : (unit -> ('a * 'astream)) -> 'astream,
qui retourne le stream vide, ajoute un élément explicite
en tête d'un stream et construit un stream à partir d'une fonction
génératrice.
3. Définir une fonction filter : ('a -> bool) -> 'astream -> 'astream
qui prend un prédicat et un stream et retourne le stream des éléments qui
satisfont le prédicat. En déduire le stream des entiers pairs à partir
du stream des entiers.
4. En déduire une fonction crible qui prend un stream d'entiers
s et qui retourne le sous-stream des éléments qui ne sont pas
divisibles par les éléments qui les précédent. En déduire le stream des
entiers premiers.
5. Les streams proposés sont rémanants, c'est-à-dire qu'ils peuvent être relus
plusieurs fois (une fois lue, les éléments du début d'un stream sont chaînés
comme ceux d'une liste). Cela a un coût important d'une part en temps de
calcul par la gestion de cette rémanence, d'autre part en espace mémoire.
Cela n'est souvent pas nécessaire. Par exemple, si on veut se contenter
d'énumérer les nombres premiers, on peut se contenter de streams purement
fonctionnels permettant simplement une évaluation retardée à la demande.
Refaire l'exercice en utilisant la structure de donnée plus simple:
type 'a delay = Delay of (unit -> 'a * 'a delay);;
Pourquoi utilise-t-on un constructeur, puisqu'il n'y a qu'un seul cas?
Définir une fonction first de type int -> 'adelay -> 'alist
qui calcule et place les n premières valeurs dans une liste.
Calculer les 13 premières valeurs du streem des entiers.
On peut seulement ajouter de nouvelles définitions à la fin du programme.
Réutilisation du code par “couper-coller”.
Pas de partage de code:
•
duplication du code, et des erreurs!
•
difficulté de maintenance.
Pas de protection du code:
•
Pas de types abstrait.
•
Abstraction de valeur, seulement.
La programmation modulaire
Découpage du programme en morceaux compilables indépendamment
Rendre les gros programmes compilables
Donner de la structure au programme
Rendre les gros programmes compréhensibles
Spécifier les liens (interfaces) entre les composantes
Rendre les gros programmes maintenables
Identifier des sous-composantes indépendantes
Rendre les composantes réutilisables
Deux approches
Programmation par objets
Les objets sont définis à partir de classes.
Les classes peuvent être construites à partir d'autres classes par
héritage.
Un langage de module très riche
Les modules de bases permutent de contrôler la visibilité des
champs en cachant certains définitions de valeurs ou de types.
Les foncteurs sont des fonctions des modules vers les modules, permettant de
générer de nouveaux modules à partir d'autres.
Les modules sont également le support du mécanisme de compilation séparée.
Modules et compilation séparée
Une unité de compilation A se compose de deux fichiers:
•
Le fichier d'implémentation a.ml:
une suite de phrases.
•
Le fichier d'interface a.mli (optionnel):
une suite de spécifications.
Une autre unité de compilation B peut faire référence à A comme si
c'était une structure, en utilisant la notation pointée
A.x ou bien en faisant openA.
Les spécifications sont (essentiellement):
spécification de valeurs
valx : σ
spécification de types abstraits
typet
spécification de types manifestes
typet = τ
spécification d'exceptions
exceptionE
Compilation séparée d'un programme
Fichiers sources: a.ml, a.mli, b.ml
Étapes de compilation:
ocamlc -c a.mli
compile l'interface de A
crée a.cmi
ocamlc -c a.ml
compile l'implémentation de A
crée
a.cmo
ocamlc -c b.ml
compile l'implémentation de B
crée b.cmo
ocamlc -o monprog a.cmo b.cmo édition de liens finale
L'ordre des définitions de modules correspond à l'ordre des fichiers
objets .cmo sur la ligne de commande de l'éditeur de liens.
Utilisation de la commande make
La commande make permet de maintenir à jour une application
composée de plusieurs composantes, indépendemment du langage (C, tex, ocaml,
etc.).
Elle utilise un fichier Makefile (par défaut dans le directory
courant) qui décrit les fichiers sources, les fichiers à fabriquer,
la façon de les fabriquer, ainsi que les dépendences.
module T =
struct
module R = structlet x = 0 endlet y = R.x + 1
end;;
La notation pointée et la construction open s'étendent naturellement
aux sous-modules:
module Q =
structlet z = T.R.x
open T.R
...
end
NB: La notation openT.R rend les composantes de T.R
visibles dans la suite du corps de Q mais n'ajoute pas ces composantes
à Q.
Les types des modules de base
Les signatures: collections de spécifications (de types).
sig spécification …spécification end
spécification de valeurs
valx : σ
spécification de types abstraits
typet
spécification de types manifestes
typet = τ
spécification d'exceptions
exceptionE
spécification de sous-modules
moduleX : M
spécification de type de module
moduletypeS [ = M]
Nommage d'un type de module: par la liaison moduletype
module type MA_SIGNATURE = sig ... end
Synthèse de signature
Le système infère les signatures des modules (comme il infère les types des
valeurs).
Module
module Exemple =
structtype t = int
module R =
structlet x = 0
endlet y = R.x + 1
end;;
Signature inférée
module Exemple :
sigtype t = int
module R :
sigval x : int
endval y : int
end
Restriction par une signature
La construction (structure : signature)
•
vérifie que la structure satisfait la signature
(toutes les composantes spécifiées dans la signature doivent être
définies dans la structure, avec des types au moins aussi généraux);
•
rend inaccessibles les parties de la structure qui ne sont
pas spécifiées dans la signature;
•
produit un résultat qui peut être lié par module M = …
Sucre syntaxique:
est équivalent à:
moduleX : S = M
moduleX = (M : S)
Utilisée pour masquer des composantes et des types.
Restriction (Écritures équivalentes)
module M =
(structtype t = int
let x = 1
let y = x + 1
end :
sigtype t
val y : t
end)
;;
module type S =
sigtype t
val y : t
end
module M : S =
structtype t = int
let x = 1
let y = x + 1
end;;
M.x;; (* ``S.x is unbound'' *)
M.y + 1;; (* ``S.y is not of type int'' *)
Vues isomorphes incompatibles
Il est parfois important de distinguer des types isomorphes.
Par exemples Euros et Dollars sont tous deux représentés par des flottants.
Pourtant, il ne faut pas les confondre.
Ce sont deux espaces vectoriels, isomorphes mais disjoints, avec pour unités
respectives l'euro et le dollar.
module Float =
structtype t = float
let un = 1.0
let plus = (+.)
let prod = ( *. )
end;;
module type MONNAIE =
sigtype t
val un : t
val plus : t -> t -> t
val prod : float -> t -> t
end;;
La multiplication devient une opération externe sur les flottants.
Monnaies incompatibles
Dans Float le type t est concret donc il peut être confondu avec
"float". Par contre, il est abstrait dans les modules Euro et
Dollar ci-dessous:
module Euro = (Float : MONNAIE);;
module Dollar = (Float : MONNAIE);;
Les types Euro.t et Dollar.t sont isomorphes mais incompatibles.
let euro x = Euro.prod x Euro.un;;
Euro.plus (euro 10.0) (euro 20.0);;
Euro.plus (euro 50.0) Dollar.un;; Erreur
Pas de duplication de code entre Euro et Dollar.
Vues multiples d'un même module
On peut donner une interface restreinte pour, dans un certain contexte, ne
permettre que certaines opérations (typiquement, interdire la création de
valeurs):
module type PLUS =
sigtype t
val plus : t -> t -> t
end;;
module Plus = (Euro : PLUS)
module type PLUS_Euro =
sigtype t = Euro.t
val plus : t -> t -> t
end;;
module Plus = (Euro : PLUS_Euro)
À gauche, le type Plus.t est incompatible avec Euro.t.
À droite, le type t est partiellement abstrait et compatible avec
"Euro.t", et la vue Plus permet de manipuler les valeurs construites
avec la vue Euro.
La notation with
La notation with permet d'ajouter des égalités de types dans une
signature existante.
L'expression PLUSwithtypet = Euro.t est une abréviation
pour la signature
sigtype t = Euro.t
val plus: t -> t -> t
end
On peut alors écrire
module Plus = (Euro : PLUS withtype t = Euro.t);;
Plus.plus Euro.un Euro.un;;
Elle permet de créer facilement des signatures partiellement abstraites.
Modules paramétrés
Un foncteur est une fonction des modules dans les modules:
functor (S : signature) ->module
Le module (corps du foncteur) est explicitement paramétré par
le paramètre de module S. Il fait référence aux composantes de
son paramètre avec la notation pointée.
module F = functor(X : S) ->
structtype u = X.t * X.t
let y = X.g X.v
end;;
Utilisation des modules paramétrés
Définir des structures qui dépendent d'autres
•
Les librairies
Map,
Set,
Hashtbl,
etc. dépendent d'une fonction de
comparaison.
Le type des éléments avec leur fonction de comparaison:
module type OrderedType = sigtype t
val compare : t -> t -> int
end;;
Les polynômes sont définis par rapport à une structure d'anneau
sur les coefficients.
Application de foncteur
On ne peut pas directement accéder au corps d'un foncteur. Il faut au préalable
l'appliquer explicitement à une implémentation de la signature de son argument
(tout comme on applique une fonction ordinaire).
module P1 = F(M1)
module P2 = F(M2)
P1, P2 s'utilisent alors comme des structures ordinaires:
(P1.y : P2.u)
P1 et P2 partagent entièrement leur code.
Exemple: les ensembles d'entiers
module IntSet =
Set.Make
(structtype t = int let compare = compare end);;
Modules et compilation séparée
Fichiers sources: a.ml, a.mli, b.mlB utilse A.
Le programme se comporte comme le code monolithique:
module A =
(struct(* contenu de a.ml *)end
: sig(* contenu de a.mli *)end)
module B = struct(* contenu de b.ml *)end
Réaliser une bibliothèque fournissant les opérations sur les polynômes à une
variable.
Les coefficients forment un anneau passé en argument à la bibliothèque.
Vérifier l'égalité (X + Y) (X −Y) = (X2 − Y2)
en considérant les polynômes à deux variables comme polynôme en X
à coefficients les polynôme en Y.
•
Écrire un programme qui prend un polynôme sur la ligne de commande et
l'évalue en chacun des points lus dans stdin (un entier par
ligne) et imprime le résultat dans stdout.
Utiliser la commande make pour compiler le programme.
Exercices.
Menu conseillé
Mise en œuvre
•
C'est un point de passage obligé (exercices 1, 2 et 3 du menu).
•
Faire ces exercices en regardant les solutions.
Petits exercices
•
On peut les mettre au point “en mode calculette”
(en les écrivant dans un fichier sous emacs et en exécutant les commandes au
fur et à mesure).
•
Faire les exercices plus conséquents en mode compilé.
•
En faire au moins deux sans avoir regardé la solution.
Choisir un exercice plus conséquent
•
En choisir un et le faire sans regarder la solution.
•
En cas d'échec, refaire de petits exercices...
En dernier
•
Un exercice plus difficile, par exemple, sur les polynômes.
Quelques tuyaux
Relire le cours de façon interactive
•
en cliquant sur tous les pointeurs disponibles (et récursivement à la
profondeur qui vous plaira).
Même si vous ne lisez que les premières lignes des documents pointez,
vous connaitrez au moins leur existence.
•
en faisant tous les exercices du cours au fur et à mesure.
Gardez le cours et la documentation sous la main
Si possible en parallèle une fenêtre de votre brouteur et une fenêtre
emacs sur le même écran: on programme avec la documentation ou des exemples
sous les yeux.
Exercise 20(Nombres complexes)
Définir un type complex pour représenter les nombres complexes en
coordonnées cartésiennes (on choisira des coefficinets flottants).
Implémenter (une version simplifiée du module) de ce module,
en utilisant l'égalité générique comme comparaison.
(On ne s'autorise que la fonction hash du module Hashtbl).
Pourquoi y a-t-il une également une interface fonctionnelle?
