La programmation impérative

La programmation impérative

Références

modélisation de la notion de case mémoire: on peut consulter son contenu courant et modifier son contenu.
correspond presque à la notion d'identificateur dans les langages impératifs classiques, Pascal par exemple.
utilisées comme des compteurs ou des accumulateurs dont le contenu évolue au cours du calcul.

Création et type

#let compteur = ref (0);;
compteur : int ref = ref 0

Consultation du contenu courant (déréférencement)

#!compteur;;
- : int = 0

Modification du contenu (affectation, effet de bord)

#compteur:=2;;
- : unit = ()
#!compteur;;
- : int = 2

Exemple de fonction manipulant des références :

#let incrémente = function c -> c := !c+1;;
incrémente : int ref -> unit = <fun>
#incrémente compteur; !compteur;;
- : int = 3

Attention, l'affectation d'une référence est différente de la redéfinition par un let d'un identificateur Caml :

#let x = 1;;

x : int = 1

#let f = function y -> x+y;;

f : int -> int = <fun>

#let x = 2;;

x : int = 2

#f (0);;

- : int = 1

#let x = ref 1;;

x : int ref = ref 1

#let f = function y -> !x+y;;

f : int -> int = <fun>

#x := 2;;

- : unit = ()

#f (0);;

- : int = 2

Tableaux

Tableaux à une dimension (vecteurs)

Figure 0.1 : Les principales notions sur les vecteurs

Création et type

#[|1; 2; 3|];;
- : int vect = [|1; 2; 3|]
#make_vect 4 2;;
- : int vect = [|2; 2; 2; 2|]
#let r = make_vect 3 "Bonjour";;
r : string vect = [|"Bonjour"; "Bonjour"; 
"Bonjour"|]
#let r2 = init_vect 3 (function i -> i*i);;
r2 : int vect = [|0; 1; 4|]

Consultation du contenu courant

#r;;
- : string vect = [|"Bonjour"; "Bonjour"; 
"Bonjour"|]
#r.(0);;
- : string = "Bonjour"

Modification du contenu

#r.(1) <- "tout"; r.(2) <- "le monde!";;
- : unit = ()
#r;;
- : string vect = [|"Bonjour"; "tout"; "le 
monde!"|]

Tableaux à deux dimensions (matrices)

Création, types et dimensions

#[|[|1; 2; 3|]; [|4; 5; 6|]; [|7; 8; 9|]|];;
- : int vect vect = [|[|1; 2; 3|]; [|4; 5; 
6|]; [|7; 8; 9|]|]
#make_matrix 2 1 "Bonjour";;
- : string vect vect = [|[|"Bonjour"|]; 
[|"Bonjour"|]|]
#let M = make_matrix 2 3 0;;
M : int vect vect = [|[|0; 0; 0|]; [|0; 0; 
0|]|]
#let M2 = init_vect 3 (function i -> 
   init_vect 2 (function j -> i+j));;
M2 : int vect vect = [|[|0; 1|]; [|1; 2|]; 
[|2; 3|]|]
#(* nombre de lignes *)
 vect_length M;; 
- : int = 2
#(* nombre de colonnes *)
 vect_length M.(0);; 
- : int = 3

Consultation du contenu courant

#M;;
- : int vect vect = [|[|0; 0; 0|]; [|0; 0; 
0|]|]
#M.(0).(2);;
- : int = 0

Modification du contenu

#M.(1).(0) <- 2; M.(1).(2) <- 5;;
- : unit = ()
#M;;
- : int vect vect = [|[|0; 0; 0|]; [|2; 0; 
5|]|]

Séquences

#print_string "Bonjour "; 
 print_string "tout le monde !";;
Bonjour tout le monde !- : unit = ()
#print_string;;
- : string -> unit = <fun>
#1+2;3;;
Entrée interactive:
>1+2;3;;
>^^^
Attention: cette expression est de type 
int,
mais est utilisée avec le type unit.
- : int = 3

Boucles

Syntaxe:
while condition do actions done
for ident = début to findoactionsdone
for ident = début downto findoactionsdone

Exemples:

#for i = 0 to 9 do print_int i done;;
0123456789- : unit = ()
#let i = ref 0 in
 while !i <= 9 do
    print_int !i; incr i
 done;;
0123456789- : unit = ()
#for i = 9 downto 0 do print_int i done;;
9876543210- : unit = ()
#for i = 0 to (vect_length r)-1 do
   print_string r.(i); print_string " "
 done;;
Bonjour tout le monde! - : unit = ()

#for i = 0 to (vect_length M)-1 do
   for j = 0 to (vect_length M.(0))-1 do
   print_int M.(i).(j); print_string " "
   done;
   print_newline ()
 done;;
0 0 0 
2 0 5 
- : unit = ()

Exceptions (non détaillé en cours)

Réponse propre quand il n'y a pas de réponse pertinente
failwith déjà vu
Des exceptions nommées (plus précis pour récupérer, etc.)
Un mécanisme de traitement d'exceptions doit permettre de réaliser trois actions :
- déclarer une exception (si elle n'est pas prédéfinie);
- déclencher, lever, ou signaler une exception;
- traiter l'exception.

Les exceptions prédéfinies

exception Division_by_zero
exception Out_of_memory
exception Invalid_argument of string
exception Failure of string
exception Not_found

Deux levées d'exceptions prédéfinies

value failwith : string -> 'a
value invalid_arg : string -> 'a

Exemples de levée des exceptions prédéfinies

#(* Par des opérations prédéfinies *)
 1/0;;
Exception non rattrapée: Division_by_zero
#hd [];;
Exception non rattrapée: Failure "hd"
#[|1;2;3|].(10);;
Exception non rattrapée: Invalid_argument 
"vect_item"
#(* Par des fonctions que l'on définit *)
 let rec member = 
   function nom -> function liste -> 
 match liste with
 | [] -> raise Not_found
 | e::l -> e=nom || member nom l;;  
member : 'a -> 'a list -> bool = <fun>
#member 1 [1;2;3];;
- : bool = true
#member 4 [1;2;3];;
Exception non rattrapée: Not_found
#let chiffre1 = function n ->
   if n < 10 then n else 
   raise (Invalid_argument (string_of_int n));;
chiffre1 : int -> int = <fun>
#chiffre1 12;;
Exception non rattrapée: Invalid_argument 
"12"
#let chiffre2 = function n ->
   if n < 10 then n else 
   invalid_arg (string_of_int n);;
chiffre2 : int -> int = <fun>
#chiffre2 12;;
Exception non rattrapée: Invalid_argument 
"12"
#let chiffre3 = function n ->
   if n < 10 then n else 
   failwith "chiffre3: argument > 10";;
chiffre3 : int -> int = <fun>

#chiffre3 12;;
Exception non rattrapée: Failure 
"chiffre3: argument > 10"
#let chiffre4 = function n ->
   if n < 10 then n else 
   raise (Failure "chiffre4: argument > 10");;
chiffre4 : int -> int = <fun>
#chiffre4 12;;
Exception non rattrapée: Failure 
"chiffre4: argument > 10"

Déclaration (exception) et type (exn, type somme prédéfini extensible)

#(* Sans argument *)
 exception Stop;;
L'exception Stop est définie.
#Stop;;
- : exn = Stop
#(* Avec argument *)
 exception Trouvé of int;;
L'exception Trouvé est définie.
#Trouvé;;
- : int -> exn = <fun>
#Match_failure;;
- : string * int * int -> exn = <fun>

Levée (raise)
```
... 
raise exception 
...
```

Exemples de levées d'exceptions définies

#let search = function e -> function v ->
   for i = 0 to vect_length v - 1 do
     if v.(i)=e then raise (Trouvé i)
   done;;
search : 'a -> 'a vect -> unit = <fun>
#let search = function e -> function v ->
   let i = ref 0 in
   while true do 
     if v.(!i)=e then raise (Trouvé !i);
     i := !i+1
   done;;
search : 'a -> 'a vect -> unit = <fun>
#search "B" [|"A";"B";"C";"D"|];;
Exception non rattrapée: Trouvé 1
#search "E" [|"A";"B";"C";"D"|];;
Exception non rattrapée: Invalid_argument 
"vect_item"
#let failwith s = raise (Failure s);;
failwith : string -> 'a = <fun>

Une levée d'exception est un effet de bord.

Rattrapage ou récupération (try ... with)

try expression with 
| exception_1 -> expression_1
| exception_2 -> expression_2
| :
| exception_n -> expression_n

On appelle l'expression try ... with le traite-exception de l'exception exception_j.

Chaque expression_i peut lever à nouveau une des exceptions exception_j.

#(* Sous-vecteur d'un vecteur v commençant 
    à la première occurrence de l'élément e
    dans v *)
 let sous_vecteur = 
   function e -> function v ->
 try search e v;[|"impossible"|] with
 | Trouvé i -> 
   sub_vect v i (vect_length v - i)
 | Invalid_argument "vect_item" -> [||];;
sous_vecteur : string -> string vect -> 
string vect = <fun>
#sous_vecteur "B" [|"A";"B";"C";"D"|];;
- : string vect = [|"B"; "C"; "D"|]
#sous_vecteur "E" [|"A";"B";"C";"D"|];;
- : string vect = [||]
#let sans_doublons = function v -> 
   try 
     for i = 0 to vect_length v - 1 do
       if v.(i)=v.(i+1) then raise Stop
     done; true 
   with Stop -> false;;
sans_doublons : 'a vect -> bool = <fun>

#exception absent of int;;
L'exception absent est définie.
#let rec trouve_nom = 
   function numéro -> function amphi ->
 match amphi with
 | [] -> raise (absent numéro)
 | (x,n)::reste -> 
   if n=numéro then x 
   else trouve_nom numéro reste;;
trouve_nom : int -> ('a * int) list -> 'a 
= <fun>
#let verif = function (numéro, amphi) ->
   try (trouve_nom numéro amphi) with
   | absent p -> "chercher_à_la_scolarité";;
verif : int * (string * int) list -> 
string = <fun>

#exception erreur of int;;
L'exception erreur est définie.
#exception signal of string;;
L'exception signal est définie.
#let f_qui_déclenche = function x ->
   if x < 0 then raise (erreur (-x)) else 
   if x=0 
      then raise (signal "reprise au vol") 
   else x;; 
f_qui_déclenche : int -> int = <fun>
#f_qui_déclenche (-4);;
Exception non rattrapée: erreur 4
#f_qui_déclenche 2;;
- : int = 2
#let récupère = function x ->
   try f_qui_déclenche x with
   | erreur 0 -> 0 
   | erreur y -> 25-y+3*x 
   | signal _ -> 100*x+1;;
récupère : int -> int = <fun>
#(récupère 2),(récupère (-4)),(récupère 0);;
- : int * int * int = 2, 9, 1

Les exceptions comme style de programmation

à la place de sentinelles, permet notamment d'interrompre des boucles parcourant toute une structure dès que l'on a trouvé dans la structure un élément vérifiant une propriété donnée

#let sans_doublons = function v ->
   let i = ref 0 
   and t = ref false in
   while !i < vect_length v && not !t do
     if v.(!i)=v.(!i+1) then t := true;
     i := !i+1
   done; !t;;
sans_doublons : 'a vect -> bool = <fun>
#let rec member_rec = 
   function e -> function l -> 
 match l with
 | [] -> raise Not_found
 | e'::l' -> 
   if e=e' then raise Stop 
   else member_rec e l';;
member_rec : 'a -> 'a list -> 'b = <fun>
#let member = function e -> function l -> 
   try member_rec e l with
   | Not_found -> false
   | Stop -> true;;
member : 'a -> 'a list -> bool = <fun>
#member 2 [1;2;3];;
- : bool = true
#member 4 [1;2;3];;
- : bool = false
#let rec member e l = 
   try e = hd l or member e (tl l)  
   with Failure "hd" -> false;;
member : 'a -> 'a list -> bool = <fun>
#member 2 [1;2;3];;
- : bool = true
#member 4 [1;2;3];;
- : bool = false