Cours 2

Plan

Expressions avec opérateur infixe binaire

En ML, tout est des expressions. (En Pascal, expressions et instructions sont différentes.) Toute expression ML doit retourner une valeur (d'un certain type). Par exemple, 

e_1 + e_2
(e_1 et e_2 sont de type entier)
On calcule dans n'importe quel ordre les valeurs v_1 et v_2 de e_1 et e_2. Le résultat est v_1+v_2. Idem pour 
e_1 - e_2     e_1 * e_2      e_1 / e_2     e_1 mod e_2
Sur les flottants, on a aussi 
e_1 -. e_2     e_1 *. e_2      e_1 /. e_2
et sur les booléens 
e_1 || e_2     e_1 && e_2      not e_1
Les comparaisons se font par 
e_1 = e_2     e_1 <> e_2     e_1 < e_2     e_1 <= e_2  ...
etc. (Pour le moment, ne pas utiliser == ou !=). En général, on peut avoir des opérateurs binaires op avec des arguments d'un certain type et on écrit 
e_1 op e_2
(expressions nary-expressions dans la syntaxe du poly p.299 où op est ``infix-op'')

Expression avec définition de variables temporaires

Comme raccourci, on peut donner un nom à une valeur avec la construction let ... in. 

let x_1 = e_1 and .... x_n = e_n in
e
ML calcule les valeurs v_1 de e_1, ... v_n de e_n;
ML pose temporairement x_1=v_1, ... x_n=v_n;
ML calcule la valeur v de e.
La valeur de toute l'expression est v.

Exemples: 

let x = 4 in x*(1-x)
vaut -12 
(let x = 4 in 
    x*(1-x))
+
(let x = 20 in 
    x*(x-1))
vaut 368

Dans ces 2 exemples, x est une variable locale dont le nom a peu d'importance (variable muette ou alpha-conversion). On pourrait aussi bien écrire 

let y = 4 in y*(1-y)
ou 
(let z = 4 in 
    z*(1-z))
+
(let t = 20 in 
    t*(t-1))

Portée des définitions de variables

Les let définissent des portées pour les identificateurs. 

let x = 3 in
  let y = 4 in
    (2*x + 3*y)
a comme valeur 18 (de type int). On retrouve donc ttes les subtilités des blocs et des variables locales. Exemples: 
let x = 3 in
  let y = 4 in
    let x = 1 in
       (2*x + 3*y)
donne 14 (de type int). Mais: 
let x = 3 in
  let y = 4 in
    x + let x = 1 in
           (2*x + 3*y)
donne 17(de type int), ainsi que : 
let x = 3 in
  let y = 4 in
    (let x = 1 in
         (2*x + 3*y))
    + x
qui donne aussi 17 (de type int)

Portée -- Remarques

  1. on peut tjrs renommer une variable. L'exemple précédent est donc équivalent à: 
    let x = 3 in
  let y = 4 in
    (let z = 1 in
         (2*z + 3*y))
    + x
  2. l'expression qui donne la valeur de la variable définie par let se calcule elle aussi, dans un certain environnement. Dans 
    let x = e_1 in 
  e
    le calcul de e_1 se fait sans utiliser la nouvelle définition de x. Plus intéressant, dans 
    let x = e_1 and y = e_2 in 
  e
    le calcul de e_2 utilise la valeur de x dans l'environnement extérieur. Si on veut utiliser, la nouvelle valeur de x pour calculer y, il faut écrire 
    let x = e_1 in
  let y = e_2 in 
     e
    Exercices: trouver les valeurs de 
    let x = 1 and y = 4 in let y = x in let z = y in y + z
let x = 1 and y = 4 in let y = x  and   z = y in y + z
  3. let définit la valeur d'une constante. Si une variable veut avoir plusieurs valeurs différentes dans le temps, on devra passer par une référence ou un tableau ou tout autre dénomination de la mémoire.

Phrases de programme

Un programme est une suite de phrases (expressions ou définitions de variables), ttes finies par le symbole ;;. Le système répond en donnant la valeur et le type de la phrase. 

let x = 1 ;;
let y = 2 ;;
x+y ;;
auquel le système répond en indiquant la variable déclaré, son type et sa valeur. 
x : int = 1
y : int = 2
- : int = 3
Attention, au niveau programme, la construction let correspond à la définition de nouvelles variables jusqu'à la fin du programme.
Autre point: une phrase n'est pas une expression. On ne l'utilise qu'au niveau externe.

Un programme qui fait de l'impression (formattée) doit tjrs commencer par la directive (attention au #): 

#open "printf" ;;

Variables modifiables

Comment faire l'instruction x := x + y + 3 de Pascal? Cela consiste à changer la valeur de x. Mais, en Caml, tte variable a une valeur constante!
Cela se réalise par une indirection à travers une case mémoire, et on utilise une référence vers cette case. 

ref e
retourne la référence ref v où v est la valeur de e. (On peut voir une référence comme un pointeur vers une case mémoire contenant v). De même, 
!x
suppose que la valeur de x est ref v, et retourne v comme résultat. (On parle du contenu de la référence). Si e est de type A, alors ref e est de type A ref. (La notation est souvent suffixe sur les types). L'expression 
x := e
retourne () (la constante vide), de type unit, mais modifie le contenu de x. Exemple: 
let y = 20 in
let x = ref 1 in begin
   x := !x + y + 3;
   !x
   end
donne 24. Pourquoi?

Expressions de séquencement

(e_1; e_2; ... e_n)
begin e_1; e_2; ... e_n end
Calcule la valeur de e_1 et l'oublie! Calcule la valeur de e_2 et l'oublie! ... Calcule la valeur de e_n qui est le résultat global.
(Cela n'a de sens que si certains effets de bord se produisent dans les calculs de e_1, ... e_{n-1}). 
if e then e_1 else e_2
calcule e (de type booléen). Si vrai, le résultat est e_1. Sinon e_2. C'est une expression (comme les autres).
Attention: e_1 et e_2 sont de même type. (Pour l'instant, le conditionnel partiel (sans else) n'est pas autorisé. 
match e with          
    pat_1 -> e_1      
  ...                 
  | pat_n -> e_n
calcule e et dispatche selon le cas. Mêmes remarques que pour if. 
try e with 
    pat_1 -> e_1 
  ...
  | pat_n -> e_n
calcule e qui est le résultat, sauf si exception que l'on teste derrière le with. On donne alors e_1 ou ... e_n comme résultat.

Pour itérer, on utise 

while e_1 do          
  e_1; ...  e_n       
  done                

for i = e_1 to e_2 do 
  e_1; ... e_n        
  done
qui renvoient la valeur vide après le bon nombre d'itérations. 
raise Exit
failwith s
n'ont pas de valeur, mais lève une exception Exit (resp Failure avec la chaine s comme argument)

Pour sortir brutalement d'une boucle while, on peut utiliser 

try 
   while true do
      ...
      raise Exit
      ...
   done
with
  Exit -> e_1

Types scalaires -- Produit (cartésien)

Entiers int: 1 2 3 ... -1 -2
Booléens bool: true, false
Réels float: 2.3 3E4 -2E-9
Caractères char: `a`, `b`, etc. , `\n`, `\r`, etc

Paires (nuplets): int * int: (1, 2)
Pour accéder aux éléments d'un paire, on se sert du filtrage. 

let (x, b) = (1, true) in  
   if b then x
        else 0
ou encore 
match (1, true) with
  (x, b) ->  if b then x
                  else 0
Les filtres sont appelés pattern en anglais (et dans la syntaxe du polycopié). Le filtre universel _ filtre tout. Il sert notamment dans le dernier cas par défaut d'un match.

Tableaux

Tableaux int vect: [| 1; 2; 3 |]
L'expression 

a.(i)
retourne la valeur de l'élément i du tableau a
(Les indices commencent tjrs à 0) 
a.(i) <- e
retourne la valeur vide en mettant dans l'élément i du tableau a la valeur de e 
vect_length a
donne la taille du tableau a 
make_vect n e
retourne un tableau de taille n initialisé par e

Exemple: 

let a = make_vect 10 0 in
    for i=0 to vect_length a do
        a.(i) <- i*i
    done

Fonctions

Les définitions 

let f (x) = x + 1 ;;
let g (x, y) = x + y ;;
let h (x) (y) = x + y ;;
produisent comme résultat: 
f : int -> int = <fun>
g : int * int -> int = <fun>
h : int -> int -> int = <fun>
La valeur d'une fonction n'est pas imprimée, mais son type est indiqué. Les constantes de fonction permettent de définir des fonctions anonymes. 
function (x) -> x+1
qui a comme type int -> int. Les définitions précédentes sont équialentes à: 
let f = function (x) -> x + 1 ;;
let g = function (x, y) -> x + y ;;
let h = function (x) -> function (y) -> x + y ;;

Polymorphisme

let f x = x ;;
let g (x, y) = x ;;
let nth (a, n) =  a.(n) ;;
donnent 
f : 'a -> 'a = <fun>
g : 'a * 'b -> 'a = <fun>
nth : 'a vect * int -> 'a = <fun>
'a (lire alpha) est une variable de type. On peut donc utiliser f dans tout contexte où alpha peut être intancié. Par exemple, 
f 2 ;;
- : int = 2
ou 
f "aaaa" ;;
- : string = "aaaa"

Pb: quel est le type de := ?? 

prefix :=  ;;
donne la réponse...

Initialisation, impression d'un tableau

#open "printf";;

let initialisation a =
 for i = 0 to vect_length a - 1 do
  a.(i) <- random__int 100
 done;;

let impression a =
 for i = 0 to vect_length a - 1 do
   printf "%d " a.(i)
 done;
 printf "\n" ;;

let main () =
 let a = make_vect 15 0 in
   begin
   initialisation (a); (* On lit le tableau *)
   tri_selection (a);  (* On trie *)
   impression (a);     (* On imprime le resultat *)
   end ;;
On utilise des fonctions de librairie pour tirage au sort (entre 1 et 100) ou impression formattée.

Tri sélection

(* cf polycopié *) 

let tri_selection a =
 let min = ref 0 in
 for i = 0 to vect_length a - 2 do
  min := i;
  for j = i + 1 to vect_length a - 1 do
   if a.(j) < a.(!min) then min := j
  done;
  let t = a.(!min) in
  a.(!min) <- a.(i); a.(i) <- t
 done;;
(Remarque syntaxique: if partiel marche ici car la seule alternative min := j est de type unit, qui est aussi le type par défaut du else)

On peut même faire un tri polymorphe (en passant la relation d'ordre en argument): 

let tri_selection a plus_petit_que =
 let min = ref 0 in
 for i = 0 to vect_length a - 2 do
  min := i;
  for j = i + 1 to vect_length a - 1 do
   if plus_petit_que(a.(j),  a.(!min)) then min := j
  done;
  let t = a.(!min) in
  a.(!min) <- a.(i); a.(i) <- t
 done;;

Nombre moyen et nombre pire de comparaisons?

Tri par insertion

(* cf polycopié *) 

let tri_insertion a =
 let j = ref 0 in
 for i = 1 to vect_length a - 1 do
   let v = ref a.(i) in
      begin
      j := i;
      while !j > 0 && a.(!j - 1) > !v do
        a.(!j) <- a.(!j - 1);
        decr j
      done;
      a.(!j) <- !v;
      end
 done;;
où decr est définir pas 
let decr (x) =  
    x := !x -1 ;;
(c'est en fait une fonction de bibliothèque). Itou pour incr.

Nombre moyen et nombre pire de comparaisons? 

let initialisation (n) =
  let a = make_vect n 0 in
     begin
     for i = 0 to vect_length a - 1 do
        a.(i) <- random__int 100
     done;
     a
     end

Tri Shell 1959

(* cf polycopié *)
C'est une variante astucieuse du tri par insertion qui essaie d'éliminer les longues séquences à parcourir. 

let tri_shell a =
 let h = ref 1 in
  while !h <= vect_length a - 1 do
   h := 3 * !h + 1
  done;
  while !h > 1 do
   h := !h / 3;
   for i = !h to vect_length a - 1 do
    if a.(i) < a.(i - !h) then begin
     let v = a.(i) in
     let j = ref i in
     while !j >= !h && a.(!j - !h) > v do
      a.(!j) <- a.(!j - !h);
      j := !j - !h
     done;
     a.(!j) <- v 
    end    
   done
  done;;

Nombre moyen et nombre pire de comparaisons? C'est un pb ouvert!

Autres tris

Il y a bien d'autres tris (cf Knuth, vol 3; Searching and Sorting). Si on connait la distribution des valeurs et qu'elles ne soient pas très grandes, on peut arriver à trier en temps linéaire.

(cf. le TD1 de Bruno Salvy en http://www.polytechnique.fr/poly/salvy/)

Tri distribution, tri des mécanographes (Straight Radix Sort). Enfin, si toutes les données ne tiennent pas dans la mémoire vive d'un ordinateur (c'est de moins en moins le cas), il y a des méthodes sophistiquées de tri externe.

Exercices en TD