I. Le langage OCaml

OCaml est un langage fonctionnel, basé en partie sur la récursivité, qui est utilisé en option informatique en prépa.

Syntaxe de base du langage

a) Valeurs et types

En OCaml, chaque valeur a un type, que l'interpréteur calcule tout seul (on dit qu'il l'infère) et affiche :

42;;
3.14;;
true;;
'a';;
"bonjour";;

Les types de base sont int (entiers), float (flottants), bool (booléens), char (caractères, entre apostrophes) et string (chaînes, entre guillemets).

b) Opérations

Les opérations sur les entiers et sur les flottants sont différentes : les opérateurs sur les flottants ont un point.

3 + 4 * 2;;
7 / 2;;         (* division entière *)
7 mod 2;;       (* reste *)
3.5 +. 1.2;;
7.0 /. 2.0;;
float_of_int 7 /. 2.0;;   (* conversion explicite *)

OCaml ne convertit jamais automatiquement un type en un autre :

3 + 1.5;;

Les comparaisons s'écrivent =, <> (différent), <, <=, >, >=, et les opérations booléennes &&, || et not. Les chaînes se concatènent avec ^.

3 <> 4 && not (2 > 5);;
"bon" ^ "jour";;

c) Définitions

On donne un nom à une valeur avec let. Une fois définie, une variable ne peut pas être modifiée (on peut seulement définir une nouvelle variable du même nom).

let x = 5;;
let y = x * 2;;

Une définition locale s'écrit let ... in ... : la variable n'existe que dans l'expression qui suit le in.

let aire = let rayon = 2.0 in 3.14 *. rayon *. rayon;;

d) Conditions

En OCaml, if ... then ... else ... est une expression : elle a une valeur, comme l'opérateur ternaire. Les deux branches doivent avoir le même type.

let signe = if x >= 0 then "positif" else "négatif";;

e) Fonctions

On définit une fonction avec let, suivi de son nom et de ses arguments (sans parenthèses ni virgules). On l'appelle de la même manière, en écrivant les arguments à la suite :

let carre x = x * x;;
carre 5;;

let moyenne a b = (a +. b) /. 2.0;;
moyenne 3.0 4.0;;

L'interpréteur affiche le type de la fonction : int -> int pour une fonction qui prend un entier et renvoie un entier, float -> float -> float pour une fonction qui prend deux flottants. On peut aussi préciser les types soi-même, ce qui est recommandé :

let perimetre (longueur : float) (largeur : float) : float = 2.0 *. (longueur +. largeur);;

Une fonction récursive se définit avec let rec :

let rec factorielle (n : int) : int =
    if n = 0 then 1 else n * factorielle (n - 1);;

factorielle 10;;

f) Filtrage

La construction match compare une valeur à des motifs, dans l'ordre, et renvoie le résultat du premier motif qui correspond (_ correspond à n'importe quoi) :

let nom_jour (n : int) : string = match n with
    | 1 -> "lundi"
    | 2 -> "mardi"
    | 6 | 7 -> "week-end"
    | _ -> "un autre jour";;

nom_jour 2;;
nom_jour 7;;

g) Listes

Une liste contient des éléments du même type, séparés par des points-virgules. Une liste est soit vide ([]), soit un élément suivi d'une liste : x :: q (x est la tête, q la queue).

let l = [1; 2; 3];;
0 :: l;;
l @ [4; 5];;   (* concaténation *)

On parcourt une liste par filtrage et récursivité :

let rec somme (l : int list) : int = match l with
    | [] -> 0
    | x :: q -> x + somme q;;

somme [1; 2; 3; 4];;

II. Étude de cas : les formules

On étudie des formules limitées :

• des variables (qui sont des lettres) ;
• 3 opérations (addition, multiplication, et négation).

Par exemple, est une formule.

a) Définition par induction

On tente de définir les formules. Une addition entre deux "trucs", , est une formule. Que peuvent être ces "trucs" ?

Ils peuvent être n'importe quelle formule ! On arrive donc à la définition suivante :

b) Et en OCaml ?

On peut traduire directement cette définition en un type OCaml :

type formule =
    | Var of char
    | Neg of formule
    | Add of formule * formule
    | Mul of formule * formule;;

(* la formule (a + b) * (a + (-b)) *)
let f = Mul (Add (Var 'a', Var 'b'), Add (Var 'a', Neg (Var 'b')));;

Exercices

let rec taille (f : formule) : int = match f with
    | Var _ -> 1
    | Neg g -> 1 + taille g
    | Add (g, d) | Mul (g, d) -> 1 + taille g + taille d;;

let rec evalue (f : formule) (valeur : char -> int) : int = match f with
    | Var v -> valeur v
    | Neg g -> - (evalue g valeur)
    | Add (g, d) -> evalue g valeur + evalue d valeur
    | Mul (g, d) -> evalue g valeur * evalue d valeur;;

evalue f (fun v -> if v = 'a' then 3 else 2);;   (* (3 + 2) * (3 - 2) = 5 *)

let rec en_texte (f : formule) : string = match f with
    | Var v -> String.make 1 v
    | Neg g -> "(-" ^ en_texte g ^ ")"
    | Add (g, d) -> "(" ^ en_texte g ^ " + " ^ en_texte d ^ ")"
    | Mul (g, d) -> "(" ^ en_texte g ^ " * " ^ en_texte d ^ ")";;