Initiation au langage OCaml.

Postscript, PDFDidier RémyPolytechnique, INRIA

Travaux Dirigés

avec Fabrice Le Fessant et Maxence Guesdon
avec les contributions significatives de
Luc Maranget, David Monniaux, et Benjamin Monate

Avec menu[Manuel][Modules][TD - 1, 2, 2b, 3, 4 ]Exercices
  1. Introduction, pointeurs
  2. Syntaxe, Erreurs fréquentes
  3. Types et opérations primitives
  4. Enregistrements, références
  5. Entrées sorties
  6. Fonctions
  7. Variantes et filtrage
  8. Exceptions
  9. Mise au point
  10. Polymorphisme
  11. Programmation modulaire
  12. Compilation séparée
  13. Modules
  1. Mode compilé ou interprété
  2. Mode Emacs, Makefile
  3. Entrées-sorties (*): true, echo, cat
  4. Fibonnacci (*), Complexes (*)
  5. Listes doubles (**), Sigma (*)
  6. Exceptions (**) Glaçons (*)
  7. Jeu de cartes (**),
  8. Calculette (**)
  9. Commandes (**): grep, agrep, wc
  10. Nombres premiers (***)
  11. Librairies (*):List, Array, Hashtbl
  12. Polynômes (***)

    

Motivation

Pour l'enseignement

Le langage OCaml est utilisé en particulier
    •Langages de Programmation (majeure 1)
    •Modularité, Objets, et Types (majeure 1)
    •Programmation Système (majeure 2)
    •Compilation (majeure 2)
+ Certains stages d'options en informatique.

Après l'X
    •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,
    •y compris le vôtre.

En se référant à la définition du langage
    •la documentation: le manuel de référence, la librairie du noyau et les librairies standards;
    •le tutorial, l'expérience des autres (FAQ);
    •introspection d'OCaml;
    •les librairies développées par les utilisateurs (voir aussi la page ocaml).

Profiter des informations en ligne rassemblées dans la bosse. Il existe aussi plusieurs livres sur Caml-Light ou OCaml.

La petite histoire

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.).

Domaines d'utilisation du langage OCaml

Mais aussi…

Industrie
    •Startups, CEA, EDF, France Telecom, Simulog,...

Gros Logiciels
    •Coq, Ensemble, ASTREE, (voir la bosse d'OCaml)

Plus récemment, outils système
    •Unison,
    •MLdonkey (peer-to-peer),
    •Libre cours (Site WEB),
    •Lindows (outils système pour une distribution de Linux)

Quelques mots clés

Le langage OCaml est:
    •fonctionnel: les fonctions sont des valeurs de première classe, elles peuvent être retournées en résultat et passées en argument à d'autres fonctions.
    •à gestion mémoire automatique (comme JAVA)
    •fortement typé: le typage garantit l'absence d'erreur (de la machine) à l'exécution.
    •avec synthèse de types: les types sont facultatifs et synthétisés par le système.
    •compilé ou interactif (mode interactif = grosse calculette)


De plus le langage possède:
    •une couche à objets assez sophistiquée,
    •un système de modules très expressif.

Premiers pas en OCaml.

Le mode compilé

Éditer le source

hello.ml
print_string "Hello World!\n";;

Compiler, lier et exécuter

Sous le Shell d'Unix
ocamlc -o hello hello.ml ./hello
Hello World!

Le mode interprété

Mode interactif avec l'utilisateur:

Sous le shell d'Unix
ocaml
Objective Caml version 3.06
print_string "Hello World!\n";;
Hello World! - : unit = ()
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:

bonjour
#!/usr/bin/ocamlrun /usr/bin/ocaml print_string "Bonjour!"; print_newline();;
Sous le Shell d'Unix
chmod +x bonjour bonjour

Le mode caml pour Emacs

Installation (si nécessaire)

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    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

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  let x = e1 in e2
  (définition locale de fonctions mutuellement récursives)
– 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

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 in let 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);;
Exercise 1   Que fait ce code?
Answer


Le modifier le code pour filtrer selon un préfixe donné.

Remarques

Il n'y a ni instructions ni procédures.
Toutes les expressions retournent une valeur.
    •La valeur unité () de type unit ne porte aucune information (c'est l'unique valeur possible dans son type).

print_int: int -> unit
print_string: string -> unit

    •L'expression e dans les boucles for et while et dans la séquence doit être de type unit.
    •Si nécesaire, jeter explicitement le résultat, en utilisant

– une fonction (prédéfinie):-1.5em
let ignore x = ();;
ignore : 'a -> unit
ignore e1; e2 : unit
 – ou une définition:-1.5em
let _ = e1 in e2

Ne pas confondre

La liaison toplevel
let x = 1;; let f x = x + 1;; let y = f x;;
les ;; intermédiaires sont optionnels
 La liaison locale
let y = let x = 1 in let f x = x + 1 in f x;;
Une seule phrase toplevel et deux liaisons locales

La séquence

let sequence = print_string "vitesse = "; print_int 10; print_newline ()

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!
booltrue   false&&   ||   not
char'a'   '\n'   '\097'code   chr
int1   2   3+   -   *   /   max_int
float1.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, (+) x1 x2 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 |]   :  int  array 
[| truefalse |]   :  bool  array 

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.

fun x -> x.(0)   :  'a array -> 'a 
fun t k x -> t.(k) <- x   :  'a array -> int -> 'a -> unit 

Les tableaux sont toujours initialisées:

Array.create  :  int -> 'a -> 'a  array 

- 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

let rec fact n = if n > 1 then n * fact (n -1) else 1;;

... et mutuellement récursives

let rec 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):
 f x y (f xy f (x y(f(x))(y)
Answer

Application partielle

Une fonction à deux arguments peut n'en recevoir qu'un seul.

let plus x y = x + y;;
val plus : int -> int -> int = <fun>
let incr2 = plus 2;;
val incr2 : int -> int = <fun>

La fonction incr2 est équivalente à fun y -> plus 2 y  Remarque: on aurait pu écrire:

let plus = ( + );;

Abstraction

Exercise 3   On suppose que f est de type int -> int -> int . Quelle différence y a-t-il entre:
 ffun x -> f x  fun x y -> f x y  
Montrer le cas échéant la différence sur un exemple.

Indication: on pourra choisir une fonction f qui fait des effets de bord   

Answer

Les enregistrements

Il faut les déclarer au préalable

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.

1 = 1 && [|2|] = [|2|] && "un" = "un" && ref 1 = ref 1
- : bool = true

É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.

[] = [] && [ 1 ] != [ 1 ] && "eq" != "eq" && 1.0 != 1.0 && ref 1 != ref 1 && (let x = ref 1 in x == fst (x, x))
- : bool = true

Égalité (exercice)

Exercise 4   Quelles sont les égalitées vraies?
1 == 1;; 1L == 1L;; nan = nan;; nan == nan;; 'a' == 'a';; type nat = Zero | Succ of nat;; Zero == Zero;; Succ Zero == Succ Zero;;
Answer

    Utilisez l'égalité structurelle de préférence.
    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 : string array

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é).
Answer

Usage avancé

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).
Answer

Les entrées-sorties

Canaux pré-définis
stdin  :  in_channel
stdout  :  out_channel
stderr  :  out_channel
 Ouverture de canaux
open_out  :  string -> out_channel 
open_in  :  string -> in_channel 
close_out  :  out_channel -> unit 
Lecture sur stdin
read_line  :  unit -> string 
read_int  :  unit -> int 
 Écriture sur stdout
print_string  :  string -> unit 
print_int  :  int -> unit 

Les entrées sorties avancées
    •Voir la librairie noyau
    •Voir la librairie Printf par exemple, on écrira comme en C:

Printf.printf "%d %s %d = %d\n" 2 "+" 3 (2+3);;

La puissance des fonctions

Les fonctions sont des valeurs comme les autres
    •En particulier, elles peuvent être retournées en résultat et passées en argument à d'autres fonctions.
    •Les fonctions se manipulent comme en mathématiques.

La composition de deux fonctions est une fonction

let compose f g = fun x -> f (g x);;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

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 fun x -> f (g x 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

let rec 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;;
val derivative : float -> (float -> float) -> float -> float = <fun>

La dérivée nème est la puissance n de la dérivée. Soit!

let pi = 4.0 *. atan 1.0;; let sin''' = (power (derivative 1e-5) 3) sin in sin''' pi;;
- : float = 0.99999897...

à la précision des calculs numériques près...

Les variantes et le filtrage

Les définitions de types sommes

Analogues aux définitions de types d'enregistrements.
Par exemple, les booléens sont éléments du type suivant:

type boolean = Vrai | Faux;; let t = Vrai and f = Faux;;
Les constructeurs sont toujours capitalisés

Le filtrage permet d'examiner les valeurs d'un type somme.

let int_of_boolean x = match x with Vrai -> 0 | Faux -> 1;;

Raccourci (notation équivalente)

let int_of_boolean = function Vrai -> 0 | Faux -> 1;;

Le type option

Les références sont toujours initialisées en OCaml. Il peut être nécessaire de créer des références qui seront définies plus tard.

Ce traitement doit être explicite.

Prédéfini par le système

type 'a option = Some of 'a | None let statut = ref None;;

Plus tard, on pourra définir la valeur:

statut := Some 3;;

La lecture du statut doit aussi considéré le cas où celui-ci est indéfini.

match !statut with Some x -> x | None -> 0;;

Les listes

Les (fausses) listes sont simplement un type somme récursif

Types récursifs
type 'a liste = Vide | Cellule of 'a * 'a liste;;
 


FaussesVraies
'a liste'a list
Vide[ ]
Cellule (t,r)t :: r

Définition alternative (utilisant un enregistrement)

type 'a liste = Vide | Cellule of 'a cell and 'a cell = { tête : 'a; reste : 'a liste };;

Listes modifiables en place (les champs sont mutables)

type 'a liste = Vide | Cellule of 'a cell and 'a cell = { mutable hd : 'a; mutable tl : 'a liste };;

Les vraies listes (librairie List)

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.

let rec 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 = let rec 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).
Answer
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).
Answer
Écrire une autre version de la fonction dédouble qui n'utilise pas de référence (on s'inpirera de la fonction reverse ci-dessus).
Answer
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.

Answer

Voici un exemple de recherche:

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).

Answer

Exercise 9 (La fonction Sigma)  
  1. 2em Écrire une fonction sigma : ('a -> int) -> 'a list -> int telle que l'expression sigma f l calcule la formule xl f(x).
  2. Écrire la fonction pi : ('a -> int) -> 'a list -> int analogue mais en remplaçant la somme par le produit.
  3. Comment généraliser la fonction, de façon à partager le code en commun, en une fonction
    fold : (int -> int -> int) -> int -> ('a -> int) -> 'a list -> 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).
  4. Réécrire la fonction sigma en utilisant une fonction de librairie.

Les exceptions (exemple)

exception Perdu let rec 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 = try let 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.
Answer

Syntaxe

– Définition (phrase)exception C [ of t ]
– Levée (expression)raise e
– Filtrage (expression)try e with p1 -> e1 … ∣ pn -> en

Remarquer l'analogie avec la construction de filtrage.

Exceptions pré-définis

ExceptionUsagegravité
Invalid_argument of string  accès en dehors des bornes forte
Failure of string  liste vide, retourne le nom de la fonction moyenne
Not_found of unit  fonctions de recherche nulle
Match_failure of ...  É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:

try while true do print_string (read_line()); print_newline() done with 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.
Answer

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:
ocamlc -o grep str.cma grep.ml
ou bien la commande Makefile générique avec LIBS=str.
Answer

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.)

Answer

Une limitation est que le motif ne peut pas se superposer sur plusieurs lignes. Lever cette limitation.

Answer

De même le délimiteur ne peut pas se superposer sur plusieurs lignes. Comment peut-on lever cette limitation?

Answer

1
Les ' sont les quotation du shell, mais ne font pas partie de l'argument passé par le shell à agrep.

Exercices

Exercise 14 (La calculette)  

- Écrire une fonction sigma qui prend une fonction f, un tableau et deux indices et qui calcule i = jk f (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.

Answer

- 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.

Answer

- Écrire un Makefile manuellement.

Answer

- Utiliser le Makefile générique

Exercices (suite)

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.
Answer

La trace (mode interactif)

Fonctionne seulement en mode interprété à l'aide de directives

Mise en œuvre

let observe x y = x + y;; #trace observe;; #untrace observe;; #untrace_all;;

Changer l'imprimeur par défaut
La trace se combine souvent avec l'ajout d'imprimeurs

let imprimeur x = Printf.printf "%d0" x;; #install_printer imprimeur;; 1;; #remove_printer imprimeur;;

L'argument imprimeur est le nom d'une fonction de type τ -> unit avec laquelle les valeurs du types τ seront imprimées.

Le débogueur

Fonctionne seulement en mode compilé.

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 ocamldebug nom-du-programme

Il existe une interface conviviale pour Emacs: appeler la commande camldebug (taper ESC X camldebug nom-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.

export OCAMLRUNPARAM=b ./mon_programme ses_arguments

Les abréviations

type donnée = int * int array

L'algèbre des types

– Constantes de type    int     char     ...
– Types sommes    list     ...
– Types abstraits    in_channel
– Paires    τ1 * τ2
– Flèches    τ1 -> τ2
– Tuples    1, ... τn)
– Enregistrements    {l1 : τ1; ... ln : τn}

Les types abstraits

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 identity identity  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.

Answer

Streams

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.)

Answer

2. Donnez également des fonctions de construction nil, cons : 'a -> 'a stream -> 'a stream  et une fonction freeze : (unit -> ('a * 'a stream)) -> 'a stream , 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.

Answer

Construire le stream des entiers pairs.

Answer

3. Définir une fonction filter : ('a -> bool) -> 'a stream -> 'a stream  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.

Answer

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.

Answer

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?

Answer

Écrire le stream des entiers.

Answer

Définir une fonction first de type int -> 'a delay -> 'a list  qui calcule et place les n premières valeurs dans une liste. Calculer les 13 premières valeurs du streem des entiers.

Answer

Réécrire les fonctions filter et crible. En déduire une fonction premiers qui prend un entier k et retourne la liste des k premiers nombres entiers.

Answer

La programmation traditionnelle

Les programmes sont écrits de façon linéaire.

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 open A.

Les spécifications sont (essentiellement):

spécification de valeursval x : σ
spécification de types abstraitstype t
spécification de types manifestestype t = τ
spécification d'exceptionsexception E

Compilation séparée d'un programme

Fichiers sources: a.ml, a.mli, b.ml

Étapes de compilation:

ocamlc -c a.mlicompile l'interface de Acrée a.cmi
ocamlc -c a.mlcompile l'implémentation de Acrée a.cmo
ocamlc -c b.mlcompile l'implémentation de Bcré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.

Un Makefile spécifique

On peut écrire un fichier Makefile spécialisé pour chaque application. Par exemple, celui-ci fonctionne pour l'ensemble des exercices de ce cours.

Le Makefile générique

Le Makefile générique pour OCaml, écrit par Markus Mottl, couvre la plupart des situations.
    •Copier Makefile dans votre dossier de travail.
    •Éditer les variables SOURCES et RESULT

(au plus un exécutable à la fois)

    •Faire make

Mode graphique Il suffit d'ajouter la définition suivante:

LIBS= graphics

Voir README pour en savoir plus sur les autres commandes.

Pour installer le Makefile générique chez vous, il vous suffit de copier OCamlMakefile et d'ajuster le chemin d'accès dans le modèle Makefile

Voir README pour en savoir plus

Modules.

Les modules en quelques mots

    •Un petit langage fonctionnel typé

    •pour manipuler des collections de définitions (de valeurs, de types) du langage de base.

    •Leurs types: des collections de déclarations/spécifications (types des valeurs, déclarations des types).

    •Modules emboîtés.
    •Fonctions (foncteurs) et application de fonctions.
Largement indépendant du langage de base.

Modules de base

Les structures sont collections de phrases

    struct p1pn end

Les phrases sont celles du langage de base, plus

définition de sous-modules   module X = …
définition de type de module   module type  S = …

Le nommage d'un module se fait à l'aide de la liaison module.

module S = struct type t = int let x = 0 let f x = x+1 end;;

Utilisation d'un module

On fait référence aux composantes d'un module avec la notation pointée module.composante

... (S.f S.x : S.t) ...

Autre possibilité: la directive open module permet d'omettre le préfixe et le point:

open S ... (f x : t) ...

Exemples:

    List.map

    Hastbl.find

    Pervasives.exit

Modules emboîtés

Un module peut être composante d'un autre module:

module T = struct module R = struct let x = 0 end let y = R.x + 1 end;;

La notation pointée et la construction open s'étendent naturellement aux sous-modules:

module Q = struct let z = T.R.x open T.R ... end
 NB: La notation open T.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écificationspécification end
spécification de valeursval x :  σ
spécification de types abstraitstype t
spécification de types manifestestype t = τ
spécification d'exceptionsexception E
spécification de sous-modulesmodule X : M
spécification de type de modulemodule type  S  [ = M]

Nommage d'un type de module: par la liaison module type 

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 = struct type t = int module R = struct let x = 0 end let y = R.x + 1 end;;
 
Signature inférée
module Exemple : sig type t = int module R : sig val x : int end val 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 à:
  module X : S = M   module X = (M : S

Utilisée pour masquer des composantes et des types.

Restriction (Écritures équivalentes)

module M = (struct type t = int let x = 1 let y = x + 1 end : sig type t val y : t end) ;;
 
module type S = sig type t val y : t end module M : S = struct type 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 = struct type t = float let un = 1.0 let plus = (+.) let prod = ( *. ) end;;
 
module type MONNAIE = sig type 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 = sig type t val plus : t -> t -> t end;; module Plus = (Euro : PLUS)
 
module type PLUS_Euro = sig type 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 PLUS with type t = Euro.t  est une abréviation pour la signature

sig type t = Euro.t val plus: t -> t -> t end

On peut alors écrire

module Plus = (Euro : PLUS with type 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) -> struct type 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 = sig type t val compare : t -> t -> int end;;

Le type des ensembles

module type S = sig .. end

Le foncteur qui “fabrique” des implémentations:

module Make: functor (Ord : OrderedType) -> S with type elt = Ord.t

    •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 (struct type t = int let compare = compare end);;

Modules et compilation séparée

Fichiers sources: a.ml, a.mli, b.ml B 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

Exercice

Exercise 18 (Polynômes à une variable (***))  
    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.
    Utiliser la bibliothèque pour vérifier par exemple l'égalité (1 + X) (1 − X) = 1 − X2.
    Vérifier l'égalité (X + Y) (XY) = (X2Y2) 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é

  1. Mise en œuvre
        •C'est un point de passage obligé (exercices 1, 2 et 3 du menu).
        •Faire ces exercices en regardant les solutions.
  2. 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.

  3. Choisir un exercice plus conséquent
        •En choisir un et le faire sans regarder la solution.
        •En cas d'échec, refaire de petits exercices...
  4. 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.

A  Exercices

Calculs numériques

Fonctions récursives, simple ou multiples, avec calculs sur les nombres.

Exercise 19 (Fibonnaci)   Écrire, en mode intéractif, la fonction de fibonnaci définie par induction
fib(n) = 

1if n = 0 ou n= 1
fib (n−1) + fib (n−2)otherwise
Answer
Fabriquer un exécutable qui prend son argument sur la ligne de commande.
Answer

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).
Answer
Définir l'addition ++ et la multiplication ** sur les nombres complexes.
Answer
En déduire la calcul de (zn) = (1 + i/10)n et la valeur de z99.
Answer
Donner le calcul à l'aide de la fonction power définie ci-dessus.
Answer

Les librairies

Exercise 21 (Listes)   Consulter la librairie List.

Implémenter la fonction length

Answer

La fonction est-elle tail-récursive? (Donner, le cas échéant, une version fonctionnelle (qui n'utilise pas de référence) en récursion terminale.

Answer

Implémenter la fonction find.

Answer

Implémenter d'autres fonctions de la librairie...

Exercise 22   Consulter et comparer les librairies Array et String.

On se propose de réimplémenter les opérations sur les tableaux en utilisant seulement les fonctions length et make.

Donner les opérations get et set.

Answer

Impémenter l'opération init

Answer

Implémenter l'opération make_matrix;;

Answer

Implémenter l'opération blit:

Answer

Comparer la librairie String avec la librairie Array.

Exercise 23 (Les libairies)   Consulter la librairie Hashtbl.

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?

Answer

Donner un exemple d'utilisation de la version fonctorisée.

Answer
    

Ce document a été traduit de LATEX par HEVEA