Caml Light

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Caml Light est une implémentation légère du langage de programmation Caml développé par l'INRIA. Elle est stable et facilement portable. Cette version de Caml permet une programmation fonctionnelle et impérative. Caml Light ne permet pas la programmation orientée objet contrairement à OCaml, son successeur.

Ce langage est utilisé en classe préparatoires scientifiques (MPSI puis MP option info) pour initier les élèves à l'algorithmique[1].

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

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[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 if v < u then
    pgcd v u
  else
    pgcd (v mod u) u;;

Suite de Fibonacci[modifier | modifier le code]

La suite de Fibonacci (F_n)_{n\ge 1} est définie par :

F_0=F_1=1, \quad F_{n+2}=F_{n+1}+F_n \quad \mbox{ avec } n \ge 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 -> 1
    | 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 (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 ;;

Notes et références[modifier | modifier le code]

  1. [PDF] Programme d'informatique en MPSI et MP, B.O. Hors série n° 3 du 29 avril 2004, annexe VII

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]