Avec le système interactif, je définis la fonction carré et la fonction factorielle récursive. Puis j'essaie mes nouvelles fonctions sur quelques exemples:
> Caml Light version 0.74 #let carré (x) = x * x;; carré : int -> int = <fun> #let rec fact (x) = if x <= 1 then 1 else x * fact (x - 1);; fact : int -> int = <fun> #fact (5);; - : int = 120 #carré (120);; - : int = 14400
Toutes les opérations d'allocation et de libération de la mémoire sont complètement automatiques. Je donne l'exemple des listes.
Les listes sont prédéfinies en Caml, la liste vide est notée
[], et le constructeur d'ajout d'un élément à une liste
est :: (opérateur binaire et infixe).
#let l = 1 :: 2 :: 3 :: [];; l : int list = [1; 2; 3] #[1; 2; 3];; - : int list = [1; 2; 3] #5 :: l;; - : int list = [5; 1; 2; 3]
Le tri par insertion est défini à l'aide de deux fonctions récursives, en utilisant le filtrage sur les listes.
#let rec tri = function | [] -> [] | x :: l -> insert x (tri l) and insert elem = function | [] -> [elem] | x :: l -> if elem < x then elem :: x :: l else x :: insert elem l;; tri : 'a list -> 'a list = <fun> insert : 'a -> 'a list -> 'a list = <fun> #tri [2; 1; 0];; - : int list = [0; 1; 2] #tri ["oui"; "ok"; "sûr"; "ouais"; "certain"];; - : string list = ["certain"; "ok"; "ouais"; "oui"; "sûr"]
Les polynômes sont représentés comme des vecteurs; je les ajoute en créant d'abord le polynôme somme et en remplissant ensuite ses cases à l'aide de deux boucles ``for''.
#let ajoute_polynômes p1 p2 = let result = make_vect (max (vect_length p1) (vect_length p2)) 0 in for i = 0 to vect_length p1 - 1 do result.(i) <- p1.(i) done; for i = 0 to vect_length p2 - 1 do result.(i) <- result.(i) + p2.(i) done; result;; ajoute_polynômes : int vect -> int vect -> unit #ajoute_polynômes [| 1; 2 |] [| 1; 2 |];; - : int vect = [|2; 4|]
Les accumulateurs sont définis en Caml à l'aide de cellules
modifiables appelées références.
ref init renvoie une
nouvelle cellule, dont le contenu initial est init,
!cell renvoie le contenu actuel de cell, et
cell := val met dans cell la valeur
val.
Je définis fact avec un accumulateur et une boucle ``for'':
#let fact n =
let result = ref 1 in
for i = 1 to n do
result := i * !result
done;
!result;;
fact : int -> int = <fun>
#fact 5;;
- : int = 120
Il n'y a pas de restriction sur les fonctions, qui peuvent donc
être d'ordre supérieur. Je définis d'abord la fonction sigma qui
renvoie la somme des résultats de l'application d'une fonction
f donnée aux éléments d'une liste:
#let rec sigma f = function
| [] -> 0
| x :: l -> f x + sigma f l;;
sigma : ('a -> int) -> 'a list -> int = <fun>
Les fonctions temporaires peuvent se définir comme des valeurs fonctionnelles anonymes à l'aide de la construction ``function'':
#sigma (function x -> x * x) [1; 2; 3];; - : int = 14
Combinée au polymorphisme, la pleine fonctionnalité permet de définir la composition des fonctions.
#let compose f g = function x -> f (g (x));;
compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
#let carré_o_fact = compose carré fact;;
carré_o_fact : int -> int = <fun>
#carré_o_fact 5;;
- : int = 14400
Je considère des expressions symboliques simples comprenant des entiers, des variables, un opérateur de liaison let, et des opérateurs binaires. Ces expressions symboliques sont définies à l'aide d'un nouveau type de données, par une définition de type:
#type expression =
| Int of int
| Var of string
| Let of string * expression * expression
| Binop of string * expression * expression;;
Type expression defined.
L'évaluation symbolique de ces expressions utilise un environnement qui est une simple liste d'association (identificateur, valeur).
#let rec eval env = function
| Int i -> i
| Var x -> assoc x env
| Let (x, e1, in_e2) ->
let val_x = eval env e1 in
eval ((x,val_x) :: env) in_e2
| Binop (op, e1, e2) ->
let v1 = eval env e1 in
let v2 = eval env e2 in
eval_op op v1 v2
and eval_op op v1 v2 =
match op with
| "+" -> v1 + v2
| "-" -> v1 - v2
| "*" -> v1 * v2
| "/" -> v1 / v2
| _ -> failwith ("Opérateur inconnu: " ^ op);;
eval : (string * int) list -> expression -> int = <fun>
eval_op : string -> int -> int -> int = <fun>
Évaluons par exemple la phrase ``let x = 1 in x + x'':
#eval [] (Let ("x", Int 1, Binop ("+", Var "x", Var "x")));;
- : int = 2
En combinaison avec la définition des types de données, le filtrage conduit à un moyen facile de définir des fonctions portant sur des données symboliques. Par exemple, à partir du type des expressions:
type expression = | Int of int | Var of string | Let of string * expression * expression | Binop of string * expression * expression
on obtient le squelette d'une fonction d'impression des expressions:
let print_expression = function | Int int -> | Var string -> | Let (string, expression1, expression2) -> | Binop (string, expression1, expression2) ->
Il suffit maintenant de compléter les clauses du filtrage pour obtenir la procédure d'impression:
#let rec print_expression = function
| Int int -> print_int int
| Var string -> print_string string
| Let (string, expression1, expression2) ->
print_string "let "; print_string string; print_string " = ";
print_expression expression1; print_string " in ";
print_expression expression2
| Binop (string, expression1, expression2) ->
print_string "("; print_expression expression1;
print_string (" "^string^" ");
print_expression expression2; print_string ")";;
print_expression : expression -> unit = <fun>
#print_expression (Let ("x", Int 1, Binop ("+", Var "x", Var "x")));;
let x = 1 in (x + x)- : unit = ()
Caml vous offre un ensemble d'outils de génération d'analyseurs
syntaxiques, comprenant non seulement des interfaces avec les outils
classiques lex et yacc, mais aussi une méthode d'analyse syntaxique
originale reposant sur le type primitif des flux: l'``analyse
syntaxique fonctionnelle''.
Écrire un analyseur syntaxique est toujours un peu délicat, et on peut
s'en passer en première lecture. Cependant j'ai écrit en quelques
lignes, un analyseur
syntaxique pour le type des expressions vu plus haut.
Pour terminer, voici le moyen le plus élémentaire pour espionner les fonctions:
#let rec fib x = if x <= 1 then 1 else fib (x - 1) + fib (x - 2);; fib : int -> int = <fun> #trace "fib";; La fonction fib est dorénavant tracée. - : unit = () #fib 3;; fib <-- 3 fib <-- 1 fib --> 1 fib <-- 2 fib <-- 0 fib --> 1 fib <-- 1 fib --> 1 fib --> 2 fib --> 3 - : int = 3 #untrace"fib";; La fonction fib n'est plus tracée. - : unit = ()
Si vous connaissez le lambda calcul, cliquez là pour voir un exemple plus consistant de manipulation de données symboliques avec Caml: j'y définis les lambda termes avec leurs analyseurs lexicaux et syntaxiques associés, puis un imprimeur en à peu près 50 lignes de Caml.
Contacter l'auteur Pierre.Weis@inria.fr