Avant toute chose

---

Attention, quelques consignes sur le code !

• Les noms des variables doivent être explicites, en particulier lorsque leur rôle n'est pas évident. On tolère l et sa décomposition x::q pour une liste, f pour une formule, i pour un indice... Mais restez cohérents.
• Votre code doit être commenté, et les types des arguments ainsi que le type de retour des fonctions doit être précisé. C'est d'autant plus vrai pour les fonctions auxiliaires.
• Vous devez testez chacune des fonction que vous écrivez. Vous disposez d'une variable formule_test à cet effet.

Syntaxe OCaml : généralités

---

• Les commentaires en OCaml doivent être encadrés par (* ... *)
• Les retours à la ligne et l'indentation n'ont pas d'importance (enfin, uniquement la lisibilité)
• les noms de variables ne peuvent pas commencer par une majuscule

Syntaxe Ocaml : les types

---

OCaml est un langage fortement typé. Cela veut dire que toutes les variables, fonctions, arguments de fonction doivent avoir un type bien défini.

Entre autre, on n'a pas de type simple "liste", mais on parle de "liste d'entiers" : il ne peux y avoir qu'un seul type d'éléments dans la liste.

Syntaxe OCaml : fonctions et variables

---

• Les variables globales se déclarent avec

let nom_de_variable: type = (*valeur*);;

• Les fonctions se déclarent avec

let nom_de_la_fonction (arg1: type1) (arg2: type2): type_de_retour = 
    (*corps de la fonction*)
    ;;

Question 1

---

Executez les cellules suivantes, et tentez de comprendre le résultat.

Syntaxe OCaml : Les expressions

---

Dans le corps d'une fonction, ou bien d'une déclaration de variable, on a une expression. Les expression peuvent être :

• Des variables, des constantes, des opérations dessus : x + 8;;
• Des déclaration de variables locales ou de fonctions auxiliaires, déclarées avec let [nom] = ... in
• Des conditions : if [condition] then [expresssion 1] else [expression 2]

Question 2

---

Que font les cellules suivantes ? Vous pouvez les exécuter sur des exemples si besoin.

Ecrivez des équivalents en langage Python, dans la cellule Python qui suit les cellules OCaml (l'étiquette en haut à gauche de chaque cellule indique son langage).

Question 3

---

Traduisez les fonctions python suivantes en OCaml.

Avantage

---

Avec la notation préfixe, il n'est plus nécéssaire d'utiliser des parenthèses ! Essayez de comprendre pourquoi.

Question 4

---

Transformez les formules suivantes en notation préfixe, en des formules en notation usuelle :

Syntaxe OCaml : les listes

---

Les listes en OCaml ne contiennent qu'un seul type de données, et le type en question se note [type] list.

On peut donner une liste explicite avec la syntaxe [1; 2; 3; 4; 5] (attention aux point-virgules !).

On a les opérations suivantes sur les listes l1 et l2 et un élément x :

• x::l1 est la liste l1 à laquelle on a ajouté x au début
• l1 @ l2 est la concaténation de l1 et l2

À noter qu'on n'a pas d'opérateur pour accéder au ième élément d'une liste !

Par exemple, la formule en notation préfixe, sera représentée par la liste ['+'; '-'; '*'; 'a'; '-'; 'b'; '*'; '-'; 'a'; 'b']

Rappel

---

Si vous n'avez pas lu l'encadré en haut du TP, c'est le moment.

Question 5

---

Compléter les fonctions suivantes, qui appliquent des opérations à des formules. La négation est déjà complétée à titre d'exemple.

Question 6

---

À l'aide des fonctions ci-dessus (et uniquement elles), réécrivez la formule formule_test_prefixe.

Syntaxe OCaml : fonctions récursives

---

En OCaml, on peut écrire des fonctions récursives avec le mot-clé let rec. De plus, on peut faire du pattern matching sur les listes, avec match .. with ...

En combinant les deux, on obtient une construction très commune :

let rec f (l: 'a list) = match l with 
    |[] -> (*cas de base, lorsque la liste est vide*)
    |x::q -> (*cas récursif : faire quelque chose avec x, et appeler (f q).*)

Question 7

---

Écrivez une fonction récursive nombre_variables_prefixe de type formule_prefixe -> int, qui prend en argument une formule, et renvoie le nombre de variables dans la formule (sans enlever les doublons).

Vous pourrez vous aider d'une fonction auxilliaire est_variable qui renvoie true si le char donné en argument est une variable, et false sinon.

Rappels de OCaml : types énumération

---

En OCaml, il est possible de déclarer des types "énumération", de la manière suivante :

type classe = MP | MPSI | PCSI | PC

Un élément de ce type a 4 valeurs possible, une pour chaque variant défini.

On peut aussi ajouter des données à un variant avec le mot-clé of. Par exemple :

type classe = MP | MPSI | PCSI | PC | Autre of string

On peut écrire par exemple

let classe_actuelle: classe = MPSI;;

Enfin, il est possible stocker une donnée du type lui-même dans un variant ! Par exemple, si on veut redéfinir le type list pour les entiers, on peut écrire

type liste_entier = Vide | Element of (int * liste_entier)

Question 8

---

On a commencé à définir un type formule. Complétez la définition pour ajouter les variants manquants.

Question 9

---

Définissez une variable formule_test qui contient la version arbre de formule_test_prefixe.

Rappels de OCaml :

---

pattern-matching sur des énumérations On peut également faire du pattern-matching sur les énumérations ! Par exemple, avec le type classe de l'exemple précédent, cela donnerait :

let nombre_heure_math (c: classe): int = match c with 
    |MP -> 10
    |MPSI -> 8
    |PCSI -> 7
    |PC -> 7
    |Autre (s) -> (print_string "Classe inconnue : "; print_string s; -1)

Je reviendrais sur l'impression et l'utilisation des ; dans la bulle suivante.

Question 10

---

Écrivez une fonction nombre_variable de type formule -> int qui renvoie le nombre de variables dans un arbre de formule. Vérifiez que votre fonction renvoie bien la même chose sur formule_test que nombre_variable_prefixe sur formule_test_prefixe.

Rappels de OCaml : instructions et impression

---

• Pour afficher une valeur en OCaml, il faut utiliser la fonction qui correspond au type de l'objet. Les fonctions disponibles sont : print_int, print_char, print_string, print_float. Pour revenir à la ligne, on utilise print_newline () (attention à bien ajouter () à la fin !).
• En OCaml, certaines fonctions renvoie un type particulier, le type unit (ce qui signifie en vérité qu'elles ne renvoient rien). En particulier, c'est le cas de toutes les fonctions d'affichage. Il devient alors possible de "chainer" ces fonctions, c'est à dire d'en utiliser plusieurs à la suite. Pour cela, on utilise ; pour les séparer.
• Lorsqu'on utilise des ;, ou bien plusieurs if ou match, il est bon de mettre des parenthèses pour délimiter les blocs.

Je vous fournis une fonction print_char_list comme exemple. Notez qu'elle renvoie le type unit, c'est à dire qu'elle ne renvoie rien.

Question 11

---

Écrivez une fonction de type formule -> unit qui permet d'afficher un arbre de formule, et testez-là sur formule_test.

Indice

---

Vous avez plusieurs options :

• afficher l'arbre comme une formule dans la notation usuelle (donc avec les opérateurs entre leurs opérandes)
• (plus compliqué) afficher l'arbre sous forme d'arbre. Je vous conseille alors de calculer au passage la profondeur de chaque noeud, et de l'afficher avec une identation correspondant à sa profondeur.

Question 12

---

Écrivez une fonction récursive de type formule -> formule_prefixe qui prend en argument une formule sous forme d'arbre, et renvoie la même formule en notation préfixe.

Donnez sa complexité en temps et en espace.

Interface de Hashtbl en OCaml

---

• Création d'une table : Hashtbl.create n créé une table avec une capacité initale n, renvoie unit
• Ajout d'un élément : Hashtbl.add table clé valeur, renvoie unit
• Récupération d'un élément : Hashtbl.find table clé, renvoie la valeur associée à la clé (ou une erreur si elle n'existe pas)
• Autre option : Hashtbl.find_opt table clé, renvoie Some (valeur) si la valeur existe, et None sinon.
• Test d'existence : Hashtbl.mem table clé, renvoie true si la clé est présente, false sinon.
• Supression : Hashtbl.remove table clé, renvoie unit.
• Parcours : Hashtbl.iter fonction table applique une fonction de type clé -> valeur -> unit à chaque élément de la table.

Question 13

---

Créer une table de hashage, puis ajoutez-y les correspondances suivantes : | clé | valeur | |---|---------| | 'a' | 3 | | 'b' | 0 | | 'c' | 8 | | 'd' | 1 |

Quel est le type de votre table, après ajout des valeurs ?

Question 14

---

Ecrivez une fonction récursive eval de type formule -> (char, int) Hashtbl.t -> int qui renvoie la valeur d'une formule si toutes les variables de la formule sont fixées dans la table, et renvoie une erreur sinon.

Rappels de OCaml : les erreurs

---

Il y a plusieurs façon de gérer les erreurs en OCaml, mais la manière la plus simple est d'utiliser l'instruction failwith "raison de l'erreur". Elle peut correspondre à tous les types, pour plus de facilité d'utilisation.

Question 15

---

Écrivez une fonction eval_prefixe de type formule_prefixe -> (char, int) Hashtbl.t -> int qui renvoie la valeur d'une formule si toutes les variables de la formule sont fixées dans la table, et une erreur sinon.

Indice

---

Vous pouvez utiliser une fonction auxiliaire récursive qui calcule la valeur de la première formule valable d'une liste, et renvoie cette valeur ainsi que la liste où on a supprimé les caractère correspondants.

Par exemple, pour la liste ["a"; "+"; "b"; "c"], la fonction renverra (3, ["+"; "b"; "c"]). Sur ["+"; "b"; "c"], elle renverra la valeur de (après avoir faire deux appels récursifs pour les arguments du +).

Question 16

---

Écrivez une fonction de type formule_prefixe -> formule qui convertit une formule en notation préfixe, en une formule sous forme d'arbre.

Indice

---

C'est presque la même fonction qu'à la question précédente !