|
Zakath |
  |
Guru
Déconnecté
Niveau : 5
N° de Membre :
7213
Ancienneté : 97%
Participation : 12%
Inscription: 15 Dec 2002
Localisation: Copenhague
Messages: 9866
Sujets Lancés : 426
|
 [TUTORIEL] Programmation Caml
MaJ du 11/02 : tableaux
Je ne suis pas du tout sûr d'être dans la bonne section, donc n'hésitez pas à me déplacer le cas échéant...
Ce post se veut un tutorial d'initiation à la programmation en Caml. Comme j'en suis l'auteur et que je rédige au fur et à mesure, il se peut qu'il y ait des erreurs ou que je ne sois pas clair... N'hésitez pas à me le dire !
Introduction
Tout d'abord, petite présentation de Caml :
Il s'agit d'une version de ML (abbréviation de Meta Language) développée par les petits gars de l'INRIA (à ne pas confondre avec l'INRA ;-)). Par méta-langage, on entend (me semble-t-il, mais cela reste à vérifier) que ce langage a été spécifiquement développé pour que les programmes soient faciles à démontrer (au sens mathématique du terme). Ceci implique une syntaxe claire et structurée (contrairement au C !), mais aussi que Caml est un langage de haut niveau, donc qui ne fait pas se préoccuper la programmeur de questions liées au matériel (comme l'allocation de mémoire en C, par exemple).
Il s'agit également d'un langage fonctionnel, par opposition aux langages dits impératifs (C,...), orientés objet (C++, Java,...) ou logiques (PROLOG,...), bien que Objective Caml (la version de Caml la plus communément usitée, j'y reviendrais) supporte une couche objet. L'exemple-type de langage fonctionnel est Haskell. En bref, dans un langage impératif, on définit une suite d'ordres que l'ordinateur doit effectuer :
Citation:
let k = ref 0 in
for i = 1 to 10 do
k:= !k+i
done; |
Alors que dans un langage fonctionnel, on définit des fonctions (d'où le nom) qui vont effectuer une action spécifique, puis on appelle les fonctions avec les arguments voulus :
Citation:
let sum n =
let k = ref 0 in
for i = 1 to n do
k:= !k+i
done;
!k in
sum 10;;
|
La différence peut sembler minime. Néanmoins, il s'agit d'une caractéristique importante qui va vite se révéler extrêmement utile, notamment pour écrire du code clair.
Installation
Pour cette section, je supposerai que vous êtes sous windows. De toute manière, l'installation Linux n'est pas plus difficile.
Il existe grosso modo deux distributions de Caml, gérées toutes deux par l'INRIA : Caml Light et Objective Caml. Le premier, comme son nom l'indique, est une version un peu simplifiée. Cela dit, toutes les fonctionnalités nécessaires à la réalisation de programmes avancés sont disponibles. Objective Caml, au contraire, est la version la plus puissante. Le compilateur rivalise même avec C++. Des logiciels comme MLDonkey sont développés en O'Caml. Toutes les librairies sont développées pour O'Caml, alors que Caml Light n'évloue plus. Enfin, O'Caml auorise la création d'éxécutables autonomes, ce qui n'est pas le cas de Caml Light.
Pour toutes ces raisons, j'utiliserai ici O'Caml (NB : si vous connaissez Caml Light, les différences sont très minimes : gestion des opérations sur les structures de données (Liste, Tableau, Chaine...) qui changent de nom et `` (touche 7) des caractères transformés en '' (touche 4)).
Pour installer O'Caml, téléchargez le fichier suivant : http://caml.inria.fr/distrib/ocaml-...l2-win-msvc.exe et installez-le dans le répertoire de votre choix (je supposerai que c'est C:\Caml\ dans la suite). Il devrait maintenant y avoir une icône O'Caml sur votre bureau : il s'agit du frontend, ou système interactif. En clair, vous tapez un programme et l'envoyez au système Caml qui se charge de le compiler, l'exécuter et te renvoyer le résultat. Un autre moyen d'utiliser Caml est de compiler puis d'exécuter le programme à partir d'un shell (le prompt MS-DOS sous windows).
Double-cliquez sur Objective Caml : nous voici prêts à commencer.
Mon premier programme
C'est une tradition dans la littérature informatique, le premier programme affiche la chaine de caractère "Hello World". Nous ne dérogerons pas à cette règle. Il faut donc taper les lignes suivantes, en respectant la casse et la ponctuation (NB : un copier/coller ne servira pas à grand chose...) :
Citation:
let monPremierProgramme() =
print_string "Hello World";
print_newline();;
monPremierProgramme();;
|
S'il n'y a pas d'erreur, Caml vous affiche "Hello World" et renvoie la main (c'est le #). Examinons notre code (très simple) :
La première ligne déclare la fonction monPremierProgramme au système. Une déclaration de quelque type que ce soit utilise toujours le mot clé let, le nom de ce qu'on veut déclarer, éventuellement les arguments en cas de déclaration de fonction et enfin le signe =. La déclaration est terminée lorsque l'on rencontre le mot clé in ou ;; (j'y reviendrai).
Comme notre fonction ne doit rien prendre en argument, on le lui précise avec les parenthèses ().
On définit ensuite le corps de la fonction qui consiste en 2 lignes : afficher la chaine (string en anglais) puis effectuer un retour à la ligne. La fonction print_string prend une chaine de caratères en argument et la fonction print_newline ne prend rien : on lui donne donc encore ().
On remarque que deux instructions sont séparées par un ;
La fin d'une séquence d'instructions est déclarée par ;;
Enfin, nous n'avons jusqu'ici fait que définir une fonction. Nous ne demandons encore rien au système Caml. En l'état des choses, nous n'affichons rien. Cette demande est effectuée par l'appel à monPremierProgramme suivi d'un argument vide. L'affichage est alors effectué.
Paramètres et variables
Notre premier programme, même s'il répond à nombre de questions existentielles, n'est pas des plus intéressants car il ne tient absolument pas compte de l'utilisateur. Le rôle de celui-ci se borne à lancer le programme. Or, dans 99,99% des cas, un programme a besoin de demander des instructions à l'utilisateur, du type : combien de fois dois-je effectuer cette opération, quelle chaine de caractères afficher, sur quel tableau effectuer cette opération, etc...
C'est pourquoi nous allons passer à notre fonction des paramètres (ou arguments). On a vu précédemment que la fonction monPremierProgramme ne prenait aucun paramètre en entrée. En réalité, elle prend un argument vide : unit, symbolisé par (). Mais imaginons que nous désirions afficher une chaine quelconque : on doit alors passer en argument la chaine à afficher. Ce qui nous donne :
Citation:
let monDeuxièmeProgramme chaine_a_afficher =
print_string chaine_a_afficher;
print_newline();;
|
On a ici remplacé () par le nom de variable chaine_a_afficher.
Plusieurs remarques :
On peut donner le nom que l'on veut à une variable du moment que cela commence par une lettre et ne contient que des lettres, des chiffres et "_" (touche '8'). Les noms utilisés par Caml, du type "let", "for", "string", etc... sont bien entendus interdits. Dans la pratique, il vaut mieux utiliser des noms plus courts afin de garder des programmes lisibles et de ne pas passer une heure à retaper son nom, mais ne pas non plus exagérer. Si vous utilisez les noms "a", "b", "c", "d", etc sans vous soucier du type de variable et de son utilisation, vous allez très vite être perdus... Les noms du type "str", "text", "opt", "leng"... sont à mon avis les meilleurs compromis.
Contrairement à nombre de langages (au hasard, le C  ), vous n'avez pas à déclarer le type de vos variables, Caml le fait tout seul lors de la compilation. Outre un grand confort d'utilisation, cela permet d'éliminer toute erreur de typage (puisque deux instructions donnant des types différents à une variable renverront systématiquement un message d'erreur) et l'usage du polymorphisme (cf plus tard).
Ici, Caml détexte grâce l'instruction "print_string" que la varibale chaine_a_afficher est du type "string".
On peut évidemment passer plusieurs arguments à une fonction, ce qui donnera
Citation:
let maFonction x y z t = ... |
Dans l'esprit d'un langage fonctionnel, les structures de données ne sont pas mutables. Ce qui veut dire que vous ne pouvez pas les modifier, juste les réassigner grâce à un nouveau "let". Par exemple :
Citation:
let i = 10;; (*Assignation de la valeur 10 à la variable i *)
let i = 5;; (* Réassignation de la valeur 5 à i. L'ancienne valeur est oubliée *) |
Mais par contre, il n'est pas possible de dire Citation:
let i = i+1;; (*Car la variable est redéfinie à partir du let. Caml ne connait donc pas encore le i de la partie droite *) |
Cela dit, les références (équivalents aux pointeurs C) nous permettront ce genre de manipulation : on les déclare en rajoutant ref entre le signe "=" et la valeur initiale. L'accès à leur valeur se fait en ajoutant "!" avant leur nom et leur redéfinition avec le signe ":=".
Citation:
let i = ref 10;;
i:= !i+1;;
!i;; (* -> 11 *) |
En fonctionnel, chaque fonction prend au moins un argument en entrée et renvoie exactement une valeur en sortie. Cette valeur peut éventuellement être de type unit (vide) comme dans le cas de nos deux fonctions monPremierProgramme et monDeuxièmeProgramme. Cette valeur correspond à ce que renvoie la dernière instruction effectuée.
C'est cette valeur que l'on récupère lorsque l'on appelle la fonction. Voyons un exemple concret : le calcul de la factorielle (selon la définition n! = n * (n-1) * ... * 3 * 2 * 1)
Citation:
let factorielle n = (* n est le paramètre : le nombre dont on veut calculer la factorielle *)
let k = ref 1 in (*initialisation de notre référence qui stockera les valeurs intermédiaires *)
for i = 1 to n do (* toutes les instructions contenues entre le do et le done seront répétées en donnant à la variable i toutes les valeurs entre 1 et n *)
k:= !k * i
done;
!k;; (*renvoi de la valeur finale *) |
Pour essayer le programme, il suffit de demander à CAML factorielle 10, par exemple, pour obtenir 10! ...
Exercice Ecrire une fonction renvoyant la somme des carrés des entiers de m à n (m et n étant des nombres entiers)...
Une structure élémentaire : le tableau (ou vecteur)
Nous avons vu (brièvement) comment manipuler des variables simples, de types divers, comme les entiers ou les chaines de caractères. Mais il est bien souvent nécessaire de manipuler de très nombreuses variables (plusieurs milliers ou plus). Et on se doute bien qu'on ne va pas s'amuser à déclarer une par une ces variables (d'autant plus que leur nombre peut n'être pas fixé à l'avance !). D'où l'utilisation d'une très pratique structure de données : le tableau.
Quelques faits importants sur le tableau :
- il s'agit d'une structure de données impérative et non fonctionnelle. Quésaco ? En gros, cela veut dire que l'on va modifier les valeurs du tableau à l'intérieur d'une boucle par des opérations de type 'a -> unit, c'est-à-dire qui ne renvoient rien. On ne renvoie pas le tableau obtenu après modification, celui-ci est directement modifié en mémoire : c'est ce qu'on appelle un effet de bord. Dans les langages dits purement fonctionnels, on ne trouve pas du tout d'effets de bords car ceux-ci peuvent poser quelques problèmes au moment du typage (mais ce sont là des points de détails).
- Les tableaux ont une longueur fixe et peuvent contenir un type de données unique. Tous deux sont déclarés au moments de l'initialisation du tableau.
- Par opposition à la structure de liste (que nous verrons plus loin), l'accès à un élément du tableau se fait en un temps constant (en |I]O(1)[/I] pour ceux qui ont fait un peu de maths). Il s'agit du principal avantage d'un tableau.
- Important : Comme pour toutes les structures de données en CAML, le premier élément est l'élément 0ème et le dernier l'élément (n-1)ème si le tableau est de longueur n
Voyons maintenant la syntaxe (en Objective Caml, pour Caml Light, les choses sont un peu différentes). Avant d'appeler une fonction agissant sur un tableau, on précisera à Caml qu'on souhaite utiliser la librairie dédiée aux tableaux en préfixant notre fonction par Le "." est primordial !
Pour initialiser/déclarer un tableau on utilisera la syntaxe :
Citation:
let mon_tableau = Array.create longueur element_initial;; |
Ceci crée un tableau de longueur l'entier positif longueur et rempli de element_initial. On ne pourra par la suite stocker que des éléments du type de element_initial dans le tableau.
L'accès à l'élément étiqueté par i (où 0 <= i <= longueur-1) se fait par
Citation:
mon_tableau.(i) |
Là aussi, le point comme les parenthèses sont primordiaux.
La modification d'un élément, elle, est obtenue par
Citation:
mon_tableau.(i) <- nouvelle_valeur |
Cette fonction est de type int -> 'a -> unit, i.e. on lui donne l'entier correspondant à l'indice et la nouvelle valeur et elle ne renvoie rien !
Pour finir, deux primitives utiles :
Citation:
Array.length mon_tableau (* renvoie la longueur du tableau *)
Array.init longueur fonction (* Pas important pour l'instant, mais permet d'initialiser le tableau en appliquant fonction sur les indices du tableau *) |
Un exemple de programme utilisant un tableau : le calcul de la factorielle en stockant les valeurs intermédiaires dans un tableau :
Citation:
let tab_factorielle n =
let tab = Array.create (n+1) 1 in (* tab.(i) vaudra i! Il nous faut donc (n+1)! cases *)
for i = 1 to n do
tab.(i) <- (tab.(i-1) * i) (* Remplissage du tableau avec la formule de récurrence *)
done;
tab.(n);; (* Renvoi de la valeur finale *) |
Exercice : transposer l'exercice précédent en utilisant un tableau.
Annexe : différences entre Caml Light et O'Caml
L'ensemble de ce qu'il faut faire différemment entre Light et Objective est vraiment minime et ne demande quasiment pas de temps d'adaptation.
Voici :
1) les apostrophes autour d'un char, de la combinaison 'Alt Gr' + '7' passent à celles de la touche '4' en accès direct (sur la rangée numérique au dessus de la ligne AZERTYUIOP, bien sûr). Ca a l'air ridicule, mais j'ai passé plus de 2 heures à essayer de débugger un programme correct à cause de ça :'(
2) les instructions de manipulation des structures de données changent. Par exemple, string_length devient String.length : on utilise l'instruction length du module String. De même, List.length, Array.length, etc... Les vect deviennent des Array.
Pour la création de ces structures , on a les instructions create des modules correspondants. Plus puissant (mais inconnu en Light) : les init (cf la doc).
De manière générale, toute opération sur une structure de données utilise un module. Par exemple, rev sur les listes devient List.rev, etc...
Sinon, les primitives de conversion d'un type à un autre (string_of_int, etc...) sont toujours reconnues.
Pour la liste complète des instructions dans les modules, cf : http://caml.inria.fr/ocaml/htmlman/...ex_modules.html
Le site officiel de Caml : http://caml.inria.fr/ pour tout savoir.
NB : Ce tuto est destiné à :
1) b.michael.007 qui voulait apprendre un langage
2) moi qui avait envie de faire un truc du genre
3) tous les gens qui veulent bien la lire
__________________
Allez jeter un œil à mon portfolio !
Edité par Zakath le 11-02-2004 à 12:39
Signaler ce message à un modérateur | IP: Logguée
Temps en ligne : 103 Jours, 6 Heures, 14 Minutes, 38 Secondes en ligne
|
30-01-2004 21:41
)
pour Centrale 2001, je n'ai rien rédigé...
) 
