Caml Light

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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 :

et sa définition récursive est :

En Caml Light, cela donne :

let rec fact n = 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 est définie par :

.

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 et 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 (), 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. 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
  2. [PDF] Programme d'informatique en MPSI et MP, B.O. Hors série no 3 du 29 avril 2004, annexe VII.
  3. Note de service ESRS1732186N du 27 novembre 2017

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]