Programmation impérative
Table des matières

À la différence de la programmation fonctionnelle où on calcule une valeur par l'application d'une fonction à ses arguments sans se soucier du déroulement des opérations, la programmation impérative est plus proche de la représentation machine car elle introduit un état mémoire que le déroulement des actions d'un programme va modifier. On appelle instructions ces actions des programmes et un programme impératif est une suite, ou une séquence, d'instructions. L'état mémoire est susceptible d'être modifié à l'exécution de chaque instruction. On considère les opérations d'entrées-sorties comme des modifications de la mémoire, de la mémoire vidéo ou de fichiers.

Ce style de programmation est directement inspiré de la programmation assembleur. On le retrouve dans les premiers langages évolués généralistes (Fortran, C, Pascal, etc. ). En OCaml, les éléments suivants du langage correspondent à ce modèle:

Certains algorithmes s'écrivent plus facilement dans ce style de programmation. On peut citer comme exemple le produit de deux matrices. Même s'il est effectivement possible de le traduire dans une version purement fonctionnelle, où des listes remplacent les vecteurs, cela n'est ni naturel, ni efficace par rapport à une écriture impérative.

L'intérêt d'intégrer ce modèle dans un langage fonctionnel est de pouvoir écrire certains algorithmes dans ce style de programmation quand ceux-ci s'y prêtent. Les deux principaux désavantages par rapport au style purement fonctionnel sont:

Néanmoins, avec quelques règles de prudence dans l'écriture des programmes, le choix entre plusieurs styles de programmation offre de plus grandes possibilités d'écriture d'algorithmes, ce qui est l'objectif principal des langages de programmation. En outre, un programme écrit dans un style proche de l'algorithme utilisé sera plus simple donc aura plus de chances d'être correct (ou, tout du moins, plus rapidement mis au point).

Pour ces raisons, le langage OCaml possède des types de données dont les valeurs sont physiquement modifiables, des structures de contrôle de l'exécution des programmes et une bibliothèque d'entrées-sorties dans un style impératif.

1. Structures de données physiquement modifiables

La programmation impérative nécessite des structures de données modifiables. OCaml en est pourvu et nous les détaillons ci-dessous.

1.1. Vecteurs

Les vecteurs sont des tableaux à une dimension, de taille fixe, et contenant des éléments qui sont tous du même type. Ils sont le pendant impératif des listes. Le type OCaml pour les représenter est le type paramétré 'a array, le paramètre de type 'a permettant d'avoir des vecteurs de différents types, de la même manière que le type 'a list.

1.1.1. Construction de valeurs

La construction d'un vecteur se fait en listant, séparées par des ';', les valeurs du vecteur entre [| et |]:

# let tab = [| 1 ; 2 ; 3 ; 4 |];;
val tab : int array = [|1; 2; 3; 4|]

Il est également possible d'utiliser des fonctions du module Array pour créer des vecteurs:

# let tab = Array.make 10 0;;
val tab : int array = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]
# let tab = Array.init 10 (fun i -> i * 2);;
val tab : int array = [|0; 2; 4; 6; 8; 10; 12; 14; 16; 18|]

Les indices d'un vecteur de longueur n vont de 0 à n-1.

1.1.2. Accès

On peut accéder de deux façons équivalentes à un élément d'un vecteur:

  • soit en utilisant la fonction Array.get : 'a array -> int -> 'a:
    # Array.get tab 0;;
    - : int = 0
    # Array.get tab 3;;
    - : int = 6
  • soit en utilisant la syntaxe vecteur.(indice):
    # tab.(0);;
    - : int = 0
    # tab.(3);;
    - : int = 6

L'accès à un élément d'un vecteur de longueur n en utilisant un indice en dehors de la plage 0..n-1 déclenche la levée d'une exception Invalid_argument:

# tab.(42);;
Exception: Invalid_argument "index out of bounds".

On peut bien sûr également utiliser le filtrage sur les vecteurs:

# match Array.sub tab 0 2 with
  [| _ ; x |] when x > 2 -> false
| [| 0 ; 2 |] -> true
| _ -> false;;
- : bool = true
1.1.3. Modification

Il existe deux manières équivalentes de modifier un élément d'un vecteur:

  • soit en utilisant la fonction Array.set : 'a array -> int -> 'a -> unit:
    # tab.(0);;
    - : int = 0
    # Array.set tab 0 42;;
    - : unit = ()
    # tab.(0);;
    - : int = 42
  • soit en utilisant la syntaxe vecteur.(indice) <- valeur:
    # tab.(1);;
    - : int = 2
    # tab.(1) <- 42;;
    - : unit = ()
    # tab.(1);;
    - : int = 42

Comme pour l'accès, et en général toutes les fonctions agissant sur les vecteurs, une exception Invalid_argument est levée lors de l'utilisation d'un indice invalide (en dehors des bornes).

1.1.4. Autres opérations

D'autres opérations sur les vecteurs sont disponibles via des fonctions prédéfinies du module Array:

# Array.length tab (* longueur *) ;;
- : int = 10
# Array.sub tab 3 4 (* extraction d'un sous-vecteur de longueur 4 à partir de l'indice 3 *);;
- : int array = [|6; 8; 10; 12|]
# Array.to_list tab (* création d'une liste à partir des éléments du vecteur *);;
- : int list = [42; 42; 4; 6; 8; 10; 12; 14; 16; 18]
# Array.map string_of_int tab (* map sur les éléments du vecteur *) ;;
- : string array =
[|"42"; "42"; "4"; "6"; "8"; "10"; "12"; "14"; "16"; "18"|]

On consultera la documentation du module Array.

1.2. Tableaux d'octets

Les tableaux d'octets sont les valeurs de type bytes remplaçant les chaînes de caractères mutables depuis la version 4.02.0 d'OCaml, lorsque l'option -safe-string est passée au compilateur. Ces tableaux d'octets sont mutables, à la façon des vecteurs. Cependant, ils ont leur type propre et ne sont pas des vecteurs d'octets (le type bytes n'est pas unifiable au type char array), mais les éléments d'un tableau d'octets sont de type char.

1.2.1. Création de valeurs

La création de valeurs de type bytes se fait par des fonctions du module Bytes. Il n'y a pas de syntaxe spécifique comme pour les chaînes de caractères.

On pourra créer des tableaux d'octets de différentes façons:

# Bytes.make 10 'a' (* n fois le même caractère *) ;;
- : bytes = <abstr>
# Bytes.init 10 (fun i -> Char.chr (0x42 + i))
  (* initialisation via une fonction pour chaque case *) ;;
- : bytes = <abstr>
# let chars = Bytes.of_string "bonjour!" (* à partir d'une chaîne *);;
val chars : bytes = <abstr>
1.2.2. Accès

L'accès à un octet (ou caractère) est fait via la fonction Bytes.get: bytes -> int -> char:

# Bytes.get chars 0;;
- : char = 'b'

Les indices pour un tableau de longueur n vont de 0 à n-1. En dehors de ces bornes, un accès déclenche là encore une exception Invalid_argument:

# Bytes.get chars 10;;
Exception: Invalid_argument "index out of bounds".
1.2.3. Modifications

La modification d'une case d'un tableau est faite grâce à la fonction Bytes.set : bytes -> int -> char -> unit:

# Bytes.get chars 0;;
- : char = 'b'
# Bytes.set chars 0 'b';;
- : unit = ()
# Bytes.get chars 0;;
- : char = 'b'

Il est également possible de modifier une plage d'un tableau d'octets avec des fonctions comme Bytes.fill ou Bytes.blit, entre autres.

1.2.4. Autres opérations

D'autres opérations sur les tableaux d'octets sont offertes par les fonctions du module Bytes. Par exemple:

# Bytes.length chars (* longueur d'un tableau *);;
- : int = 8
# let animaux = List.map Bytes.of_string
  [ "chat"; "chien"; "perroquet"; "lama"; "renard" ];;
val animaux : bytes list = [<abstr>; <abstr>; <abstr>; <abstr>; <abstr>]
# Bytes.to_string (Bytes.concat (Bytes.of_string ", ") animaux) ;;
- : string = "chat, chien, perroquet, lama, renard"

Pour d'autres fonctions, on consultera la documentation du module Bytes.

1.3. Champs modifiables des enregistrements

Nous avons vu précédemment (cf. 2.5) comment définir des types enregistrements. Il est possible de spécifier un ou plusieurs champs comme étant modifiables, à l'aide du mot-clé mutable:

# type mon_record = {
  champ1 : int ;
  mutable champ2 : int ;
  };;
type mon_record = { champ1 : int; mutable champ2 : int; }

La création et le filtrage de valeurs de ce type ne changent pas, mais il est maintenant possible de modifier le champ champ2 de ces valeurs:

# let r = { champ1 = 0 ; champ2 = 1 };;
val r : mon_record = {champ1 = 0; champ2 = 1}
# r.champ2 <- 2;;
- : unit = ()
# r;;
- : mon_record = {champ1 = 0; champ2 = 2}

Par contre, tenter de modifier le champ champ1 provoque une erreur:

# r.champ1 <- 3;;
Error: The record field champ1 is not mutable
1.4. Références

OCaml fournit un type polymorphe 'a ref qui peut être vu comme le type des pointeurs sur une valeur quelconque; en OCaml, on parlera plutôt de référence sur une valeur. Une valeur référencée peut être modifiée. Le type ref est défini comme un enregistrement à un champ modifiable:

type 'a ref = {mutable contents:'a}

Ce type est muni de raccourcis syntaxiques prédéfinis. On construit une référence sur une valeur par la fonction ref. La valeur référencée peut être atteinte par la fonction préfixe (!). La fonction modifiant le contenu d'une référence est la fonction infixe (:=).

# let x = ref 3 (* création et initialisation *);;
val x : int ref = {contents = 3}
# x ;;
- : int ref = {contents = 3}
# !x (* déréférencement *);;
- : int = 3
# x := 4 ;;
- : unit = ()
# !x ;;
- : int = 4
# x := !x+1 (* affectation *);;
- : unit = ()
# !x ;;
- : int = 5

Remarque: là encore, pour plus de sûreté, il n'est pas syntaxiquement possible de créer une référence sans l'initialiser à une valeur, contrairement au langage C.

Pour les références sur les entiers, on dispose en plus de deux fonctions incr et decr permettant d'incrémenter ou décrémenter de 1 la valeur référencée. incr x est donc équivalent à x := !x + 1:

# incr x (* incrémentation, pour les références sur les entiers uniquement *) ;;
- : unit = ()
# !x ;;
- : int = 6
# decr x (* décrémentation, pour les références sur les entiers uniquement *) ;;
- : unit = ()
# !x ;;
- : int = 5
2. Entrées-sorties

Les fonctions d'entrées-sorties calculent une valeur (souvent de type unit), mais durant ce calcul elles effectuent une modification de l'état des périphériques d'entrées-sorties: modification du buffer du clavier, affichage à l'écran, écriture dans un fichier ou modification du pointeur de lecture. Les deux types suivants sont prédéfinis: in_channel et out_channel pour respectivement les canaux d'entrées et de sorties. Quand une fin de fichier est rencontrée l'exception End_of_file est déclenchée. Enfin, les trois constantes suivantes correspondent aux canaux standard d'entrée, de sortie et d'erreur à la manière d'Unix: stdin, stdout et stderr.

2.1. Canaux

Pour obtenir d'autres canaux que ceux prédéfinis (stdin, stdout et stderr), on utilise:

  • la fonction open_in: string -> in_channel qui ouvre un fichier existant en lecture,
  • la fonction open_out: string -> out_channel qui ouvre un fichier en écriture, écrasant le fichier s'il existe déjà ou le créant s'il n'existe pas.

Les problèmes rencontrés par ces fonctions sont signalés par une levée d'exception Sys_error avec un message explicite, par exemple lorsqu'un fichier à ouvrir en lecture n'existe pas, quand les droits ne sont pas suffisants, etc.

# let ic = open_in "/etc/passwd";;
val ic : in_channel = <abstr>
# let oc = open_out "/tmp/foo";;
val oc : out_channel = <abstr>
# let ic = open_in "/bar";;
Exception: Sys_error "/bar: No such file or directory".

Pour fermer un fichier en lecture ou en écriture, on utilisera respectivement les fonctions close_in et close_out.

On notera que, grâce au typage, on ne pourra utiliser un canal d'entrée (in_channel) pour y écrire des données, ni un canal de sortie (out_channel) pour lire des données.

2.2. Lecture

Voici quelques fonctions de lecture sur un canal de type in_channel. D'autres fonctions sont disponibles dans la bibliothèque de base.

# let first_line = input_line ic (* lecture d'une ligne *);;
val first_line : string = "root:x:0:0:root:/root:/bin/bash"
# let second_line = input_line ic (* lecture d'une ligne *);;
val second_line : string = "daemon:x:1:1:daemon:/usr/sbin:/usr/sbin/nologin"
# seek_in ic 0 (* retour au début du fichier *);;
- : unit = ()
# let line = input_line ic (* re-lecture de la première ligne, suite au déplacement *);;
val line : string = "root:x:0:0:root:/root:/bin/bash"
# let buffer_size = 40 ;;
val buffer_size : int = 40
# let buffer = Bytes.make buffer_size 'x';;
val buffer : bytes = <abstr>
# let nb_read = input ic buffer 0 buffer_size
 (* lecture de maximum buffer_size caractères dans ic, à stocker dans buffer à partir
     de l'indice 0 *);;
val nb_read : int = 40
# Bytes.sub buffer 0 nb_read;;
- : bytes = <abstr>
# close_in ic;;
- : unit = ()
2.3. Ecriture

Voici quelques fonctions d'écriture sur un canal de type out_channel. D'autres fonctions sont disponibles dans la bibliothèque de base.

Il est important de savoir que ces canaux sont munis de tampons (buffers). Cela signifie que l'écriture dans un canal correspondant à un fichier n'écrira pas forcément immédiatement dans ce fichier, mais attendra qu'une quantité de données suffisante soit dans le tampon pour procéder à l'écriture réelle, cela afin de conserver des performances suffisantes lors de multiples petites écritures, sans avoir à s'en préoccuper. La fermeture d'un canal provoque la vidange du tampon, de même que la fonction flush.

# output_string oc second_line (* écriture d'une chaîne sur le canal *);;
- : unit = ()
# flush oc (* forcer l'écriture du contenu du tampon dans le fichier *);;
- : unit = ()
# output oc buffer 0 nb_read (* écriture d'un certain nombre de caractères depuis une chaîne *);;
- : unit = ()
# close_out oc;;
- : unit = ()
3. Structures de contrôle

Nous présentons ci-dessous la séquence d'instructions et les boucles, structures de contrôles de base pour la programmation impérative. La structure conditionnelle a déjà été présentée dans le cadre de la programmation fonctionnelle (cf. 1.3).

3.1. Séquence

La séquence d'instructions est représentée par l'utilisation du ';' simple, différent du ';;' de fin de phrase:

expression_1 ; expression_2

L'expression_1 doit être de type unit car sa valeur de retour n'est pas exploitable dans cette construction. Si ce n'est pas le cas, le compilateur émet un avertissement indiquant que la valeur retournée par l'expression n'est pas utilisée. Le type de la séquence ainsi que sa valeur sont ceux de l'expression_2. Enfin, l'expression_1 est bien sûr évaluée avant l'expression_2.

# let chaine = "hello!";;
val chaine : string = "hello!"
# print_endline chaine ;
Bytes.sub buffer 0 nb_read;;
hello!
- : bytes = <abstr>
# 1 + 1 ; print_endline chaine ;;
Warning 10: this expression should have type unit.
hello!
- : unit = ()

On peut bien sûr composer les séquences:

La fonction ignore permet d'indiquer explicitement qu'une valeur de retour est volontairement abandonnée:

# ignore(1+1); 42;;
- : int = 42

Si la valeur de la première expression est de type fonctionnel, le compilateur émet un message d'avertissement différent pour indiquer que la fonction n'a peut-être été que partiellement appliquée, par exemple si un paramètre a été oublié:

# let f x y = x + y;;
val f : int -> int -> int = <fun>
# f 1 ; 42;;
Warning 5: this function application is partial,
maybe some arguments are missing.
- : int = 42

Attention aux précédences des constructions !

# if true then
  print_endline "c'est vrai";
  print_endline "c'est vraiment vrai";;
c'est vrai
c'est vraiment vrai
- : unit = ()
# if false then
  print_endline "c'est vrai";
  print_endline "c'est vraiment vrai";;
c'est vraiment vrai
- : unit = ()

Que se passe-t-il donc ? En fait, la branche then prend fin après le point virgule situé derrière print_endline "c'est vrai". C'est donc équivalent à

# (if false then print_endline "c'est vrai");
print_endline "c'est vraiment vrai";;
c'est vraiment vrai
- : unit = ()

Il faut donc utiliser les parenthèses ( et ) ou bien les mots-clés begin et end pour forcer la séquence à être dans la branche then:

# if true then
  (
   print_endline "c'est vrai";
   print_endline "c'est vraiment vrai"
  );;
c'est vrai
c'est vraiment vrai
- : unit = ()
# if false then
  (
   print_endline "c'est vrai";
   print_endline "c'est vraiment vrai"
  );;
- : unit = ()
3.2. Boucles

Les structures de contrôle itératives sont elles aussi en dehors du monde fonctionnel. La condition de répétition, ou de sortie, d'une boucle n'a de sens que si une modification physique de la mémoire permet d'en changer la valeur. Il existe deux structures de contrôle itératives: la boucle for pour une itération bornée et la boucle while pour une itération non bornée. Les structures de boucle elles-mêmes sont des expressions du langage. Elles retournent donc une valeur: la constante () du type unit.

3.2.1. Boucle for

La boucle for peut être croissante:

for identifiant = expression_1 to expression_2 do
  expression_3
done

ou décroissante:

for identifiant = expression_1 downto expression_2 do
  expression_3
done

La valeur de l'identifiant croît ou décroît toujours d'un pas de un. L'identifiant n'est visible que dans l'expression_3 (et masque éventuellement une variable de même nom présente dans l'environnement). expression_1 et expression_2 doivent être de type int. L'expression_3 doit être de type unit car sa valeur est ignorée et l'expression dans la boucle n'a de sens que si elle a un effet de bord. Si l'expression n'est pas de type unit, le compilateur émet un avertissement.

# for i = 10 downto 1 do print_int i; print_string " " done; flush stdout;;
10 9 8 7 6 5 4 3 2 1 - : unit = ()
3.2.2. Boucle while

La syntaxe de cette boucle est la suivante:

while expression_1 do expression_2 done

L'expression_1 doit être de type bool. Elle est évaluée au début de chaque tour de boucle. Si elle est vraie, l'expression_2 est évaluée, sinon la boucle se termine en une valeur de type unit. Comme pour le corps de la boucle for, l'expression_2 doit être de type unit, sinon le compilateur émet un avertissement.

# let compteur = ref 1;;
val compteur : int ref = {contents = 1}
# while !compteur <= 10 do
  print_int !compteur; print_string " ";
  incr compteur (* équivalent à compteur := !compteur + 1 *)
done;;
- : unit = ()
# flush stdout;;
1 2 3 4 5 6 7 8 9 10 - : unit = ()
4. Exercices
Exercice 1: Echo

Ecrire un programme qui affiche ses arguments, à la manière de la commande UNIX echo. Pour cela, on utilisera Sys.argv qui est le tableau des arguments du programme, ainsi que le module Array pour les accès aux tableaux. Le parcours du tableau sera réalisé à l'aide d'une boucle. On compilera le programme grâce à la commande

ocamlc -o myecho myecho.ml

Exemple d'exécution:

./myecho bonjour le monde
bonjour le monde 
Exercice 2: Remplacement de caractère

En utilisant une boucle, écrire une fonction blank qui prend une chaîne de caractères, la copie et remplace chaque caractère par un blanc, tant qu'elle n'a pas rencontré la lettre 's'.

Tester ensuite la fonction, par exemple:

# let str = "coucous_royal";;
val str : string = "coucous_royal"
# blank str;;
- : string = "      s_royal"
Exercice 3: Test de symétrie de matrice

On souhaite écrire une fonction prenant en paramètre une matrice de type 'a array array et retournant true ou false selon que la matrice est symétrique ou non. On suppose que la matrice est carrée. On utilisera les matrices mat1 et mat2 définies ci-dessous pour tester:

# (* matrice symétrique: *)
let mat1 = [| [| 0 ; 1 ; 2 |] ; [| 1 ; 5 ; 10 |] ; [| 2 ; 10 ; 8 |] |];;
val mat1 : int array array = [|[|0; 1; 2|]; [|1; 5; 10|]; [|2; 10; 8|]|]
# let init _ = Random.int 10 ;;
val init : 'a -> int = <fun>
# (* matrice non symétrique *)
let mat2 = [| Array.init 3 init ; Array.init 3 init ; Array.init 3 init |];;
val mat2 : int array array = [|[|4; 0; 1|]; [|1; 9; 0|]; [|4; 5; 2|]|]
# mat2.(0).(1) <- - mat2.(1).(0);;
- : unit = ()

On commence par écrire une fonction is_sym_imper impérative.

On donnera ensuite une version fonctionnelle is_sym_fun.