Annexe B    Caml

B.1  Un exemple simple

#open "printf";;

let magique a =
 let n = vect_length a in
 let i = ref (n - 1) in
 let j = ref (n / 2) in
 for k = 1 to n * n do
  a.(!i).(!j) <- k;
  if k mod n = 0 then decr i else
   begin
    i := (!i + 1) mod n;
    j := (!j + 1) mod n;
   end
 done;;

let erreur s = printf "Erreur fatale: %s\n" s; exit 1;;

let lire () =
 printf "Taille du carré magique, svp ? ";
 let n = int_of_string (read_line ()) in
 if n <= 0 || n mod 2 = 0 then erreur "Taille impossible" else n;;

let imprimer a =
 for i = 0 to vect_length a - 1 do
  for j = 0 to vect_length a - 1 do
   printf "%4d " a.(i).(j)
  done;
  printf "\n"
 done;;

let main () =
 let n = lire () in
 let a = make_matrix n n 0 in
 magique a;
 imprimer a;
 exit 0;;

main ();;

Phrases

En Caml, la valeur d'une variable est fixée lors de sa définition.

Références

let decr x =
  x := !x - 1;;

En Caml, l'opérateur := est réservé aux références.

Vecteurs et tableaux

let c = make_matrix n n 0 in

En Caml, la taille des vecteurs est fixée à la création.

Fonctions et procédures

En Caml, les fonctions sont des valeurs comme les autres.

let prochain x = if x mod 2 = 1 then 3 * x + 1 else x / 2;;

let even x = x mod 2 = 0;;

let even (x : int) = (x mod 2 = 0 : bool);;

En Caml, le typage est à la charge du compilateur.

B.2  Quelques éléments de Caml

Appel au compilateur

poly% cat fact.ml
let rec fact x = if x <= 1 then 1 else x * fact (x - 1);;

print_int (fact 10); print_newline ();;
poly% camlc fact.ml
poly% a.out
3628800

poly% camllight
>       Caml Light version 0.71

#let rec fact x = if x <= 1 then 1 else x * fact (x - 1);;
fact : int -> int = <fun>
#fact 10;;
- : int = 3628800
#quit();;
poly% 

#include "fact.ml";;
fact : int -> int = <fun>
3628800
- : unit = ()
#

B.2.1  Fonctions

#fact;;
- : int -> int = <fun>

Les fonctions récursives doivent être introduites par le mot-clé let rec.

#(function x -> x + 1);;
- : int -> int = <fun>
#(function x -> x + 1) 2;;
- : int = 3

#let successeur = (function x -> x + 1);;
successeur : int -> int = <fun>
#successeur 2;;
- : int = 3

Fonctionnelles

let abs x = if x >= 0.0 then x else -. x;;

let trouve_zéro f a b epsilon max_iterations =
 let rec trouve x y n =
  if abs (y -. x) < epsilon || n >= max_iterations then x
  else
   let m = (x +. y) /. 2.0 in
   if (f m > 0.0) = (f x > 0.0)
   then trouve m y (n + 1)
   else trouve x m (n + 1) in
 trouve a b 1;;
let zéro f a b = trouve_zéro f a b 1.0E-7 100;;

let zéro f a b =
 let epsilon = 1.0E-7
 and nmax  = 100 in
 let n = ref 1
 and m = ref ((a +. b) /. 2.0) in
 let x = ref a
 and y = ref b in
 while abs (!y -. !x) > epsilon && !n < nmax do
  m := (!x +. !y) /. 2.0;
  if (f !m > 0.0) = (f !x > 0.0)
   then x := !m
   else y := !m;
  n := !n + 1
 done;
 !x;;

#open "printf";;
#let log10 x = log x /. log 10.0;;
log10 : float -> float = <fun>
#printf "le zéro de log10 est %f\n" (zéro log10 0.5 1.5);;
le zéro de log10 est 1.000000
- : unit = ()

B.2.2  Symboles, séparateurs, identificateurs

B.2.3  Types de base

#let v = [| 1; 2; 3 |];;
v : int vect = [|1; 2; 3|]

#let symétrie (x, y) = (-x, -y);;
symétrie : int * int -> int * int = <fun>

B.2.4  Expressions

En Caml, les conversions sont explicites.

if e then e1 else e2

(b && not c) || (not b && c)

if (x > 1) && (y = 3) then ...

(b && not c) || (not b && c)

En Caml, l'ordre d'évaluation des arguments n'est pas spécifié.

#"ok" = "ok";;
- : bool = true
#"ok" == "ok";;
- : bool = false

#let x = ref 1;;
x : int ref = ref 1
#let y = ref 1;;
y : int ref = ref 1
#x = y;;
- : bool = true
#x == y;;
- : bool = false
#x == x;;
- : bool = true
#x := 2;;
- : unit = ()
#x = y;;
- : bool = false

B.2.5  Blocs et portée des variables

let successeur x = x - 1;;
let plus_deux x = successeur (successeur x);;
#plus_deux 1;;
- : int = -1

#let successeur x = x + 1;;
successeur : int -> int = <fun>
#plus_deux 1;;
- : int = -1

B.2.6  Correction des programmes

#trace "successeur";;
La fonction successeur est dorénavant tracée.
- : unit = ()
#successeur 1;;
successeur <-- 1
successeur --> 2
- : int = 2
#plus_deux 1;;
- : int = -1

B.2.7  Instructions

begin e1; e2; ...; en end

if e then e1

if e then e1 else e2

#if true then 1;;
Entrée interactive:
>if true then 1;;
>             ^
Cette expression est de type int,
mais est utilisée avec le type unit.
#if true then printf "Hello world!\n";;
Hello world!
- : unit = ()

if e then if e ' then e1 else e2

if e then begin if e ' then e1 else e2 end

Filtrage

match e with
| v1 -> e1
| v2 -> e2
  ...
| vn -> en
| _ -> défaut

Boucles

for i = e1 to e2 do e done

for i = e1 downto e2 do e done

On ne peut pas affecter l'indice de boucle d'une boucle for.

while e1 do e done

while not button_down () do () done;

B.2.8  Exceptions

B.2.9  Entrées -- Sorties

Copie de fichiers

#open_in "essai";;
Exception non rattrapée: sys__Sys_error "essai: No such file or directory"

#let ic = open_in "essai" in
  while true do input_line ic done;;
Exception non rattrapée: End_of_file

#open "printf";;

let copie_channels ic oc =
 try
  while true do
   let line = input_line ic in
   output_string oc line;
   output_char oc `\n` 
  done
 with
 | End_of_file -> close_in ic; close_out oc;;

let copie origine copie =
 try
  let ic = open_in origine in
   try
    let oc = open_out copie in
    copie_channels ic oc
   with
   | sys__Sys_error s ->
      close_in ic;
      printf "Impossible d'ouvrir le ficher %s \n" copie;
      raise (sys__Sys_error s)
   | sys__Break ->
      close_in ic;
      close_out oc;
      printf "Interruption pendant la copie de %s dans %s\n" origine copie;
      raise (sys__Break)  
 with
 | sys__Sys_error s ->
    printf "Le ficher %s n'existe pas\n" origine;
    raise (sys__Sys_error s);;

B.2.10  Définitions de types

Types sommes: types énumérés

 
type couleur = Bleu | Blanc | Rouge
and sens = Gauche | Haut | Droite | Bas;;

let c = Bleu
and s = Droite in
...
end;

type bool = false | true;;

Types sommes: unions

 
type expression =
 | Const of int
 | Var of string
 | Add of expression * expression
 | Mul of expression * expression
 | Exp of expression * int;;

let p = Add (Const 1, Mul (Const 2, Exp (Var "x", 3)));;

 
let rec dérive x e =
 match e with
 | Const _ -> Const 0
 | Var s -> if x = s then Const 1 else Const 0
 | Add (e1, e2) -> Add (dérive x e1, dérive x e2) 
 | Mul (Const i, e2) -> Mul (Const i, dérive x e2)
 | Mul (e1, e2) -> Add (Mul (dérive x e1, e2), Mul (e1, dérive x e2))
 | Exp (e, i) -> Mul (Const i, Mul (dérive x e, Exp (e, i - 1)));;

• Const _ : une constante quelconque (_), alors on retourne la valeur 0.
• Var s : une variable que nous nommons s, alors on retourne 1 ou 0 selon que c'est la variable par rapport à laquelle on dérive.
• Add (e1, e2) : une somme de deux expressions que nous nommons respectivement e1 et e2, alors on retourne la somme des dérivée des deux expressions e1 et e2.
• les autres cas sont analogues au cas de la somme.

 
#dérive "x" p;;
- : expression =
 Add
  (Const 0,
   Mul (Const 2, Mul (Const 3, Mul (Const 1, Exp (Var "x", 2)))))

 
let rec puissance i j =
 match j with
 | 0 -> 1
 | 1 -> i
 | n -> i * puissance i (j - 1);;

let rec simplifie e =
 match e with
 | Add (Const 0, e) -> simplifie e
 | Add (Const i, Const j) -> Const (i + j)
 | Add (e, Const i) -> simplifie (Add (Const i, e))
 | Add (e1, e2) -> Add (simplifie e1, simplifie e2)
 | Mul (Const 0, e) -> Const 0
 | Mul (Const 1, e) -> simplifie e
 | Mul (Const i, Const j) -> Const (i * j)
 | Mul (e, Const i) -> simplifie (Mul (Const i, e))
 | Mul (e1, e2) -> Mul (simplifie e1, simplifie e2)
 | Exp (Const 0, j) -> Const 0
 | Exp (Const 1, j) -> Const 1
 | Exp (Const i, j) -> Const (puissance i j)
 | Exp (e, 0) -> Const 1
 | Exp (e, 1) -> simplifie e
 | Exp (e, i) -> Exp (simplifie e, i)
 | e -> e;;

 
#simplifie (dérive "x" p);;
- : expression = Mul (Const 2, Mul (Const 3, Exp (Var "x", 2)))

Types produits: enregistrements

type mois =
 | Janvier | Février | Mars | Avril | Mai | Juin | Juillet
 | Aout | Septembre | Octobre | Novembre | Décembre;;

type date = {j: int; m: mois; a: int};;

let berlin = {j = 10; m = Novembre; a = 1989}
and bastille = {j = 14; m = Juillet; a = 1789};;

type personne = {nom: string; naissance: date};;

let poincaré =
 {nom = "Poincaré"; naissance = {j = 29; m = Avril; a = 1854}};;

#type point = {mutable x : int; mutable y : int};;
Le type t est défini.
#let origine = {x = 0; y = 0};;
origine : point = {x = 0; y = 0}
#origine.x <- 1;;
- : unit = ()
#origine;;
- : point = {x = 1; y = 0}

type complexe =
   | Cartésien of cartésiennes
   | Polaire of polaires

and cartésiennes = {re: float; im: float}
and polaires = {rho: float; theta: float};;

let pi = 4.0 *. atan 1.0;;

let x = Cartésien {re = 0.0; im = 1.0}
and y = Polaire {rho = 1.0; theta = pi /. 2.0};;

let rotation_pi_sur_deux = function
  | Cartésien x -> Cartésien {re = -. x.im; im = x.re}
  | Polaire x -> Polaire {rho = x.rho; theta = x.theta +. pi /. 2.0};;

Types abréviations

type compteur == int;;

Types abstraits

Égalité de types

#type t = C of int;;
Le type t est défini.
#let int_of_t x =
  match x with C i -> i;;
int_of_t : t -> int = <fun>

#type t = C of int | D of float;;
Le type t est défini.
#int_of_t (C 2);;
Entrée interactive:
>int_of_t (C 2);;
>          ^^^
Cette expression est de type t,
mais est utilisée avec le type t.

Structures de données polymorphes

type 'a liste =
   | Nulle
   | Cons of 'a * 'a liste;;

type ('a, 'b) table = {nb_entrées : int; contenu : ('a * 'b) vect};;

#let l = [1; 2; 3];;
l : int list = [1; 2; 3]
#let ll = 0 :: l;;
ll : int list = [0; 1; 2; 3]

#let print_list l = do_list print_int l;;
print_list : int list -> unit = <fun>
#print_list l;;
123- : unit = ()
#let rec map f l =
  match l with
  | [] -> []
  | x :: rest -> f x :: map f rest;;
map : ('a -> 'b) -> 'a list -> 'b list = <fun>
#let succ_l = map (function x -> x + 1) ll;;
succ_l : int list = [1; 2; 3; 4]
#print_list succ_l;;
1234- : unit = ()
#let somme l = it_list (function x -> function y -> x + y) 0 l;;
somme : int list -> int = <fun>
#somme ll;;
- : int = 6
#somme succ_l;;
- : int = 10

En Caml, la gestion mémoire est automatique.

B.2.11  Modules

(* Stacks *)

(* This module implements stacks (LIFOs), with in-place modification. *)

type 'a t;;
        (* The type of stacks containing elements of type ['a]. *)

exception Empty;;
        (* Raised when [pop] is applied to an empty stack. *)

value new: unit -> 'a t
        (* Return a new stack, initially empty. *)
  and push: 'a -> 'a t -> unit
        (* [push x s] adds the element [x] at the top of stack [s]. *)
  and pop: 'a t -> 'a
        (* [pop s] removes and returns the topmost element in stack [s],
           or raises [Empty] if the stack is empty. *)
  and clear : 'a t -> unit
        (* Discard all elements from a stack. *)
  and length: 'a t -> int
        (* Return the number of elements in a stack. *)
  and iter: ('a -> 'b) -> 'a t -> unit
        (* [iter f s] applies [f] in turn to all elements of [s], from the
           element at the top of the stack to the element at the
           bottom of the stack. The stack itself is unchanged. *)
;;

type 'a t = { mutable c : 'a list };;

let new () = { c = [] };;

let clear s = s.c <- [];;

let push x s = s.c <- x :: s.c;;

let pop s =
  match s.c with
  | hd::tl -> s.c <- tl; hd
  | []     -> raise Empty;;

let length s = list_length s.c;;

let iter f s = do_list f s.c;;

CAMLC=camlc -W -g -I .

OBJS= module1.zo module2.zo
EXEC= prog

all: $(OBJS)
        $(CAMLC) -o $(EXEC) $(OBJS)

clean:
        rm -f *.z[io] *.zix *~ #*#

depend:
        mv Makefile Makefile.bak
        (sed -n -e '1,/^### DO NOT DELETE THIS LINE/p' Makefile.bak; \
         camldep *.mli *.ml) > Makefile
        rm Makefile.bak

.SUFFIXES:
.SUFFIXES: .ml .mli .zo .zi

.mli.zi:
        $(CAMLC) -c $<
.ml.zo:
        $(CAMLC) -c $<

### EVERYTHING THAT GOES BEYOND THIS COMMENT IS GENERATED
### DO NOT DELETE THIS LINE

Bibliothèques

Nombres aléatoires

Analyse syntaxique et lexicale

B.2.12  Fonctions graphiques

#open "graphics";;
open_graph "";;

moveto x y

déplace le crayon aux coordonnées absolues (x, y).

lineto x y

trace une ligne depuis le point courant jusqu'au point de coordonnées (x, y).

plot x y

trace le point (x, y).

set\_color c

fixe la couleur du crayon. (Les couleurs sont obtenues par la fonction rgb; on dispose aussi des constantes black, white, red, green, blue, yellow, cyan et magenta.)

set\_line\_width n

change la largeur du trait du crayon.

draw\_arc x y rx ry a1 a2

trace un arc d'ellipse de centre (x, y) de rayon horizontal rx, vertical ry, de l'angle a1 à l'angle a2 (en degrés).

draw\_ellipse x y rx ry

trace une ellipse de centre (x, y) de rayon horizontal rx, et de rayon vertical ry.

draw\_circle x y r

trace un cercle centre (x, y) et de rayon r.

draw\_char c

affiche le caractère c au point courant dans la fenêtre graphique.

draw\_string s

affiche la chaîne de caractères s.

close\_graph ()

détruit la fenêtre graphique.

clear\_graph ()

efface l'écran.

size\_x ()

renvoie la taille de l'écran en abscisses.

size\_y ()

renvoie la taille de l'écran en ordonnées..

background

et foreground sont respectivement les couleurs du fond et du crayon.

point\_color x y

renvoie la couleur du point (x, y).

current\_point ()

renvoie la position du point courant.

button\_down

renvoie vrai si le bouton de la souris est enfoncé, faux sinon.

mouse\_pos ()

renvoie les cordonnées du curseur de la souris.

read\_key ()

attend l'appui sur une touche, la renvoie.

key\_pressed ()

renvoie vrai si une touche est enfoncée, faux sinon.

wait\_next\_event evl

attend jusqu'à ce que l'un des événements de la liste evl se produise, et renvoie le statut de la souris et du clavier à ce moment-là. Les événements possibles sont:

• Button_down: le boutton de la souris a été pressé.
• Button_up: le boutton de la souris a été relaché.
• Key_pressed: une touche a été appuyée.
• Mouse_motion: la souris a bougé.
• Poll: ne pas attendre, retourner de suite.

Un exemple

#open "graphics";;
open_graph "";;

let c = 5;;              (* Le rayon de la balle *)

let draw_balle x y =
 set_color foreground; fill_circle x y c;;

let clear_balle x y =
 set_color background; fill_circle x y c;;

let get_mouse () =
 while not (button_down ()) do () done;
 mouse_pos();;

let wait () = for i = 0 to 1000 do () done;;

let v_x = 2              (* Vitesse de déplacement de la balle *)
and v_y = 3;;

let x_min = 2 * c + v_x;; (* Cadre autorisé *)
let x_max = size_x () - x_min;;
let y_min = 2 * c + v_y;;
let y_max = size_y () - y_min;;

let rec pong_aux x y dx dy =
 draw_balle x y;
 let new_x = x + dx
 and new_y = y + dy in
 let new_dx =
  if new_x <= x_min || new_x >= x_max then (- dx) else dx
 and new_dy =
  if new_y <= y_min || new_y >= y_max then (- dy) else dy in
 wait ();
 clear_balle x y;
 pong_aux new_x new_y new_dx new_dy;;

let pong () = clear_graph(); pong_aux 20 20 v_x v_y;;

pong ();;

let dx = ref v_x
and dy = ref v_y;;

let pong () =
 clear_graph();
 let x = ref 20
 and y = ref 20 in
 while true do
  let cur_x = !x
  and cur_y = !y in
  draw_balle cur_x cur_y;
  x := cur_x + !dx;
  y := cur_y + !dy;
  if !x <= x_min || !x >= x_max then dx := - !dx;
  if !y <= y_min || !y >= y_max then dy := - !dy;
  wait ();
  clear_balle cur_x cur_y
 done;;

Documentation

B.3  Syntaxe BNF de Caml

Règles de grammaires

Précédences

Règles lexicales

        and    as     begin       do      done      downto 
        else   end    exception   for     fun       function 
        if     in     let         match   mutable   not 
        of     or     prefix      rec     then      to 
        try    type   value       where   while     with

        #    !    !=   &    (    )    *    *.   +    +. 
        ,    -    -.   ->   .    .(   .[   /    /.   : 
        ::   :=   ;    ;;   <    <.   <-   <=   <=.  <>
        <>.  =    =.   ==   >    >.   >=   >=.  @    [ 
        [|   ]    ^    _    __   {    |    |]   }    '

Bibliographie

• [1] Le langage Caml, Pierre Weis et Xavier Leroy, InterEditions, 1993, ISBN 2-7296-0493-6.
• [2] Manuel de Référence du langage Caml, Xavier Leroy et Pierre Weis, InterEditions, 1993, ISBN 2-7296-0492-8.
• [3] Approche fonctionnelle de la programmation, Guy Cousineau et Michel Mauny, Ediscience (Collection Informatique), 1995, ISBN 2-84074-114-8.
• [4] Concepts et outils de programmation -- le style fonctionnel, le style impératif avec CAML et Ada Thérèse Accart Hardin et Véronique Donzeau-Gouge Viguié, InterEditions, 1991, ISBN 2-7296-0419-7.
• [5] Option informatique, Denis Monasse, Vuibert (Enseignement supérieur et Informatique), 1996, ISBN 2-7117-8831-8
• [6] Lawrence C. Paulson. ML for the working programmer. Cambridge University Press, 1991.
  
  
• [7] Edinburgh LCF, M.J. Gordon, R. Milner, C. Wadsworth, LNCS 78, 1979.
  
  
• [8] Elements of ML programming, Jeffrey D. Ullman, Prentice Hall, 1994.
  
  
• [9] The definiton of Standard ML, Robin Milner, Mads Tofte, Robert Harper, The MIT Press, 1990.