Programmation Fonctionnelle, TP1

Figure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP1 : Empiler des briques.

Guyslain Naves

Ce premier TP nous permet de découvrir un environnemement de programmation en OCaml, comment mettre en place un projet. Nous travaillerons ensuite la syntaxe des fonctions et de leur application. Pour nous motiver, nous utiliserons une librairie nous permettant de contruire des structures façon Lego ® , par empilement de briques rectangulaires.

Aperçu.

Nous allons utiliser les outils suivants :

  • un éditeur (emacs, atom sont conseillés et disponibles sur les machines des salles de TP, d'autres choix sont possibles, par exemple visual studio code).
  • ocamlbuild est un outil de compilation pour OCaml. Il est paramétré à l'aide d'un fichier _tags, et optionnellement pour les projets plus complexes par un fichier myocamlbuild.ml.
  • ocamlfind permet de déterminer où se trouve les dépendances d'un fichiers sources. On ne l'utilisera pas directement, il est appelé par ocamlbuid.
  • ocamlc est le compilateur d'Ocaml. On ne l'utilisera pas non plus directement, mais via ocamlbuild.
  • merlin est un linter, il interagit avec l'éditeur pour que ce dernier détermine les auto-complétions, les erreurs de syntaxe et de types, les types des identifiants et d'autres informations utiles. Il est paramétré par un fichier .merlin.
  • utop est un interpréteur interactif, connu sous le nom de "toplevel" dans la communauté OCaml, ou REPL (pour read-eval-print loop) dans d'autres communautés. Il permet d'évaluer et d'afficher immédiatement le résultat d'une expression OCaml. (Il existe un autre interpréteur interactif, qui peut être lancé dans un shell via la commande ocaml, mais utop est bien plus agréable à utiliser). utop exécute au lancement le contenu du fichier .ocamlinit, ce qui permet typiquement de charger des librairies et des fonctions supplémentaires.

Pour ceux souhaitant travailler sur leur machine personnnelle, commencez par installer OCaml sur votre système.

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. Pour quitter l'interpréteur, faites exit 0;;.

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 devront être adaptées pour Atom. Ouvrez l'éditeur de votre choix (les instructions par la suite sont donnés pour Emacs), et créer un fichier firstFile.ml.

  1. emacs firstFile.ml

Assurez-vous de travailler avec deux zones de texte dans l'éditeur (raccourcis Emacs C-x 1 et C-x 3). 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 les fichiers sources fournis.

Voici les sources fournies pour ce TP. Décompressez-les dans le répertoire dédié à cette séance de TP.

Compiler les modules fournis.

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 le fichier lego.cma. Listez les fichiers du répertoire _build. Le fichier lego.cma est la réunion de tous les modules compilés d'extension cmo dont le nom est donné dans le fichier lego.mllib. C'est une façon simple de compiler (puis ensuite de charger) un ensemble de modules.

Un premier exemple

La librairie fournie permet de réaliser des constructions en 2 dimensions à la façon des legos, par empilage de briques rectangulaires. Nous utiliserons les modules suivants (les autres sont utilisés en interne, nous pouvons les ignorer) :

  • Generator définit le type des générateurs de constructions. Nous n'allons pas manipuler directement des constructions, mais plutôt des fonctions permettant de construire un objet (cela nous permet d'avoir du non-déterminisme, donc de l'aléatoire dans la construction). Pour autant, l'interface est faite pour donner l'impression de manipuler directements des blocs de briques, vous pouvez donc garder cette intuition.
  • Renderer fournit les fonctions permettant de dessiner les constructions réalisées.
  • Shape permet de définir de nouvelles formes de briques.

Chaque module est défini par deux fichiers : le source est dans le fichier d'extension ml. Il n'est normalement pas nécessaire de le consulter (mais soyez curieux !). Le fichier d'extension mli de même nom définit ce qui est exporté par le module, donc la partie publique du module. Il contient aussi en général la documentation sous la forme de commentaires. Vous pouvez directement utiliser les fichiers mli pour consulter la documentation. Ou bien vous pouvez générer la documentation avec la commande suivante, utilisant le fichier lego.odocl contenant les noms de modules à inclure dans la documentation :

  1. ocamlbuild -use-ocamlfind lego.docdir/index.html

Vous pouvez ensuite ouvrir le fichier généré dans un navigateur pour consulter la documentation.

Nous allons commencer par la plus simple des constructions : une simple brique rectangulaire. Le générateur de brique est Generate.block :

  1. (* from generator.mli *)

  2. (** The type of lego generators. These are functions from a random seed
  3. to a lego construction. *)
  4. type t

  5. (** [generate random_state generator] randomly builds a lego
  6. construction depending on the given seed. It returns the construction
  7. as well as a fresh random state. *)
  8. val generate : Random.State.t -> t -> Component.t * Random.State.t


  9. (** [block ~width ~height] is a single brick with given dimensions. The
  10. bottom-left corner is placed at the origin. *)
  11. val block : width:int -> height:int -> t

Créez un fichier one_brick.ml, contenant le programme suivant :

  1. let one_brick_gen =
  2. let open Generator in
  3. block ~width:2 ~height:1


  4. let main =
  5. let open Renderer in
  6. generate_and_render one_brick_gen

Remarquons que pour accéder aux noms définis dans un module, on peut le préfixer par le nom du module (par exemple Generator.block), ou localement ouvrir le module comme on l'a fait ici (let open ... in).

block prend deux arguments nommés de types entiers. Ainsi, à l'utilisation, le rôle de chaque argument est clair. Les noms sont appelés label.

Nous définissons une valeur main, mais c'est uniquement par respect pour les conventions. Cet identifiant n'est pas traitée différemment des autres, vous pouvez donc le changer par n'importe quel autre nom. C'est au moins pratique pour indiquer notre intention que cette valeur soit la raison d'être de notre programme.

Compiler le programme en un exécutable one_brick.byte (ou one_brick.native), et exécutez-le. Un fichier out.svg devrait avoir été créé, vous pouvez l'ouvrir dans un navigateur. Vérifiez qu'il y a bien un rectangle noir.

Une seule brique noire.

Nous pouvons aussi évaluer le programme sans le compiler, ce qui sera plus pratique pendant le développement pour prototyper les fonctions que nous écrirons. Pour cela, il faut charger les librairies nécessaires dans le toplevel. On utilise des directives, qui sont des commandes propres au toplevel (et ne font donc pas partie du langage OCaml). Pour ne pas avoir à les retaper à chaque fois que nous ouvrons le toplevel, nous les mettons dans un fichier .ocamlinitdans le répertoire de travail. (Vous pouvez aussi créer un .ocamlinit dans votre $HOME, qui sera systématiquement chargé par le toplevel, et qui peut par exemple contenir vos fonctions préférées).

  1. (* from .ocamlinit *)

  2. (* add the #require directive to load packages. *)
  3. #use "topfind";;

  4. (* load vg.svg and its dependencies. *)
  5. #require "vg.svg";;

  6. (* signals that _build is directory from which files can be loaded. *)
  7. #directory "_build";;

  8. (* load file lego.cma, that contains compiled modules. *)
  9. #load "lego.cma";;

  10. (* We can also add OCaml values that will be evaluated when we start
  11. the toplevel, for instance: *)
  12. let () = print_endline ".ocamlinit loaded."
Ajouter des couleurs ou une forme

Pour avoir une brique d'une autre couleur, on utilise une fonction qui prend la brique et construit une brique similaire, d'une autre couleur. Cela marche en fait sur n'importe quelle construction, en modifiant la couleur de chaque brique élémentaire dans la construction obtenue.

On trouve dans Generator les fonctions suivantes :

  1. (* from generator.mli *)

  2. (** [color c gen] is a generator similar to [gen], but with all block
  3. having color [c]. *)
  4. val color : Gg.color -> t -> t


  5. (** Some predefined color combinators (more are available in
  6. Colors.Combinator).
  7. *)

  8. val black : t -> t
  9. val red : t -> t
  10. val blue : t -> t
  11. val green : t -> t
  12. val white : t -> t

Remarquez le type des 5 fonctions de couleurs : elles prennent un générateur et produisent un nouveau générateur. On peut donc par exemple écrire (et évaluer):

  1. let one_blue_brick_gen =
  2. let open Generator in
  3. blue (block ~width:2 ~height:1)

  4. let () =
  5. let open Renderer in
  6. generate_and_render one_blue_brick_gen

On utilise ici la syntaxe usuelle de l'application en OCaml : la fonction séparée de l'argument par un espace f arg. Puisque l'argument est une expression complexe, on le parenthèse. Cependant, la librairie de simili-lego est conçue pour être utilisée de préférence avec l'opérateur d'application inversé : le pipe |>. Dans ce cas, la syntaxe est arg |> f , ce qui pour nous donne :

  1. let one_blue_brick_gen =
  2. let open Generator in
  3. block ~width:2 ~height:1 |> blue

  4. let () =
  5. let open Renderer in
  6. generate_and_render one_blue_brick_gen
Une seule brique bleue.

Pour les formes, cela fonctionne pareil, voici les combinateurs de formes :

  1. (* from generator.mli *)

  2. (** [shape s gen] is a generator similar to [gen], but with all block
  3. having shape [s] *)
  4. val shape : Shape.t -> t -> t

  5. (** Some predefined shape combinators *)

  6. val solid : t -> t (** plain rectangle *)
  7. val very_thin : t -> t (** outlined rectangle *)
  8. val thin : t -> t (** outlined rectangle *)
  9. val thick : t -> t (** outlined rectangle *)
  10. val circle : t -> t (** solid ellipsoidal *)
  11. val square : t -> t (** solid rectangle *)
  12. val bottom_left_triangle : t -> t (** solid square triangle*)
  13. val bottom_right_triangle : t -> t (** solid square triangle*)
  14. val top_left_triangle : t -> t (** solid square triangle*)
  15. val top_right_triangle : t -> t (** solid square triangle*)

Notons alors comment la syntaxe change si on veut une brique bleue et triangulaire :

  1. let one_blue_triangle_brick_gen =
  2. let open Generator in
  3. bottom_left_triangle (blue (block ~width:2 ~height:1))

  4. let one_blue_triangle_brick_gen_with_pipe =
  5. let open Generator in
  6. block ~width:2 ~height:1 |> blue |> bottom_left_triangle

  7. let () =
  8. let open Renderer in
  9. generate_and_render one_blue_triangle_brick_gen

On voit notamment comment l'opérateur |> permet de limiter l'usage de parenthèses, ce qui rend l'expression plus lisible.

Une seule brique triangulaire bleue.

Quelques questions avant de voir comment assembler des briques :

  • essayez d'autres couleurs et d'autres formes.
  • Le module Color.Combinator définit d'autres couleurs, essayez de les utiliser.
  • que se passe-t-il si vous utilisez deux couleurs différentes sur une même brique, ou deux formes différentes ?
Assembler des briques.

Voici les fonctions permettant d'assembler des blocs de briques :

  1. (** [b1 |> left_of b2] is the concatenation of [b1] to the left of
  2. [b2]. [b1] is not moved. *)
  3. val left_of : ?gap:int -> t -> t -> t

  4. (** [b1 |> right_of b2] is the concatenation of [b1] to the right of
  5. [b2]. [b2] is not moved. *)
  6. val right_of : ?gap:int -> t -> t -> t

  7. (** [b1 |> above b2] is the stacking of [b1] above [b2]. [b2] is not moved. *)
  8. val above : t -> t -> t

  9. (** [b1 |> below b2] is the stacking of [b1] below [b2]. [b2] is not moved. *)
  10. val below : t -> t -> t

Imaginons que nous souhaitions avoir une brique bleue, puis à droite une brique rouge. Autrement dit on veut placer la brique bleue à gauche de la brique rouge :

  1. let brick =
  2. let open Generator in
  3. block ~width:2 ~height:1

  4. let two_bricks =
  5. let open Generator in
  6. blue brick
  7. |> left_of (red brick)
  8. (* without pipe : left_of (red brick) (blue brick) *)

  9. let main =
  10. let open Renderer in
  11. generate_and_render two_bricks

Évaluez, vous devriez obtenir :

Une brique bleue puis une brique rouge.

Notons que la première brique donnée ne change pas de position, donc si on utilisait right_of, la brique rouge serait à gauche de la brique bleue, donc hors de l'image (essayez !).

On peut répéter pour avoir une troisième brique :

  1. let three_bricks =
  2. let open Generator in
  3. blue brick
  4. |> left_of (red brick)
  5. |> left_of (green brick)

Quel motif doit-on obtenir ? Vérifiez-le.

Pour empiler verticalement des briques, le principe est le même, avec les fonctions above et below. Essayez d'empiler trois briques de trois couleurs différentes.

Les fonctions left_of et right_of ont un argument optionnel gap, qui permet de créer un trou entre les briques. On peut donc placer deux briques noirs séparées par un vide de la taille de nos briques, ainsi :

  1. let holed_two_bricks =
  2. let open Generator in
  3. brick
  4. |> left_of ~gap:2 brick
Deux briques séparées par un trou.
Créer une pyramide.

On veut créer une pyramide. Soyons modeste et commençons par obtenir ceci :

Une petite pyramide.

Essayez de le faire. Quelle difficulté se présente ?

Lorsqu'on empile des constructions les unes au-dessus des autres, les colonnes de gauche des deux morceaux sont alignées, puis l'empilement est réalisé. Pour mettre la brique du haut au milieu, il est donc nécessaire de la pousser vers la droite avant l'empilement. Utiliser la fonction x_shift pour cela. Obtenez maintenant la petite pyramide.

Créer une grande pyramide.

Passons aux choses sérieuses, et essayons d'obtenir ça :

Une grande pyramide.

Pour cela, il faut commencer simplement par faire les niveaux horizontaux.

Définissez le niveau du haut, celui en dessous, et ainsi de suite. Vous allez voir un motif apparaitre. La fonction pack_horizontally permet de capturer l'essentiel de ce motif. Voici un exemple d'utilisation de cette fonction (l'argument nommé gap est optionnel). Le paramètre n de pack_horizontally doit être au moins 1.

  1. let many_pyramids =
  2. let open Generator in
  3. small_pyramid
  4. |> pack_horizontally ~gap:2 ~n:10
Dix petites pyramides.

Compléter la fonction permettant de créer le $k$e niveau de la pyramide :

  1. let layer k =
  2. let open Generator in
  3. if k = 0 then
  4. brick
  5. else
  6. (* TODO *)

Notez comment nous définissons une fonction, avec un paramêtre k. Nous testons séparément le cas k = 0 car pack_horizontally doit prendre un argument n positif non-nul.

Il reste à empiler tous les niveaux. On serait tenté d'utiliser pack_vertically, mais les niveaux sont distincts. On va donc plutôt utiliser une récursion, en remarquant qu'une pyramide de hauteur $n$ est une pyramide de hauteur $n-1$ posée (décalée de 1) sur une couche de niveau $n$. Complétez le programme suivant pour obtenir une grande pyramide :

  1. let rec pyramid size = (* rec for recursive! *)
  2. let open Generator in
  3. if size = 1 then
  4. (* TODO *)
  5. else
  6. (* TODO *)

  7. (* we need to draw a bigger part of the plane *)
  8. let large_view_params =
  9. let open Renderer in
  10. let open Gg in (* library for vectorial calculus *)
  11. { default_params with
  12. view = (* this parameter controls which part of the plane is drawn *)
  13. Box2.v
  14. V2.(v 0. 0.) (* bottom left corner of the picture *)
  15. V2.(v 100. 100.) (* width and length of the picture *)
  16. }

  17. let main =
  18. let open Renderer in
  19. generate_and_render ~params:large_view_params (pyramid 50)
Ajouter un peu d'aléa.

Donnons des couleurs plus authentiques à notre pyramide. Pour cela, nous allons choisir aléatoirement la couleur de chaque brique parmi une liste. Le module Colors.combinator permet de créer une liste de combinateurs de couleurs.

  1. let sandy_colors =
  2. let open Colors in
  3. Combinator.gradient
  4. ~n:100
  5. Pure.tan
  6. Pure.gold

Tout ce qu'il nous faut changer, c'est le choix de la couleur de chaque brique. On modifie donc la définition d'une brique en utilisant la fonction sample, qui déclare que nous voulons choisir un élément aléatoire parmi ceux d'une liste.

  1. let colored_brick color =
  2. block ~height:1 ~width:1
  3. |> color

  4. let brick =
  5. let open Generator in
  6. sample sandy_colors colored_brick

sample choisit un élément et le passe à la fonction donnée en deuxième argument de sample. On peut aussi utiliser l'opérateur d'application @@ pour simplifier. Tout ce qui suit cet opérateur devient argument de la fonction précédent l'opérateur, ce qui permet d'intégrer facilement une ligne avec sample dans une chaîne de |> via l'utilisation d'une fonction anonyme :

  1. let brick =
  2. let open Generator in
  3. (* think about the next line as "let color = sample sandy_colors in" *)
  4. sample sandy_colors @@ fun color ->
  5. block ~height:1 ~width:1
  6. |> color
Une pyramide de briques jaunes.

À vous de jouer...

Nous avons fait le tour des principales fonctionnalités de cette librairie. Essayez maintenant de créer de jolies constructions. Voici quelques exemples de réalisations :

Le tapis de Sierpinski.
Des maisons.
Un chateau.