Programmation Fonctionnelle, TP1

Figure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP1 : Faire pousser des arbres.

Guyslain Naves

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.

Mise en place.

Lancer un interpréteur.

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.

Mettre le projet en place.

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 :

  1. true: package(gg), package(vg), package(vg.svg)

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 :

  1. PKG gg vg vg.svg
  2. B _build
Lancer l'éditeur de programme.

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.

  1. emacs 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 :

  1. let a = 42

  2. let fact n =
  3. if n = 0 then 1
  4. else n * fact (n-1)

  5. let res = fact 10

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).

Interpréter le programme.

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.

Récupérer le module de dessin d'arbres.

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) :

  1. (** A type for generation of L-systems, this is a generator of drawings. *)
  2. type gen

  3. (** [run ~rand ~depth gen] generates a drawing using [gen], whose size
  4. depends on [depth]. [rand] is the state of a random generator to
  5. be used during the generation of the drawing.
  6. *)
  7. val run :
  8. rand:Random.State.t ->
  9. depth:int ->
  10. gen -> Vg.image

  11. (** This generators only ouputs empty drawings. *)
  12. val empty : gen

  13. (** Draws the given path at the current position. *)
  14. val stroke : Vg.path -> gen

  15. (** Fills the given path (it must be closed) at the current position. *)
  16. val fill : Vg.path -> gen


  17. (** Affine transformation of space for future drawings *)
  18. val transform : ltr:Gg.m3 -> gen

  19. (** displaces the current context to relative position [vec] *)
  20. val move : vec:Gg.v2 -> gen

  21. (** rotates the current context by [theta] radians *)
  22. val rotate : theta:float -> gen

  23. (** scales (up or down) the current context by an [alpha] factor *)
  24. val scale : alpha:float -> gen

  25. (** x-axis symmetry *)
  26. val mirror : gen

  27. (** Draws a line to the point [vec], then move to point [vec] *)
  28. val line : vec:Gg.v2 -> gen

  29. (** Draws a line to the point [vec], moves to [vec] and rotates to
  30. align with [vec] *)
  31. val step : vec:Gg.v2 -> gen

  32. (** decrements the depth of the current context *)
  33. val decr : gen
  34. (** increments the depth of the current context *)
  35. val incr : gen

  36. (** Decrements by [n] units (may be negative) *)
  37. val decr_by : n:int -> gen

  38. (** Accessors to the current context. *)
  39. val get_depth : (int -> gen) -> gen
  40. val get_state : (Random.State.t -> gen) -> gen
  41. val get_direction : (Gg.v2 -> gen) -> gen
  42. val get_color : (Gg.color -> gen) -> gen

  43. (** changes the current color *)
  44. val set_color : Gg.color -> gen


  45. (** bracket operations change the context, generate the branch, then
  46. cancel the context change. For instance [bracket_decr branch] is
  47. the same as [decr >> gen >> incr]. *)
  48. val bracket_decr_by : n:int -> gen -> gen
  49. val bracket_decr : gen -> gen
  50. val bracket_scale : alpha:float -> gen -> gen
  51. val bracket_mirror : gen -> gen

  52. (** A drawing of [gen1 >> gen2] is a drawing of [gen1] plus a drawing
  53. of [gen2] placed at the end of the drawing of [gen1] context given
  54. by [gen1]. [(>>)] is read 'then' *)
  55. val (>>) : gen -> gen -> gen

  56. (** A drawing of [gen1 && gen2] is a superposition of the drawings of
  57. [gen1] and [gen2]. The context is not modified. *)
  58. val (&&) : gen -> gen -> gen

  59. (** A drawing of [gen1 || gen2] is uniformly randomly either a drawing
  60. from [gen1] or a drawing from [gen2]. *)
  61. val (||) : gen -> gen -> gen

  62. (** [all] generalises [(&&)] *)
  63. val all : gen list -> gen

  64. (** [branch] generalizes [(>>)] *)
  65. val branch : gen list -> gen


  66. (** [dispatch gen] is [gen] without context modification *)
  67. val dispatch : gen -> gen


  68. (** [times ~n gen] is [all [gen;gen;...;gen]], with [n] items in the list *)
  69. val times : n:int -> gen -> gen

  70. (** [repeat ~n gen] is [branch [gen;gen;...;gen]], with [n] items in the list *)
  71. val repeat : n:int -> gen -> gen


  72. (** The fours next functions are randomised versions of [move],
  73. [scale], [rotate] and [step], with argument chosen randomly thanks to
  74. the given distribution [dist]. *)

  75. val move_randomly : dist:(Random.State.t -> Gg.v2) -> gen
  76. val scale_randomly : dist:(Random.State.t -> float) -> gen
  77. val rotate_randomly : dist:(Random.State.t -> float) -> gen
  78. val step_randomly : dist:(Random.State.t -> Gg.v2) -> gen

  79. (** [choose [(pr1,gen1);(pr2,gen2);...(prk,genk)]] is [gen_i] with
  80. probability [pri] (probabilities are normalised if needed) *)
  81. val choose : (float * gen) list -> gen


  82. (* fix-point combinator, to express recusive generators *)
  83. val fix : (gen -> gen) -> gen

  84. (* fix-point combinators, to express mutually recursive generators. *)
  85. val fix2 : ((gen * gen) -> (gen * gen)) -> gen * gen
  86. val fix3 : ((gen * gen * gen) -> (gen * gen * gen)) -> gen * gen * gen

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 :

  1. (** Draw an image into a file in format svg *)
  2. val draw :
  3. title:string ->
  4. description:string ->
  5. filename:string ->
  6. Vg.image ->
  7. unit

  8. (** draw a path in the given color (or black) into a file in format svg *)
  9. val draw_path :
  10. ?color:Gg.Color.t ->
  11. title:string ->
  12. description:string ->
  13. filename:string ->
  14. Vg.path ->
  15. unit

Récupérez les deux implémentations et ajoutez-les au répertoire :

Compiler les deux modules.

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 :

  1. ocamlbuild -use-ocamlfind target

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.

Définir des arbres.

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.

Un premier arbre.

Considérons le programme suivant, à recopier dans un fichier simple.ml :

  1. let triangle =
  2. let open LCo in
  3. rotate ~theta:(-. Gg.Float.pi /. 6.)
  4. >> step ~vec:(Gg.V2.v 0. 1.)
  5. >> rotate ~theta:(2. *. Gg.Float.pi /. 3.)
  6. >> step ~vec:(Gg.V2.v 0. 1.)
  7. >> rotate ~theta:(2. *. Gg.Float.pi /. 3.)
  8. >> step ~vec:(Gg.V2.v 0. 1.)

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 :

  1. #use "topfind";;
  2. #require "gg";;

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 :

  1. #directory "_build";;
  2. #load "lCo.cmo";;

On peut maintenant évaluer la définition triangle, ce qui donne :

  1. val triangle : LCo.gen = <abstr>

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 :

  1. let export_triangle =
  2. let tree =
  3. LCo.run ~rand:(Random.get_state ()) ~depth:1 triangle
  4. in
  5. ExportSvg.draw
  6. ~title:"A triangle"
  7. ~description:"Our first example: a simple triangle"
  8. ~filename:"pic/triangle.svg"
  9. tree

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 :

Un triangle.

On peut aussi compiler le programme (en console) :

  1. ocamlbuild -use-ocamlfind simple.byte

puis l'exécuter :

  1. ./simple.byte

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.

Faire pousser l'arbre.

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 :

  • quelle est la longueur et la direction de la tige ?
  • quel arbre construire au bout de la tige ?

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 :

  1. let simple_flower =
  2. let open LCo in
  3. step ~vec:(Gg.V2.v 0. 4.) >>
  4. triangle

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).

Des fleurs.

Plutôt qu'utiliser && plein de fois, on peut aussi utiliser LCo.all et donner la liste des générateurs à superposer.

Contrôler la taille.

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 :

  1. (* using short_step = step ~vec:(Gg.V2.v 1. 0.) *)
  2. let stair =
  3. let open LCo in
  4. step ~vec:Gg.V2.(v 0. 1.)
  5. >> step ~vec:Gg.V2.(v 1. 0.)
  6. >> rotate ~theta:(Gg.Float.pi_div_2)

On peut alors créer un escalier en mettant une marche après une marche après une marche...

  1. let four_stairs =
  2. let open LCo in
  3. stair >> stair >> stair >> stair

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 :

  • LCo.decr réduit la profondeur de 1.
  • LCo.get_depth make_gen crée un générateur dépendant de la profondeur de la branche. make_gen doit être une fonction prenant un entier et retournant un générateur. On peut ainsi facilement distinguer le cas où la profondeur est zéro comme nous allons le voir.

Nous pouvons maintenant écrire le générateur d'escalier de longueur arbitraire :

  1. let staircase =
  2. let open LCo in
  3. fix @@ fun staircase ->
  4. get_depth @@ fun depth ->
  5. if depth = 0 then empty
  6. else decr >> stair >> staircase

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 :

  1. get_depth (fun depth ->
  2. if depth = 0 then empty
  3. else decr >> stair >> staircase
  4. )

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 :

  1. let staircase =
  2. let open LCo in
  3. get_depth @@ fun depth ->
  4. if depth = 0 then empty
  5. else decr >> stair >> staircase

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 :

  1. let staircase =
  2. let open LCo in
  3. fix @@ fun gen ->
  4. get_depth @@ fun depth ->
  5. if depth = 0 then empty
  6. else decr >> stair >> gen

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.

Un escalier.
Un premier arbre.

Créez un fichier tree.ml. On souhaite produire un arbre tel que celui-ci :

Un arbre tout simple.

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 :

  1. let tree =
  2. let open LCo in
  3. fix @@ fun tree ->
  4. get_depth @@ fun depth ->
  5. if depth = 0 then empty
  6. else
  7. step ~vec:Gg.V2.(v 0. 3.) >>
  8. scale ~alpha:0.7 >>
  9. decr >>
  10. all [
  11. rotate ~theta:(Gg.Float.pi /. 6.) >> tree;
  12. rotate ~theta:(-. Gg.Float.pi /. 6.) >> tree
  13. ]

À 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.

Une courbe de Sierpinski

Voici un autre exemple de ce qu'on peut faire avec cette librairie :

  1. open LCo

  2. let theta = Gg.Float.pi /. 3.

  3. let turn_left = rotate ~theta
  4. let turn_right = rotate ~theta:(-. theta)
  5. let forward = step ~vec:Gg.V2.(v 0. 10.)


  6. let sierpinski =
  7. fix @@ fun sierpinski ->
  8. get_depth @@ fun depth ->
  9. if depth = 0 then forward
  10. else
  11. bracket_scale ~alpha:0.5 @@
  12. bracket_decr @@ (
  13. turn_left >>
  14. bracket_mirror sierpinski >>
  15. turn_right >>
  16. sierpinski >>
  17. turn_right >>
  18. bracket_mirror sierpinski >>
  19. turn_left
  20. )

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.

À vous de jouer...

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.

la courbe de von Koch.
la courbe du dragon.
un arbre plus complexe.
un arbre généré avec de l'aléa.