Ce premier TP nous permet de découvrir un environnemement de programmation en OCaml, comment mettre en place un projet. On en profite pour générer des arbres avec un mécanisme inspiré par les systèmes de Lindermayer, mais revu façon programmation fonctionnelle.
Ouvrez un terminal, et lancez l'interpréteur interactif utop. Quelle version d'OCaml est utilisée par l'interpréteur ? Calculez le produit de $193228$ et $55203$ (terminez par ;;). En cas de problème, OCaml (ou utop) ne doit pas être correctement installé : vérifiez l'installation et au besoin demandez de l'aide.
Commencez par créer un répertoire dédié au TP de ce jour. Nous allons utiliser plusieurs librairies, donc nous allons commencer par signaler leur présence à l'outil de compilation et à l'environnement de développement.
Créez un fichier nommé _tags. Ce fichier indique à l'outil d'automatisation de la compilation (ocamlbuild) quelles librairies nous utilisons. Nous allons faire de la géométrie avec Gg et du dessin vectoriel avec Vg, nous produirons des dessins au format svg avec Vgr_svg. Le fichier _tags doit donc contenir :
Ceci indique que tous les fichiers dépendent des trois librairies citées.
Créez un fichier nommé .merlin. Merlin est un outil utilisé par les environnements de développement pour réaliser l'auto-complétion, la détection d'erreurs, les indications de types. Nous devons aussi dire à Merlin quelles librairies sont utilisées dans le projet, et où se trouvent les fichiers compilée du projet lui-même. Le contenu du fichier .merlin pour ce projet est donc :
Il existe plusieurs éditeurs supportant OCaml. Dans les salles de TP de l'université, vous trouverez Emacs et Atom. Il est vivement recommandé d'utiliser un éditeur supportant Merlin. Atom offre une expérience un peu plus moderne qu'Emacs en général, mais Emacs est plus confortable avec OCaml. Ici se trouve des instructions pour utiliser Emacs. Choisissez votre éditeur, les instructions données par la suite sont valables pour Emacs et devrons être adaptées pour Atom. Ouvrez l'éditeur de votre choix, et créer un fichier firstFile.ml.
Assurez-vous de travailler avec deux zones de texte dans l'éditeur. L'une d'elles contiendra une interface avec l'interpréteur. Recopiez les définitions suivantes :
Si le code est mal-indenté, sélectionnez tout et appuyez sur la touche tab : Emacs réindente alors tout le code sélectionné correctement. Sauvegardez le fichier. Merlin devrait vous indiquer une erreur (sinon, Merlin est mal configuré, vérifiez l'installation). Corrigez l'erreur (indice : fact est une définition récursive).
Positionnez le curseur sur la définition de a. Le raccourci pour évaluer une définition est C-c C-e, ce qui dans la notation usuelle d'Emacs indique qu'il faut taper control et c simultanément, puis control et e simultanément.
Pour la première évaluation, Emacs doit choisir quel interpréteur utiliser. Il affiche dans la barre en bas de l'écran le choix par défaut, qui devrait être correct, validez en tapant entrée. L'une des zones de textes devrait à présent contenir la boucle d'interaction OCaml, en particulier le résultat de l'évaluation de la définition de a.
Emacs a modifié la position du curseur pour se placer sur la définition suivante, on peut donc recommencer C-c C-e deux fois pour évaluer les deux définitions restantes.
Si toutes ces étapes ont réussi, vous êtes prêt à commencer le TP. Sinon, réessayez ou cherchez de l'aide.
Nous allons utiliser deux modules fournis afin générer des dessins d'arbres. Le premier permet de définir une forme, recopiez l'interface suivante dans un fichier lCo.mli (pas besoin de la lire pour le moment) :
Le deuxième module sert à générer des fichiers au format svg à partir des description de type Vg.path. Créez un fichier exportSvg.mli, contenant l'interface :
Récupérez les deux implémentations et ajoutez-les au répertoire :
Les fichiers sources sont compilés en bytecode (ou en code natif). Les fichiers de bytecode ont pour extension cmo (cmx en natif) ou pour une collection de modules l'extension cma (cmxa en natif). Les exécutables ont l'extension byte ou native.
Plusieurs systèmes d'automatisation de la compilation peuvent être utilisées avec OCaml. En particulier on peut tout-à-fait utiliser make en écrivant un Makefile approprié. Nous allons plutôt utilisé des outils dédiés à OCaml, et en particulier ocamlbuild qui est adapté aux petits projets, en conjonction avec ocamlfind.
ocamlfind est un utilitaire permettant de trouver les répertoires d'installations des librairies OCaml. ocamlbuild est un outil d'automatisation de la compilation assurant la gestion des dépendances. Le principe est très simple : pour obtenir le fichier target, il suffit de lancer la commande :
Si tout se passe bien, target sera alors un fichier dans le répertoire _build.
Produisez ainsi les fichiers lCo.cmo et exportSvg.cmo. Listez les fichiers du répertoire _build.
Le module LCo contient des fonctions permettant de décrire des algorithmes de générations de dessin d'arbres (au sens végétal). Son cœur est le type gen : une valeur de ce type représente une méthode de construction, un algorithme de génération d'une branche, et un arbre tout entier est lui-même considéré comme une branche. Il est très important de comprendre pour la suite que les valeurs de type gen ne sont pas des dessins d'arbres, ce sont des générateurs de dessins d'arbres.
Intuitivement, on peut les imaginer comme des fonctions prenant un argument entier (la taille de l'arbre désiré), et retournant le dessin d'un arbre. En programmation fonctionnelle, nous n'hésitons pas à représenter certains objets directement comme des fonctions, les fonctions étant considérés comme des valeurs comme les autres.
Le module LCo est suffisamment général pour pouvoir dessiner des choses qui n'ont pas grand chose de végétal, mais on continuera de parler d'arbres néanmoins.
Les différentes fonctions qui permettent de manipuler le type gen permettent de créer des superpositions de plusieurs branches, de déplacer les branches, ou d'aggrandir les branches.
Considérons le programme suivant, à recopier dans un fichier simple.ml :
La ligne 2 informe que nous utilisons des fonctions du module LCo. triangle est de type LCo.gen. On peut le voir en l'interprétant (C-c C-e). Malheureusement, l'interprétation échoue parce que l'interpréteur ne connait pas le modules LCo.
LCo utilise Gg, qui est une librairie installée dans le système d'exploitation, définissant des objets géométriques comme les vecteurs en dimension 2 et 3 . On utilise ocamlfind pour la charger. Dans l'interpréteur (et pas dans le fichier source !), entrez les commandes, l'une après l'autre au niveau du prompt :
Les mot-clés commançant par le caractère # sont destinés à l'interpréteur, ils ne font pas partie du langage OCaml. Ils permettent de paramétrer l'interpréteur, par exemple pour charger des librairies.
LCo est une librairie du projet actuel. Pour la charger, il faut charger le fichier cmo, et indiquer préalablement où il se trouve :
On peut maintenant évaluer la définition triangle, ce qui donne :
L'opérateur >> est l'opérateur de succession des générateurs d'arbres : le générateur enchaînant deux arbres générés par chacun de ses termes. step est un générateur créant une ligne dans la direction vec donnée par rapport à l'axe de poussée actuel (initialement vertical). De plus l'axe de poussée est ensuite changé pour prendre la direction de vec : le dessin suivant sera donc mis dans le prolongement de la ligne venant d'être tracée. En particulier, si vec est vertical, l'axe ne change pas.
rotate tourne l'axe de poussée par un angle donné en radian. Avec un petit dessin, on peut vérifier que le code de triangle génère un triangle.
Ajoutez à la suite le code pour exporter l'image :
Pour pouvoir l'interpréter, chargez les librairies vg et vg.svg et le module exportSvg.cmo.
Créer un sous-répertoire pic dans votre projet. Ensuite, évaluez export_triangle. Vérifiez qu'un fichier pic/triangle.svg a bien été créé. Vous pouvez l'ouvrir avec un navigateur pour voir l'image générée, qui doit ressembler à ceci :
On peut aussi compiler le programme (en console) :
puis l'exécuter :
Le résultat est le même : un fichier triangle.svg est créé dans le répertoire pic, contenant l'image du triangle.
Réessayez en compilant le programme en code natif.
En supposant que le triangle ressemble très vaguement à une fleur, on voudrait bien ajouter une tige. Le principe est plus général : si on génère une branche, on peut vouloir l'allonger en la mettant au bout d'une tige, de la taille et dans la direction de notre choix.
Le principe de la fonction LCo.step est justement de créer une tige, et de générer un arbre au bout. Il lui faut donc deux informations :
Ce sont évidemment les deux arguments de la fonction LCo.step. La longueur et la direction sont données par un vecteur. L'arbre est donné par un générateur, c'est-à-dire une valeur du type branch.
On peut donc définir :
Ajoutez cette définition, puis générez l'image correspondante.
Ensuite, utilisez && et les fonctions de rotations déjà vues pour obtenir le prochain dessin. && permet de superposer deux arbres (ou plus en le répétant).
Plutôt qu'utiliser && plein de fois, on peut aussi utiliser LCo.all et donner la liste des générateurs à superposer.
Créez un nouveau fichier stairs.ml.
Essayons maintenant de dessiner un escalier de longueur arbitraire. Un escalier, c'est une marche, suivi d'un escalier. On commence donc par écrire une fonction qui génère une marche. Cela nous donne :
On peut alors créer un escalier en mettant une marche après une marche après une marche...
Générez l'image correspondante. Vérifiez que le nombre de marches est adéquat. Comment modifier le nombre de marche ?
Nous voudrions plutôt avoir un seul générateur pour tous les escaliers, quelque soit leur taille. On peut le faire en utilisant la notion de profondeur de la génération : les générateurs utilisent de façon interne un paramètre entier, la profondeur, pour gérer la taille de l'objet généré. La profondeur est ensuite donnée au générateur par l'argument ~depth de la fonction de génération ~run.
Pour écrire un générateur utilisant la profondeur, on utilise deux générateurs :
Nous pouvons maintenant écrire le générateur d'escalier de longueur arbitraire :
Ignorons la ligne 3 avec fix pour l'instant. get_depth permet de paramétrer le générateur par la profondeur : on peut immédiatement tester si la profondeur est 0 par exemple, ou tout autre condition. @@ est l'opérateur explicite d'application, autrement dit les lignes 4 à 6 sont les mêmes ainsi :
L'argument de get_depth est donc bien une fonction, comme souhaitée. L'utilisation de @@ permet d'alléger la syntaxe (moins de parenthèses). Plus encore, il permet d'expliciter le rôle de get_depth : un accesseur à la profondeur de génération : on a l'accesseur get_depth qui apparait sur la même ligne que l'identifiant qui abstrait la valeur accédée depth. Nous reverrons dans plusieurs contextes très divers ce type d'astuce syntaxique.
Expliquons maintenant la ligne 3 . Notre escalier est construit récursivement. On devrait donc utiliser let rec :
Essayez d'évaluer ce code. Pourquoi l'erreur retournée par l'interpréteur est raisonnable ?
fix permet tout simplement de contourner ce problème : il sert à déclarer explicitement une définition récursive. Ici on appelle staircase la fonction à appeler récursivement. On aurait pu écrire de façon équivalente :
Prenez le temps de comprendre ce code. Générez ensuite les images d'escaliers de différentes tailles, en faisant varier le paramètre ~depth de LCo.run.
Créez un fichier tree.ml. On souhaite produire un arbre tel que celui-ci :
Le principe est de prendre deux copies d'arbres plus petits, faire une rotation sur chacun, et ajouter une tige. Si la profondeur voulue est 0 , on ne produit rien. Voici le code :
À partir de deux (all) arbres moins profonds (decr), obtenu avec un générateur tree, les tourner, réduire leur taille (scale) et ajouter une tige. La ligne 3 fix @@ fun tree -> précise que les deux arbres moins profonds doivent être construits selon le même principe (c'est une récursion).
Générez des images d'arbres de plusieurs profondeurs. Faites varier les différents paramêtres de l'algorithme : angles des branches, longueurs des branches, etc.
Voici un autre exemple de ce qu'on peut faire avec cette librairie :
Générez l'image correspondante. Les fonctions commençant par bracket changent les paramètres de génération de l'arbre, génère selon leur argument, et annulent les changements de paramètres qu'ils ont fait. Expliquez comment fonctionne ce générateur.
Nous avons maintenant introduit la plupart des fonctions du module LCo. Il reste notamment des fonctions pour introduire de l'aléa dans la génération. Par exemple, || s'utilise comme &&, mais plutôt que de prendre tous les arbres générés, il en choisit un seul aléatoirement.
Faites maintenant parler votre imagination pour concevoir des arbres ou des figures géométriques de votre choix en utilisant LCo. Voici quelques exemples de créations réalisables, certaines inspirées par ce document.
