Caml Light — Wikipédia

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 :

${\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 :

${\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 ${\displaystyle (F_{n})_{n\geq 1}}$ est définie par :

${\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 ${\displaystyle a}$ et ${\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 (${\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]

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

• [PDF] Pierre Weis, Xavier Leroy, LE LANGAGE CAML. Deuxième édition.
• Michel Demazure, Cours d'algèbre. Primalité, divisibilité, codes Cassini 1997. De nombreux algorithmes en Caml Light.

Liens externes[modifier | modifier le code]

• Site officiel

• Portail de la programmation informatique