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. 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 et 2017. Il est désormais remplacé par OCaml.

Exemples

Fonction factorielle

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$

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}}$

En Caml Light, cela donne :

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

Algorithme d'Euclide

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

La suite de Fibonacci $(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$

.

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$ et $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)$), 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 ;;

Annexes

Bibliographie

• [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

• Site officiel