Majeure 2
Rattrapage Caml
bis

Jean-Jacques Lévy
jean-jacques.levy@inria.fr

14 janvier 1998

Les supports de cours sont en

http://www.polytechnique.fr/poly/edu/informatique/
http://www.polytechnique.fr/poly/~gonthier/
http://www.polytechnique.fr/poly/~levy/
http://www.polytechnique.fr/poly/~weis/
http://pauillac.inria.fr/~levy/x/annexe-caml/node39.html

Introduction

• Caml-light 0.74 est un dialecte de ML = Lisp + types
• Gestion automatique de la mémoire
• Appel de procédures avec filtrage
• Fonctionalité arbitraire
• Modularité, types de données abstraits
• Types polymorphes
• OCaml = Caml orienté objets + compilateur code natif
• Caml-light tourne en peu de mémoire, système à byte-code

Les langages

Pascal C Java Caml

presque sûr indicatif sûr sûr

Typage record case coercions dynamique paramétré

manuel manuel manuel auto

Pointeurs explicites centraux auto auto

Objets non non centraux O'Caml

Syntaxe du langage

• Directives: ouvrir un module, pour désigner les variables sans mettre le nom de leur module.

  #open "printf" ;;
  #open "graphics" ;;
  #open "mon_module" ;;
  

• Définitions: une variable est un nom donné à une valeur ou fonction. Définir une variable fixe à la fois sa valeur et son type.

  let quatre = 2+2;;
  let carre n = n*n;; 
  let triangle n =
     let rectangle = n * (n+1) in
     rectangle/2;;
  

La date de Pâques

Lilius et Clavius en 16xx (Knuth vol1, p.155); soit Y< 100000:

1. [Nombre d'or] G = (Y mod 19) + 1

2. [Siècle] C = Entier(Y/100) + 1

3. [Corrections] X = Entier(3 C / 4) - 12 Z = Entier((8 C + 5) /25) - 5

4. [Un dimanche] D = Entier(5 Y / 4) - X - 10

5. [Epact.] E = (11 G + 20 + Z - X) mod 30, E <- E+1 si E = 24, ou E = 25 et G > 11

6. [Pleine lune] N = 44 - E, mais N <- N + 30 si N < 21

7. [Le jour] J = N + 7 - ((D + N) mod 7)

8. [Le mois] la date est le J Mars si J31, le J-31 Avril sinon.

La date de Pâques en Caml

let paques y =
  let g = y mod 19 +1 in
  let c = y / 100 + 1 in
  let x = (3*c) / 4 - 12 and z = (8*c+5) / 25 - 5 in
  let d = (5*y) / 4 - x - 10 in
  let e = let e' = (11*g + 20 + z - x) mod 30 in
          if e'=24 || e'=25 && g>11 then e'+1 else e' in
  let n = let n' = 44-e in if n'<21 then n'+30 else n' in
  n + 7 - (d+n) mod 7;;
let mois j = if j<=31 then "Mars" else "Avril";;
let jour j = if j<=31 then j else j-31;;
#jour (paques 1998);; mois (paques 1998);;
- : int = 12
- : string = "Avril"

Les types, valeurs, et primitives

type valeurs opérations

int 0,1,2,-2 + - * / mod = <> < > <= >=

bool true,false not && || if..then..else

float 1.0,-3.5,1E3 +. -. *. /. ** sin = <> < > <= >=

string "la tete a toto" string_length ^ = <> < > <= >=

Conversions explicites float_of_int, int_of_float, string_of_int, $\ldots$

Les fonctions

En Caml, on ne met pas de parenthèses autour des arguments.

#let norme2 dx dy = dx**2.0 +. dy**2.0;;
norme2 : float -> float -> float = <fun>

Mais, il faut parenthéser chaque argument qui est une expression.

#let dist x y x' y' = sqrt (norme2 (x-.x') (y-.y'));;
dist : float -> float -> float -> float -> float = <fun>

Messages étranges quand on oublie des arguments.

#dist 0.0 0.0 1.0;;
- : float -> float = <fun>

Pour imprimer

D'abord, ouvrir le module.

#open "printf";;

L'affichage est contrôlé par un format=chaîne à trous.

let imprPaques y =
  let j = paques y in
  printf "Le %2d %s %d\n" (jour j) (mois j) y;;
imprPaques 1998;;
Le 12 Avril 1998
- : unit = ()

Les trous : %d entiers (décimaux), %s chaînes, %g réels, %b booléens, $\ldots$.

Le contrôle

Séquence, tests, filtrage, boucles, échappements.

begin               if cond then instr  match val with
  instr1;                                 0 -> instr1
  instr2;           if cond then        | 1 -> instr2
  ...                 instr             ...
  instrN            else                | n -> instr(n)
end                   instr
                                        try
for i = 1 to n do   while cond do         while true do
  instr1;             instr1;               ... raise Exit
  instr2;             instr2;               ...
  ...                 ...                 done
done                done                with Exit -> ...

Références

Une référence est un objet qui peut contenir une valeur. On les crée en leur donnant un contenu initial. On utilise l'opérateur ! pour récupérer leur contenu, et := pour le modifier.

#let somme = ref 0;;
somme : int ref = ref 0
#for i = 1 to 5 do somme := !somme + i done; somme;;
- : int ref = ref 15
#!somme;;
- : int = 15

Par rapport à Pascal ou C, il suffit d'indiquer les références par des ! :

let fact n =
  let prod = ref 1 in
  for i = 1 to n do prod := !prod * i done;
  !prod;;

Les vecteurs

Comme les références, les vecteurs sont des contenants. Comme pour les chaînes, leur longueur est implicite; on peut l'obtenir avec vect_length. Les vecteurs sont toujours indicés à partir de 0.

#let produitScalaire v1 v2 =
  let n = min (vect_length v1) (vect_length v2) in
  let p = ref 0.0 in
  for i = 0 to n-1 do p := !p +. v1.(i) *. v2.(i) done;
  !p;;
produitScalaire : float vect -> float vect -> float = <fun>
#produitScalaire [| 1.0; -2.0; 3.0|] [| -1.0; 1.0; 1.0|];;

On peut créer des vecteurs de longueur donnée.

let iota n =
  let v = make_vect n 0 in
  for i = 1 to n-1 do v.(i) <- i done; v;;

Les matrices

On utilise des vecteurs de vecteurs; Attention! Utiliser make_matrix pour créer une matrice.

#let sommeMat m1 m2 =
  let h = vect_length m1 in
  let w = if h > 0 then vect_length m1.(0) else 0 in
  if h <> vect_length m2 || h>0 && h <> vect_length m2.(0) then
    failwith "sommeMat: tailles incompatibles";
  let s = make_matrix h w 0.0 in
  for i = 0 to h-1 do
    for j = 0 to w-1 do
      s.(i).(j) <- m1.(i).(j) +. m2.(i).(j)
    done
  done;
  s;;
sommeMat : float vect vect -> float vect vect -> float vect vect

Aliasing

Que donne make_vect 2 (make_vect 2 0) ?

#let m = make_vect 2 (make_vect 2 0);;
m : int vect vect = [|[|0; 0|]; [|0; 0|]|]
#m.(0).(0) <- 1; m;;
- : int vect vect = [|[|1; 0|]; [|1; 0|]|]

Récursivité

En Caml, on peut définir des fonctions récursives

#let rec f n = if n<2 then 1 else f(n-1) + f(n-2);;

mais

#let f x = x + 3 ;;
#let f n = if n<2 then 1 else f(n-1) + f(n-2);;

donnera n'importe quoi!
Attention à rec !!

Boucles vs. récursion

On peut toujours remplacer une boucle par une récursion

let rec f () = if not Cond then begin Instr; f() end;;

équivaut à

let f () = while Cond do Instr done;;

Le système Caml reconnaît cet usage (récursion terminale), et l'exécute tout aussi efficacement.

Récursion vs. références

La récursion permet de remplacer les références par un passage explicite de paramètre.

let rec total v n = if n=0 then 0.0
                    else v.(n-1) +. total v (n-1);;

Les fonctions auxiliaires peuvent être définies localement, comme les autres variables.

let somme v =
  let rec ajout i s = if i=0 then s
                      else ajout (i-1) (s +. v.(i-1)) in
  ajout (vect_length v) 0.0;;

Règle du jeu : boucles pour les itérations simples, récursion dès que les choses se compliquent.

Tri sélection

let triSel t = let n = vect_length t in
  for i = vect_length t - 1 downto 1 do
    let j = ref i in
    for k = 0 to i-1 do
      if t.(k) > t.(!j) then j := k
    done;
    let x = t.(i) in
    t.(i) <- t.(!j); t.(!j) <- x
  done;
  t;;

Tri insertion

let triIns t = 
  for i = 1 to vect_length t - 1 do
    let x = t.(i) and j = ref i in
    while !j>0 && t.(!j-1) > x do
      t.(!j) <- t.(!j-1);
      decr j
    done;
    t.(!j) <- x
  done;
  t;;

Tri par fusion

let rec triFusion t =
  let n = vect_length t in
  if n > 1 then begin
    let n1 = n/2 in let t1 = sub_vect t 0 n1 in
    let n2 = n-n1 in let t2 = sub_vect t n1 n2 in
    let rec fusion i j =
      if i<n1 && (j>=n2 || t1.(i) < t2.(j)) then
        begin t.(i+j) <- t1.(i); fusion (i+1) j end
      else if j<n2 then
        begin t.(i+j) <- t2.(j); fusion i (j+1) end in
    triFusion t1; triFusion t2; fusion 0 0
  end; t;;

Nombres complexes

type complex = Complex of float * float;;
let re (Complex(x,_)) = x;;
let im (Complex(_,y)) = y;;
let prefix +: (Complex(x1,y1)) (Complex(x2,y2)) =
  Complex(x1 +. x2, y1 +. y2);;
let prefix -: (Complex(x1,y1)) (Complex(x2,y2)) =
  Complex(x1 -. x2, y1 -. y2);;
let prefix *: (Complex(x1,y1)) (Complex(x2,y2)) =
  Complex(x1 *. x2 -. y1 *. y2,  x1 *.y2 +. x2 *. y1);;
let prefix /: (Complex(x1,y1)) (Complex(x2,y2)) =
  let n2 = x2*.x2 +. y2*.y2 in
  Complex((x1*.x2 +. y1*.y2) /. n2, (x2*.y1 -. x1*.y2) /. n2);;
let omega n =
  let a = 8.0 *. atan 1.0 /. float_of_int n in
  Complex(cos a, sin a);;

Types récursifs

Récurrences pour définir l'organisation des données = structures de données.

Par exemple les suites d'entiers [a₁ . a₂ ... a_n] peuvent être décrites ainsi; une telle suite s est

• soit la suite vide []
• soit constituée d'un premier élément a₁, et d'une sous-suite [a₂ ... a_n].

En Caml, on peut exprimer cette récurrence directement

type suiteInt = Vide | Cons of int * suiteInt;;

On utilise le filtrage pour discriminer les cas et accéder aux éléments.

Listes Caml

Les listes sont tellement utiles qu'en Caml elles ont un type prédéfini générique `a list, comme les tableaux ont `a vect.

Elles ont une syntaxe spécifique, utilisée pour la création et le filtrage :

• [] est la liste vide.

  
  

• a :: l est la liste dont le premier élément est a, et le reste est l.
  
• [a₁; a₂; $\ldots$; a_n] est la liste [a₁ a₂ ... a_n]
  
• On a

  [a;b;c] == a::[b; c]

  == a::b::[c]

  == a::b::c::[]

Récurrence sur les listes

A type récursif, fonction récursives!

let rec longueur l = match l with
   []   -> 0
| _::l' -> 1 + longueur l';;

Quelques exemples

La bibliothèque de base de Caml comprend un large assortiment de fonctions sur les listes, et particulièrement des fonctionnelles.

let rec prefix @ l1 l2 = match l1 with
  [] -> l2
| a::l1' -> a::(l1' @ l2);;
let rev l =
  let rec revapp l1 l2 = match l1 with
    [] -> l2 | a::l1' -> revapp l1' (a::l2) in
  revapp l [];;
let rec map f = function
  [] -> []
| a::l -> f a :: map f l;;
let rec exists p =
   function [] -> false | a::l -> p a || exists p l;;
let mem x l = exists (fun y -> x=y) l;;

Polynômes

On représente un polynôme une liste triée de monômes :

type 'a monome = Mono of 'a * int;;
type 'a polynome = Poly of 'a monome list;;

Par exemple

#let poly_of_list l = Poly (map Mono l);;
poly_of_list : ('a * int) list -> 'a polynome = <fun>
#let p = poly_of_list [1.0,5; -2.0,3; 4.0,2; 3.0,0];;
p : float polynome =
 Poly [Mono (1.0, 5); Mono (-2.0, 3);
       Mono (4.0, 2); Mono (3.0, 0)]

Addition de polynômes

On suit le modèle de la procédure de fusion.

let prefix +$ (Poly p1) (Poly p2) =
  let rec add = function
    [], l2 -> l2
  | l1, [] -> l1
  | (Mono(a1,n1)::l1' as l1),
    (Mono(a2,n2)::l2' as l2) ->
           if n1 > n2 then hd l1 :: add (l1', l2)
      else if n1 < n2 then hd l2 :: add (l1, l2')
      else Mono(a1+.a2, n1) :: add (l1', l2') in
  Poly (add (p1, p2));;
+$ : float polynome -> float polynome -> float polynome

Listes associatives

Ce sont des listes dont les éléments servent à ranger une valeur sous une clé permettant de les retrouver.

let rec assoc k = function
  [] -> raise Not_found
| (k',e)::l -> if k'=k then e else assoc k l;;
let mem_assoc k l = exists (fun (k',_) -> k=k') l;;

Ces deux fonctions font partie de la bibliothèque Caml.

let pages_zoom nom annuaire =
  try
    assoc nom annuaire
  with Not_found ->
    "Il n'y a pas d'abonne " ^ nom;;

Types enregistrement

C'est le pendant en Caml des record de Pascal ou des struct de C.

• Déclaration, utilisation :

  type point = {x:int; y:int};;
  let translate p dx dy = {x=p.x+dx; y=p.y+dy};;
  

  Attention!! les noms de champs (x, y ici) ne peuvent être partagés entre plusieurs types enregistrement différents.

• On peut aussi modifier certains champs:

  type pixel = {x:int; y:int;
                mutable couleur: graphics__color};;
  let noircir p = p.couleur <- graphics__black;;
    (* p.x <- 0 n'est pas permis *)
  

Listes de collision

On hache dans un tableau de a-listes; complexité moyenne $O(\alpha)$, où $\alpha=n/m$, avec un cas pire moyen en $O(\log n/\log\log n)$.

type ('a,'b) hashtable = {
  mutable hash_buckets: ('a * 'b) list vect;
  mutable hash_n: int;
  hash_fun: int -> 'a -> int};;
let make_hash f m = {
  hash_buckets = make_vect m [];
  hash_n = 0; hash_fun = f};;
let slot k t = 
  t.hash_fun (vect_length t.hash_buckets) k;;
let lookup k t =
  assoc k t.hash_buckets.(slot k t);;

Il y a des tables de hachage génériques dans les bibliothèques Caml.

Insertion

let hash_put t (k,_ as p) =
  let i = slot k t in
  t.hash_buckets.(i) <- p::t.hash_buckets.(i);;
let overfull t = 
  t.hash_n > 10 * vect_length t.hash_buckets;;
let rehash t =
  let b = t.hash_buckets in
  t.hash_buckets <- make_vect (next_prime (2*t.hash_n)) [];
  do_vect (do_list (hash_put t)) b;;
let insert k e t =
  t.hash_n <- t.hash_n + 1;
  if overfull t then rehash t;
  hash_put t (k,e);;

Listes modifiables

L'utilisation des a-listes gaspille de la mémoire :

• Le système utilise deux blocs de mémoire pour chaque élément (un pour la cellule, un pour la paire).
• Lorsque l'on change une entrée, l'ancienne valeur reste!

Solution : gérer directement les cellules.

type annu = {nom: string; mutable tel: string;
             mutable next: annu};;

On utilise une valeur particulière pour la liste vide.

let rec null = {nom = ""; tel = ""; next = null};;

Attention aux effets de bord!!

Listes modifiables

Modification (gare aux effets de bord!) :

let rec modif nom tel a =
  if a == null then {nom = nom; tel = tel; next = a}
  else begin
    if a.nom = nom then a.tel <- tel
    else a.next <- modif nom tel a.next;
  a end;;

Suppression :

let rec retire nom a =
  if a == null then a
  else if a.nom = nom then a.next
  else begin
    a.next <- retire nom a.next;
  a end;;

Versions itératives

let modif nom tel a =
  let a' = ref a in
  while !a' != null && !a'.nom <> nom do
    a' := !a'.next
  done;
  if !a' == null then {nom = nom; tel = tel; next = a}
  else begin !a'.tel <- tel; a end;;

let retire nom a =
  let a' = ref null and a'' = ref a in
  while !a'' != null && !a''.nom <> nom do
    a' := !a''; a'' := !a''.next
  done;
  if !a'' == null then a
  else if !a' == null then a.next
  else begin !a'.next <- !a''.next; a end;;

Retournement

let retourne a =
  let rec ret_app a1 a2 =
    if a1==null then a2 else begin
      let a1' = a1.next in
      a1.next <- a2;
      ret_app a1' a1
    end in
  ret_app a null;;

En itératif

let retourne a =
  let a' = ref a and r = ref null in
  while !a' != null do
    let a'' = !a'.next in
    !a'.next <- !r; r := !a'; a' := a''
  done; !r;;

Listes doublement chaînées

Pointer sur la cellule précédente permet de supprimer une cellule en temps constant. Il est aussi commode d'avoir un chaînage circulaire et une cellule d'entête.

type 'a list2c = {val: 'a;
  mutable prev: 'a list2c; mutable next: 'a list2c};;
let make_void v =
  let rec r = {val=v; prev=r; next=r} in r;;
let insert v l =
  let c = {val=v; prev=l; next=l.next} in
  l.next <- c; c.next.prev <- c;;
let delete c =
  c.next.prev <- c.prev; c.prev.next <- c.next;;
let is_single c = c.prev==c.next;;
let make_single v = insert v (make_void v);;

Arbres binaires

Comme pour les listes:

type 'a arbre = ArbreVide
              | Noeud of 'a arbre * 'a * 'a arbre;;

let rec flat = function
  ArbreVide -> []
| Noeud(g,x,d) -> flat g @ [x] @ flat d;;

Recherche dans les arbres

La dichotomie se fait toute seule!

let rec cherche y = function
  ArbreVide -> false
| Noeud (g, x, d) ->
    x=y || cherche y (if y<x then g else d);;
let rec ajout y a = match a with
  ArbreVide -> Noeud (ArbreVide, y, ArbreVide)
| Noeud (g, x, d) ->
    if y<x      then Noeud (ajout y g, x, d)
    else if x<y then Noeud (g, x, ajout y d)
    else a;;

Arbres modifiables

Comme pour les listes, on peut utiliser des enregistrements pour représenter les nuds; on peut panacher avec le type concret pour simplifier la représentation de l'arbre vide. Les mutables permettent de faire l'ajout ``en place'' :

type 'a arbre =  ArbreVide | Noeud of 'a noeud
and  'a noeud =
  {val: 'a; mutable f_g: 'a arbre; mutable f_d: 'a arbre;};;
let ajout y a =
  let a_y = Noeud {val=y; f_g=ArbreVide; f_d=ArbreVide} in
  let rec ins_y n =
    if y < n.val then match n.f_g with
      Noeud n' -> ins_y n' | _ -> n.f_g <- a_y
    else if y > n.val then match n.f_d with
      Noeud n' -> ins_y n' | _ -> n.f_d <- a_y in
  match a with Noeud n -> ins_y n; a | _ -> a_y;;

Rotations

let rot y = function
  Noeud(Noeud(g, x1, m), x2, d) when y < x2 ->
    Noeud(g, x1, Noeud(m, x2, d))
| Noeud(g, x1, Noeud(m, x2, d)) when x1 < y ->
    Noeud(Noeud(g, x1, m), x2, d)
| a -> a;;

Quelques erreurs$\ldots$

• On ne peut utiliser que des constantes dans un filtre de match. Pour comparer avec des paramètres, il faut utiliser `=' et if ou when.
• Evitez de mélanger fonctions récursives et références. En général, la récursion est plus simple. Il est facile de retourner plusieurs valeurs en Caml.
• Evitez les booléens arbitraires. Utiliser raise Exit pour sortir d'une boucle, et des fonctions différentes (éventuellement mutuellement récursives).

Modules

• Pour limiter la taille d'un programme ou en isoler des parties critiques, on le divise en modules.
• En Caml, on écrit un fichier d'interface, mod.mli, en plus de l'implémentation mod.ml.
• On utilise les ``objets'' x (fonctions, types, étiquettes) d'un module mod soit comme mod__x, soit après avoir fait #open "mod".
• La bibliothèque Caml est organisée en modules.
• Il faut ``charger'' vos modules persos en appelant load "mod"

Fichier d'interface .mli

On y met des déclarations de types, exceptions, et de valeurs (des fonctions le plus souvent).

type color == int;;
value black : color;;
value point_color : int -> int -> color;;
value set_color : color -> unit;;
value lineto : int -> int -> unit;;

Les déclarations de types peuvent être abstraites (pas de représentation). Dans ce cas on ne pourra opérer sur les valeurs de ce type qu'avec les fonctions du module.

Piles

C'est le plus simple des ``contenants''; on ne peut lire et retirer que la dernière valeur insérée.

type 'a stack;;
exception Empty;;
value new : int -> 'a stack;;
value empty : 'a stack -> bool;;
value push : 'a -> 'a stack -> unit;;
value top : 'a stack -> 'a;;
value pop : 'a stack -> 'a;;

Peu utilisées en Caml, à cause de la récursion. Mais très utile pour la conception d'algorithme.

Implémentation des piles (1)

Le plus efficace : des tableaux.

type 'a stack =
  {mutable i: int; m: int; mutable t:'a vect};;
let new m = {i = -1; m = m; t = [||]};;
let empty s = s.i < 0;;
let push x s =
   s.i <- s.i+1;
   if s.i < vect_length s.t then s.t.(s.i) <- x
   else s.t <- concat_vect s.t (make_vect s.m x);;
let top s = if s.i >= 0 then s.t.(s.i) else raise Empty;;
let pop s = let x = top s in s.i <- s.i-1; x;;

Implémentation des piles (2)

Le plus simple : des listes.

type 'a stack == 'a list ref;;
let new m = ref [];;
let empty s = !s = [];;
let push x s = s := x :: !s;;
let top s = match !s with x::_ -> x
                        | [] -> raise Empty;;
let pop s = match !s with x::r -> s := r; x
                        | [] -> raise Empty;;

La différence entre piles et listes relève de l'usage.

Files

Semblable aux piles, mais on lit et on récupère le premier élément inséré.

type 'a queue;;
exception Empty;;
value new : int -> 'a stack;;
value empty : 'a queue -> bool;;
value add : 'a -> 'a queue -> unit;;
value peek : 'a queue -> 'a;;
value take : 'a queue -> 'a;;

Permettent par exemple le parcours d'un arbre par niveau.

Implémentation des files (1)

Tableaux circulaires.

type 'a queue = {mutable i: int; mutable j: int;
                 m: int; mutable t:'a vect};;
let new m = {i = 0; j = 0; m = m; t = [||]};;
let empty q = q.i = q.j;;
let add x ({i=i; t=t} as q) = let n = vect_length t in
  q.j <- (q.j+1) mod n;
  if q.j <> i then t.(q.j) <- x else begin
    q.t <- concat_vect (sub_vect t i (n-i)) (sub_vect t 0 i);
    q.t <- concat_vect q.t (make_vect q.m x);
    q.i <- 0; q.j <- n
  end;;
let take q = if q.i = q.j then raise Empty;
             let n = vect_length q.t and x = q.t.(q.i) in
             q.i <- (q.i+1) mod n; x;;

Implémentation des files (2)

type 'a queue =
  {mutable l1: 'a list; mutable l2: 'a list};;
let new m = {l1 = []; l2 = []};;
let empty q = q.l1 = [] && q.l2 = [];;
let add x q = q.l1 := x::q.l1;;
let take q = if q.l2 = [] then begin
               q.l2 <- rev q.l1; q.l1 <- []
             end;
             match q.l2 with
               x::l2' -> q.l2 <- l2'; x
             | [] -> raise Empty

On peut aussi utiliser des listes modifiables circulaires.