Une centaine de lignes de Caml

Contacter l'auteur Pierre.Weis@inria.fr

Fichier créé en janvier 1996.

Fonctions élémentaires

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

Gestion automatique de la mémoire

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]

Polymorphisme: le tri des listes

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"]

Programmation impérative

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

Pleine fonctionnalité

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

Traitements symboliques

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 = ()

Analyse syntaxique

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.

Trace des fonctions

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 = ()

Encore

Si vous connaissez le lambda calcul, cliquez 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.


Page de présentation de Caml Dernière modification: vendredi 26 mars 2004
Copyright © 1995 - 2004, INRIA tous droits réservés.

Contacter l'auteur Pierre.Weis@inria.fr