tp5.md

TP5: Parcours génériques de structure et projets dune

1. Arbre n-aires: recodage

Dans cet exercice, on reprend les fonctionnalités développées dans la section 1. du TP4, mais en les recodant avec les fonctions déjà fournies avec OCaml.

Remarque: en OCaml on peut écrire fun x y -> ... à la place de fun x -> fun y -> ....

1.1. Recodage de quelques fonctions de base avec la bibliothèque standard OCaml

Reprendre le type 'a arbre_n du TP4, section 1.1

On pourra reprendre les tests écrits lors du TP4.

Recoder la fonction hauteur_arbre sans utiliser hauteur_foret, mais en appelant directement List.map et List.fold_left pour extraire les hauteurs des arbres fils et trouver la hauteur maximale parmi celles-ci.

Recoder list_of_arbre_aux en utilisant List.fold_right pour remplacer les appels à list_of_foret. Encapsuler list_of_arbre_aux avec un let ... in ... dans la définition de list_of_arbre. On écrira le let avant de prendre l'argument de list_of_arbre.

1.2 Gestion d'option, fold et minimum

Pour gérer proprement le calcul du minimum, on va s'équiper d'un décorateur lift_option_2 ayant le comportement suivant. Soit f: 'a -> 'a -> 'a. On suppose que g = lift_option_2 f. Alors g aura le type 'a option -> 'a -> 'a option. Si le premier argument de g est None, alors g renvoie Some x si x est son second argument. Sinon g renvoie Some (f y x) où y est la valeur contenue dans son premier argument et x est son second argument.

Définir lift_option_2 en commençant par préciser son type. Tester avec assert en passant la fonction min à lift_option_2.

On veut à présent définir fold_left_arbre qui aggrège une valeur via un accumulateur à la manière de List.fold_left, mais en parcourant un arbre et pas une liste.

Définir le type, puis coder fold_left_arbre. On pourra utiliser intelligement List.fold_left pour gérer le cas des Noeud. Tester en calculant la somme des éléments d'arbres bien choisis.

On peut remarquer que reduce du TP4 ressemble énormément à fold_left_arbre: les deux vont parcourir les éléments de l'arbre les combinant via un accumulateur. Elles diffèrent cependant sur les points suivants:

• reduce prend en argument une fonction de type 'a -> 'a -> 'a alors que fold_left_arbre prend une fonction un peu plus générique de type 'b -> 'a -> 'b.
• reduce renvoie forcément une option alors que fold_left_arbre renvoie uniquement une option si 'b est lui-même une option.

En utilisant intelligement fold_left_arbre, recoder reduce.

Recoder list_of_arbre en utilisant fold_left_arbre.

2. Application et compilation séparée

On souhaite implémenter une application de gestion de la fabrication des jouets de Noël par les lutins du Père-Noël. Bien que l'application soit modeste on souhaite pouvoir la faire grossir selon les besoins. On va donc dès le départ la diviser en différents modules, le code de l'application contenant simplement des appels aux bonnes fonctions des autres modules.

Les différentes parties de l'application intiale sont les suivantes:

• Un module Association de gestion des associations clé-valeur basé sur des arbres binaires de recherche. On veut pouvoir, à terme (mais pas dans ce TP), remplacer les usages de ce module par un module de la bibliothèque standard OCaml.
• Un module Usine contenant les types liés au métier de l'application: lutins, jouets, etc. Ce module contiendra également les différentes fonctions utilisées pour gérer l'usine.
• Un module LutinsApp qui va contenir le code de gestion des arguments en ligne de commande

On peut résumé les dépendances simples des modules de cette application via le diagramme suivant (la flèche signifie "est utilisé par"):

graph TD
  Association --> Usine
  Usine --> LutinsApp
  LutinsApp --> main.ml

2.1. Mise en place d'un projet dune

Remarque: Si vous utilisez votre propre machine, il faut installer opam et dune. Voir la documentation opam et la documentation dune. Cette installation est déjà faite pour les machines des salles TP, mais il faut bien avoir effectué la configuration de votre compte (cf doc).

Attention: un problème se pose avec l'utilisation sur les machines TP. Les commandes dune se bloquent. Il faut impérativement travailler dans un répertoire propre à la machine, par exemple /tmp/p1234567 où p1234567 est votre login étudiant. Il vous faudra versionner votre projet dune sur https://forge.univ-lyon1.fr, ou à défaut vous envoyer le .zip du projet. Attention à exclure les répertoires _build.

Créer une nouveau projet dune intitulé lutins via la commande suivante:

dune init project lutins

La commande va créer un répertoire lutins. Ce répertoire contiendra un ou plusieurs sous-répertoires nommés _build qui vont contenir les défférents fichiers générés par les outils de compilation OCaml.

Lister les fichiers et les répertoires générés par la commande dune init.

Lancer la commande dune exec lutins depuis le répertoire du projet. Dans quel fichier se trouve le code exécuté ?

Ajouter le code suivant dans le fichier test/lutins.ml:

assert (2=1)

puis lancer la commande dune test. Constater l'erreur, puis supprimer cette ligne de test.

Pour finir créer à la racine du projet un fichier .ocamlformat avec le contenu suivant:

profile = default
margin = 70

Si vous avez installé ocamlformat (via opam sur votre machine, il sera préinstallé en salle TP), cela permettra de reformatter le code (c-à-d. réarranger la présentation).

2.2. Premier module

Créer deux fichiers dans le répertoire lib. Le premier, nommé usine.ml contiendra le code du module Usine. Le second, usine.mli contiendra les déclarations de type et de fonction pour les modules et les fichiers qui utiliseront Usine.

Dans le fichier usine.ml, définir un type somme jour pour représenter les jours de la semaine (un jour par constructeur). Définir également une fonction string_of_jour permettant d'obtenir la string représentant le jour passé en argument.

Le fichier usine.ml va ainsi contenir l'implémentation du module Usine.

On veut maintenant indiquer que ces deux déclarations sont disponibles aux autres modules. Pour cela ajouter le code suivant à l'autre fichier, c'est-à-dire usine.mli:

(**
Les jours de la semaine.
*)
type jour = Lundi | Mardi

(**
Donne une représentation sous forme de string d'un jour.
*)
val string_of_jour: jour -> string

Noter le commentaire de documentation, qui devient plus important ici car le code n'est pas accessible en dehors du module Usine.

usine.mli contient l'interface du module Usine.

2.3. Utilisation du module Usine

On souhaite maintenant utiliser ce module. Pour cela on va d'abord vérifier que la ligne suivante se trouve dans le fichier bin/dune (on l'ajoutera si elle est manquante):

 (libraries lutins)

le contenu du fichier doit ressembler à ce qui suit:

(executable
 (public_name lutins)
 (name main)
 (libraries lutins))

Le module Usine est maintenant disponible, pour utiliser ses types et ses fonctions depuis main.ml, il faudra les précéder de Lutins.Usine, par exemple pour utiliser le constructeur Lundi, on écrira Lutins.Usine.Lundi.

Modifier le code de main.ml afin afficher en plus Nous sommes suivi d'un jour de la semaine traduit en string via un appel à string_of_jour.

Vérifier le bon fonctionnement du programme en lançant dune exec lutins. Dune va recompiler le programme et la bibliothèque (c'est-à-dire le code dans lib avant de lancer l'exécution du code).

On peut constater que l'usage de Lutins.Usine va vite devenir lourd. Pour éviter ce problème, on peut utiliser la directive open Lutins.Usine;; en début de fichier. Le compilateur va ensuite directement chercher dans le module Lutins.Usine les définitions de jour et string_of_jour sans que l'on ait besoin de les précéder de Lutins.Usine..

Enfin on veut pouvoir utiliser le système de test de dune avec le nouveau module Lutins.Usine. Pour cela, il suffit d'ajouter dans le fichier test/dune une déclaration libraries similaire à ce qui est fait dans bin/dune:

(test
 (name lutins)
 (libraries lutins))

Ensuite on peut utiliser, et donc tester, les types et les fonctions déclarées dans usine.mli comme cela a été fait dans le main.ml.

Remarque: Il se peut l'extension OCaml Platform de VSCode ait parfois du mal à se mettre à jour avec les nouvelles définitions. Si cela compile correctement avec dune, mais que VSCode indique des erreurs, c'est dune qui a raison.

Ajouter des assert pour tester string_of_jour. Lancer dune test pour vérifier que tous vos tests passent correctement.

2.4. Masquer des définitions

On veut maintenant définir au sein de l'usine de fabrication de jouets une notion de configuration de la journée. La configuration d'une journée permet de connaître deux choses: pour chaque lutin, le jouet qu'il va fabriquer et pour chaque lutin et chaque jouet la quantité qu'il peut fabriquer. Les jouets et les lutins étant représentés par des chaînes de caractères, il se peut qu'un lutin ou un jouet passé en argument n'existe pas. On utilise donc une option pour gérer cette situation.

On va maintenant créer dans le module Usine un type configuration qui sera simplement une paire de fonctions. La première aura le type string -> string option, la seconde aura le type string -> string -> int option.

Définir ce type dans usine.ml:

type configuration = (string -> string option) * (string -> string -> int option);;

Dans usine.mli on va en revanche, on va masquer les détails de la définition et juste conserver le nom du type:

type configuration;;

Tel quel, on ne peut pas manipuler les valeurs de ce type à l'extérieur du module Usine. On va donc lui ajouter des fonctions pour créer des configurations et en extraire les différentes parties.

Ajouter les fonctions suivantes, en les déclarant dans l'interface du module Usine

• mk_configuration: (string -> string option) -> (string -> string -> int option) -> configuration cette fonction va fabriquer une paire avec ses deux arguments.
• get_jouet: configuration -> (string -> string option) cette fonction va extraire le premier élément de la paire
• get_nb_jouets: configuration -> (string -> string -> int option) cette fonction va extraire le deuxième élément de la paire

Tester ces fonctions dans test/lutins.ml avec une fonction qui renvoie toujours "toupie" pour le choix du jouet et toujours 42 pour le nombre de jouets.

2.5. Codage de l'application de gestion des jouets - début

On dispose à présent des éléments de langage pour pouvoir coder le début de l'application de gestion de l'usine de jouets.

Ajouter au module Usine une fonction jour_of_string qui prend une string et renvoie une option de jour avec Some du bon jour si la chaîne représente bien un jour et None sinon.

Créer un module Association contenant le code pour gérer des associations clé-valeur. Il contiendra:

• un type générique ('a,'b) assoc_t dont l'implémentation est cachée;
• une fonction put: 'a -> 'b -> ('a, 'b) assoc_t -> ('a, 'b) assoc_t qui associe une clé (de type 'a) à une valeur (de type 'b) dans une structure d'association;
• une fonction get: 'a -> ('a, 'b) assoc_t -> 'b option qui renvoie une valeur associée à une clé, si elle existe;
• une constante empty: ('a,'b) assoc_t correspondant à l'association vide.

L'implémentation est laissée libre. On peut par exemple utiliser des listes de paires clé-valeur ou bien des arbres de recherche basés sur la comparaison générique (<) prédéfinie dans OCaml.

Dans le module Usine, utiliser cette structure pour créer une variable globale pour y stocker, pour chaque jour, une configuration. Essayer de faire varier les fonctions de la configuration selon le jour.

Créer également une variable globale contenant la liste des noms des lutins.

Créer une fonction calcule_jouets_config: configuration -> (string,int) list qui indique pour chaque jouet combien d'exemplaires ont été fabriqué, en excluant les jouets fabriqués zéro fois.

Enfin créer un dernier module LutinsApp qui contiendra:

• une fonction affiche_jouets: (string,int) list -> string qui calculera une chaîne d'affichage de la sortie de la fonction calcule_jouets_config;
• une fonction run: string list -> unit qui prendra une liste de string dont le premier élément représente un jour et affichera (via print_endline) les jouets produits ce jour-là.

main.ml appelera run en lui passant la liste des arguments en ligne de commande (on pourra utiliser Sys.argv et Array.to_list pour récupérer les arguments et les transformer en string list pour être traités par run).

Il sera utile de consulter les modules de la biliothèque standard de OCaml (lien pour la version 4 utilisée en TP).

Une version plus évoluée de cette application sera codée dans les TPs ultérieurs.