Caml Light

Caml Light fue una implementación ligera del lenguaje de programación Caml desarrollado por INRIA . Ahora está obsoleto. Esta versión de Caml permitía la programación funcional e imperativa , pero no la programación orientada a objetos ofrecida por OCaml , su sucesor.

Este idioma se utilizó en las clases preparatorias científicas de francés ( MPSI, luego MP , opción de computadora) para introducir a los estudiantes a los algoritmos entre 1995 y 2017. Ahora es reemplazado por OCaml.

Ejemplos de

Función factorial

Para enteros naturales, la función factorial se define por:

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

y su definición recursiva es:

${\ Displaystyle n! = {\ begin {cases} 1 \ quad {\ mbox {si}} n = 0 \\ n \ times (n-1)! \ quad {\ mbox {de lo contrario}} \ end {cases} }}$

En Caml Light, esto da:

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

Algoritmo euclidiano

El algoritmo euclidiano para calcular el mcd natural de dos enteros u , v , está escrito en Caml Light

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

secuencia Fibonacci

La secuencia de Fibonacci está definida por: ${\ Displaystyle (F_ {n}) _ {n \ geq 1}}$

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

En Caml Light tenemos la versión recursiva ingenua, que se ejecuta en tiempo exponencial :

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

o nuevamente, en una versión terminal recursiva tomando como argumento los dos primeros términos y ejecutándose en tiempo lineal : $a$ $B$

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 ;;

Normalmente combinamos los dos, para tener una función simple fuera y dentro de la recursividad terminal:

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 ;;

También tenemos dos versiones iterativas que se ejecutan en tiempo lineal ( ), la primera en el espacio lineal y la segunda en el espacio constante: $Nosotros)$

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 ;;

Notas y referencias

Esta implementación está técnicamente desactualizada, ya no se encuentra en mantenimiento y se eliminará pronto. , Sitio oficial de Caml en INRIA
[PDF] programa informático en MPSI y MP , edición especial BO n o 3 de 29 de abril de 2004, Apéndice VII .
Memorando ESRS1732186N del 27 de noviembre de 2017

Apéndices

Bibliografía

[PDF] Pierre Weis, Xavier Leroy, LE LANGAGE CAML. Segunda edición .
Michel Demazure , Curso de álgebra. Primalidad, divisibilidad, códigos de Cassini 1997. Numerosos algoritmos en Caml Light.

enlaces externos

Sitio oficial