Caml Light

Caml Light var enlet implementering af Caml programmeringssprog udviklet af INRIA . Det er nu forældet. Denne version af Caml tillod funktionel og tvingende programmering, men ikke den objektorienterede programmering, der blev tilbudt af OCaml , dens efterfølger.

Dette sprog blev brugt i franske videnskabelige forberedende klasser ( MPSI og derefter MP- computerindstilling) for at introducere studerende til algoritmer mellem 1995 og 2017. Det erstattes nu af OCaml.

Eksempler

Faktorisk funktion

For naturlige heltal defineres faktorfunktionen af:

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

og dens rekursive definition er:

${\ displaystyle n! = {\ begin {cases} 1 \ quad {\ mbox {si}} n = 0 \\ n \ times (n-1)! \ quad {\ mbox {ellers}} \ end {cases} }}$

I Caml Light giver dette:

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

Euklidisk algoritme

Den euklidiske algoritme til beregning af gcd naturlige to heltal u , v , er skrevet i Caml Light

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

Fibonacci-sekvens

Den fibonacci sekvens er defineret ved: ${\ 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 }

I Caml Light har vi den naive rekursive version , der kører i eksponentiel tid :

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

eller igen, i en terminal rekursiv udgave tager som argument de to første semestre og og blive henrettet i lineær tid : $på$ $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 ;;

Vi kombinerer ofte de to for at have uden for en simpel funktion og inde i terminalrekursionen:

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

Vi har også to iterative versioner, der kører i lineær tid ( ), den første i lineært rum og den anden i konstant rum: $Vi)$

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

Noter og referencer

Denne implementering er teknisk forældet, er ikke længere under vedligeholdelse og udfases snart. , Caml's officielle side ved INRIA
[PDF] Datalogi program i MPSI og MP , BO Special edition n o 3 april 29., 2004 tillæg VII .
Memorandum ESRS1732186N af 27. november 2017

Tillæg

Bibliografi

[PDF] Pierre Weis, Xavier Leroy, LE LANGAGE CAML. Anden udgave .
Michel Demazure , Kursus i algebra. Primality, divisibility, Cassini codes 1997. Talrige algoritmer i Caml Light.

eksterne links

Officielt websted