Programmation Avancée
TP4: effets et contrôle
Exercices conçu par David Baelde
Dans ce TP nous allons d'abord dérouter le flot d'exécution de prédicats afin d'implémenter un test d'égalité apparemment impossible, puis mettre en place un flot d'exécution complexe dans un algorithme avec backtracking.
Exercice 1: effets espions
Une fonction est totale si elle termine normalement (sans lever une exception) sur toute entrée. Elle est pure si elle ne manipule pas d'état, d'exceptions, etc. Dans ce cas son résultat dépend uniquement de la valeur passée en entrée.
On définit un type pour représenter des prédicats: type 'a pred = 'a -> bool.
Question 1
Ecrire une fonction qui calcule l'égalité extensionnelle entre deux
prédicats purs et totaux sur les booléens:
f (p : bool pred) (q : bool pred) vaut true si et seulement si p x = q x
pour tout (x : bool).
Question 2
On représente un flux de booléens par une fonction de type
stream = int -> bool, et on veut maintenant calculer l'égalité entre
prédicats purs et totaux sur stream. Le problème est qu'il y a une infinité
de stream possibles, on ne peut donc comparer comme avant les deux prédicats
sur toutes les entrées possibles.
Sur une entrée donnée, un tel prédicat va évidemment accéder seulement à un nombre fini de valeurs du stream, dépendant potentiellement du stream. Montrez que ce nombre peut en fait être borné indépendamment du contenu du flux.
Question 3
Pour s'échauffer, implémentez à l'aide du mécanisme d'exceptions un objet de
type stream qui permette de détecter si un prédicat sur stream accède au
contenu du stream qui lui est passé en argument ou s'il s'agit d'une fonction constante.
Question 4
En généralisant, décompilez le prédicat en un arbre de décision binaire décrivant le comportement du prédicat : un chemin dans l'arbre correspondra à une description partielle d'un stream jusqu'à un certain rang, et les feuilles donnent les valeurs du prédicat.
Question 5
Écrivez une fonction permettant de déterminer si un prédicat
(pur et total) sur stream renvoie true sur toute entrée.
Il est ensuite immédiat d'obtenir une implémentation de l'égalité
extensionnelle sur stream pred.
Question 6
Peut-on faire la même chose sans utiliser les exceptions?
Exercice 2: le problème des reines
Ce problème classique consiste à poser n reines sur un échiquier de taille n
de façon à ce qu'aucune reine ne soit menacée par une autre: on doit donc
avoir exactement une reine par ligne, une reine par colonne et une reine par
diagonale montante ou descendante.
Il n'existe pas de formule magique pour énumérer, ou même compter ou décider l'existence d'une solution. Il n'y a pas d'autre choix que tester toutes les tentatives de construction de solutions possibles. On fera ceci incrémentalement, ligne par ligne, en posant à chaque étape une reine sur la première ligne vide, et en éliminant un échiquier dès lors que deux reines posées se menacent (on coupe ainsi au plus tôt une branche de l'exploration, qui correspond potentiellement à de multiples échiquiers comportant une reine par ligne).
Quand on programme de tels algorithmes, il est très inefficace de représenter explicitement les collections d'objets que l'on énumère: cela prendrait trop de place en mémoire, et c'est inutile car on ne traite jamais qu'un objet à la fois. On va donc générer les objets les uns après les autres, en "backtrackant" sur les choix faits lors la génération. D'une certaine façon, on remplace le calcul d'une liste de possibilités par la définition d'un itérateur sur cette liste.
Question 1
Implémenter une solution sous la forme d'une fonction qui prend en
argument la taille du problème et une fonction à appeler sur chaque solution
trouvée: reines : int -> (board -> unit) -> unit.
La fonction procèdera par construction progressive d'une solution, en posant des reines ligne par ligne sans avoir de conflit, et en "backtrackant" quand on se retrouve avec une ligne sans reine possible. Pour être efficace, on maintiendra en même temps que la solution en cours de construction l'ensemble des alignements déja pris, les alignements étant ici les lignes, colonnes, et diagonales.
Question 2
Utiliser votre algorithme pour afficher la première solution et arrêter le calcul ensuite. Séparemment, l'utiliser pour compter le nombre de solutions. Vous pourrez comparer vos valeurs avec les résultats officiels.