Caml Light

Caml Light était une implémentation légère du langage de programmation Caml développé par l'INRIA. Elle est aujourd'hui obsolète^[1]. Cette version de Caml permettait une programmation fonctionnelle et impérative, mais pas la programmation orientée objet proposée par OCaml, son successeur.

Ce langage a été utilisé en classe préparatoires scientifiques françaises (MPSI puis MP option informatique) pour initier les élèves à l'algorithmique entre 1995^[2] et 2017^[3]. Il est désormais remplacé par OCaml.

Exemples

[modifier | modifier le code ]

Fonction factorielle

[modifier | modifier le code ]

Pour des entiers naturels, la fonction factorielle est définie par :

$n!=\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times (n-1)\times n$ {\displaystyle n!=\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times (n-1)\times n}

et sa définition récursive est :

$n!={\begin{cases}1\quad {\mbox{si }}n=0\\n\times (n-1)!\quad {\mbox{ sinon}}\end{cases}}$ {\displaystyle n!={\begin{cases}1\quad {\mbox{si }}n=0\\n\times (n-1)!\quad {\mbox{ sinon}}\end{cases}}}

En Caml Light, cela donne :

let rec fact = function
 | 0 -> 1
 | n -> n * fact (n - 1);;

Algorithme d'Euclide

[modifier | modifier le code ]

L'algorithme d'Euclide, pour calculer le pgcd de deux entiers naturels u, v, s'écrit en Caml Light

let rec pgcd u v = 
 if u = 0 then v
 else pgcd (v mod u) u;;

Suite de Fibonacci

[modifier | modifier le code ]

La suite de Fibonacci $(F_{n})_{n\geq 1}$ {\displaystyle (F_{n})_{n\geq 1}} est définie par :

F_{0}=0,F_{1}=1,\quad F_{n+2}=F_{n+1}+F_{n}\quad {\mbox{ avec }}n\geq 0

{\displaystyle F_{0}=0,F_{1}=1,\quad F_{n+2}=F_{n+1}+F_{n}\quad {\mbox{ avec }}n\geq 0}

.

En Caml Light on a la version récursive naïve, qui s'exécute en temps exponentiel :

let rec fibonacci n =
 match n with
 | 0 -> 0
 | 1 -> 1
 | _ -> fibonacci (n - 1) + fibonacci (n - 2) ;;
let f = fibonacci 9 ;;

ou encore, en version récursive terminale prenant en argument les deux premiers termes $a$ {\displaystyle a} et $b$ {\displaystyle b} et s'exécutant en temps linéaire :

let rec fibonacci n a b =
 match n with
 | 0 -> a
 | 1 -> b
 | _ -> fibonacci (n - 1) b (a + b) ;;
let f = fibonacci 9 0 1 ;;

On combine couramment les deux, pour disposer à l’extérieur d’une fonction simple, et à l’intérieur de la récursion terminale :

let fibonacci n =
 (* Définir la version récursive avec récursion terminale... *)
 let rec fib_2termes n a b =
 match n with
 | 0 -> a
 | 1 -> b
 | _ -> fib_2termes (n - 1) b (a + b)
 (* ... et l’utiliser. *)
 in fib_2termes n 0 1 ;;
let f = fibonacci 9 ;;

On dispose aussi de deux versions itératives s'exécutant en temps linéaire ( $O(n)$ {\displaystyle O(n)}), la première en espace linéaire et la seconde en espace constant :

let fibonacci n =
 (* Un vecteur (tableau) de n+1 éléments entiers initialisés à 1. *)
 let t = make_vect (n + 1) 1 in
 (* Calculer ce vecteur pour les éléments n° 2 à n. *)
 for k = 2 to n do
 t.(k) <- t.(k - 1) + t.(k - 2)
 done;
 (* Le résultat est dans le dernier élément du vecteur. *)
 t.(n);;
let f = fibonacci 9 ;;

let fibonacci n =
 (* 3 variables modifiables (refs) n1, n2, aux. *)
 let n1 = ref 1 in
 let n2 = ref 1 in
 let aux = ref 1 in
 (* Recalculer itérativement ces variables jusqu’à n. *)
 (* Syntaxe: !x dénote l’accès à la valeur actuelle de x. *)
 for k = 2 to n do
 aux := !n1;
 n1 := !n2;
 n2 := !n2 + !aux;
 done;
 (* Le résultat est dans n2. *)
 !y;;
let f = fibonacci 9 ;;

Notes et références

[modifier | modifier le code ]

↑ Cette implémentation est techniquement dépassée, ne fait plus l'objet d'aucune maintenance, et sera bientôt supprimée., Site officiel de Caml à l'INRIA
↑ [PDF] Programme d'informatique en MPSI et MP, B.O. Hors série n^o 3 du 29 avril 2004, annexe VII.
↑ Note de service ESRS1732186N du 27 novembre 2017