Caml Light

Caml fény voltkönnyű végrehajtását a Caml programozási nyelv által kifejlesztett INRIA . Most elavult. A Caml ezen verziója lehetővé tette a funkcionális és elengedhetetlen programozást, az utódja, az OCaml által kínált objektum-orientált programozást azonban nem.

Ezt a nyelvet francia tudományos előkészítő órákon használták ( MPSI majd MP számítógépes opció), hogy 1995 és 2017 között megismertessék a diákokat az algoritmusokkal . Most ezt OCaml váltja fel.

Példák

Faktoriális függvény

Természetes egész számok esetén a faktoriális függvényt a következő határozza meg:

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

és rekurzív meghatározása :

${\ displaystyle n! = {\ elején {esetek} 1 \ quad {\ mbox {si}} n = 0 \\ n \ szer (n-1)! \ quad {\ mbox {különben}} \ end {esetek} }}$

A Caml Light-ban ez:

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

Euklideszi algoritmus

A gcd természetes két u , v egész szám kiszámítására szolgáló euklideszi algoritmust Caml Light-ban írjuk

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

Fibonacci szekvencia

A Fibonacci szekvenciát a következők határozzák meg: ${\ displaystyle (F_ {n}) _ {n \ geq 1}}$

{\ displaystyle F_ {0} = 0, F_ {1} = 1, \ quad F_ {n + 2} = F_ {n + 1} + F_ {n} \ quad {\ mbox {with}} n \ geq 0 }

A Caml Light-ban van egy naiv rekurzív verzió , amely exponenciális idő alatt fut :

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

vagy ismét egy terminál rekurzív változata véve érv az első két tag és és futtatás során lineáris idő : $nál nél$ $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 ;;

Általában kombináljuk a kettőt, hogy egy egyszerű funkción kívül és a terminál rekurzióján belül legyen:

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

Két iteratív változatunk is fut lineáris időben ( ), az első a lineáris térben, a második pedig az állandó térben: $Mi)$

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

Megjegyzések és hivatkozások

Ez a megvalósítás technikailag elavult, már nincs karbantartás alatt, és hamarosan megszűnik. , A Caml hivatalos oldala az INRIA-nál
[PDF] Computer Science program MPSI és MP , BO Különkiadás n o 3 április 29-2004 függelék VII .
ESRS1732186N memorandum, 2017. november 27

Függelékek

Bibliográfia

[PDF] Pierre Weis, Xavier Leroy, LE LANGAGE CAML. Második kiadás .
Michel Demazure , Algebra tanfolyam. Primalitás, oszthatóság, Cassini kódok 1997. Számos algoritmus a Caml Light-ban.

Külső linkek

Hivatalos oldal