Foire aux questions sur Caml

Contacter l'auteur Pierre.Weis@inria.fr

Fichier créé en octobre 1995.

Table des matières:

* Typage

* Sémantique

* Syntaxe

* Bibliothèques

* Efficacité

Typage

Message d'erreur incompréhensible : un type semble incompatible avec lui-même.

On obtient parfois le message: cette expression est de type ``un certain type'' mais est utilisée avec le type le même ``un certain type''. Ceci se produit souvent lorsqu'on travaille dans le système interactif.

Motif: en fait, vous avez déclaré deux fois le même type, c'est-à-dire deux types ayant le même nom. Le compilateur ne les confond pas, mais ne peut faire autrement que les imprimer de la même manière puisqu'ils ont le même nom. Considérez par exemple:

type compteur = Compteur of int;;

let x = Compteur 1;;

Supposez maintenant qu'on redéfinisse le type compteur, puis une fonction travaillant sur ce (nouveau) type compteur. On ne pourra pas appliquer cette fonction à x qui est de l'ancien type compteur:

type compteur = Compteur of int;;

let incr_compteur c = match c with Compteur x -> Compteur (x + 1);;
incr_compteur : compteur -> compteur = <fun>

incr_compteur x;;
Entrée interactive:
>incr_compteur x;;
>              ^
Cette expression est de type compteur,
mais est utilisée avec le type compteur.

Ce phénomène apparaît souvent lorsqu'on utilise le système interactif en rechargeant de multiples fois le même fichier (ce qui redéfinit les types de données). Il a lieu également lorsqu'on utilise le compilateur indépendant, quand les dépendances entre unités de compilation sont mal gérées et qu'une interface ou une implémentation qui aurait dû être recompilée ne l'a pas été.

La solution: quitter la session et tout recharger dans une nouvelle session. Si le phénomène apparaît lors de la compilation d'un fichier, il faut recompiler tous les fichiers dont il dépend.

Comment introduit-on le polymorphisme ?

Le polymorphisme consiste à introduire des schémas de type, c'est-à-dire des types avec des variables de type quantifiées universellement. Ces paramètres de schéma de type sont dénotée par le préfix ' (par exemple 'a). Tous les paramètres des schémas de type sont quantifiés en tête du schéma: ainsi 'a -> 'a signifie: Pour tout type 'a, 'a -> 'a. Cette quantification des paramètres de type est implicite en Caml:

#map;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>

Le (schéma) de type de map signifie Pour tous types 'a, 'b, ('a -> 'b) -> 'a list -> 'b list.

Le polymorphisme est uniquement introduit par la définition des noms lors d'une construction let (soit locale, soit globale).

Le problème et sa solution:

La règle originale de typage de la définition locale

let nom = expr1 in expr2

consiste à typer expr1 d'abord, de donner à nom un schéma de type (un type polymorphe) selon le type obtenu pour expr1, puis de typer expr2 en prenant une copie du schéma de type de nom à chaque occurrence de nom. Le schéma de nom est obtenu prenant pour paramètres de type toutes les variables de type introduites pendant le typage de expr1 qui reste sans contrainte après le typage complet de expr1. Par exemple pour

let id = function x -> x in ...

id a pour schéma de type: pour tout 'a. 'a -> 'a, et peut donc être utilisé avec plusieurs types incompatibles dans le reste du programme, par exemple avec les types int -> int et bool -> bool si la partie in est id 1; id true.

Malheureusement cette règle simple n'est pas correcte en présence de valeurs mutables (comme les références, les tableaux, ou les enregistrements à champs mutables). En effet, considérez:

let mauvaise_ref = ref [] in ...
Avec la règle let originale, mauvaise_ref a pour schéma ``pour tout 'a. 'a list ref''. On peut donc l'employer avec différents types dans le reste du programme, ce qui est faux (toutes les listes sont homogènes en Caml). Par exemple, si on pouvait utiliser mauvaise_ref avec les types int list ref et bool list ref, alors on pourrait écrire:
let mauvaise_ref = ref [] in
    mauvaise_ref := [1];
    if hd (!mauvaise_ref) then ...

(mauvaise_ref := [1] serait correctement typé, puisque mauvaise_ref pourrait être utilisée avec le type int list ref; hd (!mauvaise_ref) serait aussi correctement typé, puisque mauvaise_ref serait utilisable avec le type bool list ref. Ce programme conduirait à une erreur fatale à l'exécution puisque après l'affectation, mauvaise_ref contient une liste d'entier et non une liste de booléens.)

La nouvelle règle pour les définition de noms:

En bref, un système de type sûr pour Caml doit interdire l'existence de valeurs mutables polymorphes à l'exécution. Cela a fait l'objet de beaucoup d'études dans la communauté des chercheurs, et de nombreux systèmes complexes ont été proposés. Récemment, il est apparu qu'une modification très simple de l'ancienne règle suffisait en pratique. Quand on type

let nom = expr1 ...

On généralise le type de expr1 quand expr1 est une fonction, un identificateur ou une constante. Sinon l'identificateur nom n'est pas polymorphe (les variables de type ne sont pas généralisées).

Quels programmes sont maintenant monomorphes ?

La nouvelle règle implique évidemment que si expr1 est une application de fonction, alors l'identificateur nom est monomorphe. Par exemple

let mauvaise_ref = ref [] in ...

mauvaise_ref n'est pas polymorphe, et c'est le but recherché. En revanche:

let map_id = map (function x -> x) in ...

Puisque map_id est défini par une application son type n'est pas généralisé et map_id ne peut pas être utilisé avec plusieurs types différents. C'est pourquoi:

#let map_id = map (function x -> x) in
map_id [1]; map_id [true];;
Entrée interactive:
>map_id [1]; map_id [true];;
>                   ^^^^^^
Cette expression est de type bool list,
mais est utilisée avec le type int list.

est mal typé (la première utilisation de map_id, soit map_id [1], impose à map_id le type int list -> int list, et map_id [true] est mal typé). Le paragraphe suivant explique comment obtenir une définition polymorphe de map_id, et plus généralement comment obtenir un résultat polymorphe lorsqu'on appliquer partiellement une fonction polymorphe.

Ma fonction n'est pas (assez) polymorphe ?

Comment rendre polymorphes des définitions obtenues par application partielle ?

Le cas le plus fréquent où une définition n'est pas assez polymorphe se produit lors de la définition d'une fonction par application partielle d'une fonction polymorphe plus générale. En ce cas, il suffit de définir la fonction en rendant la fonctionnalité explicite pour le contrôleur de type: en général on ajoute une construction function ou un paramètre supplémentaire (cette transformation est techniquement appelée eta-expansion):

let map_id l = map (function x -> x) l in ...
ou encore
let map_id = function l -> map (function x -> x) l in ...

Une variable de type commence par _ ?

Quand un identificateur est défini par une expression non généralisable il peut avoir un type qui comporte des types inconnus (précisément les variables de type qui n'ont pu être généralisées) qui seront déterminées par l'usage qui est fait de l'identificateur dans le reste du programme. Ces types inconnus sont représentés par des variables de type particulières, préfixées par un souligné (par exemple '_a) qu'on appelle variables de type faibles. Attention, ces variables représentent des types inconnus qui devront être déterminés par la suite du typage: c'est pourquoi les variables faibles peuvent disparaître à tout instant, parce qu'elles ont été déterminées justement.

let map_id = map (function x -> x) in
map_id [1];;

Après sa définition map_id a le type '_a list -> '_a list, où '_a signifie un certain type a. C'est pourquoi le typage de map_id [1] va déterminer ce type inconnu int (et map_id aura le type int list -> int list dans toute la suite du programme).

Ce phénomène apparaît encore plus clairement en cassant le let in en deux phrases:

#let map_id = map (function x -> x);;
map_id : '_a list -> '_a list = <fun>
#map_id [1];;
- : int list = [1]

Maintenant l'inconnue '_a du type de map_id est déterminée, et map_id a un type sans inconnues:

#map_id;;
- : int list -> int list = <fun>

Mon programme n'est pas (assez) polymorphe ?

Sémantiquement, la définition d'un identificateur par une construction let est équivalente à une application de fonction. Plus formellement, let ident = e1 in e2 est équivalent à (function ident -> e2) e1. Cela signifie que les deux programmes produiront le même résultat et les mêmes effets.

Cependant, ces deux programmes ne sont pas interchangeables du point de vue du typage: en effet la construction let est susceptible d'introduire du polymorphisme quand l'application de fonction laissera ident monomorphe dans l'expression e2.
Ainsi:

#let id = function x -> x in id id;;
- : '_a -> '_a = <fun>

Mais:

#(function id -> id id) (function x -> x);;
Entrée interactive:
>(function id -> id id) (function x -> x);;
>                   ^^
Cette expression est de type 'a -> 'b,
mais est utilisée avec le type 'a.

Comment écrire une fonction dont l'argument est polymorphe ?

L'argument d'une fonction n'est jamais polymorphe dans le corps de la fonction. Tout emploi de cet argument contraint son type. On ne peut donc pas écrire de fonctionnelle ayant pour argument une fonction utilisée avec deux types différents. Par exemple, on peut écrire une fonction qui applique un identificateur polymorphe:

#let id x = x;;
id : 'a -> 'a = <fun>
#let phi () = id 1, id true;;
phi : unit -> int * bool = <fun>

Mais il est impossible d'abstraire cet identificateur et d'en faire un argument de la fonction phi:

#let phi id () = id 1, id true;;
Entrée interactive:
>let phi id () = id 1, id true;;
>                         ^^^^
Cette expression est de type bool,
mais est utilisée avec le type int.

Ma fonction récursive n'est pas (assez) polymorphe ?

En effet une fonction récursive n'est jamais polymorphe dans le corps de sa définition. Tout emploi monomorphe de cette fonction influence son type final:

#let rec trou_noir x = trou_noir 0;;
trou_noir : int -> 'a = <fun>

La fonction trou_noir boucle évidemment, mais le type obtenu par Caml est surprenant: l'argument x doit être de type int alors qu'il n'est même pas utilisé dans le corps de la fonction. On constate bien que le fait d'avoir appliqué trou_noir à un argument entier dans son corps a contraint son type.

Ce phénomène apparaît plus naturellement dans le cas de fonctions mutuellement récursives. Par exemple:

#let rec identite x = x
and identite_int x = (identite x : int);;
identite : int -> int = <fun>
identite_int : int -> int = <fun>

La deuxième définition identite_int utilise identite avec le type int -> int, cela rend identite monomorphe.

Comment passer outre cette limitation ?

Il n'y a pas de réponse générale satisfaisante à ce problème, mais plusieurs solutions partielles:

En cas de fonctions vraiment mutuellement récursives comme

#let rec f x = g 1
and g x = 1 + f x;;
f : int -> int = <fun>
g : int -> int = <fun>
pour obtenir un typage polymorphe pour f et g, il faut prédéfinir la fonction g parce qu'elle possède une occurrence monomorphe (plus exactement il faut définir une version de la fonction g pour chacune de ses occurrences monomorphes)
#let forward_g_int = (ref (fun _ -> raise (Failure "undefined") : 'a -> 'b));;
forward_g_int : ('_a -> '_b) ref = ref <fun>
#let rec f x = !forward_g_int 1
and g x = 1 + f x;;
f : 'a -> int = <fun>
g : 'a -> int = <fun>
#forward_g_int := g;;
- : unit = ()

Dans certains cas, on peut rendre typables des programmes qui ne le sont pas avec le système Caml utilisé. On complique un peu l'exemple précédent en employant aussi f avec un type monomorphe:

let rec f x = g 1
and g x = 1 + f true + f x;;
Entrée interactive:
>and g x = 1 + f true + f x;;
>    ^^^^^^^^^^^^^^^^^^^^^^
Cette expression est de type bool -> int,
mais est utilisée avec le type int -> int.

Pour passer outre, on prédéfinit aussi une version de f pour le type bool:

#let forward_f_bool = (ref (fun _ -> raise (Failure "undefined") : 'a -> 'b));;
forward_f_bool : ('_a -> '_b) ref = ref <fun>
#let forward_g_int = (ref (fun _ -> raise (Failure "undefined") : 'a -> 'b));;
forward_g_int : ('_a -> '_b) ref = ref <fun>
#let rec f x = !forward_g_int 1
and g x = 1 + !forward_f_bool true + f x;;
f : 'a -> int = <fun>
g : 'a -> int = <fun>
#forward_f_bool := f;;
- : unit = ()
#forward_g_int := g;;
- : unit = ()

Si on utilise l'identificateur défini récursivement avec plusieurs types monomorphes différents, il faut prédéfinir une version de l'identificateur pour chaque type d'utilisation. Par exemple pour définir

let rec f x = f 1; f true; x;;
Il faudra prédéfinir une version de f pour les entiers et les booléens:
#let forward_f_bool = (ref (fun _ -> raise (Failure "undefined")));;
forward_f_bool : ('_a -> '_b) ref = ref <fun>
#let forward_f_int = (ref (fun _ -> raise (Failure "undefined")));;
forward_f_int : ('_a -> '_b) ref = ref <fun>
#let rec f x = !forward_f_int 1; !forward_f_bool true; x;;
f : 'a -> 'a = <fun>
#forward_f_bool := f;;
- : unit = ()
#forward_f_int := f;;
- : unit = ()

Comment avoir deux types ayant un label commun ?

Lorsqu'on définit des types qui partagent un label, le label du deuxième type cache celui du premier. Par exemple:

type point_3d = {x : float; y : float; z : float};;
type point_2d = {x : float; y : float};;

# {x = 10.; y = 20.; z = 30.};;
The record field label z belongs to the type point_3d
but is here mixed with labels of type point_2d

Le moyen le plus simple de contourner cette difficulté est d'employer des noms différents. Par exemple

type point3d = {x3d : float; y3d : float; z3d : float};;
type point2d = {x2d : float; y2d : float};;

On peut également utiliser des modules, pour définir les deux types de points à l'intérieur d'un nouvel espace de noms:

module D3 = struct
 type point = {x : float; y : float; z : float}
end;;

module D2 = struct
 type point = {x : float; y : float}
end;;

Les labels peuvent être maintenant qualifiés avec le nom de leur module, et D3.x est différencié de D2.x:

# {D3.x = 10.; D3.y = 20.; D3.z = 30.};;
- : D3.point = {D3.x = 10.000000; D3.y = 20.000000; D3.z = 30.000000}
# {D2.x = 10.; D2.y = 20.};;
- : D2.point = {D2.x = 10.000000; D2.y = 20.000000}

On peut aussi adopter les objets, qui permettent la surcharge des noms de méthodes:

class point_3d ~x ~y ~z = object
  method x : float = x
  method y : float = y
  method z : float = z
end;;

class point_2d ~x ~y = object
  method x : float = x
  method y : float = y
end;;

En ce cas on obtient plus que la surcharge: on peut définir des fonctions polymorphes qui travaillent aussi bien sur les points de dimension 2 que de dimension 3, et l'on peut aussi considérer les points 3D comme des points 2D (à l'aide d'une simple coercion de type).

Comment avoir deux types ayant un constructeur commun ?

En règle général, on ne peut pas. Il faut donc utiliser des noms de constructeurs uniques dans tout le module qu'on écrit. À moins bien sûr de définir les deux types en question dans deux modules différents. Comme dans le cas des étiquettes (discuté ci-dessus), on obtient alors des constructeurs qu'on peut différencier en les qualifiant par le module auquel ils appartiennent.

Une autre solution consiste à utiliser des ``variantes polymorphes'', c'est-à-dire des constructeurs qui ne sont pas définis lors de la définition du type (ces constructeurs sont en quelque sorte préexistants). Par exemple:

type ids = [ `Name | `Val ];;
type person = [ `Name of string ];;
# let (f : person -> string) = function `Name s -> s;;
val f : person -> string = <fun>
# let (is_name : ids -> bool) = function `Name -> true | _ -> false;;
val is_name : ids -> bool = <fun>

Sémantique

Problèmes concernant les structures de données ?

Peut-on travailler au niveau du bit ?

Oui, Caml propose des fonctions qui manipulent les bits qui représentent les nombres entiers:

Lecture d'un entier bit à bit

Pour lire un entier bit-à-bit en Caml, il suffit de préfixer la liste de ses bits par 0b:

# 0b101;;
- : int = 5

Accès aux bits de la représentation d'un nombre

À l'aide des opérateurs bit-à-bits, on ``lit'' ou ``écrit'' aisément n'importe quel bit d'un nombre:

let nth_bit n i = (n lsr i) land 1;;
val nth_bit : int -> int -> int = <fun>
let set_nth_bit n i = n lor (1 lsl i);;
val set_nth_bit : int -> int -> int = <fun>
let clear_nth_bit n i = n land (lnot ((1 lsl i)));;
val clear_nth_bit : int -> int -> int = <fun>

À l'aide des opérateurs précédents et des chaînes de caractères, il est évidemment possible de définir et de gérer des tableaux de bits.

Peut-on définir des structures de données dont certains champs sont des bits ?

En C, on peut définir la taille d'une variable en terme de nombre de bits.
On écrit par exemple,
unsigned int a:1 ;,
unsigned int b:4 ; ....
Le symbole «:» sert à préciser le nombre de bits.
Puis-je définir des variable Objective Caml de la même manière ?

Non. La plus petite unité pour la représentation des données est le mot machine. Cependant, vous pouvez travailler au niveau des octets en utilisant les chaînes de caractères comme des tableaux d'octets.

En fait, je veux définir l'entête d'une donnée en utilisant le minimum de bits possible. J'imagine quelquechose comme
       type hd = { flag : int_1 ; on_off : int_1 ; seq_num : int_4 } ;;
       let header = { flag = 1 ; on_off = 0 ; seq_num = 0101 } ;;

Le mieux que vous puissiez faire est de représenter cette entête comme un entier et de définir des fonctions de constructions et d'accès, à l'aide des primitives travaillant au niveau des bits:

type hd = int;;

let make_hd flag on_off seq_num =
 flag lor (on_off lsl 1) lor (seq_num lsl 2);;

let flag_hd h = h land 1;;

let on_off_hd h = (h lsr 1) land 1;;

let seq_num_hd h = (h lsr 2) land 0xF;;

let header = make_hd 1 0 0b0101;;

L'égalité est-elle polymorphe ?

Il y a deux fonctions d'égalité en Caml: = et == qui sont toutes deux polymorphes de type: 'a -> 'a -> bool. Elles ne doivent pas être confondues car elles sont sémantiquement différentes:

En résumé: == est

En revanche, = est

Exemples:
Les chaînes de caractères sont des données allouées en mémoire, la différence sémantique entre = et == est donc évidente:

#let s = "ok";;
s : string = "ok"
#s == s;;
- : bool = true
#s == "ok";;
- : bool = false
#s = "ok";;
- : bool = true
#"ok" == "ok";;
- : bool = false
#"ok" = "ok";;
- : bool = true

Le comportement sur les valeurs mutables est aussi caractéristique: == est plus juste que =, puisque = ne répond pas toujours la même chose lorsque soumis aux mêmes données.

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

Pour les flottants le prédicat == n'est pas approprié:

1.0 == 1.0;;
- : bool = false
Ces deux flottants sont donc alloués. Pour les flottants il faut donc impérativement utiliser l'égalité =.

Pour les listes, le même phénomène se produit: comparer des listes à l'aide de == n'a pas grand sens:

#[1] == [1];;
- : bool = false
#[1] = [1];;
- : bool = true

Ce phénomène est généralement vrai pour toutes les structures de données non mutables: les comparer avec le prédicat = donne les résultats les plus intuitivement évidents.

Égalité et types abstraits

Les valeurs d'un type abstrait ne doivent pas être comparées par les prédicat polymorphes = ou == mais par une fonction d'égalité fournie avec le type abstrait: en effet les résultats que retourneraient les prédicats d'égalité prédéfinis sont en général sans signification pour les types abstraits, puisque la représentation des valeurs d'un type abstrait est souvent sans lien avec leur sémantique. À titre d'exemple, considérez le test d'égalité des nombres rationnels représentés comme un type produit; les rationnels 1/1 et 2/2 sont sémantiquement égaux, mais le prédicat = détecte à juste titre que leurs représentations sont différentes:

#type ratio = {numerateur : int; denominateur : int};;
Type ratio defined.
#{numerateur = 1; denominateur = 1} =
 {numerateur = 2; denominateur = 2};;
- : bool = false

Une autre erreur classique consiste à comparer des flux: le type stream étant un type abstrait, la comparaison des flux avec le prédicat = est sans signification.

Pour comparer des valeurs d'un type abstrait, il faut donc utiliser la comparaison définie par le module définissant le type abstrait (exemple). Si le module n'en fournit pas, il n'y a aucun moyen de comparer ces valeurs à bon escient.

Invalid_argument "equal: functional value" ?

Les valeurs fonctionnelles constituent un cas particulier de valeurs appartenant à un type de données abstrait: il n'y a donc pas lieu de comparer les fonctions avec les prédicats = ou ==. De plus il n'existe aucun prédicat pour comparer les valeurs fonctionnelles puisqu'il n'existe aucun moyen de prouver que deux fonctions sont égales (c'est un problème indécidable). Dans certains cas le prédicat = détecte ces arguments fonctionnels et échoue en déclenchant l'exception Invalid_argument.

#let id = function x -> x;;
id : 'a -> 'a = <fun>
#id = (function z ->
        let x = 1 in
        if x = 2 then z else id z);;
Exception non rattrapée: Invalid_argument "equal: functional value"

En cas de valeurs fonctionnnelles, le prédicat == teste comme d'habitude l'identité des représentations des valeurs: si == renvoie true c'est donc que les fonctions sont égales; en revanche si == rend false ce résultat démontre l'inégalité physique des deux fonctions, sans présager de leur égalité sémantique.

#(function x -> x) == (function x -> x);;
- : bool = false
#let f = function x -> x in f == f;;
- : bool = true

Exemple d'égalité définie sur un type abstrait

= échoue dès qu'il rencontre une composante fonctionnelle lors du parcours d'une valeur. Pour des valeurs d'un type abstrait cette erreur est souvent surprenante si l'on ne soupçonne pas la présence de valeurs fonctionnnelles dans les représentations. Par exemple le module set de la librairie de Caml Light propose une implémentation des ensembles par le type abstrait set__t. La représentation d'un ensemble comme valeur du type set__t fait intervenir la fonction de comparaison des éléments de cet ensemble. C'est pourquoi toute comparaison d'ensembles avec le prédicat = déclenche une erreur:

#let rec set_of_list = function
  | x :: l -> set__add x (set_of_list l)
  | [] -> set__empty (prefix -);;
set_of_list : int list -> int set__t = <fun>
#set_of_list [0] = set_of_list [0];;
Exception non rattrapée: Invalid_argument "equal: functional value"

La solution est évidemment d'utiliser la fonction de comparaison des ensembles fournie avec le module set:

#set__equal (set_of_list [0]) (set_of_list [0]);;
- : bool = true

Problèmes concernant le filtrage

Peut-on écrire plusieurs filtres pour même une clause (filtres ou) ?

Oui, on écrit tout simplement les filtres de la clause séparés par des barres verticales |. La clause sera sélectionnée si l'un des filtres correspond à l'argument du filtrage. Par exemple:

#let rec fib = function
 | 0 | 1 -> 1
 | n -> fib (n - 1) + fib (n - 2);;
Il y a certaines restrictions dans les filtres ``ou'': on ne peut pas y lier de variables. On ne peut donc y utiliser que des constantes ou des constructeurs fonctionnels ou des soulignés. Cela permet d'assurer que toutes les variables utilisées dans les parties expression des clauses sont liées quelquesoit le filtre qui a permis de sélectionner la clause.

Peut-on écrire des filtres intervalles ?

Ces filtres sont limités aux intervalles de caractères.

let is_upper = function
 | `A` .. `Z` -> true
 | _ -> false;;
Le premier filtre s'applique à tous les caractères compris entre `A` et `Z`.

Peut-on faire des gardes ?

Les gardes permettent de soumettre l'application d'une clause d'un filtrage au test d'une condition booléenne qu'on ne peut exprimer dans le filtrage (condition dépendant d'un calcul sur les valeurs manipulées par le programme, ou bien sur les variables liées dans le filtre). Un exemple typique d'utilisation consiste à tester l'égalité de certaines parties du filtre de la clause
Les gardes sont introduites par le mot-clé when suivi d'une expression quelconque qui s'évalue en un booléen.

Par exemple:

let rec boolean_or = function
 | x, y when x = y -> x
 | true, _ -> true
 | x, y -> boolean_or (y, x);;
La première clause s'applique uniquement pour un couple (x,y) qui vérifie la condition x = y.

Filtrage partiel dans une garde ?

Les gardes introduisent un phénomène nouveau dans la détection des filtrages redondants ou partiels. En effet, le compilateur traite les clauses avec garde comme si elles pouvaient échouer par échec de la condition (la garde produisant un résultat false). Voici un problème typique:

En définissant une fonction très simple : deux cas exclusifs, l'un pour n >= 0 et l'autre pour n < 0. Pourtant le compilateur me dit que le filtrage est n'est pas exhaustif. Pourquoi ? Y-a-t-il vraiment une situation concrète qui fait échouer le filtrage ?
let f = function
 | n when n >= 0 -> n
 | n when n < 0 -> n + 1;;
Entrée interactive:
......function
| n when n >= 0 -> n
| n when n < 0 -> n + 1..
Attention: ce filtrage n'est pas exhaustif.
f : int -> int = <fun>

Le filtrage est bien exhaustif. Seulement le compilateur ne peut pas s'en apercevoir statiquement. En effet, il n'y a aucune restriction sur les expressions qui peuvent apparaître dans une clause when qui sont arbitrairement compliquées: il n'y a donc pas de moyens de savoir si elles vont produire le résultat true ou false. Dans votre cas, il faudrait que le compilateur démontre que la deuxième garde est toujours vraie, ce qu'il ne peut pas faire en toute généralité.

Faut-il donc que j'ajoute une clause à l'évidence inutile ? Par exemple:
let f = function
 | n when n >= 0 -> n
 | n when n < 0 -> n + 1
 | _ -> failwith "impossible";;

Non, pour aider le compilateur, il vous suffit de lui signaler que vous savez que la deuxième garde sera toujours vérifiée si la première échoue. Le plus radical pour cela est d'enlever carrément la seconde garde et d'écrire:

let f = function
 | n when n >= 0 -> n
 | n -> n + 1;;

Vous pouvez aussi simplement remplacer la garde par une remarque, ce qui aidera la relecture:

let f = function
 | n when n >= 0 -> n
 | n (* n < 0 *) -> n + 1;;

Dans un cas si simple, on pourrait ajouter au compilateur un cas particulier qui détecterait automatiquement l'exhaustivité en présence de gardes. Mais comment généraliser et traiter des cas plus complexes comme:

let rec f = function
 | n when n >= 0 -> n
 | n when - f (- n) < 0 -> n + 1;;
qui est évidemment exhaustif, mais bien difficile à deviner!

Notez que la situation est vraiment complexe: une règle simple comme «si l'on teste la valeur de la même expression avec deux prédicats exclusifs alors le filtrage est exhaustif» est fausse. Considérez par exemple:

let rec f = function
 | n when g (n + 1) >= 0 -> n
 | n when g (n + 1) < 0 -> n + 1

and g =
 let alea = ref true in
 (function n ->
    alea := not !alea;
    if !alea then -1 else 1);;
Quoique répondant à cette règle simple, le filtrage de f est ``extrêmement'' non exhaustif, et d'une manière vraiment subtile...

Peut-on définir une sentinelle dans les tableaux ?

Autre formulation:
J'ai besoin d'une valeur ``impossible'' servant de ``sentinelle'' car ma fonction peut calculer des résultats non-significatifs en cas d'arguments aberrants. Mais ce n'est pas élégant et empêche le polymorphisme ...

D'abord, il n'y a pas de ``valeur impossible'' en Caml. La manière Caml de résoudre le problème est de définir explicitement une valeur impossible, à l'aide d'un type à deux alternatives:

type 'a valeur_gardée =
| Impossible
| Possible of 'a;;

De cette façon, on peut tester si une valeur est ``impossible''! Au passage le type valeur_gardée est isomorphe au type ``option'', qu'on utilise régulièrement pour les valeurs optionnelles:

type 'a option =
| None
| Some of 'a;;

Ce type sert à initialiser les données qui contiennent des morceaux qui ne peuvent être calculés au moment de la définition: ces morceaux (probablement des champs mutables dans un enregistrement) sont initialisés à None, et mis à jour avec la bonne valeur quand c'est possible.

Comment définir une valeur sentinelle polymorphe ?

Autre formulation de cette question:
``J'ai pensé définir un type somme: 'a | Failed, ainsi toute fonction retournerait un "union" du résultat normal et de Failed ?''

Caml dispose justement d'un moyen très clair d'obtenir ce résultat: ce sont les exceptions. Une fonction peut renvoyer un résultat normal quand c'est possible, et déclencher une exception dans le cas contraire. C'est le cas de beaucoup de fonctions de bibliothèque qui échouent soit avec l'exception Not_found (pour les fonctions de recherche), soit avec l'exception Invalid_argument, soit encore avec l'exception Failure quand rien de plus approprié ne s'impose.

Par exemple: on travaille sur les ``maps'', c'est-à-dire les fonctions à support fini d'un ensemble dans un autre. On considère le prédicat qui à (x : 'a) et (y : 'a) associe vrai si x et y ont même image et faux sinon. On utilise la fonction de bibliothèque map__find et l'on surveille ses échecs:

let map_compare cle1 cle2 table =
  try
    let image_cle1 = map__find cle1 table in
    let image_cle2 = map__find cle2 table in
    image_cle1 = image_cle2
  with Not_found -> false;;

Y a-t-il des opérateurs paresseux en Caml ?

Le premier opérateur paresseux est évidemment la construction ``if then else'', puisque les expressions de ses parties ``then'' et ``else'' ne sont pas systématiquement évaluées.

En outre, les opérateurs logiques de Caml sont définis en fonction du ``if then else'':

e1 && e2 signifie if e1 then e2 else false
e1 || e2 signifie if e1 then true else e2

De ce fait, ces opérateurs héritent un comportement paresseux de la construction ``if then else'': si e1 est faux alors e1 && e2 s'évalue en faux, sans que e2 ne soit évaluée. Ce comportement n'est reproductible par aucune fonction Caml, puisque les arguments des fonctions Caml sont systématiquement évalués avant l'appel de la fonction (appel par valeur).

Il n'y a donc pas de fonction Caml f telle que f e1 e2 soit équivalent à e1 && e2. L'opérateur préfixe correspondant à && existe cependant: comme pour toutes les constructions syntaxiques infixes, la fonction préfixe f correspondant à l'opérateur op est par définition:

let f e1 e2 = e1 op e2;;
Cette règle ne souffre pas d'exceptions, on l'applique donc évidemment pour les opérations booléennes. Par exemple pour && on obtient:
let prefix && e1 e2 = e1 && e2;;
ce qui signifie évidemment:
let prefix && e1 e2 = if e1 then e2 else false;;
Il faut donc savoir qu'à cause de ce caractère paresseux des opérateurs booléens, prefix && e1 e2 n'est pas tout-à-fait équivalent à e1 && e2: prefix && e1 e2 évalue toujours ses deux arguments, c'est la version stricte du && booléen.

Cette discussion n'a évidemment plus lieu d'être si l'opérateur booléen a été redéfini pour être lié à une fonction Caml normale: en ce cas les versions infixes et préfixes de l'opérateurs redeviennent équivalents.

Comment faire des listes paresseuses ?

Listes paresseuses simples:

(* Listes a` retardement *)
type 't llist =
   | Nil
   | Cons of 't cell
and 't cell = { hd : 't ; tl : unit -> 't llist}
;;

let rec lmap f = function
| Nil -> Nil
| Cons {hd = x; tl = t} ->
   Cons {hd = f x; tl = (fun () -> lmap f (t ()))};;

let rec ldo_list f n = function
| Nil -> ()
| Cons {hd = x; tl = t} ->
   if n > 0 then begin f x; ldo_list f (n - 1) (t ()) end;;

let rec nat = Cons {hd = 0; tl = (fun () -> lmap succ nat)};;

ldo_list print_int 10 nat;;

nat;;

Avec mise en mémoire du développement de la queue de la liste:

type 't llist =
   | Nil
   | Cons of 't cell
and 't cell = { hd : 't ; mutable tl : unit -> 't llist}
;;

let rec lmap f = function
| Nil -> Nil
| Cons ({hd = x; tl = t} as cell) ->
   Cons {hd = f x;
         tl = (function () ->
                let tail = t () in
                cell.tl <- (fun () -> tail);
                lmap f tail)};;

let rec ldo_list f n = function
| Nil -> ()
| Cons ({hd = x; tl = t} as cell) ->
   if n > 0 then begin
    f x;
    let tail = t () in
    cell.tl <- (fun () -> tail);
    ldo_list f (n - 1) tail end;;

let rec nat = Cons {hd = 0; tl = (fun () -> lmap succ nat)};;

ldo_list print_int 5 nat;;
nat;;

Avec glaçons explicites:

type 'a frozen =
   | Freeze of (unit -> 'a)
   | Val of 'a;;

type 'a llist =
   | Nil
   | Cons of 'a cell

and 'a cell = { hd : 'a ; mutable tl : 'a llist frozen}
;;

let rec lmap f = function
| Nil -> Nil
| Cons {hd = x; tl = Val l} ->
   Cons {hd = f x; tl = Freeze (function () -> lmap f l)}
| Cons ({hd = x; tl = Freeze th} as cell) ->
   let thunk () =  
     let tail = th () in cell.tl <- Val tail; lmap f tail in
   Cons {hd = f x; tl = Freeze thunk};;

let rec nat = Cons {hd = 0; tl = Freeze (fun () -> lmap succ nat)};;

let rec ldo_list f n = function
| Nil -> ()
| Cons {hd = x; tl = Val l} ->
   if n > 0 then begin
    f x;
    ldo_list f (n - 1) l end
| Cons ({hd = x; tl = Freeze th} as cell) ->
   if n > 0 then begin
    f x;
    let tail = th () in
    cell.tl <- Val tail;
    ldo_list f (n - 1) tail end;;

Exemple d'utilisation: définition de la liste des nombres entiers:

#let rec nat = Cons {hd = 0; tl = Freeze (fun () -> lmap succ nat)};;
nat : int llist = Cons {hd=0; tl=Freeze <fun>}
#ldo_list print_int 5 nat;;
01234- : unit = ()
#nat;;
- : int llist =
 Cons
  {hd=0;
   tl=
    Val
     (Cons
       {hd=1;
        tl=
         Val
          (Cons
            {hd=2;
             tl=Val (Cons {hd=3; tl=Val (Cons {hd=4; tl=Freeze <fun>})})})})}

Problèmes sur les flux ?

Problèmes sur l'impression

Les impressions du toplevel sont tronquées ?

L'imprimeur du système interactif est confronté au problème de l'impression de structures de données bouclées, et il utilise un mécanisme de troncature pour assurer la terminaison de l'impression. Cette troncature met en jeu deux compteurs, l'un, print_depth, mesure la profondeur d'imbrication des données imprimées (par exemple un élément d'une liste de liste se trouve à profondeur 2), l'autre, print_length, mesure plus simplement le nombre de noeuds imprimés (par exemple chaque élément imprimé dans une liste incrémente la valeur de print_length). Par défaut print_depth vaut 100 et print_length 300. On fixe les valeurs de ces variables avec les fonctions set_print_depth et set_print_length.

Les impressions (ou les sorties) du toplevel sont brouillées ?

Si vous utilisez la directive install_printer pour créer un imprimeur pour vos valeurs, alors il faut impérativement utiliser la bibliothèque format pour écrire votre imprimeur. Sinon les sorties de votre imprimeur et celles du système interactif ne seront pas synchronisées, ne seront pas correctement entrelacées, puisque le système utilise cette bibliothèque, qui induit un retard à l'impression puisque le moteur de l'imprimeur enregistre les impressions à effectuer, puis décide des coupures de lignes avant d'imprimer réellement.
Si vous utilisez des primitive de plus bas niveau, vous risquez d'imprimer avant le moteur. Supposons par exemple que je déclare la primitive io__print_string (c'est-à-dire la primitive de bas niveau print_string du module io) comme l'imprimeur des chaînes de caractères. Alors l'impression d'une chaîne par le système interactif se produira trop tôt:

#"coucou";;
- : string = "coucou"
#install_printer "io__print_string";;
- : unit = ()
#"coucou";;
coucou- : string = 

La trace mélange les sorties ?

Si vous utilisez la directive install_printer pour créer un imprimeur pour vos valeurs, alors vous devez l'écrire en utilisant la librairie format. En effet, il faut synchroniser les sorties de votre imprimeur avec celles de la trace comme pour le cas du système interactif (voir une explication détaillée ou un exemple complet d'utilisation d'un imprimeur pendant la trace).

Valeurs mutables

Références et champs mutables

Disposant déjà des références et plus généralement des valeurs mutables comme les vecteurs, on peut se demander à quoi servent les champs modifiables des enregistrements: au lieu d'un champ modifiable, ne suffit-il pas de définir un champ non modifiable mais qui contienne une valeur mutable ? En première approximation la réponse est affirmative, mais en réalité il existe une subtile différence qui fait qu'en général il vaut mieux choisir un enregistrement à champ modifiable (en premier lieu pour des raisons d'efficacité, car on évite une indirection (un accès mémoire supplémentaire) à chaque accès à la valeur).
Cependant la différence de sémantique est subtile et implique bien évidemment le partage: la référence contenue dans le champ non modifiable d'un enregistrement est susceptible d'être physiquement partagée entre plusieurs enregistrements. Toute modification de cette référence partagée se répercute alors instantanément sur tous les enregistrements. Si cette sémantique est implémentée par un champ d'enregistrement modifiable, il faut au contraire répercuter la modification sur tous les enregistrements.
En pratique, on remarque cependant que ce comportement est rarement désiré, il est même souvent nuisible.
Considérez un type compte défini à l'aide de références:

#type compte = {numéro : int; solde : float ref};;
Le type compte est défini.
#let solde1 = ref 0.0;;
solde1 : float ref = ref 0.0
#let compte1 = {numéro = 1; solde = solde1}
and compte2= {numéro = 2; solde = solde1};;
compte1 : compte = {numéro = 1; solde = ref 0.0}
compte2 : compte = {numéro = 2; solde = ref 0.0}
Les comptes compte1 et compte2 partagent maintenant le même solde physique: toute modification du solde de compte1 se répercute sur compte2, ce qui n'est certainement pas désirable.
#compte1.solde := 1.0;;
- : unit = ()
#compte2;;
- : compte = {numéro = 2; solde = ref 1.0}

La définition de champs d'enregistrement modifiables contenant des valeurs mutables n'est pas interdite, mais les exemples nécessitant ce genre de définitions sont peu fréquents (voir cependant cet exemple).

Mon programme fait une erreur système (bus error, segmentation fault, violation de protection) ?

Normalement cela ne devrait jamais se produire en Caml; cependant cela arrive dans certaines circonstances particulières, à la suite d'une erreur de programmation ou des particularité d'un OS ou d'un processeur:

Le remède est souvent d'utiliser le débogueur pour localiser l'endroit où se produit cette erreur, afin de la comprendre et de la supprimer.

Syntaxe

Pourquoi Caml a-t-il une syntaxe différente de celle de SML ?

La raison principale est historique: Caml a été inventé avant SML.

Le langage Caml est issu du langage ML d'origine, crée par Robin Milner en 1978, et développé conjointement à l'INRIA à partir de 1981. Le premier compilateur Caml fut écrit en 1984, et distribué à partir de 1985. Standard ML n'existait évidemment pas à l'époque, et Caml avait une syntaxe proche de celle de ML V6.2, dont le compilateur a d'ailleurs servi à compiler le premier compilateur Caml. Par la suite, lorsque la syntaxe de Standard ML fut définie, Caml a gardé sa propre syntaxe pour plusieurs raisons. La première raison, subjective, est que nous pensions que la syntaxe de Standard ML n'apportait pas de progrès significatif sur celle de ML (donc sur celle de Caml). La seconde raison, plus fondamentale, est que le langage nous semblait trop jeune à l'époque pour être figé dans un standard; la compréhension de certains traits de ML a d'ailleurs fait de gros progrès ces dernières années, et cela impose des modifications importantes (citons le typage des traits impératifs ou la sémantique et le typage des modules). En outre, nous voulions garder la liberté d'étendre la syntaxe si le besoin s'en faisait sentir (ce qui nous a permis d'introduire les boucles ``for'', le ``try with'' et le ``match with'', les caractères, les gardes dans le filtrage, la syntaxe d'accès et de modifications des vecteurs et des chaînes de caractères, les annotations ``mutable'' des enregistrements). Cette liberté relative de la syntaxe du langage, permet l'émergence de nouveaux systèmes autour de Caml: par exemple les systèmes Caml Light et Objective Caml, qui respectent bien entendu la syntaxe du coeur du langage, mais comportent leurs propres extensions.

Et donc Caml possède sa propre syntaxe.

Commentaire impossible à fermer ?

Pour assurer la mise en commentaire de n'importe quel programme, les commentaires Caml sont lexés. Cela signifie que les conventions lexicales de Caml doivent être parfois respectées dans les commentaires. Le principal problème vient des chaînes de caractères: un guillemet dans un commentaire est interprété comme le début d'une chaîne de caractères et l'analyseur lexical attendra le guillemet fermant en sautant la fin de commentaire si elle existe. Par exemple:

(* Calcul de la date de no"el *)
est un commentaire non fermé. En revanche le fragment suivant est compris comme un seul commentaire:
(* A revoir: que se passe-t-il si s contient les caractères
   * et ) à la suite ?
let comment_string s =
  print_string "(*"; print_string s; print_string "*)";;
*)

Pourquoi deux syntaxes := et <- pour la modification d'une valeur mutable ?

La raison en est qu'il y a ambiguïté lorsqu'on mélange les références et les structures de données mutables:

type fou = {mutable r : 'a ref};;

let x = {r = ref 0};;
Supposons qu'on écrive maintenant
  1. x.r := expression
  2. x.r <- expression

Pour le cas 1, il est clair que cela signifie que (le contenu) de la référence doit être modifié (expression doit avoir le type int).
Pour le cas 2, cela signifie qu'il faut changer la référence contenue dans le champ r (expression doit avoir le type int ref).
Si l'on avait la même syntaxe pour les deux cas, alors il y aurait ambiguïté...

Bibliothèques

Quel est l'équivalent de explode : string -> char list et implode : char list -> string ?

Il n'y a pas de fonctions prédéfinies équivalentes dans la bibliothèque. Vous pouvez utilisez les deux fonctions suivantes:

En Caml Light
let explode s =
  let rec exp i l =
   if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (string_length s - 1) [];;
let implode l =
 let res = create_string (list_length l) in
 let rec imp i = function
  | [] -> res
  | c :: l -> res.[i] <- c; imp (i + 1) l in
 imp 0 l;;
En Objective Caml:
let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;
let implode l =
  let res = String.create (List.length l) in
  let rec imp i = function
  | [] -> res
  | c :: l -> res.[i] <- c; imp (i + 1) l in
  imp 0 l;;

printf n'imprime pas tout ? Des parties du format de printf sont oubliées ?

En mixant des fonctions Printf.printf et List.iter, j'obtiens un résultat étrange:
si je remplace (fun i -> Printf.printf " ** %i" i) par (Printf.printf " ** %i) comme argument de List.iter, le début de la chaîne (avant le %i) est oublié (sauf à la première itération).
On devrait obtenir la même chose avec les deux définitions suivantes:
    let pas_de_probleme l =
      List.iter (fun i -> Printf.printf " ** %i" i) l;
      print_newline ();;

    let probleme l =
      List.iter (Printf.printf " ** %i") l;
      print_newline ();;
Et pourtant:
    let l = [0; 1; 2; 3; 4] in
    pas_de_probleme l;
    probleme l;;

     ** 0 ** 1 ** 2 ** 3 ** 4
     ** 01234

Ce comportement est normal bien que votre étonnement puisse se concevoir. L'affirmation ``On devrait obtenir la même chose'' repose évidemment sur le fait qu'on suppose que

fun i -> Printf.printf " ** %i" i
et
Printf.printf " ** %i"
sont deux expressions équivalentes, puisque c'est la seule différence entre les textes des programmes probleme et pas_de_probleme. Ces deux expressions pourraient être équivalentes, mais elles ne le sont pas.
Observons en effet la définition de ces deux expressions à deux identificateurs f et g:
let f = fun i -> Printf.printf " ** %i" i;;
val f : int -> unit = <fun>

let g = Printf.printf " ** %i";;
 ** val g : int -> unit = <fun>
Comme on s'y attend, la définition de f ne produit pas d'impression; en revanche la définition de g produit une impression!
Cela s'explique mieux si l'on sait que Printf.printf " ** %i" est exactement équivalent à: print_string " ** "; fun i -> print_int i, car alors la définition de g est forcément équivalente à
let g = print_string " ** "; fun i -> print_int i;;
et produit donc normalement l'impression de la chaîne " ** ", puis la liaison de g à la fonction fun i -> Printf.printf "%i".

C'est la même expansion (poursuivie récursivement) qui donne la signification des formats plus complexes. Ainsi, l'expression printf "1: %i 2: %s 3: %f." est équivalente à

print_string "1: ";
(fun i ->
   print_int i;
   print_string " 2: ";
   (fun s ->
      print_string s;
      print_string " 3: ";
      (fun f ->
         print_float f;
         print_string ".")))
Cela explique alors le comportement des définitions suivantes:
let h = Printf.printf "1: %i 2: %s 3: %f." 1;;
1: 1 2: val h : string -> float -> unit = <fun>
et
let i = h "deux";;
deux 3: val i : float -> unit = <fun>

i 4.0;;
4.000000.- : unit = ()

En conclusion, il faut éviter d'évaluer partiellement les applications de printf (et au contraire laisser dans les programmes la forme fonctionnelle explicite fun x -> printf "..." x lorsqu'on passe printf en argument). À moins évidemment de savoir parfaitement ce qu'on fait et de parier sur le fait que le lecteur du programme le saura aussi!

Comment fixer la taille de l'écran graphique ?

Il suffit de fixer cette taille lors de l'ouverture de la fenêtre graphique. Ce paramètre apparaît dans la chaîne de caractères argument de open_graph.

Par exemple:

open_graph " 640x480";;
ouvre une fenêtre de 640 pixels de large et 480 pixels de haut. (Attention le blanc en début de chaîne est obligatoire dans certaines implémentations.)

Le paragraphe suivant vous explique la syntaxe complète de l'argument de open_graph.

Comment fixer la position de l'écran graphique ?

Cette position peut être fixée lors de l'ouverture de la fenêtre graphique, dans la chaîne argument de open_graph. Attention, certaines implémentations de la librairie graphique n'autorisent pas la définition de la position de la fenêtre.

La syntaxe de la chaîne de caractères argument de open_graph est la syntaxe normale de positionnement des fenêtres sous X, à savoir:
"D G"

Par exemple:

open_graph " 640x480+100-0";;
ouvre une fenêtre graphique de taille 640 par 480 pixels, placée presque complètement à gauche et tout en bas de l'écran.
open_graph "latour:0.1 300x200+0+0";;
ouvre une fenêtre graphique de taille 300 par 200 pixels, placée en haut et à gauche de l'écran numéro 1 de la machine latour.

Comment sauver l'écran graphique ?

Il faut créer une image en Caml et la sauver sur disque avec output_value. Par exemple:

(* Écrit une image dans le fichier ``file_name'' *)
let output_image im file_name =
 let oc = open_out_bin file_name in
 let imv = dump_image im in
 output_value oc imv;
 close_out oc;;

(* Lit une image dans le fichier ``file_name'' *)
let input_image file_name =
 let ic = open_in_bin file_name in
 let im = make_image (input_value ic) in
 close_in ic;
 im;;

(* Sauve le contenu actuel de la fenêtre graphique. *)
let save_screen file_name =
 let im = get_image 0 0 (size_x ()) (size_y ()) in
 output_image im file_name;;

(* Récupère le contenu de la fenêtre graphique. *)
let restore_screen file_name =
 let im = input_image file_name in
 draw_image im 0 0;;

Remarque: le contenu de l'écran dépend de sa taille, mais ce peut être plusieurs MO.

Comment faire du graphisme sous Unix ?

Comme sur tous les systèmes d'exploitations, il faut commencer par demander à disposer des fonctions de la bibliothèque graphique à l'aide de la commande:

#open "graphics";;
Cependant, dans le système interactif normal, la bibliothèque graphique n'est pas chargée en mémoire, et tous les appels aux fonctions de la bibliothèque se soldent par un échec à l'édition des liens.

Le problème est donc de faire l'édition des liens avec la bibliothèque graphique. Pour le système interactif, cette édition a été faite pour vous à l'installation de la bibliothèque graphique: il faut donc appeler Caml avec une commande spéciale:

$ camllight camlgraph

Comment faire un programme exécutable qui comporte du graphisme ?

Comme dans le cas du système interactif (cf), il faut faire l'édition des liens avec la bibliothèque graphique. Vous devez donc utiliser le mode ``custom'' du compilateur, pour disposer des primitives C de la bibliothèque. On écrira donc:

        camlc -custom <other options> \
              unix.zo graphics.zo <other .zo and .ml files> \
              -lgraph -lunix -lX11

Remarque: l'ordre des arguments a une importance, ne pas le modifier si vous ne connaissez pas les options du compilateur.

Impossible de relire une valeur par input_value, on me dit que la valeur est tronquée ?

Le fichier que vous écrivez et lisez lorsque vous manipulez sur disque des valeurs Caml, n'est pas un fichier de texte mais un fichier «binaire»: il ne contient pas forcément des caractères ASCII habituels. C'est pourquoi il faut l'ouvrir avec les primitives open_in_bin et open_out_bin pour éviter toute conversion automatique des retour-chariots et toute interprétation d'un caractère comme l'indication de la fin du fichier (la fin d'un fichier texte est indiquée par le caractère ^Z sous DOS). Sinon, à la première occurrence du caractère ^Z, le système de fichier prétend que la fin de fichier est atteinte avant la fin réelle du fichier (d'où le message «truncated object» produit par input_value. Pour un exemple complet d'utilisation de input_value, voir ci-dessus la sauvegarde de l'écran graphique.

Comment faire un makefile pour fichiers Caml ?

Les modules permettent évidemment la compilation séparée, ce qui sous Unix s'accompagne de l'utilisation de l'utilitaire make. Nous donnons un fichier makefile générique pour Caml Light et pour Objective Caml.

Pour comprendre le mécanisme, on pourra aussi lire le makefile plus simple ci-dessous qui gère un petit système écrit en Caml, comportant la liste de modules OBJS (supposée réduite aux deux modules module1 et module2), et produisant l'exécutable EXEC (que nous appelons prog).

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

Les dépendances entre modules sont automatiquement recalculées en lançant make depend. La commande camldep peut être implémentée par le perl script suivant:

#!/usr/local/bin/perl

# To scan a Caml Light source file, find all references to external modules
# (#open "foo";; or foo__bar), and output the dependencies on standard output.
#
# Usage:    camldep [-I path] <file> ...

while ($#ARGV >= 0) {
  $_ = shift(@ARGV);
  if (/^-I(.*)$/) {
    $dir = $1 ? $1 : shift(@ARGV);
    $dir =~ s|/$||;
    unshift(@path, $dir);
  }
  elsif (/(.*)\.mli$/ || /(.*)\.zi$/) {
    do scan_source ($_, "$1.zi");
  }
  elsif (/(.*)\.ml$/ || /(.*)\.zo$/) {
    do scan_source ($_, "$1.zo");
  }
  else {
    die "Don't know what to do with $_";
  }
}

sub scan_source {
  local ($source_name, $target_name) = @_;
  $modname = $target_name;
  $modname =~ s|^.*/||;
  $modname =~ s|\.z[io]$||;
  undef(%imports);
  open(SRC, $source_name) || return;
  while(<SRC>) {
    if (m/#\s*open\s*"([^"]*)"/) {
      $imports{$1} = 1;
    }
    while (m/([a-zA-Z0-9_]+)__/g) {
      $imports{$1} = 1;
    }
  }
  close(SRC);
  undef(@deps);
  if ($target_name =~ m/\.zo$/ && -r ($source_name . "i")) {
    push(@deps, "$1.zi");
  }
  foreach $modl (keys(%imports)) {
    next if ($modl eq $modname);
    if ($dep = do find_path ("$modl.mli")) {
      $dep =~ s/\.mli$/.zi/;
      push(@deps, $dep);
    }
    elsif ($dep = do find_path ("$modl.ml")) {
      $dep =~ s/\.ml$/.zo/;
      push(@deps, $dep);
    }
  }
  if ($#deps >= 0) {
    print "$target_name: ";
    $col = length($target_name) + 2;
    foreach $dep (@deps) {
      $col += length($dep) + 1;
      if ($col >= 77) {
        print "\\\n    ";
        $col = length($dep) + 5;
      }
      print $dep, " ";
    }
    print "\n";
  }
}

sub find_path {
  local ($filename) = @_;
  if (-r $filename) {
    return $filename;
  }
  foreach $dir (@path) {
    if (-r "$dir/$filename") {
      return "$dir/$filename";
    }
  }
  return 0;
}

Y-a-t-il une interface entre Caml et LaTex ?

Une interface entre Caml et LaTex est livrée avec la distribution du système dans le répertoire contrib/caml-tex sous la forme d'une commande caml-tex. C'est un filtre qui extrait les phrases Caml d'un fichier LaTex argument, les évalue et insère leurs sorties dans le fichier LaTex résultat. (Ce filtre est écrit en Perl et nécessite donc Perl installé sur votre machine).

Y-a-t-il une interface entre Caml et Lex ?

Oui. Voir le manuel de référence du langage ici.

Y-a-t-il une interface entre Caml et Yacc ?

Oui. Voir le manuel de référence du langage ici.

Efficacité

Coûts des opérations de base ?

Il est bien difficile de donner une idée du coût des opérations de base, puisque ce coût dépend non seulement de la machine, mais encore du système Caml utilisés: un compilateur optimisant produisant directement de l'assembleur ne se comportera pas du tout comme un compilateur vers du code octet pour une machine virtuelle. Non seulement les coûts absolus des opérations seront différents, mais même les coûts relatifs des opérations les unes par rapport aux autres varieront de plusieurs ordres de grandeur. Et quand bien même on garderait toujours le même système Caml, les coûts relatifs des opérations dépendraient toujours fortement de la machine considérée.

La situation se complique encore avec les processeurs modernes qui sont capables d'effectuer plusieurs opérations en même temps, ce qui fait que certaines des instructions deviennent gratuites, c'est-à-dire à coût nul, lorsqu'elles ont la chance de s'exécuter parfaitement simultanément avec une autre opération, soit parce que le processeur a eu l'opportunité de lancer plusieurs opérations en même temps, soit parce qu'il est en attente de la fin d'une opération plus complexe mais indépendante de l'opération considérée. Ainsi, le temps requis pour l'exécution d'une instruction donnée varie selon le moment où cette instruction est présentée au processeur. Dans ces conditions, il est bien difficile d'attribuer une quelconque fonction de coût aux instructions assembleur, à plus forte raison aux opérations de base d'un langage de haut niveau comme Caml.

Certains principes résistent cependant à ces variations matérielles et à ces contingences temporelles dans le déroulement du flux d'instructions des programmes. Par exemple, l'addition des nombres entiers est pratiquement toujours l'opération la plus rapide et les processeurs modernes sont capables d'en exécuter plusieurs millions à la seconde.

Je donnerai donc une indication de coût des opérations de base en donnant un ordre de grandeur de ce coût, mesuré en unités conventionnelles, correspondant à des opérations élémentaires de la machine (par exemple l'addition des entiers). Pour certaines opérations, le temps d'exécution dépend de la taille des arguments et j'indiquerai alors la complexité correspondante. Dans tous les cas, les coûts proposés ne sont que des ordres de grandeur plausibles et donnés à titre indicatif: il ne faut absolument pas les considérer comme des données scientifiques assurées.

Un simple ordre d'idée

Avec un compilateur vers du code octet : chaque opération a un coût pratiquement constant, de l'ordre de celui d'une addition, étant donné le temps incompressible passé à décoder les instructions de code octet. Les indications de complexité des opérations de complexité non constante sont valables pour tous les compilateurs et restent donc valables pour le code octet.

Avec un compilateur optimisant : le coût des opérations reflète plus fidèlement les capacités du matériel. C'est dans cette hypothèse que sont donnés les temps relatifs qui suivent.

En résumé :
Retenez que l'appel de fonction est très rapide en Caml: il coûte souvent deux fois moins qu'une multiplication.
En revanche les concaténations de chaînes (^), de vecteurs (concat_vect, Array.concat) et de listes (@) n'ont pas un coût constant mais proportionnel à la longueur de leur résultat.

Les tests d'égalité des entiers et flottants ont un coût constant très faible, de même que le test d'égalité physique ==. En revanche l'égalité générique polymorphe a un coût non borné a priori, qui est par exemple linéaire en la longueur de ses arguments dans le cas des chaînes de caractères.

Les unités de mesure

Les unités de mesure sont les suivantes:

Ordre de grandeur des coûts relatif des unités de mesure

Les valeurs relatives de ces unités dépendent de la machine et du compilateur.

Avec un compilateur vers du code octet : on pourra considérer que toutes les unités sont équivalentes.

Avec un compilateur optimisant : les ordres de grandeurs des coûts relatifs des unités, mesurés de bonne foi sur plusieurs machines accessibles depuis ma propre station, s'établissent comme suit:

Ordre de grandeur des coûts par opération Caml

Boucles ou fonctions récursives ?

Une fonction récursive code facilement une boucle. Par exemple la boucle for i = début to fin do body done est équivalente à

let rec for_loop i =
 if i <= fin then begin body; for_loop (i + 1) end in
for_loop début
Le choix entre les deux écritures est essentiellement une question de style, bien que la deuxième forme se justifie dans le cas où la boucle doit rendre un résultat. Sinon la boucle for est plus claire: elle est plus concise et met mieux en évidence les bornes de la boucle. En revanche:
let rec for_loop i =
 if i <= fin then
   if v.(i) = 0 then i else for_loop (i + 1)
 else -1 in
for_loop début
est peut-être un peu plus clair qu'une implémentation avec une boucle lançant une exception:
exception Exit of int;;
try
 for i = début to fin do
  if v.(i) = 0 then Exit i
 done;
 -1
with Exit i -> i

D'autre part, les compilateurs reconnaîtront sans doute difficilement une boucle dans un codage par une fonction récursive, et cette version risque donc d'être moins bien compilée. Allez au plus simple!

Comment écrire des fonctions à plusieurs arguments ?

Il n'y a pas de moyen syntaxique de définir des fonctions à plusieurs arguments en Caml. C'est pourquoi l'utilisateur doit encoder ces fonctions à l'aide de la curryfication ou de n-uplets d'arguments.

let f (x, y) = x + y;;
ou
let f x y = x + y;;
Du point de vue expressivité, les fonctions curryfiées sont applicables partiellement, alors que les fonctions définies sur des n-uplets ne le sont pas.

En ce qui concerne l'efficacité, les compilateurs Caml privilégient (souvent) la curryfication.

La compilation naïve de ces deux codages n'est pas efficace et voici pourquoi. Supposons f définie par let f x y = body c'est-à-dire par

   let f = function x -> function y -> body.
Il est clair sur cette forme expansée que f supporte les applications partielles: si e1 s'évalue en v1, alors l'expression f e1 s'évalue en une fermeture avec pour partie code (function y -> body) et pour partie environnement (x, v1).
Donc la compilation naïve de f e1 e2 (c'est-à-dire de (f e1) e2) commence par appeler f avec l'argument v1, puis f construit et retourne la fermeture intermédiaire, et cette fermeture est ensuite appliquée à (la valeur de) e2. C'est inefficace, puisqu'il faut deux appels de fonction et coûteux en mémoire puisqu'il faut construire cette fermeture intermédiaire qui est immédiatement appliquée et devient inutile.

Supposons maintenant que f est définie par let f (x, y) = body. La manière naïve de compiler f (e1, e2) est maintenant:

Dans ce cas nous ne faisons qu'un seul appel de fonction, mais à nouveau nous construisons une structure de donnée intermédiaire inutile pour appeler la fonction.

Une façon plus intelligente de compiler l'une de ces deux formes est indispensable, car les fonctions à plusieurs arguments sont légions et l'efficacité du langage souffrirait d'une compilation naïve de ces fonctions. En pratique, cette compilation est un peu difficile, mais l'idée principale est simple:

Comme les fonctions curryfiées sont un peu plus puissantes, puisqu'elles supportent d'être appliquées partiellement, on suppose que les utilisateurs préfèrent cette manière de coder les fonctions n-aires. C'est pourquoi, en général, les compilateurs Caml optimisent l'application totale de fonctions curryfiées. Les optimisations mises en jeu ne sont pas toujours aussi efficaces que celle décrite ci-dessus, mais la compilation des fonctions currifiées est vraiment meilleure que celle des fonctions à n-uplets pour les compilateurs de Caml Light, Objective Caml, Bigloo et Camlot. Les compilateurs Caml n'optimisent généralement pas l'appel de fonctions à n-uplets.

let f x = let rec f_rec ... ou let rec f x ?

Quelle est la version la plus efficace ?

   let map f =
     let rec mapf l =
       match l with
       | [] -> []
       | (x::t) -> let y = f x in y::(mapf t) in
     mapf;;
ou
   let rec map f l =
     match l with
     | [] -> []
     | (x::t) -> let y = f x in y::(map f t);;
La réponse est: cela dépend du compilateur!

La première définition est un point de vue étrange sur map, considérée comme une fonction non récursive qui calcule une fonction qui boucle. La seconde définition est plus naturelle et montre bien que map a deux arguments. S'il n'y a aucun argument d'efficacité pour préférer la première définition, je préfère sans aucun doute la seconde qui est la définition ``naturelle'' de map.

Pour comparer l'efficacité de ces deux versions, je suppose que vous connaissez la problématique de la définition et de la compilation des fonctions n-aires en Caml (voyez ici).

La version naïve:

   let rec map f l =
     match l with
     | [] -> []
     | x :: t -> let y = f x in y :: (map f t);;
met en évidence que map possède deux arguments. C'est pourquoi un compilateur qui optimise l'application totale de fonctions curryfiées, compilera efficacement l'appel récursif. Au contraire, un compilateur naïf construira une fermeture intermédiaire à chaque appel récursif.

Le premier codage:

   let map f =
     let rec mapf l =
       match l with
       | [] -> []
       | x :: t -> let y = f x in y :: (mapf t) in
     mapf;;
peut tromper le compilateur optimisant qui ne détectera pas que map est une fonction curryfiée à deux arguments: au contraire il construira une fermeture pour la fonction mapf, et une fermeture est moins efficacement appelée.

Un cas intéressant: le compilateur Bigloo fait une passe d'optimisation (appelée ``eta'') qui réécrit automatiquement ce code pour compiler finalement un code équivalent à la version naïve!

En revanche, un compilateur naïf compilera naïvement comme d'habitude, mais dans cette seconde version le code demande effectivement la construction d'une seule fermeture intermédiaire, quand map est appliquée partiellement à f. Donc les appels récursifs à map (qui se produisent maintenant via mapf) ne construiront plus de fermetures intermédiaires inutiles: avec un compilateur naïf, la seconde version devient un peu plus efficace que la première.

En conclusion: préférer le programme le plus simple et naturel, il est plus clair et les compilateurs sont écrits pour optimiser le code plus naturel.

Pourquoi ma constante n'est-elle pas allouée statiquement ?

Considérez le code

let gamma x =
    let coeffs = [ 0; 1; 2 ] in
    ...
La liste coeffs est une constante immuable entre chaque appel de la fonction gamma. Le compilateur peut donc l'allouer statiquement. Pourtant la sémantique intuitive de Caml commanderait de l'allouer dynamiquement à chaque appel de la fonction gamma: le code de la définition est naturellement exécuté chaque fois qu'on entre dans le corps de la fonction gamma. Pour assurer que la définition de coeffs ne soit évaluée qu'une seule fois, lors de la définition de la fonction gamma, il aurait fallu écrire:
let gamma =
    let coeffs = [ 0; 1; 2 ] in
    (function x -> ...

Si la donnée citée dans le code n'est pas mutable, son partage ne peut donner lieu à des erreurs sémantiques. La plupart des compilateurs Caml détecteront ce cas et alloueront cette constante statiquement. Sinon, la solution la plus simple et la plus efficace est de définir la constante à l'extérieur de la fonction qui l'emploie:

let coeffs = [| 0; 1; 2 |];;
let gamma x =
    ...

Pourquoi mon vecteur n'est-il pas alloué statiquement ?

On considère une variante du problème précédent, concernant les données mutables.

let gamma x =
    let coeffs = [| 0; 1; 2 |] in
    ...
En ce cas le vecteur coeffs ne peut pas être alloué statiquement en général car on ne peut partager ses différentes incarnations (qui peuvent être incorporées dans d'autres données dans le corps de la fonction gamma, ou encore rendues en résultat).

Cependant, si le vecteur coeffs n'est pas utilisé comme une structure mutable mais comme une liste à accès direct (en particulier s'il n'est jamais modifié dans le corps de la fonction, ni rendu en résultat) alors son partage devient possible. Cette analyse est difficile, et il est probable que la plupart des compilateurs ne la feront pas. Vous devrez donc l'exprimer vous-même en définissant la constante à l'extérieur de la fonction qui l'utilise:

let coeffs = [| 0; 1; 2 |];;
let gamma x =
    ...

Obsessed by speed

> 1. If I define Array.iter + a function that uses it,
>    will ocamlopt combine these two functions two one?
>    (I looked in the assembler code, but it seemed as
>     ocamlopt didn't combine them)

You're right, the function inlining pass in ocamlopt is rather
conservative and doesn't inline and beta-reduce function arguments to
higher-order functions.  Inlining is a delicate trade-off between too
little and too much (e.g. code size and compile time explosion), and
OCaml errs on the conservative side.

> 2. Do we need special Pentium-4 adaptions to utilize
>    its very good float performance?

I'm not familiar with the P4 micro-architecture, so I don't know.
ocamlopt uses the standard IA32 stack-based model for floating-point
code.  Apparently, the P4 can now do 64-bit float arithmetic between
true registers (the SSE2 model), and ocamlopt could generate better
(and simpler!) floating-point code for this model.  Don't know how
much of a performance difference that would make, though.  

At any rate, the ocamlopt port for AMD's x86-64 architecture will use
the SSE2 model.

> 3. Would ocamlopt benefit from a peephole optimizer of
>    the assembler code? Or is the assembler code already
>    optimal?

No assembly code is ever optimal, especially if machine-generated :-)
A peephole optimizer could remove some cosmetic inefficiencies, but I
doubt this would make a significant speed difference.  Today's
processors have enough instruction-level parallelism and dynamic
instruction scheduling that a few redundant integer operations here
and there don't really hurt.  

Other higher-level optimizations not currently performed could improve
performance more, e.g. common subexpression elimination on memory loads.

> 4. What is unboxed and what isn't?
>    I have noticed that there is a
>    continuos work to unbox more.

Very briefly:

Always unboxed:
  int, char, bool, constant constructors of datatypes.
Locally unboxed (in expressions and let...in): 
  float, int32, nativeint (and int64 on 64-bit processors)
Unboxed inside arrays:
  float
Unboxed inside big arrays:
  all numerical types
Always boxed:
  everything else (records, non-constant datatype constructors,
  tuples, arrays, etc)

> 5. How do you make sense of gprof-output? Any suggestions?

The "info" docs for gprof contain a tutorial.
The function names that appear are of the form Modulename_functionname_NNN
where NNN is a unique integer.
Be careful with the call graph reported by gprof: it is totally
inaccurate for higher-order functions.

Comment faire des encarts d'assembleur ?

Vous pouvez interfacer votre programme Caml avec un programme C quelconque. Dans ce programme C quelconque, vous pouvez alors utiliser librement des encarts d'assembleur si votre compilateur C les supporte.

Il n'y a en revanche aucun moyen direct d'insérer de l'assembleur dans un code source Caml; le langage est de trop haut niveau pour que cette opération soit aisée à procurer au programmeur (les invariants du gestionnaire mémoire sont complexes et doivent impérativement être respectés); de surcroît, nous avons la volonté de maintenir la portabilité parfaite du langage et les encarts d'assembleur rendrait cette portabilité par trop difficile à assurer.


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