Table des matières:
'_a
?
_
(un souligné) ?
:=
et <-
pour la modification d'une
valeur mutable ?
explode : string -> char list
et
implode : char list -> string
?
printf
n'imprime pas tout ?
Des parties du format de printf
sont oubliées ?
printf
ne marche pas ?
Des parties du format de printf
sont oubliées ?
input_value
, on me dit que la valeur est tronquée ?
let f x = let rec f_rec
... ou let rec f x ?
gprof
?
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.
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).
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.)
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).
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.
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 ...
_
?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>
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.
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.
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.
Il n'y a pas de réponse générale satisfaisante à ce problème, mais plusieurs solutions partielles:
#let rec identite x = x and id_int (id : 'a -> 'a) x = (id x : int);; identite : 'a -> 'a = <fun> id_int : (int -> int) -> int -> int = <fun> #let identite_int x = id_int identite x;; identite_int : int -> int = <fun>
#let forward_id = (ref (fun _ -> raise (Failure "undefined") : 'a -> 'a));; forward_id : ('_a -> '_a) ref = ref <fun> #let rec identite x = x and id_int x = (!forward_id x : int);; identite : 'a -> 'a = <fun> id_int : int -> int = <fun> #forward_id;; - : ('_a -> int) ref = ref <fun> #forward_id := identite;; - : unit = () #forward_id;; - : (int -> int) ref = ref <fun>Maintenant
forward_id
a pour type le type de l'occurrence
correspondante d'emploi de la fonction identite
, tandis
que la fonction identite
est bien polymorphe.
#forward_id;; - : (int -> int) ref = ref <fun> #identite;; - : 'a -> 'a = <fun>
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 = ()
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).
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>
Oui, Caml propose des fonctions qui manipulent les bits qui représentent les nombres entiers:
land
calcule le ``et'' logique bits à bits de deux nombres.
lor
calcule le ``ou'' logique bits à bits de deux
nombres.
lsl
décale les bits vers la gauche (ainsi
n lsl 1
multiplie n
par 2
).
asr
décale les bits vers la droite en respectant
le bit de signe de son argument (ainsi n asr 1
divise
n
par 2
en respectant le signe de n
).
lsr
décale les bits vers la droite sans
respecter le bit de signe (ainsi n lsl 1
divise
n
par 2
, sans forcément respecter le signe de
n
).
lnot
change chaque bit du nombre par sa négation
logique.
Pour lire un entier bit-à-bit en Caml, il suffit de préfixer
la liste de ses bits par 0b
:
# 0b101;; - : int = 5
À 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.
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 commetype 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;;
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:
==
teste l'identité de ses arguments, en testant l'égalité
physique des représentations mémoires. ==
est très efficace
car ce prédicat correspond généralement à une instruction de la
machine. ==
s'applique à tout couple de valeurs du même type sans
provoquer d'erreurs: pour toutes les valeurs non allouées on teste
l'identité bit-à-bit de leur représentation, et pour toutes les
valeurs allouées on teste si elles sont stockées à la même adresse mémoire.
=
teste l'égalité sémantique: les arguments sont-ils
isomorphes ? Pour cela =
parcourt en parallèle les deux données
jusqu'à trouver une différence, ou avoir terminé le parcours.
=
peut boucler en cas de valeurs cycliques.
En résumé: ==
est
==
).
=
: il faut avoir une
certaine connaissance de la représentation interne des valeurs pour
l'utiliser à bon escient (par exemple deux nombres flottants
``évidemment égaux'' ne sont pas ==
avec la plupart des compilateurs Caml).
En revanche, =
est
=
peut boucler à jamais (il serait sans doute concevable
d'améliorer le prédicat pour qu'il utilise un algorithme qui termine
plus souvent).
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 = falseCes 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.
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.
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
=
é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
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.
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`
.
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
.
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 pourn >= 0
et l'autre pourn < 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...
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.
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;;
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.
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>})})})})}
let
intempestif (non protégé par la construction d'un flux) ou
bien un filtrage qui oblige à calculer tout le flux avant de
déterminer la bonne branche. Avant d'examiner ces deux cas, je vous rappelle
la règle de l'évaluation des flux:
#let rec suivants_de n = [< 'n; suivants_de (n + 1) >];; suivants_de : int -> int stream = <fun>
suivants_de (n + 1)
est évalué
paresseusement, c'est-à-dire seulement lorsque qu'on accèdera au
deuxième élément du flux.
#let rec double = function [< 'n; s >] -> [< '(2 * n); double s >];; double : int stream -> int stream = <fun>
double
où l'appel récursif est dans le
filtre et produit directement la queue du flux résultat:
#let rec boucle = function [< 'n; boucle s >] -> [< '(2 * n); s >];; boucle : int stream -> int stream = <fun>L'appel récursif sur la queue du flux argument, oblige le système à dégeler le flux pour prouver que
boucle
s'applique sans
échec sur la queue de son flux argument; l'appel récursif provoque
alors le filtrage par le même filtre qui entraîne à nouveau le dégel
et la fonction boucle en cas de flux infini, ou échoue si le flux est
fini (puisque les appels récursifs vont finalement vider le flux et
que la fonction ne sait pas traiter le cas d'un flux vide):
#boucle [< '1 >];; Exception non rattrapée: Parse_error
=
est sans signification. On pourrait
éventuellement les comparer élément par élément, mais il faut
être conscient que ce parcours supprime les éléments des flux à comparer.
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
.
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 =
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).
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).
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:
Obj
,
output_value
, input_value
, etc,
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.
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.
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 "*)";; *)
:=
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
x.r := expression
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é...
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:
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;;
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 ?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" iet
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.
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!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!
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
.
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"
D
spécifie le dispositif d'affichage où
mettre la fenêtre (display name
du serveur X). Si cet
argument est omis, sa valeur par défaut correspond à la machine qui
lance l'ordre de création de la fenêtre; il faut cependant tout de même
mettre un espace pour séparer cet argument omis de la spécification de
la géométrie de la fenêtre. Attention, cet espace en début de chaîne
est donc obligatoire si l'on précise la taille et la position de la
fenêtre. (La syntaxe complète des dispositifs est nom de
machine:d.s
où d
est le numéro de dispositif
(ensemble d'écrans partageant les mêmes claviers et souris) et
s
est le numéro d'écran du dispositif où afficher la
fenêtre. Ainsi, pour un seul écran et un seul clavier nom de
machine:0.0
représente l'écran de cette machine.)
G
spécifie la géométrie de la fenêtre,
c'est-à-dire sa taille et sa position sur l'écran.G
a pour syntaxe LxHsXsY
, où:
L
est un entier mesurant la largeur de la fenêtre en pixels.
H
est un entier mesurant la hauteur de la fenêtre en pixels.
x
est un séparateur obligatoire entre ces deux nombres.
X
et Y
sont deux entiers indiquant la
position de la fenêtre dans l'écran par le déplacement à effectuer
par rapport aux bords.
s
est un signe qui vaut +
ou
-
:
+
: le déplacement suivant est à compter
par rapport au bord gauche de l'écran (pour les abscisses) ou au haut de l'écran
(pour les ordonnées),
-
: le déplacement suivant est à compter
par rapport au bord droit de l'écran (pour les abscisses) ou au bas
(pour les ordonnées).
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
.
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.
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
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 -lX11Où
<other options>
représente n'importe quelle option
du compilateur (par exemple, fixer le nom de l'exécutable (-o program
)
<other .zo files>
comprend l'ensemble des fichiers compilés
nécessaires à fabriquer le programme.
Remarque: l'ordre des arguments a une importance, ne pas le modifier si vous ne connaissez pas les options du compilateur.
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.
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; }
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).
Oui. Voir le manuel de référence du langage ici.
Oui. Voir le manuel de référence du langage ici.
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.
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 sont les suivantes:
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:
lsl
, lsr
,
asr
) : 1 add.
create_string
: coût constant environ
1 cell (le coût de création d'une cellule de liste).
make_string
: coût proportionnel à la
longueur de la chaîne (coût sans initialisation
+ une écriture par caractère).
make_string
. Dans le
meilleur des cas, le coût est presque nul (allocation statique à
la compilation).
l1
et l2
la
complexité est à peu près de
``création d'une chaîne de longueur(l1 +. L2)
''
+ (1 lecture + 1 écriture) *. (l1 +. l2)
).
l1
et l2
la
complexité est à peu près (2 écritures + 1 lecture) *. (l1
+. l2)
).
==
le coût est de 1 add. Sur
flottants avec eq_float
coût 3 add. Sur les chaînes de
caractères les tests (par exemple eq_string
) ont, dans
le cas le pire, un coût proportionnel au nombre de
caractères. Pour les autres valeurs le test avec l'égalité
générique dépend de la valeur elle-même et nécessite le parcours
complet de la structure (et peut même boucler dans certains cas),
par exemple le test d'égalité de deux listes impose un parcours
complet des deux listes dans le pire des cas (listes égales).
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ébutLe 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ébutest 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!
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)
.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:
e1
et e2
pour obtenir
v1
et v2
,
(e1, e2)
f
sur ce n-uplet.
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.
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.
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 = ...
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 = ...
> 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.
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.
Contacter l'auteur Pierre.Weis@inria.fr