Le but de ce TP est de corriger un programme contenant plusieurs erreurs à l'aide de QCheck. Le programme doit générer des images de la fractale de Mandelbrot. Le programme est contenu dans cette archive :
Récupérez-le et extrayez l'archive dans un répertoire dédié. Le projet vient tout prêt avec ses fichiers .merlin et _tags.
Compilez mandelbrot.native et lancez le programme. Décevant, n'est-ce pas ?
La fractale de Mandelbrot représente la convergence d'une suite complexe définie selon un paramètre, nous verrons les détails plus tard, mais dans l'immédiat il nous faut faire des calculs sur les nombres complexes, et c'est le rôle du module Cplex. Cplex n'a pas de dépendances dans le projet, c'est donc un bon candidat pour commencer les corrections.
Lisez l'interface du module (le fichier cplex.mli). Assurez-vous de bien comprendre le rôle de chaque fonction. arbitrary est un générateur aléatoire de nombres complexes qui sera utilisable par QCheck.
Créez un nouveau fichier checkCplex.ml, qui va contenir le code pour tester le module Cplex. Puisqu'on va utiliser Cplex abondamment, autant l'importer avec open Cplex au début du fichier.
Pour commencer, on va vérifier que l'addition est correcte. L'addition complexe vérifie les mêmes lois que l'addition réelle : neutralité de zéro, associativité, commutativité, existence d'un inverse. Cela fait déjà quelques candidats pour l'écriture de tests. Par exemple :
Compilez checkCplex et exécutez-le. Si rien n'est écrit, le test est passé avec succès.
Ajoutez un test pour l'associativité. Le test doit prendre un triplet de complexes en argument. Comment construire un générateur aléatoire de triplets de complexes ? cherchez ici.
Ajoutez un test pour la commutativité. Cette fois il faut une paire de complexes, cela ne devrait pas être bien dur si vous avez compris.
Imaginez deux tests, pour negate et (-:) et ajoutez-les.
Ajouter un test pour vérifier que l'addition se comporte correctement sur des complexes sans partie imaginaire (l'addition doit coïncider avec l'addition des flottants).
Si vous avez trouver une erreur, corriger le code de l'addition, jusqu'à ce que tous les tests passent. N'oubliez pas que si vous détectez une erreur, elle peut être dans le code testée (c'est le but) mais elle peut aussi être dans le code testant (c'est ballot) ! Pour examiner une erreur, vous pouvez ouvrir un interpréteur et effectuer directement des calculs pour essayer de comprendre pourquoi ce n'est pas correct.
Avec tous ces tests, on commence à avoir confiance dans la qualité du code de l'addition. On recommence maintenant pour la multiplication. Ajoutez des tests pour l'associativité et la commutativité de la multiplication, la distributivité de la multiplication sur l'addition, la neutralité de 1 . Testez aussi l'inverse.
Les nombres complexes représentent des transformations géométriques : multiplier par un réel pur, c'est grandir ou rétrécir un objet, multiplier par un point du cercle unité (de centre 0 , de rayon 1), c'est effectuer une rotation. On trouve donc une fonction créant un complexe représentant une rotation d'un angle donné en argument (en radian). On définit :
Proposez des tests pour la rotation. On peut utiliser par exemple que composer deux rotations d'angle $\alpha$ et $\beta$ fait une rotation d'angles $\alpha + \beta$, ou que $i$ correspond à la rotation d'un quart de tour. Commencez donc par écrire un générateur aléatoire d'angles entre $0$ et $2\pi$.
Finalement testez la norme. Elle est invariante par rotation, et la norme d'un réel pur est sa valeur absolue. Utiliser Cplex.compare_float pour tester l'égalité des flottants.
Une fois le module Cplex corrigé, réessayez d'exécuter le programme principal. Est-ce mieux ?
Il reste d'autres erreurs deci-delà. On commence par la fonction range de MoreList, qui permet de générer l'intervalle de tous les entiers entre deux bornes (incluses)
Pour la tester, il faut un générateur d'instances intervalles. Pour cela, il faut :
Pour le générateur aléatoire, utilisez pair, -- et map (voir la doc), pour générer la valeur minimum de l'intervalle (disons entre $-1000$ et $1000$), la longueur (entre 0 et 100), et en déduire une paire (borne inférieure, borne supérieure).
Pour la conversion, utilisez Printf.printf.
Pour la simplification, utilisez QCheck.Iter. Voici deux règles de simplification possibles. Si la longueur est strictement positive, essayez de la diviser par deux en diminuant la borne supérieure. Si la borne inférieure est non-nulle, essayez de la diviser par deux ainsi que la borne supérieure.
Ensuite, écrivez des tests pour range (par exemple, tester les extrémités de la liste, et sa longueur).
Le module Sequence permet d'effectuer des calculs sur des suites d'entiers définies par une récursion simple ($u_0 = c$, $u_n = f(u_{n-1})$). L'ensemble de Mandelbrot est l'ensemble des points complexes $c$ tels que la suite définie avec $u_0 = 0$, $f : z \to z^2 + c$ converge.
Sequence.first_term calcule le premier terme de la suite satisfaisant une condition donnée. Cette fonction se base sur repeat et repeat_until qui permettent d'itérer une fonction à partir d'une valeur initiale, soit $n$ fois, soit jusqu'à la réalisation d'une condition.
Proposez des tests pour repeat et repeat_until. Pour générer des fonctions aléatoires, utilisez QCheck.(fun1 small_int small_int).
Le module View permet de définir le cadrage de l'image : on affiche seulement un rectangle du plan complexe. Pour chaque pixel, on trouve un point complexe correspondant, on calcule la suite complexe et on détermine si elle diverge. complex_of_pixel est la fonction permettant de calculer le point complexe associé à un pixel, par rapport au cadrage donné.
Malheureusement, elle contient une erreur. Proposez un test capable de détecter l'erreur, et corrigez-là.
Réessayez d'exécuter le programme mandelbrot. Cette fois, le résultat devrait être l'image en haut de cette page. Sinon, continuez de tester, il vous manque des erreurs.
Le principe du dessin est de calculer pour chaque point le $n$e terme (disons $n = 100$) de la suite définie par sa fonction polynomiale associée. Si la suite diverge, la norme de ses termes diverge aussi. On classe alors les pixels selon la norme du $n$e terme, et on leur associe une couleur dans cet ordre.
Pour accélérer, on ne calcule pas nécessairement tous les $n$ termes, on s'arrête lorsque la norme est assez grande, et cela suffit pour estimer à quel point la divergence est rapide, et trier les pixels. On laisse en noir les pixels pour lesquels la suite converge (ou semble converger).
Le programme peut facilement être personnalisé. Voici quelques défis :
Lisez le code, comprenez-le et appropriez-vous-le.
